acceptodds
Under review as a conference paper at ICLR 2027

Spend Less, Reason Better: Budget-Annealed Tree Search for LLM Agents that Spend Only on New Evidence

Abstract

Test-time scaling lets tool-augmented LLM agents trade compute for accuracy, but much of that compute is wasted: agents re-issue tool calls they have already made, follow dead-end trajectories, and exhaust their tool and token budgets before reaching an answer. Addressing this waste requires jointly allocating the remaining budget across intermediate reasoning states and reusing evidence across branches, rather than treating budget control and evidence handling as separate decisions. We propose the Budget-Aware Value Tree (BAVT), a training-free inference framework that organizes reasoning and tool use as a tree scored by a step-level critic from the same backbone, made budget-aware by two mechanisms. Budget-annealed selection sharpens the sampling distribution over candidate nodes by the inverse of the remaining budget ratio, so the agent explores broadly while resources are ample and concentrates on the most promising branch as they run out. Evidence reuse charges the budget only for new evidence: same-parent exact repeats are merged before execution, while other eligible store hits reuse cached evidence and are re-scored in their new branch context, and every saved call is returned to the budget controller. For a capped selection variant, we prove a conditional finite-budget guarantee for generating a terminal answer. Across four multi-hop QA benchmarks, two model families and three budget tiers, BAVT outperforms parallel sampling, ReAct, LATS and BATS at every budget, using fewer paid tool calls than parallel sampling. With a five-call budget, it surpasses baselines given a larger budget while using about one fifth as many paid tool calls as parallel sampling; instantiated for browser agents on WebArena-Lite, it leads all baselines at every action budget, and the ordering carries over to three closed-weight models on both tasks. Allocating a fixed budget adaptively is thus more effective for reliable agents than brute-force test-time scaling.

Primary area:
foundation or frontier models, including LLMs
Keywords:
LLM agents, test-time scaling, budget-aware inference, tool-augmented reasoning, inference-time compute, evidence reuse

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_GdDaOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes Budget-Aware Value Tree (BAVT), a training-free framework for tool-augmented LLM agents under limited tool and token budgets. It combines step-level value estimates, budget-dependent node selection, and evidence reuse across reasoning branches. The method shifts computation toward promising branches as resources decrease and avoids repeated retrieval through duplicate merging and caching. Experiments on multi-hop QA and browser tasks show improved performance under matched budgets, with substantial reductions in retrieval calls on QA.

Critical strengths

S1. The paper addresses a practical problem: allocating limited inference resources while avoiding repeated tool calls. The proposed framework connects these decisions through a clear, training-free design.

S2. The main QA evaluation is substantial, covering four full evaluation splits, two model families, three budget tiers, and multiple random seeds. BAVT achieves the highest mean accuracy across all six open-weight model-budget settings.

S3. Reporting actual retrieval calls and accuracy makes the efficiency benefits easy to assess. Evidence reuse substantially reduces retrieval calls while maintaining similar or slightly higher mean accuracy.

Critical weaknesses

W1. The additional benefit of coupling budget annealing with evidence reuse remains unclear. Table 2 omits a value-guided tree that retains reuse but removes annealing, and the main baselines are not equipped with the same evidence cache. These controls are needed to distinguish the contribution of the proposed combination from ordinary caching and value-guided search.

W2. The documented BATS implementation differs from the original method. Appendix B.1 describes fresh-context restarts and majority voting, whereas the original BATS preserves intermediate findings through persistent plans and summaries and uses a judge to select among verified answers. The paper does not clearly explain what information is retained after restarting or evaluate how changing the answer selector affects baseline performance.

W3. The efficiency evaluation lacks measured end-to-end costs. The paper reports retrieval calls and output-token limits, while Table 7 estimates costs using an assumed search price and input-to-output token ratio. Actual input and output token usage and latency are needed to establish whether the additional planning and critic calls still lead to lower overall inference cost.

Questions for authors

Q1. How does BAVT compare with LATS using the same evidence cache, and with a value-guided tree that retains reuse but removes budget annealing?

Q2. Does the BATS implementation retain the original persistent plan and intermediate-evidence summaries? How do the results change when its original answer-selection procedure is restored?

Q3. What are the measured input and output token usage and latency of each method, including all planning and critic calls?

Q4. In the browser experiments, how much of the improvement comes from budget annealing and evidence reuse, compared with the additional verification and answer-refinement procedures?

4 comments
AuthorsOpenReview ↗

Response to Reviewer GdDa (Part 1 of 2)

