anytime algorithm

A class of algorithm, named by Thomas Dean and Mark Boddy in 1988, that "can be terminated at any time and will return some answer," with answer quality improving "in some well-behaved manner as a function of time" the longer it is allowed to run — spending more computation at answer-time for a better answer, rather than at training or design time.

Matters to this vault as the earliest clearly-named occupant of the shape now called test-time / inference-time compute: a 2026 position paper on LLM test-time compute names "anytime algorithms expose quality as a function of deliberation (Zilberstein, 1996)" as part of the direct theoretical lineage behind present-day test-time-compute allocation (claim-anytime-algorithms-continuously-connected-not-stent-premature). The concept's own historical status is itself interesting: it was correct and industrially under-exploited for roughly 36 years, but — unlike a genuinely Stent-premature idea — never disconnected from its own era's canonical AI knowledge.

References

• claim-dean-boddy-1988-anytime-algorithms-formalize-compute-for-quality-tradeoff
• claim-anytime-algorithms-continuously-connected-not-stent-premature
• Captures: 10-inbox/raw/2026-10-21-does-the-history-of-ai-or-cognitive-science.md