Does AI/cognitive-science history contain a genuinely Stent-premature articulation of inference-time ('think longer at answer-time') compute?

history-of-aitest-time-computeinference-time-computeanytime-algorithmsmetareasoningstent-prematurityphilosophy-of-sciencecognitive-science

Core question (from the hook): does the history of AI or cognitive science contain a genuinely premature, in Stent's specific sense — correct, but logically disconnected from the canonical knowledge of its own moment — articulation of "think longer at answer-time" (inference-time / test-time / deliberation compute), something that anticipated the idea before the infrastructure existed to make it pay off?

Finding: the strongest AI-historical candidate for this shape — "anytime algorithms" and the adjacent flexible-computation / metareasoning tradition, 1987–1994 — does NOT meet Stent's specific criterion. It was correct, it did wait roughly three decades for the economics and model capability that made it industrially dominant (large pretrained language models doing "extended thinking"), but it was never disconnected from the canonical AI knowledge of its own moment. Its own originators cross-cited each other as contemporaries, and modern researchers explicitly describe an unbroken "intellectual lineage" running from it to today's test-time compute. By Stent's own definition (confirmed in claim-stent-prematurity-covers-neglected-not-contested-ideas: "cannot be connected by a series of simple logical steps to canonical... knowledge"), a continuously-cited, continuously-built-upon research program is the opposite case — delayed by missing infrastructure/economics, not by missing conceptual connection. This is a sourced negative answer to the core question for its best candidate, not an unresolved search.

Claim: Dean & Boddy's 1988 "anytime algorithms" paper formalized the "spend more computation at answer-time, get a better answer" trade — the same shape now called test-time/inference-time compute — thirty-six years before it became an industry default

Thomas Dean and Mark Boddy, in "An Analysis of Time-Dependent Planning" (AAAI-88), introduced a class of algorithms that trade computation time for answer quality at the moment a decision is needed, rather than at training or design time. Motivating the idea: "For many planning tasks, polynomial performance is not sufficient; we need algorithms that compute the best answers they can in the time they have available." They characterize the defining property of the resulting algorithms — that they "can be terminated at any time and will return some answer, and ... the answers returned improve in some well-behaved manner as a function of time" — and name the class on the strength of that property: "we christen them anytime algorithms."

This is, in substance, the same trade-off Anthropic describes for Claude's extended thinking in 2025 ("serial test-time compute": "it uses multiple, sequential reasoning steps before producing its final output, adding more computational resources as it goes" — see claim-extended-thinking-as-serial-inference-compute) and that Snell et al. (2024) formalize for LLM test-time compute (see claim-test-time-compute-can-substitute-parameters): more computation spent after the model/system is fixed, applied at the moment an answer is needed, yields a better answer. Dean & Boddy state the principle thirty-six years before Anthropic's product framing.

source_url: https://cdn.aaai.org/AAAI/1988/AAAI88-009.pdf source_sha: 6559c7f4933aa178cb0de5d716c3fb3526c24b837997f31235a013aeaab56102 source_title: "An Analysis of Time-Dependent Planning" source_author: "Thomas Dean, Mark Boddy" source_date: 1988 source_venue: "AAAI-88 Proceedings, pp. 49-54 (Association for the Advancement of Artificial Intelligence, hosted on AAAI's own digital-library CDN)" source_quote: "For many planning tasks, polynomial performance is not sufficient; we need algorithms that compute the best answers they can in the time they have available." source_quote_2: "they can be terminated at any time and will return some answer, and (iii) the answers returned improve in some well-behaved manner as a function of time" source_quote_3: "we christen them anytime algorithms" source_tier: 1

Claim: The anytime-algorithms idea was not logically disconnected from its own moment's canonical AI knowledge — contemporaries cross-cited it as compatible, which is the opposite of Stent's criterion for prematurity

