# Cost-Awareness in Tree-Search LLM Planning: A Systematic Study

arXiv: https://arxiv.org/abs/2505.14656 · HTML: https://mlsanity.com/paper/2505.14656/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 47 references that are in the map.
- First posted on arXiv 20 May 2025.

## Builds on (most cited first, 25 of 25)

- [ReAct: Synergizing Reasoning and Acting in Language Models](https://mlsanity.com/paper/2210.03629/) (2022)
- [ALFWorld: Aligning Text and Embodied Environments for Interactive Learning](https://mlsanity.com/paper/2010.03768/) (2020)
- [Inner Monologue: Embodied Reasoning through Planning with Language Models](https://mlsanity.com/paper/2207.05608/) (2022)
- [Reasoning with Language Model is Planning with World Model](https://mlsanity.com/paper/2305.14992/) (2023)
- [Language Agent Tree Search Unifies Reasoning Acting and Planning in Language Models](https://mlsanity.com/paper/2310.04406/) (2023)
- [Understanding the planning of LLM agents: A survey](https://mlsanity.com/paper/2402.02716/) (2024)
- [VirtualHome: Simulating Household Activities via Programs](https://mlsanity.com/paper/1806.07011/) (2018)
- [Describe, Explain, Plan and Select: Interactive Planning with Large Language Models Enables Open-World Multi-Task Agents](https://mlsanity.com/paper/2302.01560/) (2023)
- [TravelPlanner: A Benchmark for Real-World Planning with Language Agents](https://mlsanity.com/paper/2402.01622/) (2024)
- [PlanBench: An Extensible Benchmark for Evaluating Large Language Models on Planning and Reasoning about Change](https://mlsanity.com/paper/2206.10498/) (2022)
- [AdaPlanner: Adaptive Planning from Feedback with Language Models](https://mlsanity.com/paper/2305.16653/) (2023)
- [LLMs Can't Plan, But Can Help Planning in LLM-Modulo Frameworks](https://mlsanity.com/paper/2402.01817/) (2024)
- [ADaPT: As-Needed Decomposition and Planning with Language Models](https://mlsanity.com/paper/2311.05772/) (2023)
- [NATURAL PLAN: Benchmarking LLMs on Natural Language Planning](https://mlsanity.com/paper/2406.04520/) (2024)
- [SmartPlay: A Benchmark for LLMs as Intelligent Agents](https://mlsanity.com/paper/2310.01557/) (2023)
- [PlanGenLLMs: A Modern Survey of LLM Planning Capabilities](https://mlsanity.com/paper/2502.11221/) (2025)
- [Acting Less is Reasoning More! Teaching Model to Act Efficiently](https://mlsanity.com/paper/2504.14870/) (2025)
- [Put Your Money Where Your Mouth Is: Evaluating Strategic Planning and Execution of LLM Agents in an Auction Arena](https://mlsanity.com/paper/2310.05746/) (2023)
- [ISR-LLM: Iterative Self-Refined Large Language Model for Long-Horizon Sequential Task Planning](https://mlsanity.com/paper/2308.13724/) (2023)
- [Dualformer: Controllable Fast and Slow Thinking by Learning with Randomized Reasoning Traces](https://mlsanity.com/paper/2410.09918/) (2024)
- [Thought of Search: Planning with Language Models Through The Lens of Efficiency](https://mlsanity.com/paper/2404.11833/) (2024)
- [Inference-Time Computations for LLM Reasoning and Planning: A Benchmark and Insights](https://mlsanity.com/paper/2502.12521/) (2025)
- [SelfGoal: Your Language Agents Already Know How to Achieve High-level Goals](https://mlsanity.com/paper/2406.04784/) (2024)
- [CATP-LLM: Empowering Large Language Models for Cost-Aware Tool Planning](https://mlsanity.com/paper/2411.16313/) (2024)
- [PLANET: A Collection of Benchmarks for Evaluating LLMs' Planning Capabilities](https://mlsanity.com/paper/2504.14773/) (2025)

## Built on by (most cited first, 5 of 5)

- [Toward Efficient Agents: Memory, Tool learning, and Planning](https://mlsanity.com/paper/2601.14192/) (2026)
- [Cognitive Workspace: Active Memory Management for LLMs -- An Empirical Study of Functional Infinite Context](https://mlsanity.com/paper/2508.13171/) (2025)
- [Lookahead-R: Budget-Aware Tool Retrieval via Execution-Centric Planning](https://mlsanity.com/paper/2609.35811/) (2026)
- [CAMI: Cost-Aware Agent-Guided Multi-Indexing for Semantic Retrieval](https://mlsanity.com/paper/2606.28365/) (2026)
- [How Hard Does It Think? Analyzing Step-Aware Reasoning Energy in LLM Chain-of-Thought Trajectories](https://mlsanity.com/paper/2607.28674/) (2026)

## Abstract (arXiv)

Planning under resource constraints is central to real-world decision making, yet most large language model (LLM) planners assume uniform action costs. We systematically analyze whether tree-search LLM planners are cost-aware and whether they efficiently generate budget-feasible plans. In contrast to black-box prompting, explicit search trees expose intermediate decisions, node evaluations, and failure modes, which allows for controlled ablations of planner behavior. We study depth-first search, breadth-first search, Monte Carlo Tree Search, and bidirectional search within a unified framework. Our experiments show that existing tree-based LLM planners often struggle to find cost-optimal plans, and that additional search computation does not reliably improve optimality. Among the methods evaluated, bidirectional search achieves the best overall efficiency and success rate. MCTS achieves the highest optimality on short-horizon tasks. Tree-search planners are especially valuable for studying LLM planning because their reasoning steps are explicit, in contrast to plain LLMs that internalize planning dynamics through post-training trajectories. Our findings suggest that improving LLM planning under resource constraints will likely require new search algorithms, rather than solely scaling inference-time compute.