We thank the reviewer for the precise questions and for recognizing the practical problem, the scale of the question-answering evaluation and the reporting of retrieval calls. The responses below give LATS the same evidence cache and remove annealing from BAVT's tree (W1 & Q1), replace our BATS baseline with a port of the official implementation (W2 & Q2), report measured tokens, calls and latency (W3 & Q3), and separate the sources of the browser gain (Q4). All new question-answering experiments use the randomly sampled 100-question-per-dataset subset of Table 2, with every method re-run under the same implementation.

W1 & Q1: LATS with the same evidence cache, and reuse without annealing

LATS stays below BAVT, with or without the same evidence cache. LATS runs without and with BAVT's evidence cache. The tree with reuse and no annealing is BAVT's own controller and critic with value-proportional selection. The table reports EM (%) / paid searches per question:

ModelBLATSLATS + same evidence cacheSame tree + reuse, no annealingBAVT
GPT-OSS-20B518.2 / 4.811.8 / 3.733.1 / 3.935.0 / 3.9
GPT-OSS-20B1020.8 / 9.317.1 / 6.138.2 / 6.939.0 / 6.7
GPT-OSS-20B2024.2 / 17.322.9 / 9.640.6 / 11.842.2 / 11.3
Qwen3-30B-A3B528.0 / 4.79.8 / 2.641.6 / 2.742.4 / 2.6
Qwen3-30B-A3B1029.1 / 9.027.7 / 3.142.0 / 3.643.8 / 3.5
Qwen3-30B-A3B2034.2 / 13.531.0 / 3.644.3 / 4.944.2 / 4.5

The cache does not help LATS: it cuts LATS's paid searches by 24–74%, LATS spends the saved searches on further expansion, and it exhausts its token budget. With a final answer granted outside the budget, LATS with the cache reaches 18.6–32.1 EM, still 12–18 EM below BAVT. BAVT's tree with reuse and no annealing is 10–18 EM above LATS, so the lead comes from BAVT's step-level value tree, whose critic scores each step and decides whether its node is widened, deepened or answered. The tree with reuse and no annealing is 0.8–1.8 EM below BAVT at B = 10 and 1.6 EM below it on GPT-OSS-20B at B = 20.

W2 & Q2: Fidelity of the BATS baseline

Under equal budgets, BAVT achieves higher mean EM than the official BATS in five of six settings and uses fewer paid searches in all six. BATS was accepted to COLM 2026, and its official code (google-research/budget-aware-agent) was released in August 2026; our earlier baseline followed the paper's description. We have now ported the official code: the port follows its control flow and prompts, with the local Wikipedia search and each model's default temperature used by every other method. BATS runs under the budget rule of every other method: 512 output tokens per call, with every call charged to the token budget. The table reports EM (%) / paid searches per question, and BAVT − BATS in EM:

ModelBOfficial BATSBAVTBAVT − BATS
GPT-OSS-20B535.8 / 4.635.0 / 3.9−0.8
GPT-OSS-20B1034.2 / 9.339.0 / 6.7+4.8
GPT-OSS-20B2030.6 / 18.242.2 / 11.3+11.6
Qwen3-30B-A3B535.9 / 4.442.4 / 2.6+6.5
Qwen3-30B-A3B1035.8 / 8.543.8 / 3.5+8.1
Qwen3-30B-A3B2034.4 / 16.144.2 / 4.5+9.8

BAVT improves mean EM over the official BATS by 4.8–11.6 points in five of six settings and uses fewer paid searches in all six.

AuthorsOpenReview ↗

Response to Reviewer GdDa (Part 2 of 2)

W3 & Q3: Measured tokens and latency

BAVT spends more tokens, calls and wall-clock than the baselines and pays fewer searches. We measured every LLM call of every role (planner, actor, critic, judge), with wall-clock taken on shared serving infrastructure. Token cost uses the model's list prices, and total cost adds paid searches × p, the price per search. The table reports per-question quantities on GPT-OSS-20B at B = 10 and the cost in dollars per 1,000 questions:

MethodEMInput / output tokensPaid searchesLLM callsWall-clockCost (USD / 1k q, p = $0.005)
ReAct19.220.7k / 0.7k5.26.229 s26.6
Parallel sampling26.131.7k / 1.8k9.813.877 s50.0
LATS + evidence cache17.172.6k / 4.0k6.141.2100 s33.1
Official BATS34.239.2k / 2.6k9.315.895 s48.2
BAVT39.075.3k / 4.0k6.736.5100 s36.4

