mlsanityData to 14 Oct 2026

Sample Complexity and Representation Ability of Test-time Scaling Paradigms

arXiv 2506.05295 ↗First posted 5 Jun 2025cs.LG cs.AI stat.MLcited by 12

On the map: LLM reasoning → Test-time compute and efficient thinking

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.

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.

Builds on

83 of 107 references.

Closest ancestors · 18

Same direction, newest first

  1. 2025L1: Controlling How Long A Reasoning Model Thinks With Reinforcement Learning6 Mar
  2. 2025Self-Training Elicits Concise Reasoning in Large Language Models27 Feb
  3. 2025On the Query Complexity of Verifier-Assisted Language Generation17 Feb
  4. 2025Scaling Test-Time Compute Without Verification or RL is Suboptimal17 Feb
  5. 2025The Danger of Overthinking: Examining the Reasoning-Action Dilemma in Agentic Tasks12 Feb
  6. 2025SETS: Leveraging Self-Verification and Self-Correction for Improved Test-Time Scaling31 Jan
  7. 2025Thoughts Are All Over the Place: On the Underthinking of o1-Like LLMs30 Jan
  8. 2024Do NOT Think That Much for 2+3=? On the Overthinking of o1-Like LLMs30 Dec
  9. 2024TreeBoN: Enhancing Inference-Time Alignment with Speculative Tree-Search and Best-of-N Sampling18 Oct
  10. 2024Interpretable Contrastive Monte Carlo Tree Search Reasoning2 Oct
  11. 2024Training Language Models to Self-Correct via Reinforcement Learning19 Sep
  12. 2024Inference Scaling Laws: An Empirical Analysis of Compute-Optimal Inference for Problem-Solving with Language Models1 Aug
6 more
  1. 2024When is the consistent prediction likely to be a correct prediction?8 Jul
  2. 2024Small Language Models Need Strong Verifiers to Self-Correct Reasoning26 Apr
  3. 2024Toward Self-Improvement of LLMs via Imagination, Searching, and Criticizing18 Apr
  4. 2023Alphazero-like Tree-Search can Guide Large Language Model Decoding and Training29 Sep
  5. 2023CRITIC: Large Language Models Can Self-Correct with Tool-Interactive Critiquing19 May
  6. 2023Self-Refine: Iterative Refinement with Self-Feedback30 Mar

Other references · 65

  1. 2020Language Models are Few-Shot Learnerscited by 32,419
  2. 2019PyTorch: An Imperative Style, High-Performance Deep Learning Librarycited by 20,305
  3. 2024The Llama 3 Herd of Modelscited by 14,715
  4. 2022Chain-of-Thought Prompting Elicits Reasoning in Large Language Modelscited by 12,459
  5. 2021Training Verifiers to Solve Math Word Problemscited by 10,109
  6. 2025Qwen3 Technical Reportcited by 8,820
  7. 2020Scaling Laws for Neural Language Modelscited by 6,586
  8. 2022Self-Consistency Improves Chain of Thought Reasoning in Language Modelscited by 5,708
  9. 2021Measuring Mathematical Problem Solving With the MATH Datasetcited by 5,371
  10. 2022PaLM: Scaling Language Modeling with Pathwayscited by 5,326
  11. 2023Sparks of Artificial General Intelligence: Early experiments with GPT-4cited by 2,592
  12. 2023Efficient Streaming Language Models with Attention Sinkscited by 2,186
