# Sample Complexity and Representation Ability of Test-time Scaling Paradigms

arXiv: https://arxiv.org/abs/2506.05295 · HTML: https://mlsanity.com/paper/2506.05295/

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- Placed in Test-time compute and efficient thinking, one of 17 directions in LLM reasoning.
- Builds on 83 of its 107 references that are in the map.
- First posted on arXiv 5 Jun 2025.

## Placed in

- LLM reasoning / [Test-time compute and efficient thinking](https://mlsanity.com/lr/test-time-compute-and-efficient-thinking/)

## Builds on (most cited first, 30 of 83)

- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [The Llama 3 Herd of Models](https://mlsanity.com/paper/2407.21783/) (2024)
- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [Training Verifiers to Solve Math Word Problems](https://mlsanity.com/paper/2110.14168/) (2021)
- [Qwen3 Technical Report](https://mlsanity.com/paper/2505.09388/) (2025)
- [Scaling Laws for Neural Language Models](https://mlsanity.com/paper/2001.08361/) (2020)
- [Self-Consistency Improves Chain of Thought Reasoning in Language Models](https://mlsanity.com/paper/2203.11171/) (2022)
- [Measuring Mathematical Problem Solving With the MATH Dataset](https://mlsanity.com/paper/2103.03874/) (2021)
- [PaLM: Scaling Language Modeling with Pathways](https://mlsanity.com/paper/2204.02311/) (2022)
- [Self-Refine: Iterative Refinement with Self-Feedback](https://mlsanity.com/paper/2303.17651/) (2023)
- [Sparks of Artificial General Intelligence: Early experiments with GPT-4](https://mlsanity.com/paper/2303.12712/) (2023)
- [Efficient Streaming Language Models with Attention Sinks](https://mlsanity.com/paper/2309.17453/) (2023)
- [Big Bird: Transformers for Longer Sequences](https://mlsanity.com/paper/2007.14062/) (2020)
- [Kimi k1.5: Scaling Reinforcement Learning with LLMs](https://mlsanity.com/paper/2501.12599/) (2025)
- [Large Language Monkeys: Scaling Inference Compute with Repeated Sampling](https://mlsanity.com/paper/2407.21787/) (2024)
- [Teaching Large Language Models to Self-Debug](https://mlsanity.com/paper/2304.05128/) (2023)
- [In-context Learning and Induction Heads](https://mlsanity.com/paper/2209.11895/) (2022)
- [CRITIC: Large Language Models Can Self-Correct with Tool-Interactive Critiquing](https://mlsanity.com/paper/2305.11738/) (2023)
- [Transformers learn in-context by gradient descent](https://mlsanity.com/paper/2212.07677/) (2022)
- [What Can Transformers Learn In-Context? A Case Study of Simple Function Classes](https://mlsanity.com/paper/2208.01066/) (2022)
- [What learning algorithm is in-context learning? Investigations with linear models](https://mlsanity.com/paper/2211.15661/) (2022)
- [Do NOT Think That Much for 2+3=? On the Overthinking of o1-Like LLMs](https://mlsanity.com/paper/2412.21187/) (2024)
- [Training Language Models to Self-Correct via Reinforcement Learning](https://mlsanity.com/paper/2409.12917/) (2024)
- [Are Transformers universal approximators of sequence-to-sequence functions?](https://mlsanity.com/paper/1912.10077/) (2019)
- [L1: Controlling How Long A Reasoning Model Thinks With Reinforcement Learning](https://mlsanity.com/paper/2503.04697/) (2025)
- [ReST-MCTS*: LLM Self-Training via Process Reward Guided Tree Search](https://mlsanity.com/paper/2406.03816/) (2024)
- [Transformers as Statisticians: Provable In-Context Learning with In-Context Algorithm Selection](https://mlsanity.com/paper/2306.04637/) (2023)
- [Alphazero-like Tree-Search can Guide Large Language Model Decoding and Training](https://mlsanity.com/paper/2309.17179/) (2023)
- [Towards Revealing the Mystery behind Chain of Thought: A Theoretical Perspective](https://mlsanity.com/paper/2305.15408/) (2023)

## Built on by (most cited first, 12 of 12)

- [Best-of-Majority: Minimax-Optimal Strategy for Pass@k Inference Scaling](https://mlsanity.com/paper/2510.03199/) (2025)
- [Optimal Self-Consistency for Efficient Reasoning with Large Language Models](https://mlsanity.com/paper/2511.12309/) (2025)
- [Optimal Bayesian Stopping for Efficient Inference of Consistent LLM Answers](https://mlsanity.com/paper/2602.05395/) (2026)
- [On the Limits of Test-Time Compute: Sequential Reward Filtering for Better Inference](https://mlsanity.com/paper/2512.04558/) (2025)
- [Test-time Verification via Optimal Transport: Coverage, ROC, & Sub-optimality](https://mlsanity.com/paper/2510.18982/) (2025)
- [Demystifying LLM-as-a-Judge: Analytically Tractable Model for Inference-Time Scaling](https://mlsanity.com/paper/2512.19905/) (2025)
- [Spend Less, Fit Better: Budget-Efficient Scaling Law Fitting via Active Experiment Selection](https://mlsanity.com/paper/2604.22753/) (2026)
- [When does Chain-of-Thought Help: A Markovian Perspective](https://mlsanity.com/paper/2603.00306/) (2026)
- [Reward Learning from Best-of-N Preference Data: Targets, Tradeoffs, and Design Principles](https://mlsanity.com/paper/2605.30619/) (2026)
- [FluxLite: Inference-Time Proposal Control for Discrete Diffusion Models](https://mlsanity.com/paper/2609.35947/) (2026)
- [Adaptive Self-Consistency: From Black-Box Sampling to Distribution-Valued Feedback](https://mlsanity.com/paper/2609.38931/) (2026)
- [From Discovery to Decision: Finite-Budget Recoverability in LLM Voting](https://mlsanity.com/paper/2610.01014/) (2026)

## Abstract (arXiv)

Test-time scaling paradigms have significantly advanced the capabilities of large language models (LLMs) on complex tasks. Despite their empirical success, theoretical understanding of the sample efficiency of various test-time strategies -- such as self-consistency, best-of-n, and self-correction -- remains limited. In this work, we first establish a separation result between two repeated sampling strategies: self-consistency requires Theta(1/Delta2) samples to produce the correct answer, while best-of-n only needs Theta(1/Delta), where Delta < 1 denotes the probability gap between the correct and second most likely answers. Next, we present an expressiveness result for the self-correction approach with verifier feedback: it enables Transformers to simulate online learning over a pool of experts at test time. Therefore, a single Transformer architecture can provably solve multiple tasks without prior knowledge of the specific task associated with a user query, extending the representation theory of Transformers from single-task to multi-task settings. Finally, we empirically validate our theoretical results, demonstrating the practical effectiveness of self-correction methods.