Spend Less, Reason Better: Budget-Aware Value Tree Search for LLM Agents

• URL: http://arxiv.org/abs/2603.12634v1
• Date: Fri, 13 Mar 2026 04:10:27 GMT
• Title: Spend Less, Reason Better: Budget-Aware Value Tree Search for LLM Agents
• Abstract summary: Budget-Aware Value Tree (BAVT) is a training-free inference-time framework that models multi-hop reasoning as a dynamic search tree.<n>BAVT consistently outperforms parallel sampling baselines.
• Score: 40.18150559561834
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Test-time scaling has become a dominant paradigm for improving LLM agent reliability, yet current approaches treat compute as an abundant resource, allowing agents to exhaust token and tool budgets on redundant steps or dead-end trajectories. Existing budget-aware methods either require expensive fine-tuning or rely on coarse, trajectory-level heuristics that cannot intervene mid-execution. We propose the Budget-Aware Value Tree (BAVT), a training-free inference-time framework that models multi-hop reasoning as a dynamic search tree guided by step-level value estimation within a single LLM backbone. Another key innovation is a budget-conditioned node selection mechanism that uses the remaining resource ratio as a natural scaling exponent over node values, providing a principled, parameter-free transition from broad exploration to greedy exploitation as the budget depletes. To combat the well-known overconfidence of LLM self-evaluation, BAVT employs a residual value predictor that scores relative progress rather than absolute state quality, enabling reliable pruning of uninformative or redundant tool calls. We further provide a theoretical convergence guarantee, proving that BAVT reaches a terminal answer with probability at least $1-ε$ under an explicit finite budget bound. Extensive evaluations on four multi-hop QA benchmarks across two model families demonstrate that BAVT consistently outperforms parallel sampling baselines. Most notably, BAVT under strict low-budget constraints surpasses baseline performance at $4\times$ the resource allocation, establishing that intelligent budget management fundamentally outperforms brute-force compute scaling.

Related papers

• Exploit More, Explore Smarter for Budget-Constrained Agentic Search [6.894751260400948]
  Budget-constrained agentic search arises when an agent must refine candidates under a small evaluation budget.<n>We introduce ExTS, a tree-search policy that treats expansion itself as a value-of-information decision.
  arXiv  Detail & Related papers  (2026-08-24T21:38:05Z)
• TRACE: A Unified Rollout Budget Allocation Framework for Efficient Agentic Reinforcement Learning [52.67756371231985]
  Reinforcement learning with verifiable rewards (RLVR) is a promising approach for enhancing reasoning and agentic behavior in large language models.<n>We introduce Tree Rollout Allocation for Contrastive Exploration (TRACE), a unified rollout allocation framework.<n>Technically, TRACE allocates rollout budget to both prompt roots and intermediate prefixes that are most likely to yield mixed terminal rewards.
  arXiv  Detail & Related papers  (2026-06-09T17:16:03Z)
• Thinking Economically: A Hierarchical Framework for Adaptive-Complexity Reasoning in LLMs [36.73612668202756]
  HAB learns step-specific token budgeting signals from PPL-derived step comparisons.<n>Experiments on GSM8K and MATH500 show that HAB not only surpasses standard CoT in accuracy but also reduces token usage.
  arXiv  Detail & Related papers  (2026-05-31T11:20:00Z)
• How Many Iterations to Jailbreak? Dynamic Budget Allocation for Multi-Turn LLM Evaluation [22.523809021772802]
  Key events in large language models (LLMs) in multi-turn conversational settings often emerge only after repeated interactions.<n>Recent conformal survival frameworks construct reliable lower predictive bounds (LPBs) on the number of iterations to trigger the event of interest.<n>We introduce DAPRO, the first theoretically valid dynamic budget allocation framework for bounding the time-to-event in multi-turn interactions.
  arXiv  Detail & Related papers  (2026-05-07T17:25:15Z)
• $V_{0.5}$: Generalist Value Model as a Prior for Sparse RL Rollouts [81.48669089692189]
  Generalist Value Models (such as $V_0.5$) achieve pre-trained value estimation by explicitly encoding model capabilities in-context.<n>We propose $V_0.5$, which adaptively fuses the baseline predicted by such value model with the empirical mean derived from sparse rollouts.<n>$V_0.5$ significantly outperforms GRPO and DAPO, achieving faster convergence and over some 10% performance improvement.
  arXiv  Detail & Related papers  (2026-03-11T14:57:41Z)
