CostBench: Evaluating Multi-Turn Cost-Optimal Planning and Adaptation in Dynamic Environments for LLM Tool-Use Agents

• URL: http://arxiv.org/abs/2511.02734v1
• Date: Tue, 04 Nov 2025 16:58:29 GMT
• Title: CostBench: Evaluating Multi-Turn Cost-Optimal Planning and Adaptation in Dynamic Environments for LLM Tool-Use Agents
• Authors: Jiayu Liu, Cheng Qian, Zhaochen Su, Qing Zong, Shijue Huang, Bingxiang He, Yi R. Fung,
• Abstract summary: CostBench is a cost-centric benchmark designed to evaluate agents' economic reasoning and replanning abilities.<n>It comprises tasks solvable via multiple sequences of atomic and composite tools with diverse, customizable costs.<n>It also supports four types of dynamic blocking events, such as tool failures and cost changes, to simulate real-world unpredictability.
• Score: 20.07359140801559
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Current evaluations of Large Language Model (LLM) agents primarily emphasize task completion, often overlooking resource efficiency and adaptability. This neglects a crucial capability: agents' ability to devise and adjust cost-optimal plans in response to changing environments. To bridge this gap, we introduce CostBench, a scalable, cost-centric benchmark designed to evaluate agents' economic reasoning and replanning abilities. Situated in the travel-planning domain, CostBench comprises tasks solvable via multiple sequences of atomic and composite tools with diverse, customizable costs. It also supports four types of dynamic blocking events, such as tool failures and cost changes, to simulate real-world unpredictability and necessitate agents to adapt in real time. Evaluating leading open-sourced and proprietary models on CostBench reveals a substantial gap in cost-aware planning: agents frequently fail to identify cost-optimal solutions in static settings, with even GPT-5 achieving less than 75% exact match rate on the hardest tasks, and performance further dropping by around 40% under dynamic conditions. By diagnosing these weaknesses, CostBench lays the groundwork for developing future agents that are both economically rational and robust.

Related papers

• Budget-Constrained Agentic Large Language Models: Intention-Based Planning for Costly Tool Use [20.31276001607449]
  We study budget-constrained tool-augmented agents, where a large language model must solve multi-step tasks by invoking external tools under a strict monetary budget.<n>We propose INTENT, an inference-time planning framework that leverages an intention-aware hierarchical world model to anticipate future tool usage, risk-calibrated cost, and guide decisions online.
  arXiv  Detail & Related papers  (2026-02-12T04:01:30Z)
• 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)
• EvoRoute: Experience-Driven Self-Routing LLM Agent Systems [100.64399490164959]
  EvoRoute is a self-evolving model routing paradigm that transcends static, pre-defined model assignments.<n> Experiments on challenging agentic benchmarks demonstrate that EvoRoute, when integrated into off-the-shelf agentic systems, not only sustains or enhances system performance but also reduces execution cost by up to $80%$ and latency by over $70%$.
  arXiv  Detail & Related papers  (2026-01-06T04:06:46Z)
• Towards Efficient Agents: A Co-Design of Inference Architecture and System [66.59916327634639]
  This paper presents AgentInfer, a unified framework for end-to-end agent acceleration.<n>We decompose the problem into four synergistic components: AgentCollab, AgentSched, AgentSAM, and AgentCompress.<n>Experiments on the BrowseComp-zh and DeepDiver benchmarks demonstrate that through the synergistic collaboration of these methods, AgentInfer reduces ineffective token consumption by over 50%.
  arXiv  Detail & Related papers  (2025-12-20T12:06:13Z)
• LeJOT: An Intelligent Job Cost Orchestration Solution for Databricks Platform [28.16213013287002]
  We introduce LeJOT, an intelligent job cost orchestration framework for Databricks jobs.<n>LeJOT proactively predicts workload demands, dynamically allocates computing resources, and minimizes costs.<n>We show that LeJOT achieves an average 20% reduction in cloud computing costs within a minute-level scheduling timeframe.
  arXiv  Detail & Related papers  (2025-12-20T08:09:58Z)
• AgentChangeBench: A Multi-Dimensional Evaluation Framework for Goal-Shift Robustness in Conversational AI [5.165179548592513]
  AgentChangeBench is a benchmark designed to measure how tool augmented language model agents adapt to mid dialogue goal shifts.<n>Our framework formalizes evaluation through four complementary metrics: Task Success Rate (TSR) for effectiveness, Tool Use Efficiency (TUE) for reliability, Tool Call Redundancy Rate (TCRR) for wasted effort, and GoalShift Recovery Time (GSRT) for adaptation.
  arXiv  Detail & Related papers  (2025-10-20T23:48:07Z)
• Dynamic Speculative Agent Planning [57.630218933994534]
  Large language-model-based agents face critical deployment challenges due to prohibitive latency and inference costs.<n>We introduce Dynamic Speculative Planning (DSP), an online reinforcement learning framework that provides lossless acceleration with substantially reduced costs.<n>Experiments on two standard agent benchmarks demonstrate that DSP achieves comparable efficiency to the fastest acceleration method while reducing total cost by 30% and unnecessary cost up to 60%.
  arXiv  Detail & Related papers  (2025-09-02T03:34:36Z)
• 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)
• Cost-Optimal Active AI Model Evaluation [71.2069549142394]
  Development of generative AI systems requires continual evaluation, data acquisition, and annotation.<n>We develop novel, cost-aware methods for actively balancing the use of a cheap, but often inaccurate, weak rater.<n>We derive a family of cost-optimal policies for allocating a given annotation budget between weak and strong raters.
  arXiv  Detail & Related papers  (2025-06-09T17:14:41Z)
• The Cost of Dynamic Reasoning: Demystifying AI Agents and Test-Time Scaling from an AI Infrastructure Perspective [3.0868637098088403]
  Large-language-model (LLM)-based AI agents have recently showcased impressive versatility by employing dynamic reasoning.<n>This paper presents the first comprehensive system-level analysis of AI agents, quantifying their resource usage, latency behavior, energy consumption, and test-time scaling strategies.<n>Our findings reveal that while agents improve accuracy with increased compute, they suffer from rapidly diminishing returns, widening latency variance, and unsustainable infrastructure costs.
  arXiv  Detail & Related papers  (2025-06-04T14:37:54Z)
• The Real Barrier to LLM Agent Usability is Agentic ROI [110.31127571114635]
  Large Language Model (LLM) agents represent a promising shift in human-AI interaction.<n>We highlight a critical usability gap in high-demand, mass-market applications.
  arXiv  Detail & Related papers  (2025-05-23T11:40:58Z)
• CEBench: A Benchmarking Toolkit for the Cost-Effectiveness of LLM Pipelines [23.925385446070717]
  We introduce CEBench, an open-source toolkit for benchmarking online large language models.<n>It focuses on the critical trade-offs between expenditure and effectiveness required for LLM deployments.<n>This capability supports crucial decision-making processes aimed at maximizing effectiveness while minimizing cost impacts.
  arXiv  Detail & Related papers  (2024-06-20T21:36:00Z)
• Optimal Cost Design for Model Predictive Control [30.86835688868485]
  Many robotics domains use non model control (MPC) for planning, which sets a reduced time horizon, performs optimization, and replans at every step. In this work, we challenge the common assumption that the cost we optimize using MPC should be the same as the ground truth cost for the task (plus a terminal cost) We propose a zeroth-order trajectory-based approach that enables us to design optimal costs for an MPC planning robot in continuous MDPs.
  arXiv  Detail & Related papers  (2021-04-23T00: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.