Cost-Augmented Monte Carlo Tree Search for LLM-Assisted Planning

2025-05-20 · Zihao Zhang, Fei Liu

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.

📄 PDF Abstract BibTeX arXiv:2505.14656

Code (0)

등록된 구현이 없습니다.

Tasks

Decision Making

Methods 이 논문이 사용한 방법론

Attention 설명 없음

Linear Layer A Linear Layer is a projection $\mathbf{XW + b}$.

Layer Normalization Unlike batch normalization, Layer Normalization directly estimates the normalization statistics from the summed inputs…

Multi-Head Attention 설명 없음

Dense Connections Dense Connections, or Fully Connected Connections, are a type of layer in a deep neural network that use a linear operation where every input is connected to every output…

Softmax The Softmax output function transforms a previous layer's output into a vector of probabilities. It is commonly used for multiclass classification. Given an input vector $x$…

Position-Wise Feed-Forward Layer 설명 없음

Absolute Position Encodings Absolute Position Encodings are a type of position embeddings for [Transformer-based models] where positional encodings are…

Active Reinforcement Learning with Monte-Carlo Tree Search

2018-03-13 · Sebastian Schulze, Owain Evans

Active Reinforcement Learning (ARL) is a twist on RL where the agent observes reward information only if it pays a cost. This subtle change makes exploration substantially more challenging. Powerful principles in RL like…

reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)Thompson Sampling

Monte Carlo Search Algorithms Discovering Monte Carlo Tree Search Exploration Terms

2024-04-14 · Tristan Cazenave

Monte Carlo Tree Search and Monte Carlo Search have good results for many combinatorial problems. In this paper we propose to use Monte Carlo Search to design mathematical expressions that are used as exploration terms f…

Feature Acquisition using Monte Carlo Tree Search

2022-12-21 · Sungsoo Lim, Diego Klabjan, Mark Shapiro

Feature acquisition algorithms address the problem of acquiring informative features while balancing the costs of acquisition to improve the learning performances of ML models. Previous approaches have focused on calcula…

Costly Features Classification using Monte Carlo Tree Search

2021-02-14 · Ziheng Chen, Jin Huang, Hongshik Ahn, Xin Ning

We consider the problem of costly feature classification, where we sequentially select the subset of features to make a balance between the classification error and the feature cost. In this paper, we first cast the task…

Classification General Classification Sensitivity

Structure and Reduction of MCTS for Explainable-AI

2024-08-10 · Ronit Bustin, Claudia V. Goldman

Complex sequential decision-making planning problems, covering infinite states' space have been shown to be solvable by AlphaZero type of algorithms. Such an approach that trains a neural model while simulating projectio…

Decision Making Sequential Decision Making