• Scalable and Reliable State-Aware Inference of High-Impact N-k Contingencies [4.588028371034407]
  Exhaustive evaluation of all outage combinations using AC power-flow or ACOPF is infeasible in routine operation.<n>This paper proposes a scalable, state-aware contingency inference framework designed to directly generate high-impact $N!-!k$ outage scenarios.
  arXiv  Detail & Related papers  (2026-02-10T06:55:59Z)
• TreePS-RAG: Tree-based Process Supervision for Reinforcement Learning in Agentic RAG [71.06073770344732]
  Agentic retrieval-augmented generation (RAG) formulates question answering as a multi-step interaction between reasoning and information retrieval.<n>We present TreePS-RAG, an online, tree-based RL framework for agentic RAG that enables step-wise credit assignment while retaining outcome-only rewards.
  arXiv  Detail & Related papers  (2026-01-11T14:07:30Z)
• Enhanced-FQL($λ$), an Efficient and Interpretable RL with novel Fuzzy Eligibility Traces and Segmented Experience Replay [0.0]
  Enhanced-FQL($$) achieves superior sample efficiency and reduced variance compared to n-step fuzzy TD and fuzzyA($$) baselines.<n>The framework's inherent interpretability, combined with its computational efficiency and theoretical convergence guarantees, makes it suitable for safety-critical applications.
  arXiv  Detail & Related papers  (2026-01-07T20:59:18Z)
• BARD: budget-aware reasoning distillation [25.725960386304646]
  Long Chain-of-Thought (CoT) distillation effectively transfers reasoning capability to smaller language models.<n>We propose bftextBudget-Aware Reasoning Distillation (BARD), a novel framework that simultaneously distills reasoning capability and enables fine-grained control over the reasoning length.
  arXiv  Detail & Related papers  (2025-11-03T11:30:18Z)
• Computational Economics in Large Language Models: Exploring Model Behavior and Incentive Design under Resource Constraints [1.00707850217229]
  Large language models (LLMs) are limited by substantial computational cost.<n>We introduce a "computational economics" framework that treats an LLM as an internal economy of resource-constrained agents.<n>We show that when computation is scarce, standard LLMs reallocate attention toward high-value tokens while preserving accuracy.
  arXiv  Detail & Related papers  (2025-08-14T07:55:45Z)
• Steering LLM Thinking with Budget Guidance [48.65894557568655]
  Budget guidance is a method for steering the reasoning process of LLMs toward a target budget without requiring any fine-tuning.<n>Our approach introduces a lightweight predictor that models a Gamma distribution over the remaining thinking length.<n>This signal is then used to guide generation in a soft, token-level manner, ensuring that the overall reasoning trace adheres to the specified thinking budget.
  arXiv  Detail & Related papers  (2025-06-16T17:57:05Z)
• Trajectory Bellman Residual Minimization: A Simple Value-Based Method for LLM Reasoning [55.33984461046492]
  Policy-based methods currently dominate reinforcement learning pipelines for large language model (LLM) reasoning.<n>We introduce Trajectory Bellman Residual Minimization (TBRM), an algorithm that naturally adapts this idea to LLMs.<n>We prove convergence to the near-optimal KL-regularized policy from arbitrary off-policy via an improved change-of-trajectory-measure analysis.
  arXiv  Detail & Related papers  (2025-05-21T09:41:53Z)
• Self-Evaluation Guided Beam Search for Reasoning [61.523627290397556]
  We introduce a stepwise self-evaluation mechanism to guide and calibrate the reasoning process of Large Language Model (LLM) We propose a decoding algorithm integrating the self-evaluation guidance via beam search. Our approach surpasses the corresponding Codex-backboned baselines in few-shot accuracy by $6.34%$, $9.56%$, and $5.46%$ on the GSM8K, AQuA, and StrategyQA.
  arXiv  Detail & Related papers  (2023-05-01T02:37:59Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.