CostBench: Evaluating Multi-Turn Cost-Optimal Planning and Adaptation in
  Dynamic Environments for LLM Tool-Use Agents
Authors: name: Jiayu Liu; name: Cheng Qian; name: Zhaochen Su; name: Qing Zong; name: Shijue Huang; name: Bingxiang He; name: Yi R. Fung
Published: 2025-11-04 16:58:29

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.