Related papers: One Policy, Any Budget: Internalizing Budget-Aware Search via Reinforcement Learning

One Policy, Any Budget: Internalizing Budget-Aware Search via Reinforcement Learning

URL: http://arxiv.org/abs/2609.00813v1
Date: Tue, 01 Sep 2026 07:12:32 GMT
Title: One Policy, Any Budget: Internalizing Budget-Aware Search via Reinforcement Learning
Abstract summary: 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.
Score: 41.55260785497756
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: While reinforcement learning has enabled LLM-based search agents to invoke external tools, existing methods train under fixed budgets and cannot adapt when constraints vary at deployment. We propose AnySearch, a framework that enables a single policy to perform budget-aware search under any budget constraint through a training scaffold and curriculum reinforcement learning. In the first phase, we train the agent with explicit budget state injection and structured reasoning prompts that guide efficient allocation under linearly decaying budgets. In the second phase, the scaffold is removed and the agent learns to operate autonomously under adaptively sampled budget constraints, matching inference conditions. Both phases are optimized with a composite reward that couples answer accuracy with budget efficiency through absolute and relative signals, where an adaptive weight amplifies the efficiency signal for high-accuracy queries and attenuates it for low-accuracy ones. Extensive experiments on seven general and multi-hop QA benchmarks show that our method outperforms baselines across all budget scales, generalizes to unseen constraints beyond the training range, and achieves superior tool productivity without excessive token overhead. Our code is available at https://github.com/xwsun01/AnySearch.

Related papers

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)
ZEBRA: Zero-shot Budgeted Resource Allocation for LLM Orchestration [8.226365534099399]
We propose ZEBRA, a framework that reduces multi-phase budget allocation to a continuous nonlinear knapsack problem.<n>On a $150$-task APPS coding benchmark, both ZEBRA variants outperform LLM-direct on every aggregate metric.<n>We show that lightweight algorithmic guidance at inference time can improve the economic behavior of autonomous multi-agent systems.
arXiv Detail & Related papers (2026-05-19T20:50:05Z)
When Is Rank-1 Steering Cheap? Geometry, Granularity, and Budgeted Search [61.73232505100331]
Activation steering offers a lightweight way to control LLMs without retraining, but its effectiveness varies sharply across concepts.<n>We formalize rank-1 steering as a budget-constrained optimization over intervention layer and coefficient.<n>We present textitGRACE, a Granularity- and Representation-Aware Concept Engineering framework that uses activation geometry to diagnose the dominant source of steering difficulty.
arXiv Detail & Related papers (2026-05-09T14:26:49Z)
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)
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)
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)
WebLeaper: Empowering Efficiency and Efficacy in WebAgent via Enabling Info-Rich Seeking [60.35109192765302]
Information seeking is a core capability that enables autonomous reasoning and decision-making.<n>We propose WebLeaper, a framework for constructing high-coverage IS tasks and generating efficient solution trajectories.<n>Our method consistently achieves improvements in both effectiveness and efficiency over strong baselines.
arXiv Detail & Related papers (2025-10-28T17:51:42Z)
Train Long, Think Short: Curriculum Learning for Efficient Reasoning [51.506559652495476]
We propose a curriculum learning strategy for length-controlled reasoning.<n>Our method starts with generous token budgets and gradually tightens them over training.<n>Experiments on GSM8K, MATH500, SVAMP, College Math, and GSM+ demonstrate that curriculum-based training consistently outperforms fixed-budget baselines.
arXiv Detail & Related papers (2025-08-12T13:48:03Z)
Why Ask One When You Can Ask $k$? Learning-to-Defer to the Top-$k$ Experts [6.792743621449621]
We introduce the first framework for Top-$k$ Learning-to-Defer.<n>It allocates queries to the $k$ most cost-effective entities.<n>We also propose Top-$k(x)$ Learning-to-Defer, an adaptive variant that learns the optimal number of experts per query.
arXiv Detail & Related papers (2025-04-17T14:50:40Z)
Scalable Online Exploration via Coverability [45.66375686120087]
Exploration is a major challenge in reinforcement learning, especially for high-dimensional domains that require function approximation. We introduce a new objective, $L_Coverage, which generalizes previous exploration schemes and supports three fundamental desideratas. $L_Coverage enables the first computationally efficient model-based and model-free algorithms for online (reward-free or reward-driven) reinforcement learning in MDPs with low coverability.
arXiv Detail & Related papers (2024-03-11T10:14:06Z)
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.