Inference-Time Budget Control for LLM Search Agents

• URL: http://arxiv.org/abs/2605.05701v1
• Date: Thu, 07 May 2026 05:45:58 GMT
• Title: Inference-Time Budget Control for LLM Search Agents
• Abstract summary: We study the problem in multi-hop question answering (QA) and formulate it as two-stage inference-time budget control.<n>At search time, our controller assigns each feasible action a task-level Value-of-Information (VOI) score.<n>After search, a selective evidence-grounded finalizer compares the trajectory answer with a refined candidate and rewrites only when the residual error appears to be a low-risk answer-form error.
• Score: 21.14983754890843
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: LLM search agents increasingly rely on tools at inference time, but their trajectories are often constrained by hard limits on both tool calls and generated tokens. Under such dual budgets, better answers require not only stronger models, but also explicit control over which search action should receive the next budget unit and when the accumulated evidence is sufficient to commit a final answer. We study this problem in multi-hop question answering (QA) and formulate it as two-stage inference-time budget control. At search time, our controller assigns each feasible action a task-level Value-of-Information (VOI) score, defined as an operational estimate of marginal task value per unit budget under the current search state and remaining dual budget, and uses this score to choose among retrieval, decomposition, and answer commitment. After search, a selective evidence-grounded finalizer compares the trajectory answer with a refined candidate and rewrites only when the residual error appears to be a low-risk answer-form error. Across four multi-hop QA benchmarks, three LLM backbones, and four budget levels, the method yields positive aggregate gains over four audited baselines under the same hard dual-budget protocol. Ablations show that search-time budget control, especially budget-dependent penalty, provides the main performance gain, while answer-time control helps mainly when the retrieval path is already adequate. These results suggest that inference-time budget control for LLM search agents should govern both how budget is spent during search and how the final answer is committed.

Related papers

• One Policy, Any Budget: Internalizing Budget-Aware Search via Reinforcement Learning [41.55260785497756]
  We propose AnySearch, a framework that enables a single policy to perform budget-aware search under any budget constraint.<n>In the first phase, we train the agent with explicit budget state injection and structured reasoning prompts.<n>In the second phase, the scaffold is removed and the agent learns to operate autonomously under adaptively sampled budget constraints.
  arXiv  Detail & Related papers  (2026-09-01T07:12:32Z)
