mlsanityData to 7 Oct 2026

On Learning Verifiers and Implications to Chain-of-Thought Reasoning

arXiv 2505.22650 ↗First posted 28 May 2025cs.LGcited by 6

On the map: LLM reasoning → Prompting and chain-of-thought reasoning

Abstract (arXiv)

Chain-of-Thought reasoning has emerged as a powerful approach for solving complex mathematical and logical problems. However, it can often veer off track through incorrect or unsubstantiated inferences. Formal mathematical reasoning, which can be checked with a formal verifier, is one approach to addressing this issue. However, currently LLMs are simply not good enough to solve complex problems in a formal way, and even just formalizing an informal problem statement can be challenging. Motivated by this fact, in this work we consider the problem of learning reliable verifiers for natural language Chain-of-Thought reasoning. That is, given a problem statement and step-by-step solution in natural language, the aim of the verifier is to output [Yes] if the reasoning steps in the solution are all valid, and [No] otherwise. In this work we give a formal PAC-learning framework for studying this problem. We propose and analyze several natural verification goals, at different levels of strength, in this framework. We provide sample complexity upper-bounds for learning verifiers satisfying these goals, as well as lower-bound and impossibility results for learning other natural verification objectives without additional assumptions.

Key facts. Cited by 6 papers in the map (data through 7 Oct 2026). Placed in Prompting and chain-of-thought reasoning, one of 17 directions in LLM reasoning. Builds on 63 of its 104 references that are in the map. First posted on arXiv 28 May 2025.

Builds on

63 of 104 references.

Closest ancestors · 7

Same direction, newest first

  1. 2025PENCIL: Long Thoughts with Short Memory18 Mar
  2. 2025A Theory of Learning with Autoregressive Chain of Thought11 Mar
  3. 2024Chain of Thoughtlessness? An Analysis of CoT in Planning8 May
  4. 2024Chain of Thought Empowers Transformers to Solve Inherently Serial Problems20 Feb
  5. 2022Automatic Chain of Thought Prompting in Large Language Models7 Oct
  6. 2022Self-Consistency Improves Chain of Thought Reasoning in Language Models21 Mar
  7. 2022Chain-of-Thought Prompting Elicits Reasoning in Large Language Models28 Jan

Other references · 56

  1. 2021Training Verifiers to Solve Math Word Problemscited by 9,743
  2. 2023Let's Verify Step by Stepcited by 3,598
  3. 2023Tree of Thoughts: Deliberate Problem Solving with Large Language Modelscited by 3,155
  4. 2021WebGPT: Browser-assisted question-answering with human feedbackcited by 1,722
  5. 2023Reasoning with Language Model is Planning with World Modelcited by 846
  6. 2019On Exact Computation with an Infinitely Wide Neural Netcited by 572
  7. 2019Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networkscited by 562
  8. 2023Sophia: A Scalable Stochastic Second-order Optimizer for Language Model Pre-trainingcited by 260
  9. 2025Reasoning with Latent Thoughts: On the Power of Looped Transformerscited by 223
  10. 2020Towards Resolving the Implicit Bias of Gradient Descent for Matrix Factorization: Greedy Low-Rank Learningcited by 148
  11. 2018Towards Understanding the Role of Over-Parametrization in Generalization of Neural Networkscited by 140
  12. 2022Understanding Gradient Descent on Edge of Stability in Deep Learningcited by 126
