Technical Summary: Inference-Time Budget Control for LLM Search Agents

1. Problem Formulation

The paper addresses the challenge of deploying Large Language Model (LLM) search agents under explicit, hard dual budgets: a limit on tool calls ($B_{tool}$) and a limit on output tokens ($B_{tok}$). While prior work has explored test-time scaling via repeated sampling or self-refinement, these approaches often treat compute as a token-only resource. For search agents, however, extra budget can lead to redundant retrieval, wasted branching, and brittle context growth if not managed explicitly.

The core problem is formulated as a two-stage inference-time control problem:

1. Search-Time Action Allocation: At each step, the agent must decide how to allocate the remaining dual budget among heterogeneous actions: retrieving evidence (SEARCH), decomposing the question (DECOMPOSE), or committing to an answer (ANSWER). These actions differ in cost and potential return, and the optimal choice depends on the current evidence state and remaining budget.
2. Answer-Time Finalization: After the search terminates, the agent must decide whether to keep the trajectory's base answer ($a_{base}$) or replace it with a refined candidate ($a_{ref}$). This decision must balance the potential gain in exactness against the risk of "intervention harm"—erasing correct bridge structures or altering comparative semantics through unnecessary rewriting.

The objective is to maximize the expected reward $E[R(\hat{a}, y)]$ subject to the dual budget constraints and a constraint on the expected harm from answer replacement ($E[L_{harm}] \leq \rho_{harm}$).

2. Methodology

The proposed method, VOI (Value-of-Information), is a training-free, two-stage controller built on top of a generic tree-search backbone (inspired by BAVT).

Stage 1: Search-Time Budget Allocation

The controller selects the next action by scoring feasible options using a Task-Level VOI score. This score is an operational estimate of the marginal task value per unit of budget, distinct from Shannon information gain or learned value models.

• Utility Construction: For each action $k$, a task-level utility $u_t(k)$ is computed as:
  $$u_t(k) = \hat{\Delta}_t(k) + \Psi_t(k) - \Pi_t(k; b_t)$$
  • $\hat{\Delta}_t(k)$: A critic-derived progress signal.
  • $\Psi_t(k)$: Structural signals (e.g., bridge structure, loop pressure, readiness).
  • $\Pi_t(k; b_t)$: A budget-dependent penalty term that increases for SEARCH and DECOMPOSE actions when the remaining budget is tight, acting as a proxy for the oracle shadow cost.
• Normalization and Guards: The utility is normalized by an action-specific budget scale to produce the VOI score $r_t(k)$. A deterministic guard operator $G_t$ then adjusts this score to enforce conservative behaviors (e.g., suppressing premature answers, enforcing minimum search for compositional questions).
• Selection: The action with the highest guarded executable score is selected and executed.

Stage 2: Answer-Time Finalization

Once search concludes, a selective, evidence-grounded finalizer evaluates whether to rewrite the answer.

• Gain-Risk Trade-off: The finalizer compares the base answer $a_{base}$ and a refined candidate $a_{ref}$ (constructed from the same trace). It intervenes only if the expected exactness gain outweighs the risk of damaging the answer.
• Safe Set ($S_{safe}$): Rewriting is restricted to low-risk scenarios, such as correcting yes/no polarity, binary choices, typed-slot mismatches, or completing supported factoids.
• Abstention: The system abstains from rewriting if the trajectory contains unresolved bridge structures, comparative semantics, or missing direct support, as aggressive rewriting in these cases often harms correctness.
• Zero-Overhead: This stage adds no new tool calls or LLM inference calls; it is a deterministic selection policy over existing candidates.

3. Key Contributions

1. Two-Stage Formulation: The paper formalizes budget-aware inference in LLM search agents as a coupled problem of search-time action allocation and risk-controlled answer finalization under hard dual budgets.
2. Task-Level VOI Control: It introduces a training-free scorer that ranks actions based on estimated marginal task value per unit budget, incorporating budget-dependent penalties and structural signals without learning a value model.
3. Risk-Controlled Finalization: It proposes a conservative answer selector that intervenes only for local answer-form errors, explicitly avoiding the destruction of correct multi-hop reasoning paths.
4. Empirical Validation: The method is evaluated across four multi-hop QA benchmarks (HotpotQA, 2WikiMultihopQA, MuSiQue, Bamboogle), three LLM backbones (Qwen3-32B, Qwen3.5-122B, GPT-5.4-Mini), and four budget levels under a strict, shared hard-budget audit.

4. Experimental Results

• Aggregate Gains: VOI yields positive aggregate gains over four audited baselines (BAVT, BATS, AFlow, Search-o1) across the tested settings. On Qwen3-32B, it achieves the best F1 in 7 of 16 dataset-budget cells and ties for best in 2 others, outperforming baselines in 14/16, 10/16, 16/16, and 15/16 cells respectively.
• Budget Sensitivity: The most significant improvements occur in low and lower-mid budget regimes, where careful action allocation is critical to avoid exhausting resources on low-yield actions.
• Component Ablation:
  • Search-Time Control: Removing the budget-dependent penalty term causes the largest performance drop, confirming that budget-aware action allocation is the primary driver of gains.
  • Finalization: Stage 2 (finalization) provides significant gains (up to 41.9% of total gain on MuSiQue) primarily when the search trajectory is adequate but contains local answer-form errors. It contributes less on datasets where errors are structural (e.g., MuSiQue).
• Efficiency: The VOI controller reduces mean inference time by 27.2% on average compared to BAVT, as it avoids low-value operations that would otherwise consume the budget.

5. Significance and Claims

The paper claims that inference-time budget control is essential for LLM search agents, governing both how budget is spent during search and how the final answer is committed.

• Non-Monotonic Scaling: The results demonstrate that larger budgets do not always yield better answers; without explicit control, increased budgets can lead to redundant search and noisier finalization.
• Boundary Conditions: The method's effectiveness is not uniform. It shows diminishing returns on stronger backbones (e.g., Qwen3.5-122B) and in high-budget regimes where baselines like BATS remain competitive.
• Safety and Deployability: By explicitly modeling the risk of answer replacement and enforcing hard budget audits, the approach makes agent behavior more predictable and inspectable, which is crucial for deployment in cost-constrained or latency-sensitive environments.

The authors emphasize that their method does not claim global optimality of the search tree but rather provides a local, decision-level control mechanism that significantly improves performance under strict resource constraints.