Cost-Augmented Monte Carlo Tree Search for LLM-Assisted Planning
This addresses budget-aware decision-making for users needing structured planning with LLMs, but it is incremental as it adapts an existing method (MCTS) to a specific bottleneck.
The paper tackles the problem of LLMs struggling with cost-sensitive planning by introducing Cost-Augmented Monte Carlo Tree Search (CATS), which improves task success rates and cost efficiency compared to raw LLMs like GPT-4.1.
While LLMs excel at open-ended reasoning, they often struggle with cost-sensitive planning, either treating all actions as having equal cost or failing to stay within strict budgets. In this paper, we introduce Cost-Augmented Monte Carlo Tree Search (CATS), a novel approach that brings explicit cost-awareness into LLM-guided planning. Tight cost constraints push the planner to quickly identify infeasible solutions, while looser constraints encourage optimization for minimal cost. We benchmark top LLMs such as GPT-4.1, Claude-3.7-Sonnet, and DeepSeek-R1, against our CATS planner to evaluate their performance in cost-sensitive scenarios. Our experiments suggest that raw LLMs such as GPT-4.1 often falter under tight budgets, whereas CATS consistently delivers strong performance, achieving higher task success rates and better cost efficiency. CATS provides an effective solution for budget-aware decision-making by combining the reasoning power of LLMs with structured search.