38 more
  1. 2020Big Bird: Transformers for Longer Sequencescited by 1,684
  2. 2025Kimi k1.5: Scaling Reinforcement Learning with LLMscited by 1,210
  3. 2024Large Language Monkeys: Scaling Inference Compute with Repeated Samplingcited by 991
  4. 2023Teaching Large Language Models to Self-Debugcited by 988
  5. 2022In-context Learning and Induction Headscited by 964
  6. 2022Transformers learn in-context by gradient descentcited by 732
  7. 2022What Can Transformers Learn In-Context? A Case Study of Simple Function Classescited by 715
  8. 2022What learning algorithm is in-context learning? Investigations with linear modelscited by 684
  9. 2019Are Transformers universal approximators of sequence-to-sequence functions?cited by 406
  10. 2024ReST-MCTS*: LLM Self-Training via Process Reward Guided Tree Searchcited by 344
  11. 2023Transformers as Statisticians: Provable In-Context Learning with In-Context Algorithm Selectioncited by 298
  12. 2023Towards Revealing the Mystery behind Chain of Thought: A Theoretical Perspectivecited by 294
  13. 2022Generating Sequences by Learning to Self-Correctcited by 277
  14. 2022Transformers Learn Shortcuts to Automatacited by 268
  15. 2024Chain of Thought Empowers Transformers to Solve Inherently Serial Problemscited by 260
  16. 2021The Statistical Complexity of Interactive Decision Makingcited by 218
  17. 2022Exploring Length Generalization in Large Language Modelscited by 206
  18. 2022Hidden Progress in Deep Learning: SGD Learns Parities Near the Computational Limitcited by 187
  19. 2025When More is Less: Understanding Chain-of-Thought Length in LLMscited by 183
  20. 2014Learning to Optimize via Information-Directed Samplingcited by 168
  21. 2024AlphaMath Almost Zero: Process Supervision without Processcited by 162
  22. 2013lil' UCB : An Optimal Exploration Algorithm for Multi-Armed Banditscited by 149
  23. 2021Inductive Biases and Variable Creation in Self-Attention Mechanismscited by 144
  24. 2025Optimizing Test-Time Compute via Meta Reinforcement Fine-Tuningcited by 123
  25. 2024The Good, The Bad, and The Greedy: Evaluation of LLMs Should Not Ignore Non-Determinismcited by 116
  26. 2021Self-Attention Networks Can Process Bounded Hierarchical Languagescited by 105
  27. 2024Self-Improvement in Language Models: The Sharpening Mechanismcited by 104
  28. 2021Statistically Meaningful Approximation: a Case Study on Approximating Turing Machines with Transformerscited by 102
  29. 2024Easy-to-Hard Generalization: Scalable Alignment Beyond Human Supervisioncited by 96
  30. 2020On the Computational Power of Transformers and its Implications in Sequence Modelingcited by 85
  31. 2023Transformers as Decision Makers: Provable In-Context Reinforcement Learning via Supervised Pretrainingcited by 83
  32. 2024o1-Coder: an o1 Replication for Codingcited by 78
  33. 2024BOND: Aligning LLMs with Best-of-N Distillationcited by 76
  34. 2024Can Language Models Solve Olympiad Programming?cited by 72
  35. 2024OlympicArena: Benchmarking Multi-discipline Cognitive Reasoning for Superintelligent AIcited by 71
  36. 2023Rewarding Chatbots for Real-World Engagement with Millions of Userscited by 59
  37. 2022Your Transformer May Not be as Powerful as You Expectcited by 55
  38. 2024Contextual Position Encoding: Learning to Count What's Importantcited by 54

50 most cited of 65 All 65 (JSON)

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 5; 2026: 7.

12 papers.

  1. 2025Best-of-Majority: Minimax-Optimal Strategy for Pass@k Inference Scalingcited by 9
  2. 2025Optimal Self-Consistency for Efficient Reasoning with Large Language Modelscited by 9
  3. 2026Optimal Bayesian Stopping for Efficient Inference of Consistent LLM Answerscited by 8
  4. 2025On the Limits of Test-Time Compute: Sequential Reward Filtering for Better Inferencecited by 6
  5. 2025Test-time Verification via Optimal Transport: Coverage, ROC, & Sub-optimalitycited by 4
  6. 2025Demystifying LLM-as-a-Judge: Analytically Tractable Model for Inference-Time Scalingcited by 4
  7. 2026Spend Less, Fit Better: Budget-Efficient Scaling Law Fitting via Active Experiment Selectioncited by 3
  8. 2026When does Chain-of-Thought Help: A Markovian Perspectivecited by 2
  9. 2026Reward Learning from Best-of-N Preference Data: Targets, Tradeoffs, and Design Principlescited by 1
  10. 2026FluxLite: Inference-Time Proposal Control for Discrete Diffusion Modelscited by 1
  11. 2026Adaptive Self-Consistency: From Black-Box Sampling to Distribution-Valued Feedbackcited by 0
  12. 2026From Discovery to Decision: Finite-Budget Recoverability in LLM Votingcited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2025Efficient Test-Time Scaling via Self-Calibration
  2. 2025A Theoretical Study on Bridging Internal Probability and Self-Consistency for LLM Reasoning
  3. 2025Iterative Deepening Sampling as Efficient Test-Time Scaling
  4. 2024Scaling LLM Test-Time Compute Optimally can be More Effective than Scaling Model Parameters
  5. 2025A Survey on Test-Time Scaling in Large Language Models: What, How, Where, and How Well?
  6. 2026Test-Time Scaling in Reasoning LLMs: Inference Regimes, Evaluation, and Reproducibility
  7. 2025The Art of Scaling Test-Time Compute for Large Language Models
  8. 2025Trust but Verify! A Survey on Verification Design for Test-time Scaling