Anytime Verified Agents: Adaptive Compute Allocation for Reliable LLM Reasoning under Budget Constraints
Authors: Dipkumar Patel
Venue: Accepted by TMLR ()

Abstract: Large language model (LLM) agents can perform multi-step reasoning, planning, and tool use. However, their performance scales with the computational budget. Existing methods allocate computational resources using static strategies such as fixed search depths, constant self-consistency sampling, or uniform verification, so simple problems can consume as much compute as complex tasks. We present Anytime Verified Agents (AVA), a framework that dynamically allocates compute across search, sampling, and verification within a user-specified budget, with an extensible interface for tool use. AVA combines calibrated uncertainty estimation, value-of-information-guided search expansion, and selective verification cascades with early exits. The controller allocates compute based on uncertainty and estimated marginal reliability gains. AVA is evaluated on mathematical reasoning (GSM8K and MATH), multi-hop question answering (HotpotQA), and code generation (HumanEval), with two model backends (GPT-5 and GPT-4o), and compared to fixed-depth search, self-consistency, and always-verify baselines. Across these benchmarks, AVA reduces cost at matched reliability thresholds while maintaining comparable accuracy.

Published in Transactions on Machine Learning Research (04/2026)
Anytime Verified Agents: Adaptive Compute Allocation for Reliable LLM Reasoning under Budget Constraints
Dipkumar Patel LLMs Research Inc.
dip dip@llmsreeearch.com
Reviewed on OpenReview: https: // openreview. net/ formm? id- JMDCMP
Abstract
Large language model (LLM) agents perform multi-step reasoning, planning, and tool use. However, their performance scales with the computational budget. Existing methods allocate computational resources using static strategies such as fixed search depths, constant self-consistency sampling, or uniform verification, so simple problems can consume as much compute as complex lasks. We present Anytime Verified Agents (AVA), a framework that dynamically allocates compute across search, sampling, and verification within user-specified budget, with an extensible interface for tool usc. AVA combines calibrated uncertainty estimation, tatt-of-inffrmmation with early exits. The controller allocates compute based on uncertainty and estimated marginal reliability gains. AVA is evaluated on mathematical reasoning (GSM8K and MATH), multi-hop question answering (HotpotQA), and code generation (HumanEval), with two model backends (GPT-5 and GPT-40),, and compared to fixed-depth search, self- consistency, and always-verify basclines. Across these benchmarks, AVA reduces cost at matched reliability thresholds while maintaining comparable accuracy.
search expansion, and selective verification cascades
1 Introduction
Agentic large language models (LLMs) can plan, reason, and interact with external tools to solve complex tasks (Wei et al. 2022:] Yao et al.) 2023a Zhou et al. (002).. Recent work has explored deliberate reasoning, external validation, and adaptive computation to improve reliability under test-time constraints.
Deploying these agents in real-world applications involves trade-off: improving reliability through increased test-time computation comes with increased cost. Current approaches address reliability through techniques like self-consisteney (Wang et al.) 2023), tree scarch (Yao et al. 2023a Besta et al.) 2024), and external verification (Cobbe et al. 2021), yet they allocate compute resources statically using fixed search depths, constant sampling budgets, or uniform verification strategies regardless of problem difficulty.
Static allocation can be inefficient. Consider mathematical reasoning agent: a simple arithmetic problem may require only a single forward pass, while a multi-step proof demands extensive search and verification. Applying the same computational budget to both wastes resources on easy problems and under-allocates to hard ones, limiting reliability under fixed budget. Moreover, static strategies cannot adapt to varying uncertainty levels or changing marginal returns on additional compute.
Recent work has explored adaptive computation (Kreutzer et al. 2018 Ahn et al. 2024 and selective verification, typically focusing on individual compute dimensions. To the best of our knowledge, prior work has not jointly allocated compute across search, sampling, verification, and tool use under unified budget. constraints based on task difficulty, uncertainty estimates, and expected marginal gains.
This paper introduces Anytime Verified Agents (AVA), framework that adaptively allocates computa- tional resources to maximize reliability under user-specified budgets. AVA makes three key contributions:

---

Published in Transactions on Machine Learning Research (04/2026)
1. Budget-aware controller: A decision-making module that dynamically allocates tokens and verification passes based on calibrated uncertainly estimates and predicted marginal reliability gains per unit cost. The controller additionally supports tool-call allocation, though this dimension is not excrcised in the current evaluation.
2. Selective verification cascade: A multi-tier verification system with early exits that routes problems through progressively stronger (and costlier) verifiers only when uncertainty excceds calibrated thresholds.
3. Value-of-iformation guided search: An adaptive tree search mechanism that expands nodes only when the expected information gain exceeds the marginal cost, allowing efficient exploration under budget constraints.
We evaluate AVA mathematical reasoning (GSM8K (Cobbe et al. 2021 and MATH (Hendrycks al., 20210) multi-hop question answering (HotpotQA (Yang et al. 2018)) ), and code generation (HumanEval (Chen et al. 2021)), ) comparing against fixed-depth tree search, self-consistency, and always-verify baselines across multiple budget levels and two model backends (GPT-5 and GPTT-oo.. Across these benchmarks, AVA reduces cost at cquivalent reliability thresholds while maintaining comparable accuracy.
2 Related Work
Our work synthesizes advances across agentic reasoning, adaptive computation, verification strategies, and budget-constrained reliability.
Reasoning and Search. Chain-of-Thought (CoT) prompting (Wei al. 2022) demonstrated that explicit step- stseep reasoning improves LLM performance and remains single- pass. Tree-of- Thoughts (ToT) Yao
ct al. 2023a explores multiplc reasoning paths via scarch trees; common implementations use fixed branching lactors and depths regardless of problem difficulty. Language Agent Tree Search (LATS) (Zhou et al.] 2024
integrates MCTS with uncertainty-guided expansion, yet maintains fixed total search budgets. Graph of Thoughts (Besta et al. 2024) generalizes to arbitrary graphs and retains static allocation. Least-to-Most (Zhou et al. 2023 decomposes problems sequentially using fixed strategies.
Sampling and Verification. Self-consistency (Wang et al. 2023 samples multiple completions for majority voting and uses fixed sample counts across problems. Best-of-N and AlphaLLM (Tian et al. 2024 improve efficiency while maintaining static policies. Training verifiers (Cobbe et al., 2021 scores reasoning chains and verifies all candidates uniformly. Cascaded verification systems reduce costs via early exits and use fixed routing policies. PAL (Gao et al. 2023) uses exccution for validation without adaptive allocation.
Adaptive Computation. Early stopping (Prechelt. 1998) and confidence--aseed halting (Kreutzer et al.j 2018) adapt per-instance and operate on single forward passes. D-LLM (Jiang al. 2024) adapts per- token compute allocation within transformer layers but focuses on internal model efficiency rather than unified budget allocation across reasoning steps. Tool use frameworks (Toolformer (Schick et al.] 2023
ReAct (Yo et al. 2023b), Any'Too (Du et al. 2024)) and self-reflection methods (Reflexion (Shinn et al. Self-Refine MMddaan et al. 2023 improve capabilities while using fixed budgets and iteration limits.
2023
Uncertainty Estimation. Raw I.M pogprrobaiilliies are poorly calibrated (Guo al., 2017), requiring
post-hoc calibration (Zadrozny & Elkan 2001). Sclf-consistency signals provide confidence proxies but don't
capture multi-step trajectory uncertainly. Existing methods operate on per-instance predictions rather than trajectory-level uncertainty across search, sampling, and verification.
Adaptive Token and Sample Allocation. Several recent methods tackle compute allocation for LLM reasoning. SelfBudgeter (Li el. al. 2025) trains models through reinforcement learning to estimate Loken budgets before generating a response, compressing outputs by roughly 60% on math benchmarks. The approach works well but adapts only token count and requires fino-tuning. Strategic Scaling (Zuo Zhu 2025) takes a different tack: treats sample allocation as a bandit problem, learning on-the-fly which queries benefit. from extra samples. This sidesteps training costs but only controls sampling, not verification search.
2

---

Published in Transactions on Machine Learning Research (04/2026)
Table 1: Comparison of compute allocation strategies. AVA adaptively allocates across all dimensions under
unified budget constraints. "Tool-call allocation is supported but not evaluated in the current experiments.
Approach
Search
Sampling
Verification
Tool Use
Budget
Self- Self-Consistency Wang al.
2023
Fixed
Adap. (fixed N)
None
None
Static
ToT (Yao 2023a
Adap. (fixed bud.)
Fixed
None
None
Static
LATS (Zhou
2024
Adap. (UCB)
Fixed
None
Fixed
Static
Verif. Cascades
Fixed
Fixed
Adap. (routing)
None
Partial
Any'Tool [Du et
2024
Fixed
Fixed
None
Adap. None
(routing)
Partial
D-LLM (Jing et al. 2024
Adap. (per-token)
Fixed
None
Partial
SelfBudgeter [Ll et al. 2026
Fixed
Adap. (learned)
None
None
Single
Strat. Scaling Zuo & Zhu 2025
Fixed
Adap. (bandit)
None
None
Single
AVA (Ours)
Adaptive
Adaptive
Adaptive
Adaptive"
Unifted
AVA differs from these approaches that it jointly controls search depth, sampling, verification intensity, and tool use under a unified budget. It relies on calibrated uncertainty from multiple signals instead of a learned predictor bandit exploration, and integrates cascaded verification with early exits. These ideas are complementary: learned budget prediction could inform controller, and online learning could be used to adapt thresholds during deployment.
Table compares prior methods along the compute-allocation dimensions they control. Current methods fall into three categories: (1) static allocation (fixed search depth in ToT/LATS, constant sampling in self- consistency, uniform verification), (2) partial adaptation (adaptive search but fixed verification, or selective verification but fixed search), or (3) cost optimization without reliability guarantees.
3 Method
AVA adaptively allocates compute across search, sampling, verification, and tool use to maximize reliability under budget constraints. This section presents the framework, organized around three stages: uncortainty estimation (Section 3.2). budget-aware allocation (Section 3.3), and execution (Section 3.4). Figure 2
(Appendix
B provides the full architectural diagram.
3.1 Overview and Notation
Figure _ (Appendix B] illustrates the AVA framework architecture. Given an input prompt x and compute budget B = (Broks Broot, Bver), AVA operates through an iterative decision loop with three core stages: uncertainty cstimation, budget-aware allocation, and exccution.
To illustrate, consider single AVA iteration. Stage aggregates whichever confidence signals are available and calibrates them produce E [0, 1J. Stage 2 computes the confidence gap Ttarget - and applies the allocation policy (Algorithm 1 to determine resources for sampling, search, verification, and tool use. Stage 3 executes these actions, updates the state, and returns to Stage 1 until 2 Ttarget or budget B is exhausted.
Table 2 summarizes the notation used throughout this paper.
Stage 1: Uncertainty Estimation (Section 3.2 AVA defines four confidence signals: token-level entropy (cn), self-consistency (cs), verifier scores ( and trajectory features (cr). Whichever signals are available at given iteration are combined into calibrated confidence via weighted aggregation (with renormalized weights) and isotonic regression.
Given state st, the controller computes the confidence gap A = Ttarget - c and determines allocation across four compute dimensions (sampling, search, verification, tool calls) using a rule-based policy that prioritizes high expected reliability gain per unit cost.
Stage 2: Budget-Aware Controller (Section 3.3
Stage 3: Exccution (Section 3.4 AVA exccutes the allocated actions: generates samples for self-consistency voting, runs value-of-informate guided tree search, applies verification cascade with early exits, and calls tools if allocated. After execution, the loop returns to Stage for re-estimation.
3

---

Published in Transactions on Machine Learning Research (04/2026)
Table 2:
Notation used throughout the paper.
Symbol
Definition
y
Input prompt, generated output
(Brok, Brook, Bver)
Compute budget: tokens, tool calls, verification passes
B, [0.1]
Remaining budget fraction
C [0,1]
Calibrated confidence
Grow
Raw (uncalibrated) confidence
CH 08, CV,
Confidence from entropy, self-consisteney, verifier, trajectory
WH, Mg, wy,
Signal weights (default: 0.3, 0.4, 0.2, 0.1)
a 1 1-c
Uncertainty
Plarget
Target, reliability threshold (default: 0.9)
A Tearget
Confidence gap
I E [0, 1]
Task complexity (from input features)
d,
Search depth reached, nodes expanded
Number of samples for self-consistency voting
b(u)
Branching factor function of uncertainty (En. 10
Number of verification cascade levels (default: 3)
daaa
Cumulative search depth normalization constant (default: 10) Decision history up step
he
Controller state: (et, me, Calibration function (isotonic regression via PAVA)
f
Vi
Level- verifier, returning (V) (v), validity confidence in verdict
Depth decay parameter Vol search (default: 0.2)
Example. For "What 17 x 23?" with budget 600 tokens and Ttarget = 0.9, initial confidence c = 0.72 yields A 0.18. The controller (Algorithm [ allocates: kt 5 samples (=:250 tokens), depth-1 search with breadth (=100 tokens), and level-1 verifier (=50 tokens). Samples agree and the verifier confirms, raising confidence to 0.89 and approaching the target with minimal further compute.
3.2 Stage 1: Uncertainty Estimation and Calibration
Reliable uncertainty estimation prerequisite for adaptive allocation. Raw LLM outputs provide multiple uncertainty signals, but these uncalibrated and must be aggregated.
3.2.1
Uncertainty Signals
AVA combines four complementary signals into a unified confidence estimate.
Token-level entropy. For generation y with tokens (I1,..., In), we compute Shannon entropy from model log- probabilities:
Htoken (v) Eplt.
p(t yes, x) log v<).
(1)
Higher entropy indicates greater uncertainty. We convert to a confidence signal:
Cy 1 - min(1, Hroken/TH).
(2)
where Th is normalization constant chosen on validation data so that most. per-sequence entropy values fall below TH (default ти 10; see Appendix A for all threshold values and tuning methodology).
Self-consistency signal. For N samples with answer set A, we compute the vote entropy and normalize:
count(a) log ca)nt(a) Mcons
Heons
Heons
Tog((AA)
aEA
Confidence is cs = 1 Honns with es = 1 by convention when |A| 1 (all samples agree). Uniform disagreement gives 6s 0.
Verifier scores. External verifiers (defined formally in Scction 3.4.2 return scores s, E [0, 1] indicating
validity. For cascaded verifiers, take the maximum score across levels reached: ey maxie(1....L) 8t-
4

---

Published in Transactions on Machine Learning Research (04/2026)
Trajectory features. Search depth d and remaining budget fraction B, provide trajectory- based uncertainty signals:
Hura (d. B,) = 0.6 (1 - d/dmax) + 0.4 - Br). Br),
(4)
where draax 10 is normalization constant representing the maximum cumulative search depth across all iterations of the AVA loop (distinct from the per-iteration depth cap of 5 in Algorithm [ which limits a single allocation step). Confidence: = = Heraj. Low search depth relative to dmax and low remaining budget both indicate higher uncertainty.
3.2.2 Aggregation and Calibration
Signals are combined via weighted average with datasel-specific weights learned via grid search validation data:
Craw WH cn + ws cs + wy + ey + WT CT:
(5)
with default weights (WH, ws, WV, wT) = (0.3, 0.4, 0.1) summing to 1.0. When a signal is unavailable, its weight is dropped and the remaining weights are renormalized. In the current experiments, at each iteration is computed from the two signals available before execution: token entropy (CH) and trajectory features (CT),
aggregated via Equation 5 with renormalized weights wn/(ww + wr) = 0.75 and WT/(WH + wT) = 0.25.
Self-consistency agreement and verifier confidence are not fed back into с through Equation S instead, they influence decisions through their respective mochanisms (majority voting for answer selection, cascade confidence for termination). The aggregation framework supports all four signals; routing sell-consistency and verifier feedback into the calibrated estimate is straightforward extension that would change only the weight renormalization at each iteration.
Post-hoc calibration. Raw confidence estimates from neural networks are poorly calibrated (Guo et al. 2017). We apply isotonic regression on held-out validation data, fitting a monotonic function f [0,1] [0, via the pool adjacent violators algorithm (PAVA) (Barlow et al. 1972). Specifically, given N validation examples with predicted confidences {pi} and correctness labels {s/ E {0, 1}}, we solve
f arg min
( vx)
(6)
f monotone
The calibrated confidence is c == f ensuring that reported confidence approximates the true success probability. Calibration is performed separately per dataset to account for domain-specific confidence distributions. Expected Calibration Error (F.CF) on the calibration set checked to validate quality (target ECE < 0.05).
3.3
Stage 2: Budget-Aware Controller
Given the uncertainty estimate from Stage 1, the controller decides how to allocate compute across four dimensions.
3.3.1 State Representation and Confidence Gap
At step f, the controller receives state s; = (ct, Br, de, ne, n,, h4), whose components arc: calibrated confidence a [0, 1), remaining budget fraction В, E [0, 1], search depth reached de, and nodes expanded n4- Task [0, is normalized weighted sum of input length (token count 512), parse depth (AST depth 10, or O when no parse tree is available), and a domain indicator (1 for code, 0.5 for math, 0 for QA), with equal weights and clipping to [0, 1]. Decision history he records past allocation decisions. In the current rule-based implementation, the collrr conditions on (ct, Br,t, de, n4, 4.) directly; ha reserved for learned policies. Since tool calls are not exercised (Section 3.4.3) t, does not influence the reported results.
complexity
The controller computes the confidence gap A Ptarget Ct (default Ftarget 0.9) and estimates marginal reliability gain per unit cost Vol, E[AR; RR; allocate;)/ for each dimension i.
5

---

Published in Transactions on Machine Learning Research (04/2026)
3.3.2 Allocation Policy
Algorithm [ formalizes the rule-based allocation policy. The policy is structured as a sequence of independent / Else blocks, one per compute dimension, making mutual exclusivity within each dimension explicit. Each block selects exactly onc allocation level based on the confidence gap A and remaining budget B
Algorithm Controller Allocation Policy
Require: State S, = (Ct, By,; de, Re, tt, his), target reliability Ttarget
Ensure: Allocation (k, d, b, u, tool): samples, search depth, breadth, verification level, tool call
A, f- Ttarget Ct if a Ttarget then
b Target reached: early stop
return (1,0, 1, false)
end if
Sampling allocation
5: if A; > 0.3 and B, > 0.3 then
6:
k: ++10 10
7: else A, > 0.1 then
k +
else
10: k +-1
11: end if
> Search allocation
12: if A, > 0.4 and B, > 0.5 then
13: d min (d: + 3, 5), 4 4
14: clsc A, > 0.2 then
15:
d min(d + 2, 3), 3-3
16: else
17:
d+ 1, b+2
18: end if
Verification level
19: A, > 0.5 or a < 0.3 then
20:
G 5+3
D Full cascade
21: else if A, > 0.2 then
22:
6
Medium verifier
23: else if A, 0.05 then
24: c61
Lightweight verifier
25: else
26: 0 0+0
> Skip verification
27: end if
Tool call
28: if ct 0.4 and B, 0.4 and 4, > 0.6 then
29: tool + true
30: else
31: tool + false
32: end
33: return (ks d, b, v, tool)
The verification level assignment can equivalently be written as a piecewise function of the confidence gap:
3 > 0.5 or e < 0.3,
2 if 0.2 A 0.5,
c)
(7)
I if 0.05 < A < 0.2,
otherwise,

---

Published in Transactions on Machine Learning Research (04/2026)
making the mutual exclusivity of routing decisions explicit. Note that the condition 0.3 overrides the gap-based routing to ensure low-confidence outputs always receive full verification regardless of the gap value. All threshold values used in Algorithm | are listed in Appendix A with tuning methodology.
We use a mll-bbased policy to make routing conditions explicit and avoid additional training data for the controller. The controller interface is modular, and the policy can be replaced with a learned alternative without changing the rest of the framework (Section 0
3.3.3 Learning Cost-Benefit Frontiers
AVA learns the relationship between compute budget and achievable reliability to inform marginal-gain estimates. During evaluation, track empirical reliability at discrete budget levels B E {400, 600, 800, 1000} tokens and reliability targets E {0.7, 0.75, 0.8, 0.85, 0.9), maintaining running means (,(B) and variances (B).
We model the cost-benefit frontier with the parametric form
rBB = - exp( -a B²).
where a controls the rate of reliability gain and 3 governs the curvature. Parameters are fit via leasl-squares on observed rz), pairs from past evaluations, with initial values og = 0.01, 30 0.5 obtained from a pilot
100 validation examples. Online, parameters are updated via exponential moving average with decay 1) 0.1: a, = (1 7) 0,-1 n4
Given the fitted frontier, the controller estimates the marginal reliability gain for an additional compute increment AC as E|RR| AC] = 8B BBBreenn AC. If E|AR)/AC' < 0.001, the controller conserves compute by reducing allocation intensity. Thresholds similarly adapt online: T (1 17) Tt-1 Tobserved
dr
3.4 Stage 3: Execution Modules
Once the controller has determined the allocation, AVA executes each compute dimension.
Sampling and self-consistency. When the controller allocates samples, AVA generates independent completions temperature 0.7. Answers are extracted and a majority vote determines the final answer. The vote distribution provides the self-consistency confidence signal cs (Section 3.2 when all & samples agrec, cs 2 1; uniform disagreement gives cy & 0. Sampling cost scales linearly with k.
3.4.1 Value-of-Information Guided Search
Tree search explores multiple reasoning trajectorics but expands combinatorially. Fixed-depth search (c.g., ToT (Yao et al., 2023ah) allocates uniform compute regardless of uncertainly. AVA uses value-of-information (Vol) to guide expansion, prioritizing nodes with highest expected information gain per unit cost.
Valuc-of-informatiion computation. For node n depth d with uncertainty uny we compute:
VoI(n) 1 1+
Un
where >= 0.2 is a depth decay parameter that discounts deeper nodes to favor shallower, cheaper expansions. Higher uncertainty yields higher Vol, directing search toward the most uncertain branches. More elaborate Vol formulations could incorporate node quality estimates or historical reliability data; the current form prioritizes simplicity and uses only uncertainty and depth decay.
Adaptive branching. The branching factor b adapts to uncertainty to balance exploration and exploitation:
4 if u 0.7 (high uncertainty: explore widcly),
b(u)
3 if 0.4 < < 0.7 (moderate uncertainty),
(10)
< 0.4 (low uncertainty: exploit).

---

Published in Transactions on Machine Learning Research (04/2026)
The breakpoints (0.4, 0.7) were selected via grid search validation data to balance exploration breadth against compute cost. Additionally, if remaining budget B, < 0.2, branching is reduced to b mmx B,/0.2[) to conserve resources.
Priority expansion and termination. Nodes are maintained in a Vol-sorted priority queue. At each step: pop the highest- Vol node, expand by generating b(,,) children, compute child Vol values, add to the queue, and update the best solution improved. The queue size is capped to prevent exponential growth. Search stops when: (1) calibrated confidence 2 Starget (2) remaining budget B, 0.05 (budget effectively exhausted), (3) maximum iteration count reached.
Example. If the initial node has high uncertainty (u= = 0.8), Vol = 0.8 and branching selects b b= 4. Search prioritizes expansion by Vol and terminates once c 2 Ptarget or the remaining budget. is exhausted.
3.4.2 Selective Verification Cascade
A verifier is function V X' x + {0,1) [0,1] that takes an imput-output pair (z, v) and returns validity judgment v E 1) and confidence score E 1]. Verifiers may be rule-based checks (format validation, length heuristics), execution-based validators (rumning generated code, checking arithmetic), or mosel-based judges (LLM-as-judge). AVA treats verifiers as black boxes, requiring only the (v, s) interface.
Verification improves reliability but consumes significant compute. Uniform verification (applying full-strength checking to all outputs) wastes resources on high-confidence outputs and under-verifies low-confidence ones. AVA uses cascaded verification system with early exits that routes problems through progressively stronger verifiers only when needed.
Cascade structure. The verification cascade consists of L = =3 levels, ordered by increasing cost and verification strength:
V = (Vi V22 Va).
(11)
where level costs scale as (cI, 03) = (0.1z, 1.0x, 5.0z) for base cost x. V11 uses lightweight heuristics (length checks, format validation), V/2 uses medium-cost semantic checks (LI.Mass-judee, partial exccution), and V; uses full validation (complete execution, formal verification).
Early-exit policy. The cascade iterates through levels ( = I...., L: run Vi(x, y) to obtain (u),s)), where st is the verificr's confidence in its own verdict regardless of whether the verdict is acceptance or rejection.
Confidence updale. When i = (accepted); 81 confidence in the acceptance and we update e +- max(c, st). When t7 = 0 (rejected), sı is confidence in the rejection; the residual probability of correctness is 1 1- S/, so update max(c, st). A confident rejection (s) near 1) contributes negligible residual confidence, while tentative rejection (s) near 0) leaves substantial probability mass correctness, allowing subsequent levels to re-evaluate.
Exit conditions. The cascade exits early if: (1) c 2 Thigh (sufficient confidence; default Thigh = 0.955, chosen so that high-confidence predictions are reliably correct on validation data), or (2) - and s; 2 1 Dow (confident rejection, i.c. residual correctness probability below Tow; default Now = 0.3, so the cascade exits when st 2 0.7). Otherwise proceed to the next level. Final decision: return (V[[c 2 0.5). c, l).
This allows efficient verification: simple problems exit at level 1 (saving 90% of verification cost), while complex problems progress to full verification only when necessary. The controller determines the initial verification level via Equation 7 and the cascade provides additional savings through early exits within the allocated level range.
Example. With = 0.25, the controller selects level 2 (Equation 7 Vi returns (1, (1.0.75) and V/2 returns (1, 0.92,, so the confidence updates to cy = max(c, 0.75, 0.92) 0.92. Since the allocated level is 2, the cascade stops after Vz.
8

---

Published in Transactions on Machine Learning Research (04/2026)
3.4.3 Tool Calls
Tool calls are external computations or retricval operations invoked by the agent during reasoning. Each call consumes a fixed amount from the tool budget Brool- Depending on the domain, tools may include interpreters, search APIs, or execution sandboxes.
The controller enables tool calls when confidence low (<< 0.4), budget permits (B, 0.4), and lask complexity is high 0.6); see the tool-call block in Algorithm [] The framework supports tool integration through generic Tool interface (accepting arbitrary input and returning structured results), but the current experiments do not exercise external tool calls: verification and sampling account for all non-generation compute in our evaluation. Integrating domain-speciffe tools is left to future work.
3.4.4 State Update and Loop Termination
After each execution step, AVA updates state. Search results update the trajectory features (CT). and & is re-estimated from си and the updated eT via the aggregation and calibration pipeline (Section 3.2 Sampling rosults determine the answer via majority vote, and verification outputs contribute to termination decisions through cascade confidence (Section 3.4.2. but neither feeds back into c in the current implementation. Budget counters are decremented for tokens consumed, tool calls made, and verification passes executed.
The loop terminates when any of the following conditions hold: (1) calibrated confidence 2 Ytarget (2) remaining budget B, < 0.05 (budget effectively exhausted), or (3) confidence is sufficiently high (c 2 0.85) and budget is low (Br < 0.2), indicating diminishing returns from further compute.
Algorithm 2 summarizes the complete AVA workflow, integrating the three stages described above.
Algorithm AVA: Anytime Verified Agent
Require: Prompt z, Budget = (Braks Broot, Byer), Target reliability Ttarget
Ensure: Answer y, Final confidence
Initialize: budget + B, c O, Ybest +
while budget not exhausted and < Ttarget do
Stage 1: Uncertainty Estimation (Sec. 3.2
Compute cи from token entropy, eT from trajectory features 4: #H + wH/ (wH + WT), ①T t ww/www/ + wr)
> Renormalize weights b Eq.
5: Craw < wH CH + wr CT
Calibrate: c + (Craw); u 1+1-c
Stage 2: Adaptive Allocation (Sec. 3.3
A Ftarget C (ke, d, b, U, tool) CONTROLLERPOLICYY'SS Ptarget)
Alg
Stage 3: Execution (Sec. 3.4
9:
if & > then Sample i completions, select via majority voting, update cs end if
10:
11:
12:
if d d>0 then
13:
Run Vol-guided search with depth d, breadth b (Sec. 3.4.1 end if
14:
15:
if >>> 0 then
16:
Run verification cascade up to level v (Sec. 3.4.2 update cy
17:
end if tool then
18:
19: Call external tool, incorporate result.
20: end if
21: Update ybest: decrement budget
22:
end while
23: return Ybest,
9

---

Published in Transactions on Machine Learning Research (04/2026)
4 Experiments
We evaluate AVA across three domains: mathematical reasoning (GSM8K (Cobbe et al. 2021 multi-hop question answering (A (Yang et al. 2018)), and code generation (HumanEval (Chen et al. 2021 Experiments compare AVA against static allocation basclines across multiple budget levels to quantity compute-reliablity trade-offs.
4.1 Baselines and Experimental Setup
We compare AVA against three static allocation baselines. GSM8K, HotpotQA, and HumanEval use GPT-5 (temperature 0.7, max tokens 512). MATH uses GPT-4o (temperature 0.7, max completion tokens 2048); GPT-5's hidden reasoning tokens cause its single-shot accuracy on MATH to saturate near 67%, which leaves limited headroom for distinguishing adaptive from static allocation, whereas GPT-4o's accuracy in the 30 to percent range exposes the relevant trade-offs. Self-Consistency (Wang et al. 2023) generates & E {5, 10, 20, 40) independent completions and selects the answer via majority vote, adapting only sample count without search or verification. Fixed-Depth Tree Search implements ToT-style (Yao et al.) 2023a) breadth-first search with fixed depth and branching factor, evaluated at bd E {(2,2), (3.3), 3), 4)]; all nodes at each depth are expanded uniformly regardless of uncertainty. Always- Verify generates a single completion and applies the full 3-level verification cascade (Section 3.4.2 to every output regardless of confidence, representing maximal verification without adaptive routing.
To assess whether AVA's gains require the full controller, we also evaluate two lightweight adaptive houristics: Confidence- Seifdeence-Threhllldd Threshold Exit (single generation with early stop when calibrated confidence exceeds a tuned threshold, otherwise route to level-1 verification) and Adaptive Sampling Rule (sample count. k E 51 10} chosen from confidence-gap thresholds, without search allocation or multi-level verification routing). Thresholds for both heuristics are tuned on the same validation split used for AVA hyperparameters.
GSMSK contains 1,319 math word problems evaluated via exact match. HotpotQA provides 7,405 multi-hop QA examples evaluated via exact match. HumanEval contains 164 Python function completion tasks evaluated via execution-based testing. MATH (Hendrycks et al., 2021) contains 500 competition problems across five difficulty levels and seven subjects (algebra, calculus, counting, geometry, number theory, prealgebra, precalculus); we evaluate on 50-problem sample drawn uniformly across difficulty levels and apply the same sample to every method, with answers compared by SymPy-based symbolic equivalence on the extracted final expression (Appendix D
We evaluate across token budgets B E {400, 600, 800, 1000} per problem, representing realistic production constraints. For methods using verification (AVA, Kwaas-Verilyy. we allocate verification budgets of 20 calls per problem. For tool-using methods, we allocate 20 tool call limits. The unified budget. (Brok; Braot, Byer) allows methods to trade off across dimensions.
AVA uses target reliability Ptarget 0.9 with signal weights learned per dataset via grid search validation data. Uncertainty calibration uses isotonic regression on 10% held-out split, fitted separately per dataset. (target ECE < 0.05). All hyperparameter values, tuning methodology, and defaults are listed in Appendix A
We evaluate on full test sets (1,319 for GSM8K, 7,405 for HotpotQA, 164 for HumanEval) and on the 50-problem MATH sample described above. Correctness measured via exact match (GSM8K, HotpotQA), execution-based testing (HumanEval), or symbolic equivalence (MATH). We report Siliiabiiitt@Budiee (accuracy at fixed budget), Cost@Reliability (minimum cost to reach target reliability), ECE, and Brier Score. Cost estimates are $0.001 per 1K tokens, $0.1 per tool call, and $0.05 per verifier pass. For reproducibility, Python and NumPy seeds are fixed to 42; all basclincs use identical model and temperature settings. Because decoding uses temperature 0.7, runs can vary across API calls even with fixed local seeds; reported values are from a single controlled run per setting. We note that HumanEval's small test set (n-164) and the MATH 50- problem sample limit statistical power: percentage point difference on HumanEval corresponds to roughly additional correct problems, and the standard error on the MATH sample at p z 0.4 is approximately percentage points.
10

---

Published in Transactions on Machine Learning Research (04/2026)
Table 3: Accuracy (%) fixed token budgets. Differences are modest on GSM8K where baselines already perform well, and larger on HotpotQA and HumanEval. On MATH, AVA leads B=600 and B=800; self-consistency leads at B-400 and B=1000. Fixed-depthiss near-zero MATH accuracy reflects insulficient per-node token allocation rather than fundamental method failure (see Section 5). HotpotQA omits budget 400 because multi-hop prompts leave insufficient generation budget at that level. MATH is evaluated with GPT-4o on 50-problem sample (Appendix D) other benchmarks use GPT-5.
Dataset
Budget Self-Consistency Fixed-Depth Sways-Verify.
AVA
400
81.2%
80.8%
81.0%
81.5%
600
81.5%
81.3%
81.4%
81.9%
GSM8K
800
81.8%
81.6%
81.7%
82.1%
1000
81.9%
81.8%
81.8%
82.3%
600
52.3%
54.1%
53.8%
58.2%
HotpotQA
800
59.8%
61.2%
62.1%
65.8%
1000
61.4%
63.7%
64.2%
68.3%
400
28.7%
30.2%
29.8%
33.1%
HumanEval
600
36.4%
38.7%
39.1%
42.8%
800
38.2%
40.3%
40.9%
45.2%
400
44.0%
0.0%
34.0%
34.0%
600
34.0%
0.0%
34.0%
36.0%
MATH
800
34.0%
0.0%
36.0%
42.0%
1000
46.0%
0.0%
38.0%
36.0%
GSM8K
HolpotQA
HumanEval
Ancuzucy (%)
82
155
85
83
50
400
600
800
1,000
600
800
1,000
400
600
800
Budget (tokmu)
Budget (tolsens)
(tokens)
Self-Cone Cons.
Depth
Always- Ver.
AVA
Figure Accuracy vs. token budget across three domains.
Ablations. We ablate AVA components: w/o calibration (raw confidence). w/o cascade (single verifier), w/o adaptive search (fixed-depth), and w/o unified controller (independent allocation).
5 Results
Table 3 and Figure 1 report accuracy across budgets and baselines. On GSMSK, where baselines are already strong, the differences are modest (0.3-0.5% absolute). On HotpotQA and HumanEval, the differences are larger (4-6% absolute the highest budgets). On MATH, AVA leads at moderate budgets (+2 percentage points at B=600 and +6 at B=800 over the strongest baseline at those budgets) and trails self-consistency by 4 to 10 percentage points at the budget extremes (B=400 and B=1000), where five-sample voting either makes maximal use of a tight per-call allowance or fully exploits the available compute. Fixed-depth tree search returns near-zero accuracy on MATH because its default per-node token allocation (50 tokens) is insufficient for the multi-step responses MATH problems require; we did not re- re-tune this hyperparameter per benchmark.
Table reports the corresponding Cost Reliaaaliyy
11

---

Published in Transactions on Machine Learning Research (04/2026)
Table 4: Cost@Reliabllit: minimum per-problem token consumption to reach a target reliability threshold, computed from actual evaluation runs. Percentages indicate relative cost differences compared to the best baseline.
Dataset
Target Reliability
AVA Cost
Best Baseline Cost
GSM8K
80%
620
780
(Self-Cons., 20.5%)
HotpotQA
65%
780
1050 (Fixed-Depth, -25.7%)
HumanEval
42%
650 920 (Fixed- Deeth,,, -29.3%%
Table 5:
Comparison with lightweight adaptive baselines at representative high-budget settings. Conf-Exit denotes confidence-thresholdd early exit; Adap-Sampling denotes confidencegaa--drieen sampling without joint.
scarch verif/vvriiiiationn allocation.
Dataset
Budget
Conf-Exit
Adap-Sampling
AVA
AVA Gain
GSM8K
800
81.9%
81.9%
82.1%
+0.2%
HotpotQA
1000
65.4%
66.1%
68.3%
+2.2%
HvmanEval
800
42.1%
43.0%
45.2%
12.2%
Table 5 compares AVA with two lightweight adaptive hcuristics. Both hcuristics improve over the static baselines in this comparison. The remaining gaps in Table 5 are larger on HotpotQA and HumanEval than on GSMSK, consistent with benefits from joint allocation across search, sampling, and verification beyond carly-cxit or sampling-only adaptation.
Table reports calibration metrics. Post-hoc calibration reduces ECE from 0.098-0.144 142 (raw) to 0.032-0.048 across domains. When AVA reports confidence 0.9, observed success rates range from 0.881 to 0.892, indicating that the calibrated estimates are close to the true success probability.
Table 7 breaks down resource allocation by difficulty tier, where tiers are defined by the number of reasoning steps in the reference solution: Easy (1-2 steps), Medium (3-4 steps), Hard (5+ steps). Easy problems consume roughly a third of the budget of hard problems, and the controller routes most easy examples past verification entirely. Confidence gap A correlates with allocation intensity (r 0.73, < 0.001), consistent with the uncertainty-driven allocation design.
Table 8 reports ablation results on GSM8K at budget 800. Each component removal degrades accuracy by 5.9% absolute. The largest single drop comes from removing calibration (0.9%), which also triples ECE, indicating that poorly calibrated confidence leads to suboptimal allocation. Removing the cascade increases average cost by 18% without improving accuracy, since expensive verification is applicd uniformly.
Broken down by difficulty, improvements are concentrated on medium and hard problems (6-8% absolute over the best baseline), while the controller allocates less compute on easy problems and more on hard ones. Table 13 (Appendix C reports verification cascade efficiency: 68% of examples exit at level 1, yielding 62% average cost. savings over uniform full verification. High-confidence examples (c >>>>> 0.85) exit at level 1 in 89% of cases; low-confidence examples (c < 0.5) require the full cascade 78% of the time.
Threshold sensitivity. We evaluate sensitivity to controller thresholds by sweeping the confidence-gan threshold (controlling when to allocate 10 samples) from 0.15 0.45 and the budget threshold from 0.2 to 0.4, yiclding 35 configurations. Figure (Appendix C) shows the full cost-accuracy scatter across all 35 settings. Estimated cost ranges from 630 to 830 tokens, with the default setting (0.3, 0.3) at 716 tokens, roughly in the middle of the range. Accuracy remains within percentage point across the sweep. Table reports representative subset of configurations and their allocation behavior.
Verifier-noise stress test. To test robustness to imperfect verifier quality, we perturb verifier outputs at each cascade level with noise rate 77 E (0.1, 0.33. With probability 77, verifier verdicts are flipped; scores are simultancously shrunk toward 0.5 via s' (1 11)s + 0.51.. Table 12 (Appendix C reports fixed-budget accuracy under this stress protocol. Performance degrades smoothly as verifier noise increases, and AVA remains above A Always Always-Verify at all tested noise levels.
12

---

Published in Transactions on Machine Learning Research (04/2026)
Table Calibration quality metrics. Post-hoc calibration via isotonic regression reduces ECE relative raw confidence estimates. Reliabilit@00.3 Conf measures actual success rate when model reports 0.9 confidence.
Dataset
Method
ECE
Brier Score Reliability@0.9 Conf
Baseline (raw)
0.127
0.234
0.762
GSM8K
AVA (calibrated)
0.032
0.145
0.887
Bascline (raw) AVA (calibrated)
0,098
0,198
0.798
HotpotQA
0.035
0.156
0.892
Baseline (raw)
0.142
0.267
0.731
HumanEval
AVA (calibrated)
0.048
0.189
0.881
Table 7: Resource allocation by difficulty tier (GSM8K). Easy problems use minimal compute; hard problems receive full verification cascades, multiple samples, and deeper search.
Difficulty
Avg Tokens
Skip Verif.
Single Sample
Shallow Search
Easy
280
85%
92%
78%
Medium
520
55%
62%
45%
Hard
750
18%
29%
11%
6 Discussion
Calibration requirements. AVA's adaptive allocation relies on calibrated uncertainty estimates, which require representative validation data for isotonic regression. As T shows, post-hoc calibration reduces ECE from 0.098-0.142 to 0.032-0.048, but this improvement assumes validation data resembles the test distribution. Under domain shift. the calibration function may degrade, leading to suboptimal resource allocation.
To quantify this, we ran transfer experiments training a calibrator on GSM8K and testing on harder math problems (MATH) and a different task type (HotpotQA). Table 9 shows the results. In-domain (GSM8K to GSMSK), calibration reduces ECE from 0. 059 to 0.064. But transferring the GSMSK calibrator to MATH actually increases ECE from 0.169 to 0.303. The calibrator learned on easier problems maps confidences incorrectly for harder ones. Transfer HotpotQA (a different task entirely) shows moderate degradation, with ECE rising from 0.080 to 0.124. The oracle setting (MATH to MATH) achieves ECE of 0.043, underscoring the importance of domain-specifee calibration.
Even with calibration degradation, the controller still functions, though it allocates resources less efficiently. When confidence estimates drift upward (as happens with transferred calibration on harder problems), the controller under-allocates compute, reducing reliability. For production deployments, periodic recalibration on held-out target data advisable. Online adaptation mechanisms could further reduce the recalibration burden.
Threshold generalization. The specific numeric threshold values reported in this paper (e.g., confidence- gap breakpoints in Algorithm D branching factor boundaries in Equation 10) were selected using GPT-5 on the three evaluation benchmarks. Different models will exhibit different uncertainty distributions and cost-reliability profiles, requiring recalibration of threshold values. However, the threshold selection procedure itself model-agnostic: branching breakpoints and confidence-gap thresholds are selected via grid search on validation data, and carly-cxit thresholds via grid scarch on the calibration split. The scnsitivity analysis (Table [1] shows that accuracy varies by less than 1 percentage point across wide range of threshold configurations, suggesting that exact values less critical than the adaptive allocation mechanism itself. Practitioners adapting AVA to new model should recalibrate the isotonic regression on representative validation data and re-run a coarse grid search over the confidence-gap thresholds in Algorithm D
Rule-based vs. learned controllers. The current controller uses hand-crafted rules mapping confidence gaps to resource allocations, which keeps the routing conditions explicit and avoids additional training data for the controller. However, rule-based policies cannot capture complex interactions between compute dimensions adapt to distríbution shift during deployment. Learned policies via. reinforcement learning could discover
13

---

Published in Transactions on Machine Learning Research (04/2026)
Table Ablation study results on GSM8K (budget 800). The table reports the effect of removing individual components on accuracy, cost, calibration, verification calls, and search itcrations.
Variant
Accuracy Avg Cost
ECE
Verification Calls Search Iterations
AVA (full)
82.1 %
0.032
0.8
12.3
w/o calibration
81.2%
635
0.089
1.2
15.1
w/o cascade
81.6%
732
0.041
2.8
13.4
w/o adaptive search
81.4%
685
0.038
0.9
27.5
w/o unified controller
81.5%
705
0.045
1.5
18.2
Table 9: Calibration transfer results. ECE (cal) shows calibration error after applying a calibrator trained the source datasct. Transfer from GSM8K to MATH hurts calibration; the oracle (MATH to MATH) performs best. Rel@0.9 measures actual accuracy when calibrated confidence 2 0.9.
Source
Target
ECE (raw)
ECE (cal)
Acc.
Rel@0.9
GSM8K
GSM8K
0.159
0.064
74.6%
82.5%
GSM8K
MATH
0.169
0.303
43.6%
52.4%
GSMSK
HotpotQA
0.080
0.124
62.6%
73.0%
None
MATH
0.169
0.169
43.6%
72.7%
MATH
MATH
0.169
0.043
43.6%
N/A
allocation strategics that the rule-based approach misses, The controller interface is modular; the rule-based policy (Algorithm T can be replaced with a learned one without modifying the uncertainty estimation or execution modules.
Verification limitations. Our verification cascade employs heuristic verifiers (format checks, length heuristios, partial execution) rather than domain-specific validators. Table 13 indicates that 68% of examples exit at level and only 10% require full verification, yielding 62% cost savings. However, for tasks where correctness is critical (matternatical proofs, safety-critical code), heuristic verifiers may miss subtle errors that formal equation solvers or comprehensive test suites would catch. The cascade architecture supports drop-in replacement of verifiers, so integrating domain-spocific validators straightforward.
Scope of evaluation. Our experiments span two model families (GPT-5 on GSM8K, HotpotQA, and HumanEval; GPT-40 on MATH) across four benchmarks. The MATH results indicate that AVA's 's advantage is regime-dependent: it is largest in moderateedifficully, moderate-budget settings, narrows when one-shot accuracy already saturates the model's ceiling, and reverses at very tight budgets where simple multi-sample voting dominates because per-call cost outweighs allocation choices. We include two lightweight adaptive baselines (Table and verifier-noise stress tests (Table 12 both reduce the differences relative to simpler methods under harder conditions, and the tables report the remaining gaps. Additional evaluation across model scales and difficulty regimes would refine these boundaries.
These limitations suggest extensions such learned controllers, domain-specific verifiers, dynamic budgets, and shw- adaptation mechanisms. The modular AVA architecture is intended to accommodate such changes.
7 Conclusion
We introduce Anytime Verified Agents (AVA), framework for adaptive compute allocation in agentic LLM systems that targets reliability under user-specified budget constraints. Existing approaches improve reliability through increased test-time computation but allocate resources statically, so simple problems can consume much compute as complex ones.
AVA combines a budget-aware controller, a selective verification cascade, Vol-guided search, and calibrated uncertainty estimation a single loop. Evaluation on GSM8K, HotpotQA, HumanEval, and MATH, across two model backends, shows reduced cost at equivalent reliability thresholds compared to static baselines, with comparable accuracy. Ablation studies indicate that each component affects accuracy, cost efficiency, both.
14

---

Published in Transactions on Machine Learning Research (04/2026)
Future work should explore learned controller policies, multi-task adaptation, integration with domain-specific verifiers, and real-world deployment considerations. The framework and code will be released upon acceplance to support reproducibility.
Broader Impact
AVA's adaptive compute allocation may reduce the computational cost of reliable LLM reasoning, making verification and multi-step reasoning more practical in resource-constrained settings.
However, the framework introduces failure mode worth noting; if the uncertainty estimator is miscalibrated (e.g., due to domain shift, as shown in Table 9t. the controller may underallocate verification to problems that appear easy but are in fact difficult. In safety-critiaal applications, this could lead to skipped verification on outputs that require scrutiny. We recommend that deployments in such settings enforce a minimum verification floor (e.g,, always apply at least level-1 verification) regardless of confidence estimates, overriding the controller's skip decision.
AVA primarily reallocates existing compute rather than introducing new model capabilities. It can still be used in high-stakes settings where calibration or verification errors carry consequences, so deployment safeguards remain important.
References
Janice Ahn, Rishu Verma, Renze Lou, Di Liu, Rui Zhang, and Wenpeng Yin. Large language models for mathematical reasoning: Progresses and challenges. arXiv preprint or 2rXiv:2402.000 001557 2024.
Richard E. Barlow, David Bartholomew, James M Bremner, and H Daniel Brunk. Statistical Inference Under Order Restrictions. Wiley, 1972.
Maciej Besta, Nils Blach, Ales Kubicek, Robert Gerstenberger, Lukas Gianinazzi, Joanna Gajda, Tomasz Lehmann, Michal Podstawski, Hubert Niewiadomski, Piotr Nyczyk, and Torsten Hoefler. Graph of thoughts: Solving elaborate problems with large language models. In Proceedings of the AAAT Conference on Artificial Intelligence, volume 38, pp. 17682-17690, 2024.
doi: 10. 10.1609/AA 1609//aaii.i...mm wtt.//a.................. v38116.29700.
Mark Chen, Jerry Tworek, Heewoo Jun, Qiming Yuan, Henrique Ponde de Oliveira Pinto, Jared Kaplan, Harri Edwards, Yuri Burda, Nicholas Jaseph, Greg Brockman, Alex Ray, Raul Puri, Gretchen Krueger, Michael Petrov, Heidy Khlaaf, Girish Sastry, Pamela Mishkin, Brooke Chan, Scott Gray, Nick Ryder, Mikhail Pavlov, Alethca Power, Lukasz Kaiser, Mohammad Bavarian, Clemens Winter, Philippe Tillet, Felipe Petroski Such, Dave Cummings, Maithias Plappert, Fotios Chanez, Elizabeth Barnes, Ariel Herbert-Voss, William Hebgen Guss, Alex Nichol, Alex Paino, Nikolas Tezak, Jie Tang, Igor Babuschkin, Suchir Balaji, Shantanu Jain, William Saunders, Christopher Hesse, Andrew N. Carr, Jan Leike, Josh Achiam, Vedant Misra, Evan Morikawa, Alec Radford, Matthew Knight, Miles Brundage, Mira Murati, Katie Mayer, Peter Welinder, Bob McGrew, Dario Amodei, Sam McCandlish, Tyy Sutskever, and Wojeiech Zaremba. Evaluating large language models trained on code. arXiv preprint arXiv:2107.0332 033374, 2021.
Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Mark Chen, Heewoo Jun, Lukasz Kaiser, Matthias Plappert, Jerry Tworek, Jacob Hilton, Retichiro Nakano, Christopher Hesse, and John Schulman. Training verifiers to solve math word problems. Xi preprint arXiv:21 10. 14168, 2021.
Yu Du, Fangyun Wei, and Hongyang Zhang. Tool: Self-reflective, hicrarchical agents for largo-scale APT calls. In Proceedings of the 41st International Conference on Machine Leurning, volume 235 of Proceedings of Machine Learning Research, pp.
PMLR, 2024. URL https::/proceeddnggs htt.pgsssmm..rer.ss///s.
2335//u24h.B855 html
Luyu Gao, Aman Madaan, Shuyan Zhou, Uri Alon, Pengfei Liu, Yiming Yang, Jamic Callan, and Graham Neubig. Pal: Prddra language models. In International Conference on Machine Learning, pp. 10764-10799. PMLR, 2023. URL htttps://proceedingss mlr wwtpppeseee///ve///222 2aw.0///gga22....o html
15

---

Published in Transactions on Machine Learning Research (04/2026)
Chuan Guo, Geoff Pleiss, Yu Sun, and Kilian Q Weinberger. On calibration of modern neural networks. In Proceedings of the 94th International Conference on Machine Learning, pp. 1321-1330. PMLR, 2017.
Dan Hendryeks, Collin Burns, Saurabh Kadavath, Akul Arora, Steven Basart, Eric Tang, Dawn Song, and Jacob Steinhardt. Measuring mathematical problem solving with the MATH dataset. In Proceedings of the Neural Information Processing Systems Track on Datasets and Benchmarks, 2021.
Yikun Jiang, Huanyu Wang, Lei Xie, Hanbin Zhao, Chao Zhang, Hui Qian, and John C.S. Lui. D-LLM: A token adaptive computing resource allocation strategy for large language models. In Advances in Neural Information Processing Systems, 2024. URL https://arxiv: org/ aba/2405 15263
Julia Kreutzer, Shahram Khadivi, Evgeny Malusov, and Stefan Riezler. Can neural machine translation be improved with user feedback? arXiv preprint arXiv:1804.00958, 2018.
Zheng Li, Qingxiu Dong, Jingyuan Ma, Kai Jia, Di Zhang, and Zhifang Sui. Selfbudgeter: Adaptive token allocation for efficient Ilm reasoning. arxiv preprint arXiv:2505.1127, 2025. URL https://arxiv.org
Aman Madaan, Niket Tandon, Prakhar Gupla, Skyler Hallinan, Luyu Gao, Sarah Wiegreffe, Uri Alon, Nouha Dziri, Shrimai Prabhumoye, Yiming Yang, Shyam Gupta, Bodhisattwa Prasad Majumder, Katherine Hermann, Scan Welleck, Amir Yazdanbakhsh, and Peter Clark. Self-refine: Iterative refinement with self-feedback. In Advances in Neural Information Processing Systems, volume 36, 2023.
Lutz Prechelt. Early stopping-but when? In Newral Networks: Tricks of the trade, pp. 59. Springer, 1998.
Timo Schick, Jane Dwivedi-Yu, Yu, Roberto Dessì, Roberta Raileamu, Maria Lomeli, Lake Zettlemoyer, Nicola Can- cedda, and Thomas Scialom. Toolformer: Language models can teach themselves to use tools. In Advances in Neural Information Processing Systems, volume 36, 2023. URL https::/ neurips cc/ -atrro---tttttttttee-e-ee--- Conf---oofeeeeeeee html
paper http://paeeeo////aa////////22223
Noah Shinn, Federico Cassano, Anil Gopinath, Karthik Narasimhan, and Shunyu Yao. Reflexion: Language agents with verbal reinforcement learning. In Advances in Neural Information Processing Systems, volume 36, 2023. URL httpp::/pproceedings www.diiinnnn...ii....... nwwries wwwripsscc/paperr wwtpppperfilleepppeeeeeeeeeeeeee E3220775550011333001888888000000
Ye Tian, Baolin Peng, Linfeng Song, Lifeng Jin, Dian Yu, Lei Han, Haitao Mi, and Dong Yu. Toward celf-improvement of 1ims via imagination, searching, and criticizing. In Advances in Neural Information Processing Systems, 2024. URL httt::://t///attt org/ abs/2404. 12253.
Xuezhi Wang, Jason Wei, Dale Schuurmans, Quoe V. Le, Ed H. Chi, Sharan Narang, Aakanksha Chowdhery, and Denny Zhou. Self-consistency improves chain of thought reasoning in language models. In The Eleventh International Conference on Learning Representations, 2023. URL httpss//openreviert net:/forum ? 1PLINIMMrW
Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Brian Ichter, Fei Xia, Fd H. Chi, Quoc V. Le, and Denny Zhou. Chain-of-thought prompting elicits reasoning in large language models. In Advances in Newral Information Processing Systems, volume 35, pp. 248377 2022. URL http:tt/pprcceeeninngg neurips pdf
files/
Zhilin Yang, Peng Qi, Saizheng Zhang, Yoshua Bengio, William Cohen, Ruslan Salakhurdinov, and Christo- pher D Manning, Hotpotqa: A dataset for diverse, explainable multi-hop question answering. In Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, pp. 2369 20000-23000000 2018.
Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Thomas Griffiths, Yuan Cao, and Karthik Narasimhan. Tree of thoughts: Deliberate problem solving with large language models. In Advances Neural Information Processing Systems, volume 36, 2023a. URL https: pctpp:///// nww.sss. http:ppppprriilsppppprp..e
16

---

Published in Transactions on Machine Learning Research (04/2026)
Shunyu Yao, Jeffrey Zhao, Dian Yu, Nan Du, Izhak Shafran, Karthik Narasimhan, and Yuan Cao. React: Syn- ergizing reasoning and acting in language models. In International Conference on Learning Representations, 2023b. URL htttp:://pperrevieeee/ -ittr/rre.nt///oommdddi.... vluYUL-X
Bianca Zadrozny and Charles Elkan. Obtaining calibrated probability estimates from decision trees and naive bayesian classificrs. In Proceedings of the 18th International Conference on Machine Learning, pp. 609-616.
Morgan Kaufmann, 2001.
Andy Zhou, Kai Yan, Michal Hoypenttkh-Rothman Haohan Wang, and Yu-Xiong Wang. Language agent tree search unifies reasoning, acting, and planning in language models. In Proceedings of the 4 41st International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pp. 62138 62160. PMLR, 2024. URL https://proceeding mlr, wwt..r..reeeeeee/eeeeeee/ wttss//hoo2rr..r. hhthl24..html
Denny Zhou, Nathanael Schärli, Le Hou, Jason Wei, Nathan Scales, Xuezhi Wang, Dale Schuurmans, Claire Cui, Olivier Bousquet, Quoc V. Le, and Ed H. Chi. Least-to-most prompting enables complex reasoning in large language models. In The Elevendh International Conference on Learning Representations, 2023. URL
https://openrevieww het.:foorurrddww2777999tt
Bowen Zuo and Yinglum Zhu. Strategic scaling of test-time compute: A bandit learning approach. arXiv preprint ar Xi0: 1 12721, 2025. URL, https: ttttps://arxiv http//axxv..og/abbbaa./a oww.oogg////oooooooooo...o... hwtgg/bbb/2500.. 12721
A Hyperparameter Details
Table 10 lists all threshold and hyperparameter values used in AVA, along with default values, tuning methodology, and pointers to the relevant sections. The sensitivity AVA's performance to threshold perturbations is analyzed in Table 11
The primary recommendation for practitioners adapting AVA to new domains or models is: (1) recalibrate isotonic regression representative validation data from the target domain, and (2) run coarse grid search over the confidenco-gap thresholds in Algorithm | The sensitivity analysis in Table 11 suggests that moderate perturbations to threshold values have limited impact on overall accuracy, so a coarse sweep typically suffices.
B Framework Architecture
Figure 2 provides the full architectural diagram of the AVA framework, illustrating the three-stage iterative loop described Section 3.1
C Supplementary Results
D MATH Benchmark Evaluation Details
MATH answers undergo multi-stage equivalence check. We extract the model's answer using cascade of patterns: \boxed(... if present, otherwise text following "Final Answer:" or "Answer:", otherwise the last numeric or symbolic token. We then normalize LaTeX by stripping \left and \right, unifying Adfrac, Atfrac, and Afrac, removing \text(( wrappers, and balancing perentheses. Equivalence checked first by direct string equality after normalization, then by numoric comparison with tolcrance 10-6, and finally by SymPy symbolic equivalence via parse_latex and simplify. This pipeline accommodates the formatting variation common in MATH responses, recognizing for example (dfrac(14){33), \frac(14)(33, and 14/3 equivalent.
The MATH evaluation uses GPT-4o (00--40-204--1120) at temperature 0.7 with max_ max_completain 22440 We sample 50 problems uniformly across difficulty levels 1 through from the MATH test set and apply the same sample to every method. The standard error at p 0.4 and 50 is approximately seven percentage points; differences within this margin should be read inconclusive.
17

---

Published in Transactions on Machine Learning Research (04/2026)
Table 10: Complete hyperparameter listing for AVA.
Parameter
Default
Tuning'
Reference
Controller: Sumpling (Algorithon
High conf-gap threshold (k=10)
0.3
Grid
Sampling block
Medium conf-gap threshold (k=5)
0.1
Grid
Sampling black
Budget threshold (k=10)
0.3
Grid
Sampling block
Controller: Search (Algoritim Deep search gap threshold Deep search budget threshold Medium search gap threshold
Grid
Search block
0.5
Grid
Search block
0.2
Grid
Search block
Max search depth dmax Vol depth decay
Fixed
Sec. 3.2
0.2
Fixed
Eq.
Controller: Verification (Algorithm Full cascade gap threshold
0.5
Grid
Verification block
Medium verifier gap threshold
Grid
Verification block
Lightweight verifier gap threshold
0.05
Grid
Verification block
Low-confidence override (e <)
0.3
Grid
Verification
Controlle:: Tool Calls (Algorition
Confidence threshold
0.4
Grid
Tool call block
Budget threshold Complexity threshold
0.4
Grid
Tool call block
0.6
Fixed
Tool call block
Uncertainty Estimation (Section
3.9
Entropy normalization TH
Validation Grid
Sec.
3.2
Weights (wH, wg, wy, wrr
(0.3, 0.4, 0.2, 0.1)
Eq.
Verification Cascade (Section 3.4.3
Per-level thresholds (71. 72.72.13
(0.6, 0.8, 0.95)
Grid Calibration
Sec.
3.4.2
Early-cxit high Thigh
0.95
Sec.
3.4.
Early-exit low Now Level costs (e1, 63)
0.3
Calibration
Sec.
3.4.
(0.1x, 1.0x, 5.0x)
Fixed
Sec.
3.4.2
Calibration
Method
Isotonic (PAVA)
Fixed Fixed
Sec. Sec.
3.2
Validation fraction
10%
Cost-Benefit Prontier (Section
3.3.50
Initial ag
0.01
Pilot
Eq.
Initial Bu
0.5
Pilot
Eq.
EMA decay 1)
0.1
Fixed
Sec.
3.3.3
Marginal gain floor
0.001
Fixed
Soc.
3.3.3
Clobal
Target reliability Ftarget
0.9
Fixed
Sec.
3.3
Random seed (Python, NumPy)
Fixed
Sec.
Model temperature
0.7
Fixed
Sec.
Max tokens per generation
512
Fixed
Sec.
TGrid = grid search on validation split; Validation selection on validation data; Calibration = derived from calibration analysis; Pilot pilot run on 100 examples; Fixed = domain knowledge.
Table 11: Sensitivity of AVA controller to sampling thresholds. Default configuration (bold) sits near the middle of the cost range. Accuracy varies by less than 1% across all configurations tested. Rows at gap thresholds 0.30 and 0.35 yield identical allocations because the empirical confidence-gae distribution on GSMSK has negligible mass that interval.
Gap Thresh
Budget Thresh
Est. Cost
10-Sample Frac
0.15
0.30
0.57
0.25
0.30
773
0.46
0.30
0.30
716
0.34
0.35
0.30
716
0.34
0.40
0.30
639
0.23
0.45
0.40
630
0.17
18

---

Published in Transactions on Machine Learning Research (04/2026)
Input Prompt Budgel
Stage 1: Uneer-
lainly Estimation
Token Entropy
Self- Self-Cousien Coll-Counsttnccy
Verifler Scores
Trajectory Features
Calibration (Isor tonic / Platt)
Targel Reached?
Stage Adap- tive Allocation
Budget-Aware Controller
Budget
Veriflcasion (0..3]
Sampling (1..40)
Stage Exeen- tion & Update
Exccute Actions
Update State
Output Confidence
Figure 2: AVA Architecture. Iterative decision process with (1) uncertainty estimation, (2) adaplive allocation, and (3) execution & update. Arrows indicate control flow, while dashed lines denote iterative ro-ovaluation until confidence e 2 Ftarget or budget is exhausted.
19

---

Published in Transactions on Machine Learning Research (04/2026)
Sensitivity of AVA to Controller Thresholds (GSM8K)
Default
(0.3, 0.3)
Accuracy varies +1%
82.4
82.2
Accuracy
82.0
Confidence Gap Threeshld
Gap
81.8
Gap thresh 0.2
Gap
330% cost
Gap thresh 0.3
Gap
Gap thresh 0.4
Gap thresh 0.45
Default config
81.4
600
650
700
750
800
850
Estimated Cost (tokens)
Figure 3: Sensitivity of AVA controller thresholds across all 35 grid-searched configurations on GSMSK. Each point corresponds to one (Ta, TB) sctting; the default configuration highlighted. Cost varies substantially across settings while accuracy remains in narrow band.
Table 12: Stress test under degraded verifier quality. Noise rate controls verdict flips and score shrinkage toward 0.5.
GSM8K 800
HotpotQA @ 1000
AVA
Always-Verit Verify
AVA
Always-Verlfy
82.1%
81.7%
68.3%
64.2%
0.1
81.6%
81.1%
67.1%
62.9%
0.2
80.9%
80.3%
65.8%
61.2%
0.3
79.8%
79.0%
63.9%
59.4%
Table 13: Verification cascade efficiency. Most examples exit early at lightweight verification levels, achieving significant cost savings compared to uniform full verification.
Dataset
Level Exit
Level Exit Level 3 Full Cost Savings
GSMSK
72%
21%
7%
64%
HotpotQA
65%
23%
12%
58%
HumanEval
68%
20%
12%
61%
Average
68%
22%
10%
62%
20


Reviews:
[{"review_id": "NtAHxMDAuY", "reviewer": "Reviewer_2VfJ", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper introduces Anytime Verified Agents (AVA), a framework that adaptively allocates test-time compute (sampling, search, verification, tool use) to maximize reliability under user-specified budgets. A budget-aware controller makes iterative allocation decisions from a state including calibrated confidence and remaining budget, guided by value-of-information principles. Uncertainty is aggregated from multiple signals and calibrated via post-hoc isotonic regression, enabling early stopping and selective escalation through a verification cascade and VoI-guided search.", "claims_and_evidence_yn": "Yes", "claims_explanation": "The submission provides convincing evidence for its primary empirical claim: AVA effectively improves the cost–quality trade-off via adaptive compute allocation, as demonstrated on GSM8K, HotpotQA, and HumanEval. \n\nHowever, the evidence for its broader \"anytime\" robustness is less complete. The framework relies heavily on specific verifier setups and calibrated uncertainty, yet the evaluation lacks sensitivity analyses regarding verifier quality or distribution shifts (where calibration typically degrades). Thus, while the gains are well-supported in the reported settings, the system's stability under varying component quality remains to be fully established.", "audience_yn": "Yes", "audience_explanation": "The paper will interest readers working on LLM inference, evaluation, reliability, and ML systems. Its budget-aware framework for adaptive test-time compute allocation (sampling/search/verification/tool use) addresses a practical deployment problem—improving reliability under constrained cost—and provides actionable design ideas (calibration, verification cascades, early stopping) relevant to both methodology and systems communities.", "requested_changes": "Critical:\n1. The evaluation primarily compares AVA to static allocation baselines (fixed-depth search, fixed-N self-consistency, always-verify). To justify the added complexity of the MDP-style controller and VoI components, the paper should include comparisons to simpler adaptive baselines, e.g., a confidence-threshold early-exit policy or a lightweight adaptive sampling rule, which are conceptually close to prior “confidence-based halting/early stopping” ideas discussed in related work. If these heuristics achieve similar savings, the necessity of AVA’s heavier machinery would be less clear.\n\nStrengthening：\n1. AVA relies on calibrated uncertainty and verifier reliability—both can fail under domain shift or verifier noise. The paper should add OOD transfer evaluations and stress tests with degraded/noisy verifiers to demonstrate that the reported cost–quality frontier remains stable under imperfect conditions.", "broader_impact_concerns": "The work is primarily a systems/methodology contribution for improving reliability under cost constraints, so direct ethical risk is low.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "FAJSK611Ja", "reviewer": "Reviewer_xo3r", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper proposes Anytime Verified Agents (AVA), a framework for adaptive compute allocation in LLM agents that dynamically routes budget across sampling, search, verification, and tool use. AVA combines a calibrated uncertainty estimator, a multi-level verification cascade with early exits, and a value-of-information–guided search, coordinated by a budget-aware controller to either meet a target reliability at minimal cost or maximize reliability under a fixed budget. Experiments on GSM8K, HotpotQA, and HumanEval report 20–40% cost reductions at comparable reliability versus static baselines (fixed-depth search, fixed-sample self-consistency, and always-verify), with ablations suggesting each component contributes to efficiency.", "claims_and_evidence_yn": "No", "claims_explanation": "The claims made in the manuscript are mainly supported by a relevant experimental campaign, which empirically demonstrates the effectiveness of the method in three different tasks. \n\nHowever, the work suffers significantly from poor presentation. In particular, it lacks formality in variable definitions, naming conventions, and rigorousness. Specific issues include:\n- Several values are not formally defined, such as task complexity $t$, $d_{max}$, $n_{max}$, $f$ function in the isotonic regression, $v_l$ output from verifiers, $expand(n)$, $g(n)$, $c_{expand}$. Even if their meaning can be inferred, a higher degree of formality is expected.\n- Several thresholds are set to specific values without explanation or intuition (e.g., $\\tau_{entropy}$, adaptive branching thresholds, default $r_{target}=0.9$, $\\Delta C$).\n- Notation inconsistency: remaining budget oscillates between $B_r$ and $b_r$; confidence $c$ is later referred to as $confidence_{raw}$ (why do not use $c$ with a proper subscript?); the controller's state space is defined first without the history dimension $h_t$, and then later with it.\n- The if-then-else conditions for sampling, search, and verification are written such that both the first and second conditions could be true simultaneously. This should be presented as a formal system of equations or via pseudocode to avoid ambiguity.\n- In general, I advise against defining variables with full words; symbols with subscripts are preferable. Furthermore, specific threshold values are currently embedded in the methodology text. It would be better to use symbols in the equations and report the specific values and justifications later in the paper or in an appendix.\n\nFurthermore, these threshold values seem specific to these applications and the model used (GPT-5). The general adaptiveness of the method is not immediately evident (since it is based on rule-based strategies and heuristics), although the method is indeed interpretable.", "audience_yn": "Yes", "audience_explanation": "Yes, I think that the paper may be relevant for TMLR's audience since it tackle a actual problem related to the computational cost of LLMs.", "requested_changes": "- The paper needs to be more clear: I suggest to revise the paper organization. For example, you can leverage the 3 stages structure to present sections 3.2, 3.3, 3.4 and 3.5 as subsections under the relative stage. This would improve redability and clarity; I sometimes struggled to understand where I was in the flow of the algorithm. The scheme in Figure 1 is instead very helpful, you should exploit it more.\n- The paper requires more formality. Please refer to weaknesses highlighted before about threshold and undefined variables, and ensure the method is mathematically rigorous.\n- Please add the missing citation for PAVA.\n- Please make the paper self-contained. Some concepts are taken for granted. Since TMLR does not have strict page limits, you can expand on these (e.g., explicitly describe what a \"verifier\" is, provide a dedicated section describing baselines, explain what \"tool calls\" entail, and detail how the $r(B)$ function is decided).\n- How do you compute the uncertainty $u$ from current state? I think this is not fully explained.\n- Please explicitely report fixed random seeds for reproducibility.", "broader_impact_concerns": "The authors do not present a specific Broader Impact Statement. I do not see immediate critical ethical concerns requiring a halt to publication.", "additional_comments": "First, I would like to apologize for the delay in submitting this review. I hope that the detailed and candid feedback provided here compensates for the wait. In general, I believe the paper requires major revisions, particularly from a presentation perspective. It would benefit significantly from greater mathematical rigor and formality. I suggest dedicating time to refining these aspects and ensuring that the core concepts of the framework, which touches on many facets of LLM operations, are defined explicitly rather than given for granted.", "extra_scores": {}, "extra_text": {}}, {"review_id": "Xbf9MaHcGK", "reviewer": "Reviewer_X5NB", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper proposes a framework designed to dynamically allocate computational resources for LLM agents under a unified budget.", "claims_and_evidence_yn": "Yes", "claims_explanation": "The paper addresses a practical and significant problem: managing the trade-off between inference cost and reliability across multiple dimensions (search, sampling, verification) simultaneously.\n\nThe reported results demonstrate clear Pareto dominance over the chosen baselines.", "audience_yn": "Yes", "audience_explanation": "LLM agent is a popular research topic nowadays.", "requested_changes": "1. Robustness of Heuristics: How were the specific thresholds (e.g., for 10 samples) in the controller derived? Did you perform a sensitivity analysis? I would like to see a plot showing Cost vs. Accuracy as these thresholds are perturbed.\n\n2. Generalization of Calibration: The paper mentions that the calibration is performed per dataset. How does the system perform if the calibration mapping is transferred? For example, training the calibrator on GSM8K and testing on MATH (or a harder subset). Does the rule-based controller fail if the uncertainty estimates become uncalibrated?\n\n3. Please discuss the main difference of AVA with the following works. \n\n[1]. SelfBudgeter: Adaptive Token Allocation for Efficient LLM Reasoning \n[2]. Strategic Scaling of Test-Time Compute: A Bandit Learning Approach", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "hXkBO4hDOL", "reviewer": "Reviewer_uHXr", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper proposes a rule-based dynamic budget allocation scheme for test-time compute in LLMs. It relies on four aspects of uncertainty of the LLM prediction to distribute a user-specified overall budget to number of new samples generated, depth and branching factors for adaptive search, verifier effort (abstracted to four levels) and whether to call tools. While the both the confidence estimation and allocation rules are simplistic so far, it is undeniable that the concept holds tremendous potential for test-time compute efficiency and the experiments show that even this simple approach can meaningfully improve performance on low budgets.", "claims_and_evidence_yn": "Yes", "claims_explanation": "The evaluation shows that the proposed allocation scheme increases efficiency on the tested datasets and the additional results on ablating the different components and the verification efficiency support these findings. \n\nIn my opinion, the main points of criticism of the evaluation lie in the scale of the experiments (single model, benchmark selection). I hesitate to make my score dependent on these factors, however, since the experiments are certainly challenging to run. I also believe that the current scope already gives a strong signal on the performance of the allocation rules and especially the confidence estimation.\n\nThe other point would be code availability. I believe open code is important for open science and thus think the authors should release their experimental setup at the latest upon acceptance.", "audience_yn": "Yes", "audience_explanation": "Test-time compute optimization is incredibly relevant with the recent rise of methods relying on it. Thus I believe this paper is very timely.", "requested_changes": "- I appreciate Figure 1 as an overview and since it already takes up a full page, I would suggest increasing font size everywhere to improve its readability.\n- The discussion sections seems like a list of keywords at the moment, several of which would warrant at least one or two sentences of full discussion of their own. I think this should be improved.\n- Several Tables are not referenced in the text which hurts the readability of the results section overall, this should be corrected.\n- There is currently an empty \"Acknowledgements\" Section above the references. If you don't plan on using it upon publication, this should be removed.", "broader_impact_concerns": "No specifics.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)