- 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
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:
| Method | EM | Input / output tokens | Paid searches | LLM calls | Wall-clock | Cost (USD / 1k q, p = $0.005) |
|---|---|---|---|---|---|---|
| ReAct | 19.2 | 20.7k / 0.7k | 5.2 | 6.2 | 29 s | 26.6 |
| Parallel sampling | 26.1 | 31.7k / 1.8k | 9.8 | 13.8 | 77 s | 50.0 |
| LATS + evidence cache | 17.1 | 72.6k / 4.0k | 6.1 | 41.2 | 100 s | 33.1 |
| Official BATS | 34.2 | 39.2k / 2.6k | 9.3 | 15.8 | 95 s | 48.2 |
| BAVT | 39.0 | 75.3k / 4.0k | 6.7 | 36.5 | 100 s | 36.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:
| Arm | Success rate · browser actions |
|---|---|
| BAVT | 22.0 · 11.2 |
| − Verification/refinement | 20.2 · 8.4 |
| Core search only | 21.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.
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:
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:
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.