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

arXiv: https://arxiv.org/abs/2511.02734 · HTML: https://mlsanity.com/paper/2511.02734/

## Key facts

- Cited by 33 papers in the map (data through 14 Oct 2026).
- Placed in General LLM agent frameworks and benchmarks, one of 16 directions in LLM agents and tool use.
- Builds on 47 of its 87 references that are in the map.
- First posted on arXiv 4 Nov 2025.

## Placed in

- LLM agents and tool use / [General LLM agent frameworks and benchmarks](https://mlsanity.com/agents/general-llm-agent-frameworks-and-benchmarks/)

## Builds on (most cited first, 30 of 47)

- [LLaMA: Open and Efficient Foundation Language Models](https://mlsanity.com/paper/2302.13971/) (2023)
- [Efficient Memory Management for Large Language Model Serving with PagedAttention](https://mlsanity.com/paper/2309.06180/) (2023)
- [Toolformer: Language Models Can Teach Themselves to Use Tools](https://mlsanity.com/paper/2302.04761/) (2023)
- [DAPO: An Open-Source LLM Reinforcement Learning System at Scale](https://mlsanity.com/paper/2503.14476/) (2025)
- [ToolLLM: Facilitating Large Language Models to Master 16000+ Real-world APIs](https://mlsanity.com/paper/2307.16789/) (2023)
- [τ-bench: A Benchmark for Tool-Agent-User Interaction in Real-World Domains](https://mlsanity.com/paper/2406.12045/) (2024)
- [FrugalGPT: How to Use Large Language Models While Reducing Cost and Improving Performance](https://mlsanity.com/paper/2305.05176/) (2023)
- [TravelPlanner: A Benchmark for Real-World Planning with Language Agents](https://mlsanity.com/paper/2402.01622/) (2024)
- [PlanBench: An Extensible Benchmark for Evaluating Large Language Models on Planning and Reasoning about Change](https://mlsanity.com/paper/2206.10498/) (2022)
- [ToolRL: Reward is All Tool Learning Needs](https://mlsanity.com/paper/2504.13958/) (2025)
- [MINT: Evaluating LLMs in Multi-turn Interaction with Tools and Language Feedback](https://mlsanity.com/paper/2309.10691/) (2023)
- [ToolSandbox: A Stateful, Conversational, Interactive Evaluation Benchmark for LLM Tool Use Capabilities](https://mlsanity.com/paper/2408.04682/) (2024)
- [ToolQA: A Dataset for LLM Question Answering with External Tools](https://mlsanity.com/paper/2306.13304/) (2023)
- [UI-TARS-2 Technical Report: Advancing GUI Agent with Multi-Turn Reinforcement Learning](https://mlsanity.com/paper/2509.02544/) (2025)
- [Thinking with Images for Multimodal Reasoning: Foundations, Methods, and Future Frontiers](https://mlsanity.com/paper/2506.23918/) (2025)
- [WebDancer: Towards Autonomous Information Seeking Agency](https://mlsanity.com/paper/2505.22648/) (2025)
- [OpenThinkIMG: Learning to Think with Images via Visual Tool Reinforcement Learning](https://mlsanity.com/paper/2505.08617/) (2025)
- [WebWatcher: Breaking New Frontier of Vision-Language Deep Research Agent](https://mlsanity.com/paper/2508.05748/) (2025)
- [MCP-Bench: Benchmarking Tool-Using LLM Agents with Complex Real-World Tasks via MCP Servers](https://mlsanity.com/paper/2508.20453/) (2025)
- [MATH-Perturb: Benchmarking LLMs' Math Reasoning Abilities against Hard Perturbations](https://mlsanity.com/paper/2502.06453/) (2025)
- [Planning, Creation, Usage: Benchmarking LLMs for Comprehensive Tool Utilization in Real-World Complex Scenarios](https://mlsanity.com/paper/2401.17167/) (2024)
- [Reasoning or Memorization? Unreliable Results of Reinforcement Learning Due to Data Contamination](https://mlsanity.com/paper/2507.10532/) (2025)
- [Acting Less is Reasoning More! Teaching Model to Act Efficiently](https://mlsanity.com/paper/2504.14870/) (2025)
- [Put Your Money Where Your Mouth Is: Evaluating Strategic Planning and Execution of LLM Agents in an Auction Arena](https://mlsanity.com/paper/2310.05746/) (2023)
- [UserBench: An Interactive Gym Environment for User-Centric Agents](https://mlsanity.com/paper/2507.22034/) (2025)
- [ACEBench: Who Wins the Match Point in Tool Usage?](https://mlsanity.com/paper/2501.12851/) (2025)
- [WebResearcher: Unleashing unbounded reasoning capability in Long-Horizon Agents](https://mlsanity.com/paper/2509.13309/) (2025)
- [SMART: Self-Aware Agent for Tool Overuse Mitigation](https://mlsanity.com/paper/2502.11435/) (2025)
- [AdaCtrl: Towards Adaptive and Controllable Reasoning via Difficulty-Aware Budgeting](https://mlsanity.com/paper/2505.18822/) (2025)
- [SayCanPay: Heuristic Planning with Large Language Models using Learnable Domain Knowledge](https://mlsanity.com/paper/2308.12682/) (2023)

## Built on by (most cited first, 30 of 33)

- [Calibrate-Then-Act: Cost-Aware Exploration in LLM Agents](https://mlsanity.com/paper/2602.16699/) (2026)
- [Toward Efficient Agents: Memory, Tool learning, and Planning](https://mlsanity.com/paper/2601.14192/) (2026)
- [From Question Answering to Task Completion: A Survey on Agent System and Harness Design](https://mlsanity.com/paper/2606.20683/) (2026)
- [PlanBench-XL: Evaluating Long-Horizon Planning of LLM Tool-Use Agents in Large-Scale Tool Ecosystems](https://mlsanity.com/paper/2606.22388/) (2026)
- [AdaPlanBench: Evaluating Adaptive Planning in Large Language Model Agents under World and User Constraints](https://mlsanity.com/paper/2606.05622/) (2026)
- [NOVA: NOise-aware Verbal Confidence CAlibration for Robust Large Language Models in RAG Systems](https://mlsanity.com/paper/2601.11004/) (2026)
- [CreativityBench: Evaluating Agent Creative Reasoning via Affordance-Based Tool Repurposing](https://mlsanity.com/paper/2605.02910/) (2026)
- [Scores Are Not Decisions: Cost-Aware Stopping for Tool Acquisition in LLM Agents](https://mlsanity.com/paper/2607.27083/) (2026)
- [Beyond Accuracy: Unveiling Inefficiency Patterns in Tool-Integrated Reasoning](https://mlsanity.com/paper/2604.05404/) (2026)
- [MemGuard: Preventing Memory Contamination in Long-Term Memory-Augmented Large Language Models](https://mlsanity.com/paper/2605.28009/) (2026)
- [Permission Denied: Policy-Graded Evaluation of Coding Agents in Hardened Environments](https://mlsanity.com/paper/2608.02670/) (2026)
- [VibeLifeBench: Can Your Life Agent Be Proactive and Persistent in a Living World?](https://mlsanity.com/paper/2608.10875/) (2026)
- [Code2Math: Can Your Code Agent Effectively Evolve Math Problems Through Exploration?](https://mlsanity.com/paper/2603.03202/) (2026)
- [PeakBench: Benchmarking Resource-Aware Tool Invocation in LLM Agents](https://mlsanity.com/paper/2608.24509/) (2026)
- [Evaluating Memory Condensation Strategies for Coding Agents in Data-Driven Scientific Discovery](https://mlsanity.com/paper/2605.18854/) (2026)
- [PlanningBench: Generating Scalable and Verifiable Planning Data for Evaluating and Training Large Language Models](https://mlsanity.com/paper/2605.20873/) (2026)
- [Prompt-Induced Waste in Coding Agents: Reasoning, Effort, Harness Design, and End-to-End Cost](https://mlsanity.com/paper/2608.01347/) (2026)
- [EcoAgent-Bench: Evaluating Economic Decision-Making in Budget-Constrained LLM Agents](https://mlsanity.com/paper/2608.05519/) (2026)
- [Co-Evolution in Agentic Systems: Toward Self-Directed Evolution Beyond Human Design](https://mlsanity.com/paper/2608.10299/) (2026)
- [Decoupling Strategy and Execution in Task-Focused Dialogue via Goal-Oriented Preference Optimization](https://mlsanity.com/paper/2602.15854/) (2026)
- [Agents Learn Their Runtime: Interpreter Persistence as Training-Time Semantics](https://mlsanity.com/paper/2603.01209/) (2026)
- [Latent Action Reparameterization for Efficient Agent Inference](https://mlsanity.com/paper/2605.18597/) (2026)
- [Psi-Bench: Evaluating Persona-Sensitive Influencing in Persuasive Dialogues](https://mlsanity.com/paper/2606.02754/) (2026)
- [Can Agentic Trading Systems Pay for Their Own Intelligence?](https://mlsanity.com/paper/2607.10286/) (2026)
- [Set-shifting Behavioral Test for Harnessed Agents](https://mlsanity.com/paper/2607.13396/) (2026)
- [What Does Context Compression Cost an Agent? Interaction Costs Unrevealed by Task-Completion Metrics](https://mlsanity.com/paper/2608.16370/) (2026)
- [Forecast Workflow Bench: Evaluating Language-Model Decisions with Budgeted Forecast Tools](https://mlsanity.com/paper/2609.27385/) (2026)
- [When Does Action Credit Need Updating?](https://mlsanity.com/paper/2609.29007/) (2026)
- [LLM Parkinsonism: Executive-Control Failure, Token-Inefficient Persistence, and an Uncertainty-Aware Global Executive Control Architecture for Autonomous Language-Model Agents](https://mlsanity.com/paper/2609.30662/) (2026)
- [DynGraphAgentBench: A Benchmark for Agentic Lifecycle Control in Dynamic Graph Anomaly Detection](https://mlsanity.com/paper/2609.33980/) (2026)

## Abstract (arXiv)

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.