mlsanityData to 7 Oct 2026

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

arXiv 2511.02734 ↗First posted 4 Nov 2025cs.AI cs.CLcited by 32

On the map: LLM agents and tool use → General LLM agent frameworks and benchmarks

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.

Key facts. Cited by 32 papers in the map (data through 7 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.

Builds on

47 of 87 references.

Closest ancestors · 5

Same direction, newest first

  1. 2025UserBench: An Interactive Gym Environment for User-Centric Agents29 Jul
  2. 2025Flex-TravelPlanner: A Benchmark for Flexible Planning with Language Agents5 Jun
  3. 2024BudgetMLAgent: A Cost-Effective LLM Multi-Agent system for Automating Machine Learning Tasks12 Nov
  4. 2024τ-bench: A Benchmark for Tool-Agent-User Interaction in Real-World Domains17 Jun
  5. 2024TravelPlanner: A Benchmark for Real-World Planning with Language Agents2 Feb

Other references · 42

  1. 2023LLaMA: Open and Efficient Foundation Language Modelscited by 13,958
  2. 2023Efficient Memory Management for Large Language Model Serving with PagedAttentioncited by 5,767
  3. 2023Toolformer: Language Models Can Teach Themselves to Use Toolscited by 4,072
  4. 2025DAPO: An Open-Source LLM Reinforcement Learning System at Scalecited by 2,678
  5. 2023ToolLLM: Facilitating Large Language Models to Master 16000+ Real-world APIscited by 1,880
  6. 2023FrugalGPT: How to Use Large Language Models While Reducing Cost and Improving Performancecited by 791
  7. 2022PlanBench: An Extensible Benchmark for Evaluating Large Language Models on Planning and Reasoning about Changecited by 372
  8. 2025ToolRL: Reward is All Tool Learning Needscited by 342
  9. 2023MINT: Evaluating LLMs in Multi-turn Interaction with Tools and Language Feedbackcited by 293
  10. 2023ToolQA: A Dataset for LLM Question Answering with External Toolscited by 273
  11. 2024ToolSandbox: A Stateful, Conversational, Interactive Evaluation Benchmark for LLM Tool Use Capabilitiescited by 272
  12. 2025UI-TARS-2 Technical Report: Advancing GUI Agent with Multi-Turn Reinforcement Learningcited by 205
30 more
  1. 2025Thinking with Images for Multimodal Reasoning: Foundations, Methods, and Future Frontierscited by 193
  2. 2025WebDancer: Towards Autonomous Information Seeking Agencycited by 180
  3. 2025OpenThinkIMG: Learning to Think with Images via Visual Tool Reinforcement Learningcited by 163
  4. 2025WebWatcher: Breaking New Frontier of Vision-Language Deep Research Agentcited by 114
  5. 2025MCP-Bench: Benchmarking Tool-Using LLM Agents with Complex Real-World Tasks via MCP Serverscited by 101
  6. 2025MATH-Perturb: Benchmarking LLMs' Math Reasoning Abilities against Hard Perturbationscited by 88
  7. 2024Planning, Creation, Usage: Benchmarking LLMs for Comprehensive Tool Utilization in Real-World Complex Scenarioscited by 85
  8. 2025Reasoning or Memorization? Unreliable Results of Reinforcement Learning Due to Data Contaminationcited by 81
  9. 2025Acting Less is Reasoning More! Teaching Model to Act Efficientlycited by 80
  10. 2023Put Your Money Where Your Mouth Is: Evaluating Strategic Planning and Execution of LLM Agents in an Auction Arenacited by 78
  11. 2025ACEBench: Who Wins the Match Point in Tool Usage?cited by 66
  12. 2025WebResearcher: Unleashing unbounded reasoning capability in Long-Horizon Agentscited by 66
  13. 2025SMART: Self-Aware Agent for Tool Overuse Mitigationcited by 52
  14. 2025AdaCtrl: Towards Adaptive and Controllable Reasoning via Difficulty-Aware Budgetingcited by 50
  15. 2023SayCanPay: Heuristic Planning with Large Language Models using Learnable Domain Knowledgecited by 49
  16. 2023EcoAssistant: Using LLM Assistant More Affordably and Accuratelycited by 47
  17. 2024Reasoning in Token Economies: Budget-Aware Evaluation of LLM Reasoning Strategiescited by 44
  18. 2024ACPBench: Reasoning about Action, Change, and Planningcited by 37
  19. 2025BudgetThinker: Empowering Budget-aware LLM Reasoning with Control Tokenscited by 27
  20. 2014Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false)cited by 18
  21. 2025Mathematical Proof as a Litmus Test: Revealing Failure Modes of Advanced Large Reasoning Modelscited by 18
  22. 2025Plan Then Action:High-Level Planning Guidance Reinforcement Learning for LLM Reasoningcited by 17
  23. 2025Revisiting Epistemic Markers in Confidence Estimation: Can Markers Accurately Reflect Large Language Models' Uncertainty?cited by 16
  24. 2024CATP-LLM: Empowering Large Language Models for Cost-Aware Tool Planningcited by 14
  25. 2025Advancing Language Multi-Agent Learning with Credit Re-Assignment for Interactive Environment Generalizationcited by 11
  26. 2025Diversity-Enhanced Reasoning for Subjective Questionscited by 9
  27. 2025ReST-RL: Reinforcing LLM Reasoning through Unified Self-Training and Value-Guided Searchcited by 9
  28. 2024ComparisonQA: Evaluating Factuality Robustness of LLMs Through Knowledge Frequency Control and Uncertaintycited by 8
  29. 2025ACPBench Hard: Unrestrained Reasoning about Action, Change, and Planningcited by 6
  30. 2025R-ConstraintBench: Evaluating LLMs on NP-Complete Schedulingcited by 5

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2026: 32.

