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

Sample Complexity and Representation Ability of Test-time Scaling Paradigms

ICLR 2026 · Large language models › Reasoning and chain of thought · approach: Test-time compute scaling

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.

Theoretically shows best-of-n needs Θ(1/Δ) samples versus Θ(1/Δ²) for self-consistency, and constructs general-purpose attention-only Transformers that, with verifier feedback during self-correction, simulate online learning over expert pools; validated on a synthetic 3-SAT copy/reverse task.

Problem

Sample efficiency of test-time scaling strategies (self-consistency, best-of-n, self-correction) and whether a single Transformer can express multiple tasks at inference time without knowing the task.

Approach

Separates sample complexity of self-consistency (Θ(1/Δ²)) from best-of-n (Θ(1/Δ)) via a probability-gap analysis, and builds a general-purpose Transformer whose self-correction with verifier rewards implements a bandit/regret-minimizing learner over a pool of experts, using attention sink and generalized position encodings.

Key results

• Theory: self-consistency requires Θ(1/Δ²) samples while best-of-n requires Θ(1/Δ) (up to log factors).
• Synthetic experiments: accuracy plateaus at 63.19% without test-time self-correction, while with verifier signals larger models (GPT-mini, Gopher-44M) reach near-perfect accuracy.
• Constructs a general-purpose Transformer that, via self-correction with verifier, achieves simple regret λ + reg(T) over a pool of K experts.

Limitations

• Construction applies only to attention-only Transformers
• Relies on a slightly generalized position encoding
• Experiments are small synthetic tasks rather than realistic LLM benchmarks

Experimental setup

Datasets: synthetic 3-SAT copy/reverse dataset

Benchmarks: synthetic 3-SAT copy/reverse task

Metrics: test accuracy

Baselines: self-consistency best-of-n

Builds on: self-consistency best-of-n sampling Berry-Esseen theorem minGPT

Closest papers by meaning

• A Theoretical Study on Bridging Internal Probability and Self-Consistency for LLM Reasoning (NeurIPS 2025 · similarity 0.90)
• Understanding the Role of Training Data in Test-Time Scaling (ICLR 2026 · similarity 0.90)
• Scaling Test-Time Compute Without Verification or RL is Suboptimal (ICML 2025 · similarity 0.89)
• Optimal Self-Consistency for Efficient Reasoning with Large Language Models (ICML 2026 · similarity 0.89)
• Representation Consistency for Accurate and Coherent LLM Answer Aggregation (NeurIPS 2025 · similarity 0.89)
• Provable Scaling Laws for the Test-Time Compute of Large Language Models (NeurIPS 2025 · similarity 0.89)