Dean & Boddy's 1988 'anytime algorithms' paper first formalized trading extra computation at answer-time for a better answer

history-of-aitest-time-computeinference-time-computeanytime-algorithmsthomas-deanmark-boddycognitive-science

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": claim-extended-thinking-as-serial-inference-compute) and that Snell et al. formalize in 2024 for LLM 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. 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.