Plan and Budget: Effective and Efficient Test-Time Scaling on Large
  Language Model Reasoning
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 works have 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, BBAM (Bayesian Budget Allocation Model), which models
reasoning as a sequence of sub-questions with varying uncertainty, and
introduce the E^3 metric to capture the trade-off between correctness and
computation efficiency. Building on theoretical results from BBAM, 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 +187.5% improvement in E^3. Notably, it
elevates 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
anonymous.4open.science/r/P-and-B-6513/.
683f4eaacd9938eb060f931d
Junhong Lin
extracted_confirmed
2025-06-03T19:58:21.759Z
6660de6a78c9d00c8d3bebfd
/avatars/77a77185e9e3d9a92ab5f35dfe76a1fc.svg
Junhong Lin
user
junhongmit
683f4eaacd9938eb060f931e
Xinyue Zeng
claimed_verified
2025-06-04T09:01:07.557Z
66feb5c3d74232f132ea11ba
/avatars/683bb03e904d85585cc5fe901b2f2d7c.svg
Xinyue Zeng
user
xyzeng2000
683f4eaacd9938eb060f931f
Jie Zhu
683f4eaacd9938eb060f9320
Song Wang
683f4eaacd9938eb060f9321
Julian Shun
683f4eaacd9938eb060f9322
Jun Wu
683f4eaacd9938eb060f9323
Dawei Zhou
Plan and Budget: Effective and Efficient Test-Time Scaling on Large
  Language Model Reasoning
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 works have 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, BBAM (Bayesian Budget Allocation Model), which models
reasoning as a sequence of sub-questions with varying uncertainty, and
introduce the E^3 metric to capture the trade-off between correctness and
computation efficiency. Building on theoretical results from BBAM, 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 +187.5% improvement in E^3. Notably, it
elevates 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
anonymous.4open.science/r/P-and-B-6513/.
Plan-and-Budget framework enhances reasoning efficiency in LLMs by allocating token budgets based on estimated sub-question complexity, improving accuracy, reducing token usage, and boosting $E^3$ metric.
LLMs inference overthinking underthinking BBAM Bayesian Budget Allocation Model $E^3$ Plan-and-Budget reasoning efficiency accuracy gains token reduction