38 more
  1. 2023Deductive Verification of Chain-of-Thought Reasoningcited by 122
  2. 2019An Exponential Learning Rate Schedule for Deep Learningcited by 121
  3. 2021What Happens after SGD Reaches Zero Loss? --A Mathematical Frameworkcited by 106
  4. 2019Harnessing the Power of Infinitely Wide Deep Nets on Small-data Taskscited by 87
  5. 2022Understanding the Generalization Benefit of Normalization Layers: Sharpness Reductioncited by 86
  6. 2022Same Pre-training Loss, Better Downstream: Implicit Bias Matters for Language Modelscited by 84
  7. 2021Gradient Descent on Two-layer Nets: Margin Maximization and Simplicity Biascited by 82
  8. 2019Enhanced Convolutional Neural Tangent Kernelscited by 76
  9. 2023Dichotomy of Early and Late Phase Implicit Biases Can Provably Induce Grokkingcited by 76
  10. 2024Understanding Warmup-Stable-Decay Learning Rates: A River Valley Loss Landscape Perspectivecited by 75
  11. 2021On the Validity of Modeling SGD with Stochastic Differential Equations (SDEs)cited by 73
  12. 2015The Optimal Sample Complexity of PAC Learningcited by 72
  13. 2022A Characterization of Multiclass Learnabilitycited by 66
  14. 2018Theoretical Analysis of Auto Rate-Tuning by Batch Normalizationcited by 65
  15. 2023Auto-Regressive Next-Token Predictors are Universal Learnerscited by 65
  16. 2022How Does Sharpness-Aware Minimization Minimize Sharpness?cited by 64
  17. 2019Explaining Landscape Connectivity of Low-cost Solutions for Multilayer Netscited by 63
  18. 2020Reconciling Modern Deep Learning with Traditional Optimization Analyses: The Intrinsic Learning Ratecited by 59
  19. 2024Implicit Bias of AdamW: ℓ_∞ Norm Constrained Optimizationcited by 54
  20. 2024Don't Trust: Verify -- Grounding LLM Quantitative Reasoning with Autoformalizationcited by 53
  21. 2021Risk Bounds and Rademacher Complexity in Batch Reinforcement Learningcited by 42
  22. 2023Understanding Incremental Learning of Gradient Descent: A Fine-grained Analysis of Matrix Sensingcited by 40
  23. 2023Sharpness Minimization Algorithms Do Not Only Minimize Sharpness To Achieve Better Generalizationcited by 39
  24. 2022Implicit Bias of Gradient Descent on Reparametrized Models: On Equivalence to Mirror Descentcited by 38
  25. 2024Why Do You Grok? A Theoretical Analysis of Grokking Modular Additioncited by 34
  26. 2020Why Are Convolutional Nets More Sample-Efficient than Fully-Connected Nets?cited by 32
  27. 2022Chain of Thought Imitation with Procedure Cloningcited by 30
  28. 2025Structured Preconditioners in Adaptive Optimization: A Unified Analysiscited by 30
  29. 2022Robust Training of Neural Networks Using Scale Invariant Architecturescited by 29
  30. 2019Implicit Regularization and Convergence for Weight Normalizationcited by 20
  31. 2024Adam Exploits ℓ_∞-geometry of Loss Landscape via Coordinate-wise Adaptivitycited by 20
  32. 2022Robustly-reliable learners under poisoning attackscited by 19
  33. 2023Multiclass Online Learning and Uniform Convergencecited by 19
  34. 2023The Marginal Value of Momentum for Small Learning Rate SGDcited by 16
  35. 2025Weak-to-Strong Generalization Even in Random Feature Networks, Provablycited by 13
  36. 2018Online Improper Learning with an Approximation Oraclecited by 11
  37. 2025On the Query Complexity of Verifier-Assisted Language Generationcited by 10
  38. 2023Reliable learning in challenging environmentscited by 9

50 most cited of 56 All 56 (JSON)

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2025: 3; 2026: 3.

6 papers.

  1. 2025Unlocking the Power of Multi-Agent LLM for Reasoning: From Lazy Agents to Deliberationcited by 11
  2. 2026Sample Complexity of Autoregressive Reasoning: Chain-of-Thought vs. End-to-Endcited by 2
  3. 2026Adaptive Generate-Rank-Verify: Inference-Time Search with Costly Verificationcited by 1
  4. 2026A Theoretical Framework for Self-Play Theorem Proving Algorithmscited by 1
  5. 2025If generative AI is the answer, what is the question?cited by 0
  6. 2025Prior Knowledge Makes It Possible: From Sublinear Graph Algorithms to LLM Test-Time Methodscited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2026Verify to Amplify: Improving Reasoning via Learned Chain-of-Thought Verification
  2. 2024A Chain-of-Thought Is as Strong as Its Weakest Link: A Benchmark for Verifiers of Reasoning Chains
  3. 2025VeriThinker: Learning to Verify Makes Reasoning Model Efficient
  4. 2024General Purpose Verification for Chain of Thought Prompting
  5. 2025Improving Chain-of-Thought Reasoning via Quasi-Symbolic Abstractions
  6. 2025Safe: Enhancing Mathematical Reasoning in Large Language Models via Retrospective Step-aware Formal Verification
  7. 2025From Reasoning to Super-Intelligence: A Search-Theoretic Perspective
  8. 2025VeriCoT: Neuro-symbolic Chain-of-Thought Validation via Logical Consistency Checks