Research map / Large language models / Reasoning and chain of thought

OptScale: Probabilistic Optimality for Inference-time Scaling

AAAI 2026 · Large language models › Reasoning and chain of thought · approach: Test-time compute scaling · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes OptScale, a probabilistic framework that derives a lower bound on the number of i.i.d. best-of-N samples needed for a target quality and confidence, and an adaptive algorithm (trained-predictor or training-free MLE/MAP variants) that stops sampling early to cut tokens.

Problem

Parallel inference-time scaling (Best-of-N, self-consistency) relies on heuristic choices of the number of samples N, lacking a principled way to decide how many samples are needed, which wastes tokens on easy questions and is costly on hard ones.

Approach

Model verifier (PRM) scores as a truncated normal random variable; the max of N i.i.d. scores has CDF F^N, giving a closed-form minimal N* = ceil(log(1-alpha)/log F(s_min)). Parameters (mu, sigma) are estimated either by MLE/MAP from observed scores (training-free) or with an MLP predictor providing priors (trainable), and sampling stops once N >= N*.

Key results

• On Deepseek-R1-Distill-Qwen-7B with N=64, OptScale^0 and OptScale^t reach 94.6% on MATH-500 while saving 37.0% and 56.3% tokens versus Best-of-N.
• On QwQ-32B, OptScale reduces tokens by about 45.0% (OptScale^0) and 38.5% (OptScale^t) on average across benchmarks versus the best baseline.
• On QwQ-32B with GSM8K, OptScale^0 reaches 95.9% accuracy, a level BoN does not reach even at large token budgets.

Surprising findings

• Choosing a very high quality threshold (e.g., 0.99) harms token efficiency, so the method's cost grows steeply near 100% thresholds.
• Multi-round thinking (MR-Thinking) underperforms simple Best-of-N substantially on Llama-3.1-8B-Instruct (e.g., 40.8% vs 68.8% on MATH-500 at N=64).

Limitations

• Relies on the i.i.d. assumption of parallel samples; correlation among samples is only tested empirically via temperature.
• Truncated normal approximation fails for multi-peaked or very narrow score distributions.
• Results depend on a PRM verifier (Qwen2.5-Math-PRM-7B) and hyperparameters (s_min, alpha) that must be chosen per dataset.

Experimental setup

Datasets: MATH training set

Benchmarks: MATH-500 GSM8K AIME 2024 AIME 2025 AMC 2023

Metrics: accuracy completion tokens

Baselines: Best-of-N Self-Consistency MR-Thinking Adaptive Self-Consistency Early-stopping Self-Consistency Difficulty-Adaptive Self-Consistency

Builds on: Best-of-N Self-Consistency Qwen2.5-Math-PRM-7B

Closest papers by meaning

• Inference Scaling Laws: An Empirical Analysis of Compute-Optimal Inference for LLM Problem-Solving (ICLR 2025 · similarity 0.92)
• Parallel Scaling Law for Language Models (NeurIPS 2025 · similarity 0.91)
• Scaling Inference-Efficient Language Models (ICML 2025 · similarity 0.91)
• Rollout Roulette: A Probabilistic Inference Approach to Inference-Time Scaling of LLMs using Particle-Based Monte Carlo Methods (NeurIPS 2025 · similarity 0.90)
• Scaling Laws Meet Model Architecture: Toward Inference-Efficient LLMs (ICLR 2026 · similarity 0.90)
• Provable Scaling Laws for the Test-Time Compute of Large Language Models (NeurIPS 2025 · similarity 0.90)