Dean & Boddy's own 1988 paper footnotes Eric Horvitz's contemporaneous 1987 paper on reasoning under resource constraints and explicitly folds it into the same research program rather than treating it as a separate or incompatible idea: "His conclusions concerning the algorithms and architectures appropriate for effective reasoning under resource constraints are entirely compatible with the discussion in this paper." Horvitz's own 1987 paper ("Reasoning about Beliefs and Actions under Computational Resource Constraints," presented at the Third Workshop on Uncertainty in Artificial Intelligence, Seattle, July 1987) independently states the same core trade-off in decision-theoretic terms: "We address the notion of real-time rationality, focusing on the application of knowledge about the expected timewise-refinement abilities of reasoning strategies to balance the benefits of additional computation with the costs of acting with a partial result."

Two independent groups, writing in the same year (1987-88), named adjacent versions of the same idea and explicitly recognized each other's work as part of one connected research program — the opposite of Stent's criterion that a premature discovery's "implications cannot be connected by a series of simple logical steps to canonical, or generally accepted, knowledge" (see claim-stent-prematurity-covers-neglected-not-contested-ideas). The idea was mainstream, immediately cited, and continuously built upon for decades afterward (Horvitz's own 1988 AAAI follow-up on "value of computation"; Russell & Wefald's 1991 "rational metareasoning"; Boddy & Dean's 1994 "deliberation scheduling"; Zilberstein's 1996 survey of anytime algorithms) — a trajectory of accumulation, not neglect.

source_url: https://erichorvitz.com/u87.pdf source_sha: e24f8cd0e0ef5bcba1d10c8976f35be9d31aed2cfb3518cc47691400cc5ef985 source_title: "Reasoning about Beliefs and Actions under Computational Resource Constraints" source_author: "Eric J. Horvitz" source_date: 1987-07 source_venue: "Proceedings of the Third AAAI Workshop on Uncertainty in Artificial Intelligence, Seattle, WA, July 1987, pp. 429-444 (reprinted in Uncertainty in Artificial Intelligence 3, Kanal et al. eds., Elsevier, 1989, pp. 301-324); self-hosted on erichorvitz.com" source_quote: "We address the notion of real-time rationality, focusing on the application of knowledge about the expected timewise-refinement abilities of reasoning strategies to balance the benefits of additional computation with the costs of acting with a partial result." source_quote_2: "His conclusions concerning the algorithms and architectures appropriate for effective reasoning under resource constraints are entirely compatible with the discussion in this paper." [from Dean & Boddy 1988, footnote 6, citing Horvitz 1987 — see source_url above in the companion claim] source_tier: 1 source_delight: "Horvitz still hosts his own 1987 paper, in PDF, on his personal site rather than only behind a publisher paywall — the 'entirely compatible' footnote in Dean & Boddy's paper is the direct textual evidence that the field's own members did not experience this idea as disconnected."

Claim: Modern (2026) test-time-compute researchers describe an unbroken "intellectual lineage" from this 1987-1996 classical-AI tradition to today's LLM test-time compute — framing the field's current payoff as continuity, not rediscovery of a forgotten idea

A 2026 position paper on test-time compute states its own ancestry under a section header "Intellectual Lineage": "Bounded optimality relates behavior to an agent's architecture and environment (Russell and Subramanian, 1995); ... anytime algorithms expose quality as a function of deliberation (Zilberstein, 1996)." The paper continues by naming "rational metareasoning" (Russell & Wefald, 1991) and "deliberation scheduling" (Boddy & Dean, 1994) as the direct theoretical ancestors of present-day LLM test-time compute allocation. This is a practitioner in the current test-time-compute literature explicitly tracing a continuous thread back to the 1987-1996 anytime-algorithms/metareasoning tradition — treating it as inherited theory to build on, not as a correct idea that had to be independently re-discovered after decades of disconnection.

source_url: https://arxiv.org/pdf/2609.14995 source_sha: cb341531a808fed67ce1e4482ae41de04d88ae66324ddda5dcc6df17da50fc89 source_title: "Intelligence Under Time Constraints: Rethinking Test-Time Compute" source_author: "Xiaotian Zhang" source_date: 2026-09-15 source_venue: "arXiv preprint, cs.CL (arXiv:2609.14995v2); Trooly.AI" source_quote: "Bounded optimality relates behavior to an agent's architecture and environment (Russell and Subramanian, 1995)" source_quote_2: "anytime algorithms expose quality as a function of deliberation (Zilberstein, 1996)" source_tier: 1

