Inference-Time Compute & Search Scaling

Inference-Time Compute Scaling Laws (underpinning OpenAI o1 and DeepSeek-R1) formalizes the second paradigm of scaling: trading test-time compute FLOPs for sustained logarithmic/power-law accuracy gains on complex reasoning benchmarks; unlike standard single-pass greedy decoding, Inference-Time Scaling expands compute along 3 primary dimensions: 1) Best-of-$N$ Sampling with Outcome/Process Reward Verifiers (sampling $N$ parallel rollouts and selecting the highest-scoring trajectory); 2) Sequential Tree Search & MCTS (expanding reasoning search trees over thought tokens with dynamic value pruning); 3) Autoregressive Long CoT Self-Correction (allowing the policy to generate recursive backtracking tokens to self-correct reasoning flaws before committing to final answers).

International Mathematical Olympiad (IMO) theorem proving, competitive programming synthesis, and scientific hypothesis deduction.

Complex multi-step reasoning collapses under System-1 instantaneous next-token prediction; Inference-Time compute unlocks deliberative System-2 planning, reflection, and algorithmic search.

Compare Best-of-$N$, Beam Search, and MCTS in scaling curves of test-time compute versus Pass@1 accuracy gains?

Why do Process Reward Models (PRM) outperform Outcome Reward Models (ORM) in guiding intermediate tree search branches?

How does pure reinforcement learning with rule-based verifiers induce the emergence of long-chain self-correction and backtracking?

Derive the compute trade-off showing how test-time reasoning compute allows a small 1.5B model to surpass a zero-shot 70B monolithic model on math?

How to prevent test-time search from exploiting adversarial vulnerabilities in learned Reward Models when $N$ scales into thousands?