---
title: "anytime algorithm"
type: "entity"
entity_kind: "concept"
status: "hub"
canonical_name: "anytime algorithm"
aliases: ["anytime algorithms","anytime computation"]
first_seen: "2026-10-21T00:00:00.000Z"
writer_model: "claude-sonnet-5"
connects_to: ["test-time compute","deliberation scheduling","bounded optimality","Thomas Dean","Eric Horvitz"]
seek_code_commit: "d40ee39"
---


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 [[entity-test-time-compute|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
[[entity-gunther-stent|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