32 papers.

Sort:

By area:

  1. 2026Calibrate-Then-Act: Cost-Aware Exploration in LLM Agentscited by 16
  2. 2026Toward Efficient Agents: Memory, Tool learning, and Planningcited by 11
  3. 2026PlanBench-XL: Evaluating Long-Horizon Planning of LLM Tool-Use Agents in Large-Scale Tool Ecosystemscited by 10
  4. 2026From Question Answering to Task Completion: A Survey on Agent System and Harness Designcited by 9
  5. 2026AdaPlanBench: Evaluating Adaptive Planning in Large Language Model Agents under World and User Constraintscited by 6
  6. 2026NOVA: NOise-aware Verbal Confidence CAlibration for Robust Large Language Models in RAG Systemscited by 5
  7. 2026CreativityBench: Evaluating Agent Creative Reasoning via Affordance-Based Tool Repurposingcited by 4
  8. 2026Beyond Accuracy: Unveiling Inefficiency Patterns in Tool-Integrated Reasoningcited by 3
  9. 2026Code2Math: Can Your Code Agent Effectively Evolve Math Problems Through Exploration?cited by 2
  10. 2026MemGuard: Preventing Memory Contamination in Long-Term Memory-Augmented Large Language Modelscited by 2
  11. 2026Scores Are Not Decisions: Cost-Aware Stopping for Tool Acquisition in LLM Agentscited by 2
  12. 2026Permission Denied: Policy-Graded Evaluation of Coding Agents in Hardened Environmentscited by 2
20 more
  1. 2026PeakBench: Benchmarking Resource-Aware Tool Invocation in LLM Agentscited by 2
  2. 2026Evaluating Memory Condensation Strategies for Coding Agents in Data-Driven Scientific Discoverycited by 1
  3. 2026PlanningBench: Generating Scalable and Verifiable Planning Data for Evaluating and Training Large Language Modelscited by 1
  4. 2026EcoAgent-Bench: Evaluating Economic Decision-Making in Budget-Constrained LLM Agentscited by 1
  5. 2026Co-Evolution in Agentic Systems: Toward Self-Directed Evolution Beyond Human Designcited by 1
  6. 2026VibeLifeBench: Can Your Life Agent Be Proactive and Persistent in a Living World?cited by 1
  7. 2026Decoupling Strategy and Execution in Task-Focused Dialogue via Goal-Oriented Preference Optimizationcited by 0
  8. 2026Agents Learn Their Runtime: Interpreter Persistence as Training-Time Semanticscited by 0
  9. 2026Latent Action Reparameterization for Efficient Agent Inferencecited by 0
  10. 2026Psi-Bench: Evaluating Persona-Sensitive Influencing in Persuasive Dialoguescited by 0
  11. 2026Can Agentic Trading Systems Pay for Their Own Intelligence?cited by 0
  12. 2026Set-shifting Behavioral Test for Harnessed Agentscited by 0
  13. 2026Prompt-Induced Waste in Coding Agents: Reasoning, Effort, Harness Design, and End-to-End Costcited by 0
  14. 2026What Does Context Compression Cost an Agent? Interaction Costs Unrevealed by Task-Completion Metricscited by 0
  15. 2026Forecast Workflow Bench: Evaluating Language-Model Decisions with Budgeted Forecast Toolscited by 0
  16. 2026When Does Action Credit Need Updating?cited by 0
  17. 2026LLM Parkinsonism: Executive-Control Failure, Token-Inefficient Persistence, and an Uncertainty-Aware Global Executive Control Architecture for Autonomous Language-Model Agentscited by 0
  18. 2026DynGraphAgentBench: A Benchmark for Agentic Lifecycle Control in Dynamic Graph Anomaly Detectioncited by 0
  19. 2026When Should Agents Check External State? Budgeting Observations for Stored Intentionscited by 0
  20. 2026Commitment Hierarchies under Intent Revision: A Belief-Revision Account of Salvage in Tool-Use Agentscited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2026Budget-Constrained Agentic Large Language Models: Intention-Based Planning for Costly Tool Use
  2. 2025Budget-Aware Tool Use Enables Effective Agent Scaling
  3. 2025Learning When to Plan: Efficiently Allocating Test-Time Compute for LLM Agents
  4. 2025The Cost of Dynamic Reasoning: Demystifying AI Agents and Test-Time Scaling from an AI Infrastructure Perspective
  5. 2025Beyond Itinerary Planning-A Real-World Benchmark for Multi-Turn and Tool-Using Travel Tasks
  6. 2025Cost-Awareness in Tree-Search LLM Planning: A Systematic Study
  7. 2026Cost-Utility Alignment in LLM Agent Trajectories:Profiling,Attribution,Diagnosis,Adaptation,and Evaluation
  8. 2025ALAS: A Stateful Multi-LLM Agent Framework for Disruption-Aware Planning