Is every iterative algorithm an anytime algorithm?

No. Its intermediate states must support meaningful outputs with an appropriate quality interpretation.

Must more time always improve the answer?

Not at every instant. The improvement behavior and guarantees depend on the method.

Is a contract algorithm safely interruptible?

Not necessarily. It may rely on receiving its agreed computation budget before delivering its promised result.

AI Glossary / Graphs and symbolic AI / Intermediate

Anytime algorithm

Definition

An anytime algorithm is designed to provide a usable result within a flexible computation budget and improve result quality when more computation is available. In the interruptible form, it can return its current result when stopped after any necessary initialization. The central idea is a deliberate tradeoff between computation time and the quality of the answer.

What it means

Some problems allow a useful approximate answer long before a fully refined or optimal answer is available. A planner may have a feasible schedule and then improve its cost. An inference procedure may refine an estimate or a bound as it processes more information.

Anytime design treats these intermediate results as meaningful outputs. It requires a way to describe quality, such as plan cost, approximation error, confidence under a defined method, or level of detail.

Not every algorithm that displays progress is anytime. A half-completed computation may have no valid output at all. The important question is what can be returned, what it means, and how additional work is expected or guaranteed to improve it.

How it works

An interruptible implementation retains a usable current answer while continuing computation. When quality can be compared reliably, it can keep the best result found rather than blindly replace it with the latest candidate.

A contract algorithm is a related time-sensitive approach that receives its computation budget in advance and is designed to deliver at the agreed endpoint. It need not provide the same guarantee if interrupted unexpectedly. Literature on anytime computation discusses both forms, so the intended meaning should be stated.

Performance profiles describe how quality changes with computation time, often empirically across problem instances. An average profile does not guarantee the same progress for every input. The system may also need a policy for deciding when further computation is worth its cost.

Practical design includes the time required to prepare, validate, and return an answer. An algorithm that can stop its internal search immediately may still need additional work before its result is usable by the surrounding application.

Three practical examples

1. A layout optimizer starts from a feasible arrangement and retains improvements, allowing a user to stop once the arrangement is good enough for the task.

2. A search tool returns the best complete plan found before a deadline and reports whether it has a quality bound or merely a measured objective value.

3. A decision-support process allocates extra computation to estimates whose refinement is likely to change the decision, rather than giving every calculation the same time budget.

Think of it this way

Think of drafting a map that first shows the essential roads and then adds increasingly precise detail. At specified stages, the current map can already serve a defined purpose, while further work improves it.

The analogy fails if the early map omits a critical bridge or misrepresents an unsafe route as usable. Likewise, an anytime result needs an explicit validity and quality contract. Calling an unfinished artifact approximate does not automatically make it suitable for use.

Worked example

Consider an original scheduling optimizer with a feasible initial schedule costing 50 units. After one second, it finds a schedule costing 44; after three seconds, 39; and after eight seconds, 38. Assume all schedules satisfy the same constraints and lower cost is better.

If interrupted after five seconds, the system can return the retained cost-39 schedule. It should not return a partially modified, unvalidated candidate currently under consideration. Compared with the initial schedule, the retained solution reduces cost by 11 units, or 22%.

That 22% improvement is not a bound on distance from the unknown optimum. If the optimum were 30, substantial improvement would remain possible. Without a valid lower bound or completed proof, the system cannot claim how close 39 is to best.

The invented timeline illustrates uneven improvement: five extra seconds from the third to the eighth second save only one unit. A different instance may behave differently, so the sequence is not a universal performance profile.

Illustrative case study

Fictional case: Maple Design lets a team request a draft allocation and continue refining it during a review meeting. The application preserves the latest validated allocation and displays its objective value separately from any quality guarantee.

The team tests interruptions before the first valid allocation and during a candidate update. It defines a clear no-result state for the first case and returns the prior valid allocation in the second. This invented case illustrates interface and state-management requirements, not a measured product outcome.

Common misconceptions and mistakes

Anytime does not necessarily mean instantaneous. Some algorithms need a startup period before their first usable answer.

Additional computation need not produce a strictly better result at every moment. Progress can plateau, and a procedure may only improve expected quality across runs rather than guarantee monotonic improvement on each run.

Do not equate a quality score with truth or safety. A lower-cost plan can still violate an omitted requirement. Also distinguish the ability to interrupt from the ability to suspend and resume without substantial overhead; these are separate implementation properties.

Business use

Anytime algorithms are useful when deadlines vary, available resources are uncertain, or the value of a decision declines while computation continues. They help a system offer explicit choices about latency and quality.

Evaluation should include time to first usable result, quality across representative time budgets, interruption behavior, and the cost of retaining or validating outputs. A business may prefer a slightly worse plan available on time to a better plan delivered after the opportunity has passed. That preference must be expressed in the surrounding decision objective rather than assumed from the algorithm's name.

Check your understanding

An optimizer's current candidate violates a constraint, but its stored earlier solution is feasible. What should an interruption return?

Answer: The retained feasible solution, with its actual quality status, rather than the unfinished invalid candidate.

Related terms

Anytime A*
Metareasoning
Bounded rationality
approximation algorithm
performance profile
contract algorithm
incumbent solution

Learn next

Next, define usable output for one computational task and identify a measurable quality criterion. Test interruption at several stages, including startup and result updates, before drawing a quality-versus-time curve.

Sources

Shlomo Zilberstein, Using Anytime Algorithms in Intelligent Systems: https://ojs.aaai.org/aimagazine/index.php/aimagazine/article/view/1232/1133

Hansen and Zhou, Anytime Heuristic Search: https://arxiv.org/pdf/1110.2737

Primary discussions of quality, interruptibility, and initialization read. Illustrations are original; desirable properties are distinguished from guarantees every anytime method must possess.

Previous: Anytime A* Next: Apparent contour