plan-budget-reasoning

name	plan-budget-reasoning
title	Plan and Budget: Effective and Efficient Test-Time Scaling on Large Language Model Reasoning
version	0.0.2
engine	skillxiv-v0.0.2-claude-opus-4.6
license	MIT
url	https://arxiv.org/abs/2505.16122
keywords	["test-time compute","reasoning","token allocation","efficiency","LLMs"]
description	Decompose complex queries into sub-questions and allocate computational budgets adaptively based on estimated difficulty, achieving 70% accuracy improvements and 39% token reduction without retraining.

Plan and Budget: Effective and Efficient Test-Time Scaling on Language Model Reasoning

Core Concept

Plan and Budget addresses the "overthinking" problem in language model reasoning: models generate excessively verbose outputs using computational resources inefficiently. The framework decomposes complex queries into sub-questions with varying uncertainty levels, then allocates tokens adaptively to each sub-problem based on estimated difficulty.

Rather than applying uniform computation across all reasoning steps, the approach identifies which sub-questions require more reasoning effort and concentrates tokens there, while keeping straightforward sub-questions brief. This test-time strategy is model-agnostic and requires no retraining, achieving both higher accuracy and reduced token consumption.

Architecture Overview

• Query Decomposition: Break complex questions into simpler, solvable sub-questions
• Difficulty Estimation: Predict which sub-questions require more computational effort
• Budget Allocation Model (BAM): Distribute token budget across sub-questions based on estimated difficulty
• Efficiency-Effectiveness Tradeoff (E3 Metric): Measure combined improvement in accuracy and token efficiency
• Dynamic Scheduling: Adapt token allocation in real-time during generation
• Model-Agnostic Application: Works with any reasoner without architectural changes

Implementation

The following steps outline how to implement adaptive budget allocation for reasoning:

1. Decompose the query - Break complex questions into sub-question components
2. Estimate sub-question difficulty - Assess which parts require more reasoning
3. Allocate token budget - Distribute available tokens proportionally to difficulty
4. Generate reasoning - Process each sub-question with allocated token budget
5. Synthesize answer - Combine sub-question responses into final answer
6. Measure efficiency - Track accuracy and token usage for optimization

from typing import List, Dict, Tuple
from dataclasses import dataclass
import torch

@dataclass
 :
    text: 
    estimated_difficulty: 
    allocated_tokens: 
    response:  = 

 :
     ():
        .model = decomposition_model

     () -> []:
        
        prompt = 

        response = .model.generate(prompt, max_tokens=)
        sub_questions = ._parse_sub_questions(response)
         sub_questions

     () -> []:
        
        lines = response.split()
        sub_questions = []
         line  lines:
            line = line.strip()
             line  (c.isdigit()  c  line[:]):
                
                question = line.lstrip().strip()
                 question:
                    sub_questions.append(question)
         sub_questions


 :
     ():
        .model = estimation_model

     () -> :
        
        prompt = 

        response = .model.generate(prompt, max_tokens=)
        :
            difficulty = (response.strip())
             (, (, difficulty))
        :
               


 :
     ():
        .base_budget = base_budget

     () -> [SubQuestion]:
        
          sub_questions:
             []

        
        min_tokens = 
        total_difficulty = (sq.estimated_difficulty  sq  sub_questions)

        
         total_difficulty == :
            total_difficulty = (sub_questions)

        
         sq  sub_questions:
            proportion = sq.estimated_difficulty / total_difficulty
            allocated = (.base_budget * proportion)
            sq.allocated_tokens = (min_tokens, allocated)

         sub_questions


 :

     () -> :
        
        accuracy_improvement = (optimized_accuracy - baseline_accuracy) / baseline_accuracy
        token_reduction =  - (optimized_tokens / baseline_tokens)

        
        e3 = accuracy_improvement + token_reduction
         e3


 :
     ():
        .decomposer = decomposer
        .estimator = estimator
        .allocator = allocator
        .reasoner = reasoner_model

     () -> :
        
        
        sub_question_texts = .decomposer.decompose(query)
        sub_questions = [SubQuestion(text=sq, estimated_difficulty=, allocated_tokens=)
                         sq  sub_question_texts]

        
         sq  sub_questions:
            sq.estimated_difficulty = .estimator.estimate(sq.text)

        
        allocator = BudgetAllocator(total_budget)
        sub_questions = allocator.allocate(sub_questions)

        
        total_tokens_used = 
         sq  sub_questions:
            response = .reasoner.generate(sq.text, max_tokens=sq.allocated_tokens)
            sq.response = response
            total_tokens_used += (response.split())

        
        final_answer = ._synthesize(query, sub_questions)

         {
            : query,
            : sub_questions,
            : final_answer,
            : total_tokens_used,
            : total_tokens_used / total_budget
        }

     () -> :
        
        context = .join([  sq  sub_questions])
        prompt = 

        final_answer = .reasoner.generate(prompt, max_tokens=)
         final_answer