Reasoning Inference-Time Scaling Search & RL

Test-Time Compute

The paradigm of trading computational budget (FLOPs, tokens, or search paths) at inference time to systematically scale model reasoning and accuracy.

In One Sentence

"Instead of generating answers in a single forward pass, test-time compute allows models to dynamically allocate extra processing power during inference—via internal thinking chains, search algorithms, or step-by-step verification—to solve complex, multi-step problems."

Intuition

Standard autoregressive language models spend the exact same amount of compute per token, regardless of whether they are answering "What is 2+2?" or "Prove the Riemann Hypothesis." This is highly inefficient; hard problems require planning, drafting, checking for errors, and revising.

Test-time compute scaling shifts the paradigm from purely scaling *pre-training parameter counts* to scaling *inference-time computation*. By allowing a model to generate intermediate reasoning tokens (a "chain of thought" or "thinking trajectory"), evaluate its own steps, or explore multiple solution paths, we can unlock dramatic performance gains without retraining the base model parameters.

Standard Inference

The model immediately begins generating the final answer. If it makes a mistake in token 3, it is mathematically forced to build its entire remaining response on top of that error.

Test-Time Compute Inference

The model generates an internal "thinking trace" first. It can backtrack, say "Wait, let me double check," correct its logic, and only output the final answer once it is verified.

Formal Definition

Let $x$ be the input prompt and $y$ be the final answer. In standard decoding, we sample directly from the model's policy:

$$y \sim P_\theta(y \mid x)$$

With test-time compute, we introduce intermediate reasoning steps (or a "thinking trajectory") $z = (z_1, z_2, \dots, z_T)$. The generation process is split into two phases:

Trajectory Generation: Generating the reasoning path $z \sim P_\theta(z \mid x)$.
Verification & Selection: Mapping the trajectory to the final answer $y \sim P_\theta(y \mid x, z)$.

We can scale this process using two primary mathematical formulations:

1. Process-Supervised Verification (PRM)

Instead of scoring only the final outcome, a Process Reward Model (PRM) evaluates each step $z_t$ of the trajectory:

$$R_{\text{PRM}}(z_t \mid x, z_{

The optimal trajectory $z^*$ is selected by searching a tree of generated steps to maximize the cumulative path score:

$$z^* = \operatorname{argmax}_{z} \prod_{t=1}^T R_{\text{PRM}}(z_t \mid x, z_{

2. Budget Forcing

Rather than external searching, we can directly manipulate the generation probability of the model's internal thinking length. By prepending or appending specific tokens (e.g., "Wait"), we force the model to continue reasoning:

$$P_{\text{forced}}(z_{t+1} \mid x, z_{\le t}) = P_\theta(z_{t+1} \mid x, z_{\le t}, \text{"Wait"})$$

Interactive Budget Forcing Simulator

Adjust the test-time compute budget slider below to see how a model's internal thinking trace changes when forced to spend more compute on a tricky math comparisons problem: "Which is larger, 9.11 or 9.9?"

Test-Time Compute Budget Low (Zero-Shot)

No thinking (Fast) Medium (Chain of Thought) High (Budget Forcing)

Prompt: Which is larger, 9.11 or 9.9?

Trade-offs & Decisions

When to Use

Complex Reasoning: Competitive mathematics, complex software engineering, and logical puzzles.
Verifiable Tasks: Tasks where checking an answer is much easier than generating it (e.g., code execution, math proofs).
High-Stakes Decisions: Medical diagnostics or legal analysis where accuracy is far more critical than latency.

When to Avoid

Low-Latency APIs: Real-time applications like conversational chatbots or autocomplete.
Simple Retrieval: Basic question answering or factual lookups where deeper thinking adds no value.
Tight Compute Budgets: Environments where token generation costs must be strictly minimized.

History & Evolution

May 2023

Process Supervision (PRM800K)

OpenAI researchers publish "Let's Verify Step by Step", showing that process-level supervision (scoring individual steps) dramatically outperforms outcome-level supervision on complex math problems.

January 2025

Emergent RL Reasoning (DeepSeek-R1)

DeepSeek demonstrates that reasoning capabilities (self-reflection, verification, and dynamic strategy adaptation) can emerge purely through large-scale reinforcement learning without relying on human demonstrations.

January 2025

Simple Test-Time Scaling (s1)

Researchers introduce the s1 project, showing that test-time compute can be scaled programmatically via "budget forcing" (heuristically injecting "Wait" tokens) on top of a lightweight supervised-finetuned model.

Implementation

A clean Python implementation of Budget Forcing decoding, demonstrating how we can dynamically inject "Wait" tokens to extend a model's thinking trace.

budget_forcing.py Python 3.10+

import torch
from transformers import AutoModelForCausalLM, AutoTokenizer

def generate_with_budget_forcing(model, tokenizer, prompt, min_thinking_steps=3):
    # 1. Format prompt to initiate thinking phase
    input_text = f"<prompt>{prompt}</prompt>\n<think>"
    inputs = tokenizer(input_text, return_tensors="pt").to(model.device)
    
    thinking_steps = 0
    
    while thinking_steps < min_thinking_steps:
        # Generate next chunk of reasoning
        outputs = model.generate(**inputs, max_new_tokens=64, return_dict_in_generate=True)
        generated_tokens = outputs.sequences[0, inputs.input_ids.shape[1]:]
        generated_text = tokenizer.decode(generated_tokens)
        
        if "</think>" in generated_text:
            # Model tried to stop thinking too early! Force it to continue
            thinking_steps += 1
            
            # Strip out the closing tag and append a "Wait..." nudge
            clean_text = generated_text.replace("</think>", "")
            input_text += clean_text + " Wait, let me double check..."
            inputs = tokenizer(input_text, return_tensors="pt").to(model.device)
        else:
            # Normal thinking progression
            input_text += generated_text
            inputs = tokenizer(input_text, return_tensors="pt").to(model.device)
            break
            
    # Append closing tag if not present and generate final answer
    if "</think>" not in input_text:
        input_text += " </think>"
        
    inputs = tokenizer(input_text, return_tensors="pt").to(model.device)
    final_outputs = model.generate(**inputs, max_new_tokens=128)
    return tokenizer.decode(final_outputs[0])

Common Variants

Best-of-N Sampling

Generates $N$ independent candidate trajectories and uses a verifier or outcome reward model to select the highest-scoring complete answer.

Tree Search (MCTS)

Uses Monte Carlo Tree Search guided by step-level process reward models (PRMs) to systematically explore and prune reasoning paths.

Budget Forcing

A heuristic method that forces the model to lengthen or terminate its internal thinking process by appending specific control tokens.

Foundational Architectures

While test-time compute is a modern paradigm, it is built directly on top of foundational transformer architectures and prompt methodologies:

yudgctsnk7

Attention Is All You Need

The core Transformer architecture which enables autoregressive sequence generation, the bedrock of all modern reasoning models.

ryhchkpe82

Language Models are Few-Shot Learners

Introduced GPT-3 and established the baseline for few-shot prompting, which modern test-time compute methods dramatically scale.

Grounding References

arXiv:2501.19393
s1: Simple test-time scaling — Introduces budget forcing and the s1K dataset.
arXiv:2305.20050
Let's Verify Step by Step — Establishes process-supervised reward modeling (PRM800K).
arXiv:2501.12948
DeepSeek-R1 — Demonstrates emergent reasoning patterns via reinforcement learning.