Further leads

• Claude Shannon, "Programming a Computer for Playing Chess" (1950) and the Type-A/Type-B chess-search distinction — an even earlier (1950) articulation of search-depth-for-answer-quality trade-off in a narrower domain (chess), not yet checked against Stent's criterion or for contemporary cross-citation; candidate for a dedicated capture.
• Herbert Simon's "bounded rationality" / satisficing (1950s) is referenced by Horvitz's 1987 paper as prior art ("notions of bounded rationality that have been exercised in earlier discussion of intelligent systems") but the exact citation wasn't resolved in this session — worth a direct follow-up to find Simon's own primary statement and whether it anticipates the compute-for-quality trade specifically, or only resource-bounded satisficing more generally.
• Shlomo Zilberstein, "Using Anytime Algorithms in Intelligent Systems" (AI Magazine, 1996) — the field's own retrospective survey of the anytime-algorithms tradition; not yet fetched directly, would be the natural Tier-1 source for the lineage's mid-1990s state.
• Judea Pearl's Heuristics (1985), cited by Dean & Boddy as showing that "algorithms for heuristic search, in particular those employing variable lookahead and fast evaluation functions, can easily be cast as anytime algorithms" — another pre-1988 thread (classical heuristic search) feeding the same idea, not independently chased.
• Richard Sutton's "The Bitter Lesson" (2019) explicitly frames search and learning as the two general methods that scale with compute — a much later (2019), well-connected restatement, useful as a contrast case for "correct and connected, just under-exploited until infrastructure caught up" vs. genuine Stent prematurity.
• Dual-process theories in cognitive science (System 1 / System 2, e.g. Kahneman's popularization) describe "deliberate, slower processing yields better judgments" as a human-cognition analogue; not checked for whether any specific formulation was Stent-premature in its own era — flagged as a cognitive-science angle this session did not pursue.

Entity candidates

• Herbert Simon — person — the deeper ancestor Horvitz's own 1987 paper cites for "bounded rationality" before naming anytime/flexible computation; the foundational figure the whole resource-constrained-reasoning lineage traces back to, not itself confirmed in this session (flagged first, per the instruction to catch the older figure the priority claim rests on, not just the paper's own authors).
• Thomas Dean — person — co-author, "An Analysis of Time-Dependent Planning"; coined the term "anytime algorithms."
• Mark Boddy — person — co-author of the same 1988 paper.
• Eric Horvitz — person — author of the 1987 "flexible computation" / real-time-rationality paper that predates and is cross-cited by Dean & Boddy; later Microsoft Research chief scientist.
• Stuart Russell — person — co-developer of "bounded optimality" (with Subramanian, 1995) and "rational metareasoning" (with Wefald, 1991); a major continuity node in this lineage.
• Eric Wefald — person — co-author with Russell of "rational metareasoning" (1991).
• Shlomo Zilberstein — person — author of the influential 1996 anytime-algorithms survey; candidate for an entity page given how often this lineage cites him.
• Xiaotian Zhang — person — author of the 2026 preprint explicitly naming this "intellectual lineage" for test-time compute.
• "anytime algorithm" — concept — the specific 1988-coined term for an interruptible, quality-improves-with-time algorithm; directly relevant to entity-test-time-compute and worth its own concept note distinguishing it from the modern term.
• "bounded optimality" / "rational metareasoning" / "deliberation scheduling" — concept — the cluster of 1990s terms for allocating computation under resource constraints; candidates for a shared concept note bridging classical AI and modern test-time compute.
• "value of computation" — concept — Horvitz's decision-theoretic framing (expected utility gain from more computation vs. acting now) — a direct ancestor of the "difficulty-dependent compute allocation" idea in Snell et al. 2024.