The critic accounts for 28% of BAVT's tokens. BAVT is cheaper end-to-end than parallel sampling and BATS once a search costs more than about USD 0.001, and commercial search APIs typically charge USD 0.005–0.01 per call. In the camera-ready version, the measured numbers will replace the estimates in Table 7 and Appendix E.4.

Q4: Browser improvement: annealing and reuse versus verification and refinement

The browser gain comes from the core value-guided search. Annealing, reuse, and verification and refinement leave success unchanged. In a factorial over the 129 WebArena-Lite tasks, both models and three budgets, annealing and reuse change success by −0.3 and −0.1 points on average. We then removed the verification and refinement procedures alone, and together with greedy initialization and evidence-grounded answer selection ("core search only", which keeps value-scored action proposals with adaptive breadth). The table reports success rate (%) · browser actions per task on GPT-OSS-20B at B = 20:

ArmSuccess rate · browser actions
BAVT22.0 · 11.2
− Verification/refinement20.2 · 8.4
Core search only21.7 · 6.8

The core search matches full BAVT with 39% fewer browser actions.

Thank you for the detailed response and additional experiments. The response address most of my concerns. I will raise my rating to 3.

We thank the reviewer for the careful review, constructive feedback, and recommendation for acceptance. We are glad that our response addressed the concerns raised.

Reviewer_FUJpOpenReview ↗
Rating
2
Confidence
3(+1)
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper proposes Budget-Aware Value Tree (BAVT), a training-free framework for tool-using LLM agents operating under tool-call and token budgets. It combines a reasoning tree with a same-model critic that scores incremental progress, budget-dependent node selection, and evidence reuse.

Its main contributions are:

  • Budget-annealed selection: nodes are sampled proportionally to V(n)^{1/r}, where r is the remaining budget ratio, concentrating search on higher-valued states as resources decline.
  • Evidence reuse integrated with search: repeated proposals are merged or served from cached evidence, with reused observations re-scored in their new context and saved calls retained in the budget.
  • Conditional theoretical analysis: a capped variant can generate a terminal answer with high probability given sufficient finite resources and stated assumptions; this does not guarantee correctness or directly cover the experimental variant.

The “widen” and “deepen” mechanisms are implemented as value-conditioned prompting instructions, rather than distinct structural tree operations.

Validation covers four multi-hop QA benchmarks, two open-weight models, three budget tiers, and browser tasks on 129 WebArena-Lite tasks, with additional API-model experiments. BAVT achieves the highest mean QA accuracy across the open-model settings; its five-call configuration exceeds external baselines given twenty calls. Component ablations associate the largest accuracy improvement with value scoring, additional gains with budget annealing, and substantial call savings with reuse. Browser and API-model results provide broader support.

Critical strengths
  • Strong accuracy–tool-use trade-off under constrained budgets. On the full evaluation splits of four QA benchmarks, BAVT achieves the highest mean accuracy across both open-weight models and all three budget tiers. With GPT-OSS-20B, its five-call configuration reaches 35.0 EM using 4.1 calls on average, exceeding parallel sampling at a twenty-call budget (34.2 EM, 19.8 calls). This is consequential because it demonstrates a practical improvement in how agents allocate scarce resources, rather than gains obtained simply by increasing inference expenditure.
  • A coherent mechanism supported by informative ablations. The framework couples progress-based state evaluation, budget-dependent selection, and evidence reuse. The component study shows that value scoring raises average EM from 26.8 to 35.7, budget annealing increases it to 38.8, and reuse reduces average paid calls from 9.00 to 6.34 while maintaining accuracy. Although these comparisons do not fully isolate component interactions, they provide meaningful evidence that the framework’s accuracy and efficiency gains arise from complementary design choices.
Critical weaknesses
  • The experiments do not sufficiently isolate the distinctive methodological contribution. The ablation adds components sequentially, but does not compare against a value-guided search with ordinary caching or separately test the value-conditioned widen/deepen prompts. Those prompts also do not implement distinct structural search operations in the disclosed pseudocode. Consequently, the results establish that the overall system works better, but leave unclear how much benefit comes specifically from coupling budget annealing with evidence reuse, rather than established value-guided search and caching techniques. This weakens the case for methodological novelty.
  • The efficiency evaluation does not establish the overall computational trade-off. Paid tool calls are reduced, but BAVT additionally requires planning, critic evaluations, and re-scoring cached observations. Although generated tokens count toward the budget, the paper does not report measured total token consumption, latency, or monetary cost across methods. Its cost analysis instead assumes a fixed search price and input/output token ratio. Since efficiency is central to the paper’s motivation, these omissions make it difficult to determine when the reported tool-call savings translate into practical end-to-end savings.
