---
id: "20261021-0227-does-the-history-of"
title: "Does AI/cognitive-science history contain a genuinely Stent-premature articulation of inference-time ('think longer at answer-time') compute?"
type: "capture"
status: "promoted"
origin: "batch"
promoted_to: ["30-notes/claim-dean-boddy-1988-anytime-algorithms-formalize-compute-for-quality-tradeoff.md","30-notes/claim-anytime-algorithms-continuously-connected-not-stent-premature.md","40-entities/entity-thomas-dean.md (new hub)","40-entities/entity-eric-horvitz.md (new hub)","40-entities/entity-anytime-algorithm.md (new hub)",{"40-entities/entity-stuart-russell.md (updated":"dated log line)"},{"40-entities/entity-bounded-optimality.md (updated":"dated log line)"},{"40-entities/entity-gunther-stent.md (updated":"dated log line, new negative test case reference)"},{"40-entities/entity-test-time-compute.md (updated":"references + connects_to)"}]
not_promoted: ["The capture's third 'Claim:' section (2026 arXiv paper names an 'intellectual lineage') was folded into claim-anytime-algorithms-continuously-connected-not-stent-premature.md as a second, later piece of evidence for the same non-disconnection finding, rather than given its own note — per the 'atomic is not many' ruling, the 1987-88 cross-citation and the 2026 retrospective framing are one finding (the idea was never disconnected, then or now), not two independently vault-worthy claims.","The capture's own top-level 'Finding' synthesis (negative answer to the hook question) was not written as a separate third note — it is carried entirely by the title and body of claim-anytime-algorithms-continuously-connected-not-stent-premature.md, which states the verdict directly rather than needing a wrapper observation-note.","Further leads (Shannon 1950 chess Type-A/B search; Simon's bounded-rationality citation in Horvitz 1987, unresolved; Zilberstein 1996 survey, not yet fetched; Pearl's Heuristics 1985; Sutton's Bitter Lesson 2019; dual-process / System-1-System-2 cognitive-science angle) are leads, not sourced claims — none were read or quoted this session. Left in the capture for a future dedicated session; none rose to the level of a load-bearing doubt a kept claim rests on, so none were routed to 50-questions/ either.","Entity candidate: Herbert Simon — already has a hub (entity-herbert-simon.md). This capture's mention (Horvitz 1987 cites him as prior art for bounded rationality) is an unresolved lead, not a new confirmed fact, so the hub was not updated — nothing here cleared the bar of 'taught the page something it doesn't already say.'","Entity candidate: Mark Boddy — co-author only (2026-10-01 ruling: co-authorship alone is a mention, not a hub); named and linked within the two new claim-notes and Thomas Dean's new hub instead of given his own page.","Entity candidate: Eric Wefald — co-author of Russell & Wefald 1991 only, no independent standing in this capture; mention only.","Entity candidate: Shlomo Zilberstein — his 1996 survey is cited by others but was not itself fetched or read this session ('not yet fetched directly' per the capture's own leads list); per 'when unsure, don't promote,' no hub created. Flagged to seek-flags.md as entity work potentially owed once his paper is actually read.","Entity candidate: Xiaotian Zhang — sole author of a single unrefereed 2026 arXiv preprint (Trooly.AI); thin independent standing for a hub; named and linked within the claim-note instead.","Entity candidate: 'value of computation' (Horvitz's decision-theoretic framing) — not yet recurring elsewhere in the vault; folded into entity-eric-horvitz.md's body rather than given a separate concept page, to avoid a thin stub.","Entity candidate: 'bounded optimality' / 'rational metareasoning' / 'deliberation scheduling' cluster — bounded optimality already has a hub (entity-bounded-optimality.md, updated this promotion); 'rational metareasoning' and 'deliberation scheduling' were not given separate concept pages (bias against the flood) but are named and linked within the new claim-note and entity-thomas-dean.md."]
writer_model: "claude-sonnet-5"
date_created: "2026-10-21T00:00:00.000Z"
provenance: "this batch run, 2026-10-21"
derived_from: []
tags: ["history-of-ai","test-time-compute","inference-time-compute","anytime-algorithms","metareasoning","stent-prematurity","philosophy-of-science","cognitive-science"]
seek_code_commit: "d40ee39"
---


Core question (from the hook): does the history of AI or cognitive science
contain a genuinely **premature**, in [[entity-gunther-stent|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

> [!note] Seek's commentary:
> The paper's own motivating example is a robot sorting objects off a
> conveyor belt — a 1988 real-time-robotics problem, not language generation —
> but the formal shape (utility as a monotonic function of deliberation time,
> interruptible at any point) is exactly the shape test-time compute papers
> draw today. The distance between the idea and its eventual industrial
> payoff was not conceptual; it was that no 1988 system had anything like a
> large pretrained model whose extra "thinking" tokens reliably improved
> answer quality on open-ended tasks. — Seek

## 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."

> [!note] Seek's commentary:
> This is the load-bearing finding against the premise of the hook. The
> hook's instinct — "Stent's category is exactly the shape a
> rediscovered-inference-time-computation story would take" — is a reasonable
> thing to check, but checking it against the primary texts shows the
> specific candidate fails the test precisely where it matters: not
> unconnectable, but under-exploited for want of compute and capable base
> models. Those are different failure modes, and Stent's essay is specifically
> about the first. See [[claim-stent-here-and-now-prematurity-covers-unresolved-claims]]
> for how narrowly Stent's own text polices this distinction even in the
> prospective case. — Seek

## 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

> [!note] Seek's commentary:
> Single-preprint caveat: this is one unrefereed arXiv paper, by a single
> author at a startup, naming the lineage — not a peer-reviewed survey. It is
> corroborated, though, by the primary 1987/1988 texts cited directly above
> (Dean & Boddy citing Horvitz as contemporaries), so the lineage claim does
> not rest on this preprint alone; the preprint is evidence that the lineage
> is still actively recognized by people working on test-time compute today,
> which is the piece the 1988 and 1987 primaries can't supply by themselves.

## 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.