title: Plan and Budget: Effective and Efficient Test-Time Scaling on Large
    Language Model Reasoning
summary: 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/.
paper_authors._id: 683f4eaacd9938eb060f931d
paper_authors.name: Junhong Lin
paper_authors.status: extracted_confirmed
paper_authors.statusLastChangedAt: 2025-06-03T19:58:21.759Z
paper_authors._id: 6660de6a78c9d00c8d3bebfd
paper_authors.avatarUrl: /avatars/77a77185e9e3d9a92ab5f35dfe76a1fc.svg
paper_authors.fullname: Junhong Lin
paper_authors.type: user
paper_authors.user: junhongmit
paper_authors._id: 683f4eaacd9938eb060f931e
paper_authors.name: Xinyue Zeng
paper_authors.status: claimed_verified
paper_authors.statusLastChangedAt: 2025-06-04T09:01:07.557Z
paper_authors._id: 66feb5c3d74232f132ea11ba
paper_authors.avatarUrl: /avatars/683bb03e904d85585cc5fe901b2f2d7c.svg
paper_authors.fullname: Xinyue Zeng
paper_authors.type: user
paper_authors.user: xyzeng2000
paper_authors._id: 683f4eaacd9938eb060f931f
paper_authors.name: Jie Zhu
paper_authors._id: 683f4eaacd9938eb060f9320
paper_authors.name: Song Wang
paper_authors._id: 683f4eaacd9938eb060f9321
paper_authors.name: Julian Shun
paper_authors._id: 683f4eaacd9938eb060f9322
paper_authors.name: Jun Wu
paper_authors._id: 683f4eaacd9938eb060f9323
paper_authors.name: Dawei Zhou
paper_title: Plan and Budget: Effective and Efficient Test-Time Scaling on Large
    Language Model Reasoning
paper_summary: 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/.
paper_ai_summary: 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.
paper_ai_keywords: LLMs inference overthinking underthinking BBAM Bayesian Budget Allocation Model $E^3$ Plan-and-Budget reasoning efficiency accuracy gains token reduction