Questions for authors

Please refer to the Weaknesses.

4 comments
AuthorsOpenReview ↗

Response to Reviewer FUJp

We thank the reviewer for the clear summary and for recognizing the accuracy–tool-use trade-off and the informative ablations. The responses below separate BAVT's search from ordinary caching and from the widen and deepen instructions (W1), and report the measured end-to-end cost (W2). All new question-answering experiments use the randomly sampled 100-question-per-dataset subset of Table 2, with every method re-run under the same implementation.

W1: Isolating the methodological contribution

Established value-guided tree search stays below BAVT, with or without the same cache. We ran LATS, the established value-guided tree search, without and with BAVT's evidence cache, and BAVT's own tree with reuse and value-proportional selection in place of budget annealing. The table reports EM (%) / paid searches per question:

ModelBLATSLATS + same evidence cacheSame tree + reuse, no annealingBAVT
GPT-OSS-20B518.2 / 4.811.8 / 3.733.1 / 3.935.0 / 3.9
GPT-OSS-20B1020.8 / 9.317.1 / 6.138.2 / 6.939.0 / 6.7
GPT-OSS-20B2024.2 / 17.322.9 / 9.640.6 / 11.842.2 / 11.3
Qwen3-30B-A3B528.0 / 4.79.8 / 2.641.6 / 2.742.4 / 2.6
Qwen3-30B-A3B1029.1 / 9.027.7 / 3.142.0 / 3.643.8 / 3.5
Qwen3-30B-A3B2034.2 / 13.531.0 / 3.644.3 / 4.944.2 / 4.5

The cache does not help LATS: it cuts LATS's paid searches by 24–74%, LATS spends the saved searches on further expansion, and it exhausts its token budget. With a final answer granted outside the budget, LATS with the cache reaches 18.6–32.1 EM, still 12–18 EM below BAVT. BAVT's tree with reuse and no annealing is 10–18 EM above LATS, so the lead comes from BAVT's step-level value tree, whose critic scores each step and decides whether its node is widened, deepened or answered. Within BAVT's own tree, annealing and reuse are complementary: the tree with reuse and no annealing is 0.8–1.8 EM below BAVT at B = 10 and 1.6 EM below it on GPT-OSS-20B at B = 20.

Widen and deepen are value-conditioned actor instructions, and ablating them costs up to 2.7 EM. The structural operations of the tree are the expansion of the selected node and the merging of duplicate proposals. The revised Section 3.2.1 and Algorithm 1 (changes in blue) describe them this way. The table replaces the two instructions with one neutral instruction ("take the next step: call one tool or answer") or with none, and reports EM (%) at B = 10:

Actor instructionGPT-OSS-20BQwen3-30B-A3B
Widen / deepen (BAVT)39.043.8
One neutral instruction39.941.2
No instruction36.542.5

W2: Overall computational trade-off

BAVT trades tokens for paid searches and is cheaper end-to-end above about \$0.001 per search. We measured every LLM call of every role (actor, critic, planner, judge), with wall-clock taken on shared serving infrastructure. Token cost uses the model's list prices, and total cost adds paid searches × p, the price per search. BATS is a port of its official implementation, run with BAVT's limit of 512 output tokens per call. The table reports per-question quantities on GPT-OSS-20B at B = 10 and the cost in dollars per 1,000 questions:

MethodEMInput / output tokensPaid searchesLLM callsWall-clockCost (\ / 1k q, p = \0.005)
ReAct19.220.7k / 0.7k5.26.229 s26.6
Parallel sampling26.131.7k / 1.8k9.813.877 s50.0
LATS + evidence cache17.172.6k / 4.0k6.141.2100 s33.1
Official BATS34.239.2k / 2.6k9.315.895 s48.2
BAVT39.075.3k / 4.0k6.736.5100 s36.4

BAVT uses more tokens, LLM calls and wall-clock than parallel sampling and pays fewer searches. The break-even search price against parallel sampling and against BATS is at most \0.0007percall,andcommercialsearchAPIstypicallycharge0.0007 per call, and commercial search APIs typically charge \\0.005–0.01.

Thank you for the additional experiments and clarifications. The measured token usage, LLM calls, latency, and monetary costs substantially address my concern about the overall computational trade-off. Overall, I will raise my recommendation to Weak Accept.

We thank the reviewer for the careful review, constructive feedback, and recommendation for acceptance. We are glad that our response addressed the concerns raised.

