# Plan and Budget: Effective and Efficient Test-Time Scaling on Reasoning Large Language Models

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

## Key facts

- Cited by 32 papers in the map (data through 14 Oct 2026).
- Placed in Test-time compute and efficient thinking, one of 17 directions in LLM reasoning.
- Builds on 38 of its 45 references that are in the map.
- First posted on arXiv 22 May 2025.

## Placed in

- LLM reasoning / [Test-time compute and efficient thinking](https://mlsanity.com/lr/test-time-compute-and-efficient-thinking/)

## Builds on (most cited first, 30 of 38)

- [The Llama 3 Herd of Models](https://mlsanity.com/paper/2407.21783/) (2024)
- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [Scaling Laws for Neural Language Models](https://mlsanity.com/paper/2001.08361/) (2020)
- [DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learning](https://mlsanity.com/paper/2501.12948/) (2025)
- [Self-Consistency Improves Chain of Thought Reasoning in Language Models](https://mlsanity.com/paper/2203.11171/) (2022)
- [Dropout as a Bayesian Approximation: Representing Model Uncertainty in Deep Learning](https://mlsanity.com/paper/1506.02142/) (2015)
- [Simple and Scalable Predictive Uncertainty Estimation using Deep Ensembles](https://mlsanity.com/paper/1612.01474/) (2016)
- [Let's Verify Step by Step](https://mlsanity.com/paper/2305.20050/) (2023)
- [Training Compute-Optimal Large Language Models](https://mlsanity.com/paper/2203.15556/) (2022)
- [Scaling LLM Test-Time Compute Optimally can be More Effective than Scaling Model Parameters](https://mlsanity.com/paper/2408.03314/) (2024)
- [Learn to Explain: Multimodal Reasoning via Thought Chains for Science Question Answering](https://mlsanity.com/paper/2209.09513/) (2022)
- [s1: Simple test-time scaling](https://mlsanity.com/paper/2501.19393/) (2025)
- [Language Models Don't Always Say What They Think: Unfaithful Explanations in Chain-of-Thought Prompting](https://mlsanity.com/paper/2305.04388/) (2023)
- [Aleatoric and Epistemic Uncertainty in Machine Learning: An Introduction to Concepts and Methods](https://mlsanity.com/paper/1910.09457/) (2019)
- [Super-NaturalInstructions: Generalization via Declarative Instructions on 1600+ NLP Tasks](https://mlsanity.com/paper/2204.07705/) (2022)
- [Galactica: A Large Language Model for Science](https://mlsanity.com/paper/2211.09085/) (2022)
- [Do NOT Think That Much for 2+3=? On the Overthinking of o1-Like LLMs](https://mlsanity.com/paper/2412.21187/) (2024)
- [Stop Overthinking: A Survey on Efficient Reasoning for Large Language Models](https://mlsanity.com/paper/2503.16419/) (2025)
- [TravelPlanner: A Benchmark for Real-World Planning with Language Agents](https://mlsanity.com/paper/2402.01622/) (2024)
- [Chain of Draft: Thinking Faster by Writing Less](https://mlsanity.com/paper/2502.18600/) (2025)
- [Inference Scaling Laws: An Empirical Analysis of Compute-Optimal Inference for Problem-Solving with Language Models](https://mlsanity.com/paper/2408.00724/) (2024)
- [Large Language Models for Mathematical Reasoning: Progresses and Challenges](https://mlsanity.com/paper/2402.00157/) (2024)
- [Token-Budget-Aware LLM Reasoning](https://mlsanity.com/paper/2412.18547/) (2024)
- [MathPrompter: Mathematical Reasoning using Large Language Models](https://mlsanity.com/paper/2303.05398/) (2023)
- [Thoughts Are All Over the Place: On the Underthinking of o1-Like LLMs](https://mlsanity.com/paper/2501.18585/) (2025)
- [How Well do LLMs Compress Their Own Chain-of-Thought? A Token Complexity Approach](https://mlsanity.com/paper/2503.01141/) (2025)
- [OlympicArena: Benchmarking Multi-discipline Cognitive Reasoning for Superintelligent AI](https://mlsanity.com/paper/2406.12753/) (2024)
- [FinGPT: Instruction Tuning Benchmark for Open-Source Large Language Models in Financial Datasets](https://mlsanity.com/paper/2310.04793/) (2023)
- [Efficiently Scaling LLM Reasoning with Certaindex](https://mlsanity.com/paper/2412.20993/) (2024)
- [Is In-Context Learning in Large Language Models Bayesian? A Martingale Perspective](https://mlsanity.com/paper/2406.00793/) (2024)

## Built on by (most cited first, 30 of 32)

- [JanusVLN: Decoupling Semantics and Spatiality with Dual Implicit Memory for Vision-Language Navigation](https://mlsanity.com/paper/2509.22548/) (2025)
- [Think with 3D: Geometric Imagination Grounded Spatial Reasoning from Limited Views](https://mlsanity.com/paper/2510.18632/) (2025)
- [A Survey on Large Language Models for Mathematical Reasoning](https://mlsanity.com/paper/2506.08446/) (2025)
- [Don't Overthink It: A Survey of Efficient R1-style Large Reasoning Models](https://mlsanity.com/paper/2508.02120/) (2025)
- [LoRA-Mixer: Coordinate Modular LoRA Experts Through Serial Attention Routing](https://mlsanity.com/paper/2507.00029/) (2025)
- [Towards Concise and Adaptive Thinking in Large Reasoning Models: A Survey](https://mlsanity.com/paper/2507.09662/) (2025)
- [DynaWeb: Model-Based Reinforcement Learning of Web Agents](https://mlsanity.com/paper/2601.22149/) (2026)
- [ProphetKV: User-Query-Driven Selective Recomputation for Efficient KV Cache Reuse in Retrieval-Augmented Generation](https://mlsanity.com/paper/2602.02579/) (2026)
- [From Efficiency to Adaptivity: A Deeper Look at Adaptive Reasoning in Large Language Models](https://mlsanity.com/paper/2511.10788/) (2025)
- [OckBench: Measuring the Efficiency of LLM Reasoning](https://mlsanity.com/paper/2511.05722/) (2025)
- [BeyondBench: Contamination-Resistant Evaluation of Reasoning in Language Models](https://mlsanity.com/paper/2509.24210/) (2025)
- [ROI-Reasoning: Rational Optimization for Inference via Pre-Computation Meta-Cognition](https://mlsanity.com/paper/2601.03822/) (2026)
- [Neural Chain-of-Thought Search: Searching the Optimal Reasoning Path to Enhance Large Language Models](https://mlsanity.com/paper/2601.11340/) (2026)
- [RoboRouter: Training-Free Policy Routing for Robotic Manipulation](https://mlsanity.com/paper/2603.07892/) (2026)
- [From Chatbot to Digital Colleague: The Paradigm Shift Toward Persistent Autonomous AI](https://mlsanity.com/paper/2606.14502/) (2026)
- [Do LLMs Overthink Basic Math Reasoning? Benchmarking the Accuracy-Efficiency Tradeoff in Language Models](https://mlsanity.com/paper/2507.04023/) (2025)
- [Prototype-Aligned Federated Soft-Prompts for Continual Web Personalization](https://mlsanity.com/paper/2603.27678/) (2026)
- [The Thinking Spectrum: An Empirical Study of Tunable Reasoning in LLMs through Model Merging](https://mlsanity.com/paper/2509.22034/) (2025)
- [Let's Think with Images Efficiently! An Interleaved-Modal Chain-of-Thought Reasoning Framework with Dynamic and Precise Visual Thoughts](https://mlsanity.com/paper/2603.21754/) (2026)
- [Adaptive Test-Time Reasoning via Reward-Guided Dual-Phase Search](https://mlsanity.com/paper/2509.25420/) (2025)
- [PETS: A Principled Framework Towards Optimal Trajectory Allocation for Efficient Test-Time Self-Consistency](https://mlsanity.com/paper/2602.16745/) (2026)
- [DiagnoLLM: A Hybrid Bayesian Neural Language Framework for Interpretable Disease Diagnosis](https://mlsanity.com/paper/2511.05810/) (2025)
- [FutureWeaver: Planning Test-Time Compute for Multi-Agent Systems with Modularized Collaboration](https://mlsanity.com/paper/2512.11213/) (2025)
- [A State-Transition Framework for Efficient LLM Reasoning](https://mlsanity.com/paper/2602.01198/) (2026)
- [TraceDev: A Traceability-Driven Multi-agent Framework for Requirement-to-Code Development](https://mlsanity.com/paper/2607.18886/) (2026)
- [Beyond More Context: Retrieval Diversity Boosts Multi-Turn Intent Understanding](https://mlsanity.com/paper/2510.17940/) (2025)
- [Avoiding Overthinking and Underthinking: Curriculum-Aware Budget Scheduling for LLMs](https://mlsanity.com/paper/2604.19780/) (2026)
- [LEAD: Length-Efficient Adaptive and Dynamic Reasoning for Large Language Models](https://mlsanity.com/paper/2605.09806/) (2026)
- [Efficient Chain-of-Modality Reasoning via Progressive Compression for Spoken Language Models](https://mlsanity.com/paper/2607.19932/) (2026)
- [Reasoning or Memorization: Can LLMs Understand and Generate Chinese Xiehouyu Riddles?](https://mlsanity.com/paper/2607.23440/) (2026)

## Abstract (arXiv)

Large Language Models (LLMs) have achieved remarkable success in complex reasoning tasks, but their inference remains computationally inefficient. We observe a common failure mode in many prevalent LLMs, overthinking, where models generate verbose and tangential reasoning traces even for simple queries. Recent work has tried to mitigate this by enforcing fixed token budgets, however, this can lead to underthinking, especially on harder problems. Through empirical analysis, we identify that this inefficiency often stems from unclear problem-solving strategies. To formalize this, we develop a theoretical model, BAM (Budget Allocation Model), which models reasoning as a sequence of sub-questions with varying uncertainty, and introduce the E3 metric to capture the trade-off between correctness and computation efficiency. Building on theoretical results from BAM, we propose Plan-and-Budget, a model-agnostic, test-time framework that decomposes complex queries into sub-questions and allocates token budgets based on estimated complexity using adaptive scheduling. Plan-and-Budget improves reasoning efficiency across a range of tasks and models, achieving up to 70% accuracy gains, 39% token reduction, and 193.8% improvement in E3. Notably, it improves the efficiency of a smaller model (DS-Qwen-32B) to match the efficiency of a larger model (DS-LLaMA-70B), demonstrating Plan-and-Budget's ability to close performance gaps without retraining. Our code is available at https://github.com/junhongmit/P-and-B.