• BRA-Audit: Budgeted Runtime Auditing for LLM Multi-Agent Systems via Cumulative-Exposure Audit-Point Placement [5.4775608854724345]
  Multi-agent systems (LLM-MAS) solve complex tasks through specialized collaboration, but inter-agent dependencies can propagate hallucinated or malicious outputs into system-level failures.<n>We propose BRA-Audit, a budget-aware runtime auditing framework that models MAS execution as a dynamic dependency graph and formulates audit scheduling as audit-point placement under a fixed audit-call budget to minimize cumulative unchecked exposure.<n>Across structured coordination, complex reasoning, and open-ended tasks, BRA-Audit restores performance close to the clean setting, remains competitive with heavy guard methods and reduces end-to-end token consumption by (
  arXiv  Detail & Related papers  (2026-08-02T14:35:43Z)
• TurnOPD: Making On-Policy Distillation Turn-Aware for Efficient Long-Horizon Agent Training [52.6661804966136]
  On-policy distillation (OPD) trains a student policy by matching a stronger teacher on the student's own trajectories.<n>We propose TurnOPD, a turn-level budgeting strategy for efficient on-policy distillation of long-horizon agents.
  arXiv  Detail & Related papers  (2026-07-07T03:56:35Z)
• When Independent Sampling Outperforms Agentic Reasoning [4.226475360842309]
  We study how to allocate inference-time compute for competitive programming under fixed budgets.<n>We compare agent-based reasoning with repeated independent sampling (k-shot) as a function of both cost and number of model calls.
  arXiv  Detail & Related papers  (2026-05-08T20:53:51Z)
• DUET: Optimize Token-Budget Allocation for Reinforcement Learning with Verifiable Rewards [37.28110997883518]
  Reinforcement learning with verifiable rewards generates hundreds of thousands of tokens per training step.<n>We show that jointly tuning both decisions under a shared compute budget improves both reasoning quality and wall-clock training time.
  arXiv  Detail & Related papers  (2026-05-08T20:03:19Z)
• AutoSearch: Adaptive Search Depth for Efficient Agentic RAG via Reinforcement Learning [52.305422887002656]
  We propose a reinforcement learning framework that evaluates each search step via self-generated intermediate answers.<n>By a self-answering mechanism, AutoSearch identifies the minimal sufficient search depth and promotes efficient search.<n>Experiments show that AutoSearch achieves a superior accuracy-efficiency trade-off, alleviating over-searching while preserving search quality.
  arXiv  Detail & Related papers  (2026-04-19T09:05:48Z)
• Adaptive Test-Time Compute Allocation for Reasoning LLMs via Constrained Policy Optimization [18.737087162461563]
  Test-time compute scaling has become a powerful lever for improving large language model performance.<n>Yet deploying these techniques under finite inference budgets requires a decision that current systems largely ignore.<n>We formalize this as a constrained optimization problem (maximize expected accuracy subject to an average compute budget) and solve it with a two-stage Solve-then-Learn pipeline.
  arXiv  Detail & Related papers  (2026-04-16T10:39:22Z)
• Not All Turns Are Equally Hard: Adaptive Thinking Budgets For Efficient Multi-Turn Reasoning [14.194667934432443]
  We formulate multi-turn reasoning as a sequential compute allocation problem and model it as a multi-objective Markov Decision Process.<n>We propose TAB: Turn-Adaptive Budgets, a budget allocation policy that learns to maximize task accuracy while respecting global per-problem token constraints.<n>For systems where a plan of all sub-questions is available apriori, we propose TAB All-SubQ, a budget allocation policy that budgets tokens based on the conversation history and all past and future sub-questions saving up to 40% tokens over baselines.
  arXiv  Detail & Related papers  (2026-04-06T20:48:51Z)
• Quantifying the Accuracy and Cost Impact of Design Decisions in Budget-Constrained Agentic LLM Search [0.7243632426715941]
  Agentic Retrieval-Augmented Generation (RAG) systems combine iterative search, planning prompts, and retrievals, but deployed settings impose explicit budgets on tool calls and completion tokens.<n>We present a controlled measurement study of how search depth, retrieval strategy, and completion budget affect accuracy and cost under fixed constraints.
  arXiv  Detail & Related papers  (2026-03-09T19:42:21Z)
• Learning Query-Aware Budget-Tier Routing for Runtime Agent Memory [56.0946692457838]
  BudgetMem is a runtime agent memory framework for explicit, query-aware performance-cost control.<n>A lightweight router performs budget-tier routing across modules to balance task performance and memory construction cost.<n>Across LoCoMo, LongMemEval, and HotpotQA, BudgetMem surpasses strong baselines when performance is prioritized.
  arXiv  Detail & Related papers  (2026-02-05T18:57:09Z)
• Beyond Monolithic Architectures: A Multi-Agent Search and Knowledge Optimization Framework for Agentic Search [56.78490647843876]
  Agentic search has emerged as a promising paradigm for complex information seeking by enabling Large Language Models (LLMs) to interleave reasoning with tool use.<n>We propose bfM-ASK, a framework that explicitly decouples agentic search into two complementary roles: Search Behavior Agents, which plan and execute search actions, and Knowledge Management Agents, which aggregate, filter, and maintain a compact internal context.
  arXiv  Detail & Related papers  (2026-01-08T08:13:27Z)
• Learning to Route: A Rule-Driven Agent Framework for Hybrid-Source Retrieval-Augmented Generation [55.47971671635531]
  Large Language Models (LLMs) have shown remarkable performance on general Question Answering (QA)<n>Retrieval-Augmented Generation (RAG) addresses this limitation by enriching LLMs with external knowledge.<n>Existing systems primarily rely on unstructured documents, while largely overlooking relational databases.
  arXiv  Detail & Related papers  (2025-09-30T22:19:44Z)
• Intra-request branch orchestration for efficient LLM reasoning [52.68946975865865]
  Large Language Models (LLMs) increasingly rely on inference-time reasoning algorithms to improve accuracy on complex tasks.<n>Prior work has largely focused on reducing token usage, often at the expense of accuracy, while overlooking other latency factors.<n>We present DUCHESS, an LLM serving system that reduces cost and latency without sacrificing accuracy through intra-request branch orchestration guided by predictions.
  arXiv  Detail & Related papers  (2025-09-29T15:52:08Z)
• Aligning LLMs on a Budget: Inference-Time Alignment with Heuristic Reward Models [23.37504394417425]
  We propose HIA (Heuristic-Guided Inference-time Alignment), a tuning-free, black-box-compatible approach that uses a lightweight prompt.<n>We find that HIA is effective under low-inference budgets with as little as one or two response queries.
  arXiv  Detail & Related papers  (2025-08-07T08:54:27Z)
• Confidence-Budget Matching for Sequential Budgeted Learning [69.77435313099366]
  We formalize decision-making problems with querying budget. We consider multi-armed bandits, linear bandits, and reinforcement learning problems. We show that CBM based algorithms perform well in the presence of adversity.
  arXiv  Detail & Related papers  (2021-02-05T19:56:31Z)

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.