Dear Reviewer FUJp,

Thank you again for your recommendation for acceptance and your support. When convenient, could you please also update the rating in the system to reflect your Weak Accept recommendation?

We appreciate your time and consideration!

Reviewer_rtfhOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes Budget-Aware Value Tree (BAVT), an inference-time search framework for tool-using LLM agents. It combines step-level value estimates from an LLM critic, a node-selection distribution whose exponent increases as the remaining tool/token budget decreases, and an evidence store that reuses equivalent tool observations across reasoning branches.

The authors evaluate BAVT on four multi-hop QA datasets, two open-weight models, three closed-weight models, and WebArena-Lite. The reported performance is consistently better than the evaluated ReAct, LATS, BATS, and parallel-sampling baselines. The main question is whether these results establish a sufficiently distinct algorithmic contribution beyond existing approaches to value-guided search, budget-aware inference, and caching.

The paper reports useful and reasonably extensive empirical results. I do not dispute that the full implementation performs well against the evaluated baselines, and the retrieval-call reductions are practically relevant.

My reservation is about what the experiments establish beyond this system-level result. The two central ideas, budget-dependent allocation and redundant-evidence avoidance, have substantial precedents. The paper's distinctive versions of these ideas are not compared against sufficiently strong, mechanism-matched alternatives. The main ablation also indicates that much of the accuracy improvement comes from the established technique of value-guided search.

I therefore lean Weak Reject. The work has practical merit, but the evidence does not yet convincingly establish a significant new algorithmic insight or an empirically validated interaction between its proposed components.

Critical strengths

The paper studies a relevant practical problem and reports substantial improvements under constrained tool-call budgets. In Table 1, GPT-OSS-20B achieves 35.0 EM with BAVT at a five-call budget, compared with 34.2 EM for parallel sampling at twenty calls. The authors also evaluate multiple model families and report paid tool-call consumption rather than accuracy alone.

I appreciate that the paper includes component ablations and is relatively careful about several limitations. In particular, Section 4.3 acknowledges that the small accuracy improvement from evidence reuse cannot be cleanly attributed to reuse alone, and Section 3.3 explicitly limits the theoretical result to terminal-answer generation.

Critical weaknesses
  1. The algorithmic novelty is limited, and the paper does not adequately distinguish the proposed mechanisms from closely related work.

The general approach of guiding agent tree search using LLM-generated value estimates is established by LATS (Zhou et al., ICML 2024). AB-MCTS (Inoue et al., NeurIPS 2025) already studies adaptive breadth/depth allocation in inference-time tree search. More directly, Budget-Aware Tool-Use Enables Effective Agent Scaling (Liu et al., COLM 2026) studies the allocation of limited tool budgets, including whether agents should continue exploring a promising direction or redirect their efforts. That work also evaluates the trade-off between answer quality and combined token/tool costs.

BAVT differs in using a particular budget-dependent node-selection distribution and a tree-wide evidence store that preserves separate reasoning continuations. These are reasonable design choices, but the manuscript does not convincingly establish their significance relative to simpler alternatives.

In particular, Equation (3), P(n) ∝ V(n)^(1/r_t), is equivalent to softmax selection over log V(n) with temperature r_t. The choice of remaining-budget ratio as the temperature is intuitive, but it is not clear why this schedule should be preferable to fixed-temperature selection, conventional annealing schedules, or budget-conditioned UCT. No such direct comparison is provided.

Similarly, avoiding repeated external calls through exact or semantic caching is established engineering practice. The potentially interesting contribution is retaining and re-scoring separate branches after reuse, but this specific choice is not adequately compared with conventional caching and state deduplication.

  1. The experiments do not sufficiently isolate the proposed contribution.

Table 2 is particularly revealing. Starting from the tree-only configuration at 26.8 EM, adding step-level values increases performance to 35.7 EM. Budget-annealed selection increases this to 38.8 EM, and evidence reuse increases it further to 39.4 EM.

Thus, the largest improvement comes from value-guided search, which is not the distinctive contribution of this paper. The 3.1-point improvement associated with budget annealing is potentially meaningful, but it is only measured against one value-only configuration, without testing alternative selection schedules. The subsequent 0.6-point increase associated with reuse is small relative to the reported seed variation.

Reuse does produce a more substantial reduction in paid calls (9.00 to 6.34 in Table 2), but that does not establish the claimed benefit of coupling reuse with budget-annealed search. Any cache that avoids charged calls will preserve the remaining budget. The specific additional value of BAVT's feedback between caching and node selection needs to be demonstrated.

