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

• URL: http://arxiv.org/abs/2505.14656v1
• Date: Tue, 20 May 2025 17:43:33 GMT
• Title: Cost-Augmented Monte Carlo Tree Search for LLM-Assisted Planning
• Authors: Zihao Zhang, Fei Liu,
• Abstract summary: Cost-Augmented Monte Carlo Tree Search (CATS) is a novel approach that brings explicit cost-awareness into LLM-guided planning.<n>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.
• Score: 9.475296641135289
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• Steering LLM Thinking with Budget Guidance [48.65894557568655]
  Budget guidance is a method for steering the reasoning process of LLMs toward a target budget without requiring any fine-tuning.<n>Our approach introduces a lightweight predictor that models a Gamma distribution over the remaining thinking length.<n>This signal is then used to guide generation in a soft, token-level manner, ensuring that the overall reasoning trace adheres to the specified thinking budget.
  arXiv  Detail & Related papers  (2025-06-16T17:57:05Z)
• Large Reasoning Models in Agent Scenarios: Exploring the Necessity of Reasoning Capabilities [74.35956310688164]
  We propose the LaRMA framework, encompassing nine tasks across Tool Usage, Plan Design, and Problem Solving.<n>Our findings address four research questions: LRMs surpass LLMs in reasoning-intensive tasks like Plan Design, leveraging iterative reflection for superior outcomes.<n>LRMs' enhanced reasoning incurs higher computational costs, prolonged processing, and behavioral challenges, including overthinking and fact-ignoring tendencies.
  arXiv  Detail & Related papers  (2025-03-14T04:34:31Z)
• Smart Routing: Cost-Effective Multi-LLM Serving for Multi-Core AIOS [31.60019342381251]
  Existing scheduling frameworks mainly target at latency optimization.<n>This paper proposes an efficient capability-cost coordinated scheduling framework, ECCOS, for multi-LLM serving.
  arXiv  Detail & Related papers  (2025-02-27T22:35:31Z)
• MixLLM: Dynamic Routing in Mixed Large Language Models [57.309520357563215]
  Large Language Models (LLMs) exhibit potential artificial generic intelligence recently, however, their usage is costly with high response latency.<n>We develop MixLLM, a dynamic contextual-bandit-based routing system for query-LLM assignment.
  arXiv  Detail & Related papers  (2025-02-09T02:26:15Z)
• Control Large Language Models via Divide and Conquer [94.48784966256463]
  This paper investigates controllable generation for large language models (LLMs) with prompt-based control, focusing on Lexically Constrained Generation (LCG) We evaluate the performance of LLMs on satisfying lexical constraints with prompt-based control, as well as their efficacy in downstream applications.
  arXiv  Detail & Related papers  (2024-10-06T21:20:06Z)
• OptLLM: Optimal Assignment of Queries to Large Language Models [12.07164196530872]
  We propose a framework for addressing the cost-effective query allocation problem for large language models (LLMs) Our framework, named OptLLM, provides users with a range of optimal solutions to choose from, aligning with their budget constraints and performance preferences. To evaluate the effectiveness of OptLLM, we conduct extensive experiments on various types of tasks, including text classification, question answering, sentiment analysis, reasoning, and log parsing.
  arXiv  Detail & Related papers  (2024-05-24T01:05:37Z)
• Optimising Calls to Large Language Models with Uncertainty-Based Two-Tier Selection [80.63946798650653]
  Decision centers on whether to use a large LLM with better performance or a smaller one with reduced costs. We propose a simpler solution; we use only the uncertainty of the generations of the small LLM as the decision criterion. Our experiments reveal this simple solution optimally balances cost and performance, outperforming existing methods on 25 out of 27 experimental setups.
  arXiv  Detail & Related papers  (2024-05-03T14:38:59Z)
• Assessing Economic Viability: A Comparative Analysis of Total Cost of Ownership for Domain-Adapted Large Language Models versus State-of-the-art Counterparts in Chip Design Coding Assistance [10.364901568556435]
  This paper presents a comparative analysis of total cost of ownership (TCO) and performance between domain-adapted large language models (LLM) and state-of-the-art (SoTA) LLMs.
  arXiv  Detail & Related papers  (2024-04-12T23:37:56Z)
• SMART: Automatically Scaling Down Language Models with Accuracy Guarantees for Reduced Processing Fees [21.801053526411415]
  Large Language Models (LLMs) have significantly boosted performance in natural language processing (NLP) tasks. The deployment of high-performance LLMs incurs substantial costs, primarily due to the increased number of parameters aimed at enhancing model performance. We introduce SMART, a novel framework designed to minimize the inference costs of NLP tasks while ensuring sufficient result quality.
  arXiv  Detail & Related papers  (2024-03-11T17:45:47Z)
• Switching the Loss Reduces the Cost in Batch (Offline) Reinforcement Learning [57.154674117714265]
  We show that the number of samples needed to learn a near-optimal policy with FQI-log scales with the accumulated cost of the optimal policy. We empirically verify that FQI-log uses fewer samples than FQI trained with squared loss on problems where the optimal policy reliably achieves the goal.
  arXiv  Detail & Related papers  (2024-03-08T15:30:58Z)
• Towards Optimizing the Costs of LLM Usage [4.032848774697859]
  We study optimization problems trading off the quality and costs, both theoretically and empirically. We propose several deterministics for reducing tokens in a quality aware manner. Our methods reduce costs by 40%- 90% while improving quality by 4%-7%.
  arXiv  Detail & Related papers  (2024-01-29T16:36:31Z)
• Large Language Model Cascades with Mixture of Thoughts Representations for Cost-efficient Reasoning [19.472937476936636]
  Large language models (LLMs) have exhibited remarkable performance in a variety of tasks, but this strong performance often comes with the high expense of using paid API services. In this paper, we are motivated to study building an LLM cascade to save the cost of using LLMs. Our proposed cascades can achieve performance comparable to using solely the stronger LLM but require only 40% of its cost.
  arXiv  Detail & Related papers  (2023-10-04T18:21:17Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.