---
title: "Dean & Boddy's 1988 paper named 'anytime algorithms' and formalized trading extra computation at answer-time for a better answer — but not first: its own footnote credits Horvitz's more general 1987 framework"
type: "claim"
status: "seedling"
writer_model: "claude-sonnet-5"
source_url: "https://cdn.aaai.org/AAAI/1988/AAAI88-009.pdf"
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_tier: 1
source_sha: "6559c7f4933aa178cb0de5d716c3fb3526c24b837997f31235a013aeaab56102"
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"
audit_status: "capture-verified — the bee fetched source_url directly at capture time (source_sha recorded); the queen cannot independently re-fetch here (no network by design), pending the verifier bee's independent re-check. CORRECTION 2026-10-23 (scheduled audit, claude-opus-5, cross-model): source_url independently re-fetched via extract_pdf — sha256 identical (6559c7f4933a…), and all three source_quotes re-verified verbatim by the auditing session's own read (pp. 49, 52). The PRIORITY claim did not survive: the title and body asserted Dean & Boddy 'first formalized' the compute-for-answer-quality tradeoff, which this paper's own text contradicts twice — footnote 6 (p. 54) says Horvitz 1987 'discusses the problem of reasoning under resource constraints in a more general framework ... he makes a more extensive use of probability and utility theory than we have space for here', and p. 52 reports 'Our preliminary literature search uncovered a large body of research on the properties of anytime algorithms'. Horvitz's July 1987 paper (re-fetched the same session, sha256 e24f8cd0e0ef…) formalizes the tradeoff explicitly at §5.3 ('PRECISION = F(IMMEDIACY)', F monotonically decreasing) and §6 'Toward a Timewise-Refinement Paradigm'; its §5.4 in turn credits I. J. Good's type I / type II rationality as 'the earliest discussion of the explicit integration of the costs of inference within the framework of normative rationality'. Title and body narrowed from 'first formalized' to 'named and formalized, not first'; what IS Dean & Boddy's own is the christening of the class and the deliberation-scheduling analysis. Prior wording preserved in this field and in the audit log."
provenance: "Promotion from 10-inbox/raw/2026-10-21-does-the-history-of-ai-or-cognitive-science.md, 2026-10-21 (headless)"
origin: "batch"
derived_from: "10-inbox/raw/2026-10-21-does-the-history-of-ai-or-cognitive-science.md"
date_created: "2026-10-21T00:00:00.000Z"
tags: ["history-of-ai","test-time-compute","inference-time-compute","anytime-algorithms","thomas-dean","mark-boddy","cognitive-science"]
seek_code_commit: "d40ee39"
quote_sweep: "PASS 2026-10-22 — source_quote verbatim (normalized) in the capture-time archive (sha256 6559c7f4933a…) [reading-order], same-night model-free sweep"
verified_verbatim: "2026-10-22 — source_quote matched verbatim (normalized) against a direct fetch of source_url by seek_verify (no model involved)"
---


Thomas Dean and Mark Boddy, in "An Analysis of Time-Dependent Planning"
(AAAI-88), named 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 [[entity-anytime-algorithm|anytime
algorithms]]."

The naming was theirs; the formalization was not first, and the paper says so.
Its footnote 6 grants that [[entity-eric-horvitz|Horvitz]]'s July 1987 paper
treats resource-constrained reasoning "in a more general framework," with "a
more extensive use of probability and utility theory"; Horvitz's §5.3 states
the trade-off outright as a monotonically decreasing function of precision on
immediacy, and his §5.4 traces it further back to [[entity-ij-good|I. J. Good]]'s
type II rationality — "the earliest discussion of the explicit integration of
the costs of inference within the framework of normative rationality." Dean and Boddy add that their "preliminary literature search
uncovered a large body of research on the properties of anytime algorithms."

This is, in substance, the same trade-off Anthropic describes for Claude's
extended thinking in 2025 ("serial test-time compute":
[[claim-extended-thinking-as-serial-inference-compute]]) and that Snell et al.
formalize in 2024 for LLM [[entity-test-time-compute|test-time compute]]
([[claim-test-time-compute-can-substitute-parameters]]): more computation
spent *after* the model or system is fixed, applied at the moment an answer is
needed, yields a better answer. [[entity-thomas-dean|Dean]] and Boddy state the
principle in 1988 — 36 years before Snell et al.'s 2024 compute-optimal
test-time-compute paper, 37 before Anthropic's own product framing of it; via
Horvitz 1987 the gap is 37 and 38.

> [!note] Seek's commentary:
> The paper's own motivating example is a robot sorting objects off a
> conveyor belt — 1988 real-time robotics, nothing to do with language — 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. What took 36 years wasn't the idea; it was a system whose extra
> "thinking" reliably bought anything. See
> [[claim-anytime-algorithms-continuously-connected-not-stent-premature]] for
> why that 36-year gap is a story about missing infrastructure, not a story
> about a buried insight. — Seek