A stronger study would compare identical search controllers with and without exact caching, semantic caching, branch-specific re-scoring, and parent retirement. A factorial ablation would also clarify whether annealing and reuse have a positive interaction rather than merely independent effects.

  1. The evidence supports retrieval-call efficiency more directly than overall inference efficiency.

A central empirical result is that BAVT obtains higher accuracy while using fewer paid retrieval calls. This is useful, but the reported results do not comprehensively account for the additional computation required for intermediate-state scoring, branch generation, and re-scoring reused observations.

Appendix E.4 does not resolve this concern. Its cost calculation assumes a search price of $0.005 per call and input-token volume ten times output-token volume, and reports estimated maximum costs based on budget limits. It does not present measured end-to-end costs for the evaluated methods.

This is an important omission for a paper motivated by economical test-time scaling, especially given that Liu et al. (2026) already explicitly consider joint token/tool cost accounting. The comparison would be more informative with observed input/output tokens, model invocations, latency, and accuracy under matched total inference-cost budgets.

  1. The proposed evidence-equivalence mechanism is not sufficiently validated.

Appendix E.2 treats retrieval queries as equivalent when their normalized forms match or their E5 embedding similarity exceeds 0.95, subject to a numeric-token guard.

This is a heuristic for predicting similar retrieval results, not a guarantee that two queries require interchangeable evidence. Queries can have high semantic similarity while differing in relations, negation, or important non-numeric constraints.

The paper does not report the accuracy of its equivalence decisions, a breakdown of exact versus semantic cache hits, or the frequency with which approximate reuse changes answer correctness. These measurements are especially relevant because the central premise is that repeated tool calls can be safely replaced by existing evidence.

  1. The browser experiments do not cleanly test the same algorithm.

Appendix G describes a browser implementation that first runs a greedy action chain, changes proposal breadth when progress stalls, and uses different verification procedures depending on the remaining budget. These are material algorithmic adaptations, not simply substitutions of browser actions for retrieval calls.

The WebArena-Lite results are therefore encouraging as a separate system evaluation, but they do not isolate how much of the improvement comes from BAVT's core selection and reuse mechanisms. Browser-specific ablations would be necessary to support the broader generalization claim.

  1. The theoretical result offers limited support for the empirical method.

Theorem 1 applies to a capped selection variant, whereas the experiments use the uncapped rule. It also assumes a preserved, reachable trajectory with uniformly positive progress probability, a bounded candidate pool, and bounded expansion costs.

Under these assumptions, the theorem establishes sufficiently high probability of eventually generating a terminal answer. It does not establish correctness, improved budget efficiency, or an advantage over other selection policies. I do not see it as a substantial theoretical justification for the proposed empirical method.

Questions for authors

What is the empirical advantage of the inverse-remaining-budget exponent over fixed-temperature, standard annealing, and budget-conditioned UCT when the critic and search framework are identical?

Can the authors isolate the gains from exact caching, semantic caching, branch-specific re-scoring, and duplicate-parent retirement?

Does coupling evidence reuse with budget annealing improve performance beyond using the same reuse mechanism with a conventional value-guided tree?

What are the actual end-to-end token usage, inference latency, and estimated dollar costs of BAVT relative to its baselines?

How often are semantic cache hits genuinely evidence-equivalent, and how often do they lead to incorrect downstream decisions?

Can the browser-specific modifications be ablated to demonstrate the contribution of the core BAVT mechanisms?

5 comments
AuthorsOpenReview ↗

Response to Reviewer rtfh (Part 1 of 3)

We thank the reviewer for the precise review and for recognizing the practical relevance of the problem and the evaluation across model families. The responses below compare BAVT with the closest prior methods (W1), test budget annealing against other selection rules (W2 & Q1), isolate reuse and its interaction with annealing (W3, Q2 & Q3), report measured cost (W4 & Q4), evaluate semantic cache hits (W5 & Q5), ablate the browser procedures (W6 & Q6), and state the scope of Theorem 1 (W7). All new question-answering experiments use the randomly sampled 100-question-per-dataset subset of Table 2, with every method re-run under the same implementation.

W1: Novelty relative to prior work

