Selecting Computations

A computation, measurement or acquisition is worth making when its expected effect on a later decision exceeds its cost.

Pricing information and analysis

Howard (1966) defined the value of information as the increase in expected utility from observing a variable before deciding. Matheson (1968) extended the idea from observations to analysis. A model run or a calculation also changes what the decision maker believes, and can be priced the same way.

Gittins (1979) solved a related allocation problem exactly. For a class of bandit processes, each alternative can be given an index computed from its own state alone, and the optimal policy works on the alternative with the highest index. The result is the prototype for allocating effort among competing lines of investigation, under assumptions that research problems rarely satisfy.

Metareasoning in artificial intelligence

Horvitz (1987) argued that a reasoning system with limited resources should weigh the expected costs and benefits of alternative approximation procedures, and should balance the benefit of more computation against the cost of acting on a partial result. Russell and Wefald (1991) turned this into a general theory. A computation is an action whose value lies in its effect on later actions, and a rational agent performs the computation of highest net value until none remains positive.

Anytime algorithms supply a practical setting. They return a usable answer whenever interrupted and improve with more time, so the control question is when to stop. Hansen and Zilberstein (1996) address how to monitor such algorithms and decide when to stop them.

Metalevel control as a selection problem

Hay, Russell, Tolpin and Shimony (2012) place metalevel decisions in the framework of Bayesian selection problems and argue that this is more appropriate than the bandit framework. A bandit algorithm is designed to minimise regret summed over every trial. In a selection problem only the final choice collects a reward, and the trials are pure information gathering. The paper derives finite sampling bounds for optimal policies in some cases, and heuristics that beat bandit-based ones in one-shot decisions and in Go.

Tolpin and Shimony (2012) make the same point for Monte Carlo tree search: UCT minimises cumulative regret, while search needs low simple regret at the root. Sezener and Dayan (2020) value simulations directly by their expected effect on the action eventually chosen, including the effect of computations further ahead.

The distinction carries over to research controllers. A controller that schedules research directions with a bandit, as RD-Agent(Q) does, inherits an objective that rewards every trial. A research budget spent on exploration is rewarded only through the final choice of what to deploy.

Pruning parallel computations under a budget

Cotton (2026) poses the budgeted Brownian race. A controller watches a cloud of Brownian paths, pays per unit time for every path kept alive, may prune irreversibly, and spends a finite path-time budget to maximise the expected terminal maximum. The optimal policy keeps a path while its future pivotal value, the expected gain from one more path at that level, exceeds its carrying cost.

The rule is the value of computation applied to computations that run in parallel. The applications name two cases directly: reasoning rollouts, where tokens are the cost and a verifier scores the best completion, and fleets of research agents, where compute and API spend are the cost and the best finding that survives review is the payoff.

In the committed example, with initial intensity 100 and a path-time budget of 10, the adaptive policy reaches an expected maximum of 1.960. The best one-shot screening reaches 1.643 and static random thinning 1.509. The policies are optimal among population-blind controls, which decide each path from its own state, and a population-aware controller can do better.

The payoff is the terminal best rather than a sum over trials, the same objective Tolpin and Shimony argue for in tree search. browniansearch treats the search side, a few evaluations of one path rather than pruning many. The note Posterior-Predictive Pass-at-k estimates the payoff of a best-of-$k$ batch from a posterior rather than a plug-in, and cuts held-out log loss from 3.37 to 0.48 on nine thousand rollout prompts.

Learned and resource-rational metareasoning

Callaway et al. (2017) propose Bayesian metalevel policy search, which learns a policy for selecting computations. It rests on the observation that the value of information lies between the myopic value of information and the value of perfect information. It reaches near-optimal performance on stopping, on allocation between competing options, and on planning.

The same group models human cognition this way. People choose strategies as if by rational metareasoning (Lieder & Griffiths 2017), adapt cognitive control in ways rational metareasoning explains (Lieder et al. 2018), and can be analysed as making optimal use of limited computational resources (Lieder & Griffiths 2020).

Information acquisition as a decision

A second literature asks which observation to acquire rather than which computation to run. The knowledge-gradient policy of Frazier, Powell and Dayanik (2008) measures the one-step expected improvement in the value of the best alternative. It is the myopic value of information applied to sequential sampling.

Information-directed sampling (Russo & Van Roy 2014) chooses actions to minimise the ratio of squared expected regret to the information gained about the optimal action. The authors show it accounts for kinds of information that alternative approaches do not adequately address.

Bayesian optimisation applies the same reasoning to expensive functions. Frazier’s tutorial covers expected improvement, entropy search and the knowledge gradient, along with multi-fidelity and multi-source variants. Hyperband (Li et al. 2016) takes the opposite approach and allocates resources to random configurations with early stopping. It reports order-of-magnitude speedups over Bayesian methods on its benchmarks.

Active feature acquisition (Li & Oliva 2020) decides at prediction time which missing features to pay for, using a generative model of the features to estimate the information gain of each acquisition.

Wan, Liu, Grigas and Shen (2026) join this line to decision-focused learning. When predictions feed a linear optimisation, experiments chosen to reduce prediction error are inefficient, because decision loss rather than prediction error is what counts. Their design criterion targets uncertainty in the direction that affects the decision, and stops earlier than decision-blind designs.

Metareasoning inside language models

Adaptive Computation Time (Graves 2016) lets a recurrent network learn how many internal steps to take before emitting an output. On character-level language modelling it allocates more computation to harder-to-predict transitions such as word boundaries.

Test-time reasoning has made the question urgent. Snell et al. (2024) find the best use of inference compute depends on prompt difficulty, and a per-prompt compute-optimal allocation improves efficiency more than fourfold over best-of-N. Chen et al. (2024) document the reverse failure. Reasoning models spend large amounts of computation on easy problems for little benefit.

Several methods train the metalevel explicitly. De Sabbata et al. (2024) penalise reasoning whose value of computation does not justify its cost and report 20–37% fewer generated tokens at unchanged task performance. Meta-Reasoner (Sui et al. 2025) uses a contextual bandit to decide whether to continue, backtrack, switch strategy or restart.

AERA (Wang et al. 2026) shows that present confidence is a poor guide to whether more computation will help, since correctness can evolve non-monotonically. It learns the future value of computation instead. On 300 held-out GSM8K questions it reports 92.61% accuracy against 93.01% for 128 responses, with 95.99% fewer completion tokens.

At the scale of agentic search, ExTS (Fang & Wang 2026) treats the expansion of a search tree as a value-of-information decision when each evaluation is expensive, and reports an average relative gain of 5.5% over task-specific tree search across prompt optimisation, code generation and workflow optimisation.