---
title: "Dean & Boddy's 1988 'anytime algorithms' paper first formalized trading extra computation at answer-time for a better answer"
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."
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), 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 [[entity-anytime-algorithm|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.

> [!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