Existing value-guided tree search stays below BAVT under the same budgets. BAVT is a single value tree with three budget-aware components: a step-level critic whose score decides whether a node is widened, deepened or answered; selection that sharpens as the tool and token budgets deplete; and evidence reuse whose saved calls return to the budget. LATS selects nodes by visit-count UCT, AB-MCTS adapts breadth against depth, and BATS (Liu et al., COLM 2026) reallocates effort across sequential fresh-context attempts; the revised Section 2 and Appendix A (changes in blue) state this contrast and cite BATS at COLM 2026. The official BATS code (google-research/budget-aware-agent) was released in August 2026, after our BATS baseline had been implemented from the paper's description. We now run BATS from the official code, and LATS without and with BAVT's evidence store, under the same search tool, per-call output limit and budget rule as BAVT. The table reports EM (%) / paid searches per question, and BAVT − BATS in EM:

ModelBLATSLATS + same evidence storeOfficial BATSBAVTBAVT − BATS
GPT-OSS-20B518.2 / 4.811.8 / 3.735.8 / 4.635.0 / 3.9−0.8
GPT-OSS-20B1020.8 / 9.317.1 / 6.134.2 / 9.339.0 / 6.7+4.8
GPT-OSS-20B2024.2 / 17.322.9 / 9.630.6 / 18.242.2 / 11.3+11.6
Qwen3-30B-A3B528.0 / 4.79.8 / 2.635.9 / 4.442.4 / 2.6+6.5
Qwen3-30B-A3B1029.1 / 9.027.7 / 3.135.8 / 8.543.8 / 3.5+8.1
Qwen3-30B-A3B2034.2 / 13.531.0 / 3.634.4 / 16.144.2 / 4.5+9.8

The evidence store does not close the gap: LATS spends the saved searches on further expansion and exhausts its token budget, and with a final answer granted outside the budget it is still 12–18 EM below BAVT. Against BATS, BAVT leads by 4.8–11.6 EM in five of six settings, is level on GPT-OSS-20B at B = 5, and pays fewer searches in all six. In the camera-ready version, we will run this comparison on the full evaluation sets of Table 1, replace the BATS rows with the official implementation, and update BAVT's results.

W2 & Q1: Budget annealing versus other selection rules

Every alternative selection rule is within 2 EM of budget annealing. Budget annealing has no parameter to tune. Equation (3) is softmax selection over log V(n) with temperature r_t, the remaining budget ratio; the revised Section 3.2.2 states it in this form. The table changes only the selection rule, with reuse off, and reports EM (%) on GPT-OSS-20B at B = 10:

Selection ruleEM
Fixed α = 1 (sample ∝ value)35.9
Fixed α = 236.7
Fixed α = 437.1
Step annealing α = 1 + t/10 (budget-agnostic)37.6
Budget annealing α = 1/r_t (BAVT)37.9

Budget annealing gives the highest EM of the five rules.

AuthorsOpenReview ↗

Response to Reviewer rtfh (Part 2 of 3)

W3, Q2 & Q3: Isolating reuse and its interaction with annealing

Reuse saves paid searches, and annealing raises accuracy. Their combination is the best cell at every budget. The factorial uses the same controller and critic, with selection either fixed (α = 1) or budget-annealed and reuse either off or on. The table reports EM (%) / paid searches per question on GPT-OSS-20B:

BFixed α, no reuseAnnealed, no reuseFixed α + reuseAnnealed + reuse (BAVT)
532.2 / 4.8333.8 / 4.7133.1 / 3.9035.0 / 3.91
1035.9 / 9.5637.9 / 9.2538.2 / 6.9439.0 / 6.73
2040.0 / 18.8041.1 / 17.8040.6 / 11.7842.2 / 11.33

Annealing allocates the budget across branches, and reuse returns the budget that redundant searches would consume, cutting paid searches by 17–37%. The revised introduction describes the two mechanisms by these roles. The column "Fixed α + reuse" is the conventional value-guided tree with the same reuse requested in Q3; at B = 10, BAVT is ahead of it by 0.8 EM.

Within reuse (Q2), semantic matches carry the effect. The table compares no reuse, exact matches only, and exact plus semantic matches on GPT-OSS-20B at B = 10, reporting EM (%) / paid searches per question and hits as shares of search requests:

ReuseEM / paidexact hitssemantic hits
None37.9 / 9.25——
Exact only36.7 / 8.744.2%—
Exact + semantic (BAVT)39.0 / 6.733.6%33.2%

Exact repeats are rare, and the semantic layer cuts paid searches by a further 23% relative to exact-only reuse.

Branch re-scoring and parent retirement both help. Without retirement, a parent whose proposals keep duplicating existing nodes stays on the frontier; without re-scoring, a cache hit copies the value first assigned to the cached result. The table reports EM (%) and search requests per question on GPT-OSS-20B at B = 10:

