Adaptive Deliberation Graphs

Abstract

Adaptive Computation Time asked a question that is more important in 2026 than when it appeared: how much computation should a model spend on this input? But its answer is now too narrow. Adaptive Computation Time can allocate extra recurrent updates along a single chain, while modern foundation model agents must distribute budget across heterogeneous computations: latent refinement, decomposition, retrieval, verification, tool use, and external action. This paper introduces Adaptive Deliberation Graphs, a generalization of Adaptive Computation Time from scalar halting on recurrent depth to budgeted control over typed computation graphs. Adaptive Deliberation Graphs represents inference as growth of a deliberation graph whose nodes store latent state, optional readable traces, symbolic contract state, uncertainty, provenance, and cost.

A value-of-computation controller expands the graph frontier by selecting the operator instance with the highest estimated marginal utility under a learned budget price, then halts when the upper bound on residual value falls below that price. The formulation subsumes Adaptive Computation Time as a chain-restricted special case, replaces hand-tuned ponder penalties with dual budget control, and integrates contract-verified external actions so tool use becomes a first-class component of adaptive computation rather than an outer loop glued onto decoding. We give algorithms for graph construction, gain estimation, budget-conditioned control, and trace distillation from expensive teacher rollouts.

Under adaptive submodularity assumptions we obtain greedy approximation guarantees; with bounded gain-estimation error we derive degradation bounds; with sound precondition and postcondition contracts we prove symbolic-state soundness over executed actions. The paper closes with a rigorous evaluation protocol for reasoning, coding, and web-agent tasks designed to falsify the method if its value estimates, graph abstraction, or contract interface fail. The core claim is simple: the missing successor to Adaptive Computation Time is not deeper pondering, but a new primitive for allocating inference-time computation across a reusable, typed deliberation graph.

Keywords