Quantifying the Accuracy and Cost Impact of Design Decisions in Budget-Constrained Agentic LLM Search

• URL: http://arxiv.org/abs/2603.08877v1
• Date: Mon, 09 Mar 2026 19:42:21 GMT
• Title: Quantifying the Accuracy and Cost Impact of Design Decisions in Budget-Constrained Agentic LLM Search
• Abstract summary: 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.
• Score: 0.7243632426715941
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Agentic Retrieval-Augmented Generation (RAG) systems combine iterative search, planning prompts, and retrieval backends, but deployed settings impose explicit budgets on tool calls and completion tokens. We present a controlled measurement study of how search depth, retrieval strategy, and completion budget affect accuracy and cost under fixed constraints. Using Budget-Constrained Agentic Search (BCAS), a model-agnostic evaluation harness that surfaces remaining budget and gates tool use, we run comparisons across six LLMs and three question-answering benchmarks. Across models and datasets, accuracy improves with additional searches up to a small cap, hybrid lexical and dense retrieval with lightweight re-ranking produces the largest average gains in our ablation grid, and larger completion budgets are most helpful on HotpotQA-style synthesis. These results provide practical guidance for configuring budgeted agentic retrieval pipelines and are accompanied by reproducible prompts and evaluation settings.

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)
• 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)
• CAMI: Cost-Aware Agent-Guided Multi-Indexing for Semantic Retrieval [7.07006462273528]
  CAMI (Cost-Aware Multi-Indexing) is a framework that formalizes multi-index construction as a budgeted, multi-objective portfolio selection problem.<n>Our findings reveal that the framework systematically isolates high-recall portfolios under strict budget constraints.<n> CAMI is able to systematically identify these high-recall portfolios using up to 5x less budget compared to random search baselines.
  arXiv  Detail & Related papers  (2026-06-14T16:59:18Z)
• Inference-Time Budget Control for LLM Search Agents [21.14983754890843]
  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.
  arXiv  Detail & Related papers  (2026-05-07T05:45:58Z)
• 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)
• Cost-Efficient RAG for Entity Matching with LLMs: A Blocking-based Exploration [14.88759517020146]
  Existing RAG pipelines incur substantial retrieval and generation overhead when applied to large-scale entity matching.<n>We introduce CE-RAG4EM, a cost-efficient RAG architecture that reduces computation through blocking-based batch retrieval and generation.
  arXiv  Detail & Related papers  (2026-02-05T14:33:00Z)
• Predictive Scheduling for Efficient Inference-Time Reasoning in Large Language Models [6.002670452103349]
  Large language models (LLMs) achieve state-of-the-art accuracy on complex reasoning tasks.<n>But using a fixed token budget per query leads to over-computation on easy inputs and under-computation on hard ones.<n>We introduce Predictive Scheduling, a plug-and-play framework that pre-runs lightweight predictors to estimate each query's optimal reasoning length or difficulty before any full generation.
  arXiv  Detail & Related papers  (2026-02-01T13:58:23Z)
• Rerank Before You Reason: Analyzing Reranking Tradeoffs through Effective Token Cost in Deep Search Agents [50.212640395029744]
  We study how to allocate reasoning budget in deep search pipelines.<n>Using the BrowseComp-Plus benchmark, we analyze tradeoffs between model scale, reasoning effort, reranking depth, and total token cost.
  arXiv  Detail & Related papers  (2026-01-20T18:38:35Z)
• Budget-Aware Anytime Reasoning with LLM-Synthesized Preference Data [57.996437077411315]
  We study the reasoning behavior of large language models (LLMs) under limited computation budgets.<n>We introduce an anytime reasoning framework and the Anytime Index, a metric that quantifies how effectively solution quality improves as reasoning tokens increase.<n> Experiments on NaturalPlan (Trip), AIME, and GPQA datasets show consistent gains across Grok-3, GPT-oss, GPT-4.1/4o, and LLaMA models.
  arXiv  Detail & Related papers  (2026-01-16T07:09:30Z)
• Distilling a Small Utility-Based Passage Selector to Enhance Retrieval-Augmented Generation [110.610512800947]
  Retrieval-augmented generation (RAG) enhances large language models (LLMs) by incorporating retrieved information.<n>In RAG, the emphasis has shifted to utility, which considers the usefulness of passages for generating accurate answers.<n>Our approach focuses on utility-based selection rather than ranking, enabling dynamic passage selection tailored to specific queries without the need for fixed thresholds.<n>Our experiments demonstrate that utility-based selection provides a flexible and cost-effective solution for RAG, significantly reducing computational costs while improving answer quality.
  arXiv  Detail & Related papers  (2025-07-25T09:32:29Z)
• PlanGEN: A Multi-Agent Framework for Generating Planning and Reasoning Trajectories for Complex Problem Solving [89.60370366013142]
  We propose PlanGEN, a model-agnostic and easily scalable agent framework with three key components: constraint, verification, and selection agents.<n>Specifically, our approach proposes constraint-guided iterative verification to enhance performance of inference-time algorithms.
  arXiv  Detail & Related papers  (2025-02-22T06:21:56Z)
• New Additive OCBA Procedures for Robust Ranking and Selection [0.9558392439655016]
  We develop new fixed-budget robust R&S procedures to minimize the probability of incorrect selection under a limited sampling budget.<n>We then conduct a comprehensive numerical study to verify the superiority of our robust OCBA procedure over existing ones.
  arXiv  Detail & Related papers  (2024-12-08T18:42:07Z)
• Truncating Trajectories in Monte Carlo Policy Evaluation: an Adaptive Approach [51.76826149868971]
  Policy evaluation via Monte Carlo simulation is at the core of many MC Reinforcement Learning (RL) algorithms. We propose as a quality index a surrogate of the mean squared error of a return estimator that uses trajectories of different lengths. We present an adaptive algorithm called Robust and Iterative Data collection strategy Optimization (RIDO)
  arXiv  Detail & Related papers  (2024-10-17T11:47:56Z)
• Bayesian Optimization Over Iterative Learners with Structured Responses: A Budget-aware Planning Approach [31.918476422203412]
  This paper proposes a novel approach referred to as Budget-Aware Planning for Iterative learners (BAPI) to solve HPO problems under a constrained cost budget. Experiments on diverse HPO benchmarks for iterative learners show that BAPI performs better than state-of-the-art baselines in most of the cases.
  arXiv  Detail & Related papers  (2022-06-25T18:44:06Z)
• A Survey on Advancing the DBMS Query Optimizer: Cardinality Estimation, Cost Model, and Plan Enumeration [17.75042918159419]
  A cost-based algorithm is adopted in almost all current database systems. In the cost model, cardinality, the number of the numbers through an operator plays a crucial role. Due to the inaccuracy in cardinality estimation, errors in cost, and the huge plan space model, the algorithm cannot find the optimal execution plan for a complex query in a reasonable time.
  arXiv  Detail & Related papers  (2021-01-05T13:47:45Z)

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.