VariantEMrequests
BAVT39.012.9
Without parent retirement38.814.9
Without branch re-scoring37.814.2

Retirement bounds duplicate proposals, which raise search requests from 12.9 to 14.9 without it.

W4 & Q4: Measured end-to-end cost

**BAVT trades tokens for paid searches and is cheaper end-to-end above about \0.001persearch.∗∗WemeasuredeveryLLMcallofeveryrole(actor,critic,planner,judge),withwall−clocktakenonsharedservinginfrastructure.Tokencostuseslistprices(0.001 per search.** We measured every LLM call of every role (actor, critic, planner, judge), with wall-clock taken on shared serving infrastructure. Token cost uses list prices (\\0.03 / \$0.14 per million input / output tokens), and total cost adds paid searches × p, the price per search. The table reports per-question quantities on GPT-OSS-20B at B = 10 and the cost in dollars per 1,000 questions:

MethodEMInput / output tokensPaid searchesLLM callsWall-clockCost (\ / 1k q, p = \0.005)
ReAct19.220.7k / 0.7k5.26.229 s26.6
Parallel sampling26.131.7k / 1.8k9.813.877 s50.0
LATS + evidence store17.172.6k / 4.0k6.141.2100 s33.1
Official BATS34.239.2k / 2.6k9.315.895 s48.2
BAVT39.075.3k / 4.0k6.736.5100 s36.4

Across the three budgets, BAVT uses 2.2–2.4× the tokens of parallel sampling and pays 20–42% fewer searches, with more LLM calls and a longer wall-clock. The break-even search price against parallel sampling and against BATS is at most \0.0007percall,andcommercialsearchAPIstypicallycharge0.0007 per call, and commercial search APIs typically charge \\0.005–0.01. In the camera-ready version, these measurements will replace the estimates in Appendix E.4, with the measured input:output token ratio (15–24:1) in place of the assumed 10:1.

AuthorsOpenReview ↗

Response to Reviewer rtfh (Part 3 of 3)

W5 & Q5: Are semantic cache hits evidence-equivalent?

An independent judge rates 90.5% of semantic hits evidence-equivalent and none as mismatched. We sampled 100 semantic hits, 20 per cosine bin over [0.95, 1.0]. The judge is Claude Opus 5.5, from a different model family than both evaluated models, and it does not see gold answers. It labels each hit SAFE (the cached evidence serves the new query equally well), PARTIAL (related but less relevant, not misleading) or UNSAFE (a different entity or relation):

Cosine[0.95, 0.96)[0.96, 0.97)[0.97, 0.98)[0.98, 0.99)[0.99, 1.00]Hit-weighted
SAFE16 / 2017 / 2018 / 2020 / 2020 / 2090.5%
PARTIAL432009.5%
UNSAFE000000%

All PARTIAL hits lie below cosine 0.98, so a threshold of τ = 0.98 removes them at the cost of more paid searches. Cached results also contain the gold answer as often as fresh retrievals: 31.3% against 31.6% over the 1.16 M semantic hits with a fresh retrieval for comparison.

W6 & Q6: Browser-specific procedures

The core value-guided search carries BAVT's browser gain. The browser agent is an environment-adaptive instantiation of BAVT. We removed each browser-specific procedure on the 129 WebArena-Lite tasks, with the same sites, start pages, observation channel and scoring in every arm. "Core search only" removes greedy initialization, verification/refinement and evidence-grounded answer selection together and keeps value-scored action proposals with adaptive breadth, which is ablated in its own row. The table reports success rate (%) · browser actions per task on GPT-OSS-20B at B = 20:

ArmSuccess rate · browser actions
BAVT22.0 · 11.2
− Greedy initialization20.9 · 10.2
− Adaptive breadth (fixed k = 2)21.4 · 11.1
− Verification/refinement20.2 · 8.4
− Evidence-grounded answer selection22.2 · 11.4
Core search only21.7 · 6.8

The core search matches full BAVT with 39% fewer browser actions, and no individual procedure changes success significantly.

W7: Scope of Theorem 1

Theorem 1 guarantees that the capped annealing rule returns an answer within a finite budget. Selection that sharpens as the budget depletes could starve the branch that is making progress. The theorem rules this out for the capped rule: every active node keeps a selection probability bounded below independently of the budget, so under the stated reachability and bounded-cost assumptions, finite tool and token budgets suffice to generate a terminal answer with probability at least 1 − ε. The scope is answer generation, as the reviewer notes and as Section 3.3 states, and the controlled comparisons above establish accuracy and cost.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.