Exploit More, Explore Smarter for Budget-Constrained Agentic Search

• URL: http://arxiv.org/abs/2608.23848v1
• Date: Mon, 24 Aug 2026 21:38:05 GMT
• Title: Exploit More, Explore Smarter for Budget-Constrained Agentic Search
• Abstract summary: 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.
• Score: 6.894751260400948
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Budget-constrained agentic search arises when an LLM agent must refine candidates under a small evaluation budget, because validation is expensive, generation requires multiple model calls, or both. In this regime, standard MCTS allocates budget poorly: exploration bonuses dominate at low visit counts, unpromising siblings are expanded before promising chains can deepen, and branching is independent of node quality. We introduce ExTS, a tree-search policy that treats expansion itself as a value-of-information decision. ExTS combines three mechanisms: discriminative reward shaping to separate candidates under narrow score distributions, a stochastic virtual child that estimates the value of creating a new branch from the parent's reward history, and quality-conditioned branching that expands only when a node's score justifies the budget cost. Across prompt optimization, code generation, molecular structure elucidation, and agentic workflow optimization, ExTS is competitive with or improves over task-specific tree-search baselines, with an average relative gain of +5.5% using a single fixed configuration. We further introduce pilot-run diagnostics that characterize what makes budget-constrained agentic search problems structurally different from one another, providing both understanding of the problem space and practical guidance for adaptation.

Related papers

• The Optimizer Is the Agent: Reasoning-Driven Search across Prompts, Programs, and ML Workflows [72.9051182568928]
  We present ReASearch, a unified framework for reasoning-driven optimization.<n>With a shared agent loop and domain-specific tools, ReASearch instantiates the exact same scaffold to optimize prompts, programs, and ML.<n>We observe that complex search behaviors emerge naturally from the agent's reasoning process.
  arXiv  Detail & Related papers  (2026-08-07T02:15:39Z)
• Agent-UCT: Upper Confidence Bounds Applied to Trees for Agentic Workflow Optimization with Cost-Awareness [11.231092673447735]
  We introduce Agent-based Cost-Aware Upper Bounds Applied to Trees, a tree search algorithm that extends UCT with a reuse-aware regularization term derived from a bipartite prefix reuse graph.<n>Agent-UCT biases selection toward branches that leverage previously materialized configuration prefixes, reducing redundant execution while maintaining effective exploration.<n>WTB (Workflow Test Bench) provides deterministic replay, content-addressable caching, and transactional consistency, ensuring that intermediate states are materialized once and reused across the search computation.
  arXiv  Detail & Related papers  (2026-07-27T08:41:18Z)
• 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)
• 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)
• Spend Less, Reason Better: Budget-Aware Value Tree Search for LLM Agents [40.18150559561834]
  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.
  arXiv  Detail & Related papers  (2026-03-13T04:10:27Z)
• 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)
• 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)
• 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)
• Hierarchical Budget Policy Optimization for Adaptive Reasoning [49.621779447691665]
  We present Hierarchical Budget Policy Optimization (HBPO), a reinforcement learning framework that enables models to learn problem-specific reasoning depths without sacrificing capability.<n>HBPO partitions the exploration space into budget-constrained hierarchies (512-2560 tokens), each with differentiated reward structures that preserve both efficiency incentives and reasoning capabilities.<n>Extensive experiments demonstrate that HBPO reduces average token usage by up to 60.6% while improving accuracy by 3.14% across four reasoning benchmarks.
  arXiv  Detail & Related papers  (2025-07-21T17:52:34Z)
• Decision Tree Induction Through LLMs via Semantically-Aware Evolution [53.0367886783772]
  We propose an evolutionary optimization method for decision tree induction based on genetic programming (GP)<n>Our key innovation is the integration of semantic priors and domain-specific knowledge about the search space into the algorithm.<n>This is operationalized through novel genetic operators that work with structured natural language prompts.
  arXiv  Detail & Related papers  (2025-03-18T12:52:03Z)
• VCG Mechanism Design with Unknown Agent Values under Stochastic Bandit Feedback [104.06766271716774]
  We study a multi-round welfare-maximising mechanism design problem in instances where agents do not know their values. We first define three notions of regret for the welfare, the individual utilities of each agent and that of the mechanism. Our framework also provides flexibility to control the pricing scheme so as to trade-off between the agent and seller regrets.
  arXiv  Detail & Related papers  (2020-04-19T18:00:58Z)

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.