Research map / Large language models / Reasoning and chain of thought
On Learning Verifiers and Implications to Chain-of-Thought Reasoning
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.
Formal PAC-learning framework for learning verifiers that check step-by-step chain-of-thought reasoning, with sample complexity bounds for simple (in-distribution) and trustable (sound against gold-standard reasoners) verifiers, plus lower bounds.
Problem
Chain-of-thought reasoning in LLMs can go off track via incorrect inferences, and formal verification is infeasible for natural language reasoning; the paper asks how to learn reliable verifiers for sequential reasoning from data with provable guarantees.
Approach
Formalizes CoT verification as PAC learning of prefix-checking verifiers; defines simple verifiers (in-distribution, first-fault labels) and trustable verifiers (sound on all traces for most problems, complete w.r.t. a gold-standard reasoner), giving finite-class and VC-dimension sample complexity bounds and showing linear-in-|H| lower bounds when multiple correct traces exist.
Key results
- Finite verifier classes are SVPAC-learnable with O((1/eps)(log|H| + log(1/delta))) samples; VC-dimension classes with O((1/eps)(VCDim log T + log(1/delta))).
- For trustable verifiers with a unique gold trace, finite classes are learnable with O((1/eps)(log|H| + log(1/delta))) samples, while with many gold traces the intersection-of-consistent-verifiers algorithm needs O(|H|/(eta*eps)) samples.
- Lower bounds: any proper learner for sound-only trustable verification needs Omega(|H|) samples, and even 1/2-complete improper learners need Omega(|H|) samples.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use consistency-based learning for a finite verifier class | Simple verifiers (SVPAC) · SVPAC | sample complexity: \frac{1}{\epsilon}(\log (|H|) + \log \frac{1}{\delta}) | Helped |
| Use a finite VC-dimension verifier class | Simple verifiers (SVPAC) · SVPAC | sample complexity: O\left(\frac{1}{\epsilon}(\mathsf{VCDim}(H)\log T + \log \frac{1}{\delta})\right) | Helped |
| Use all gold-standard proofs and add one-step deviation examples | Trustable verifiers with at most k gold proofs · Stepwise TVPAC | sample complexity: \frac{1}{\epsilon}(\log (|H|) + \log \frac{1}{\delta}) | Helped |
| Use a finite VC-dimension verifier class with at most k gold proofs | Trustable verifiers · Stepwise TVPAC | sample complexity: O\left(\frac{1}{\epsilon}(\mathsf{VCDim}(H)\log (kT|\Sigma|) + \log \frac{1}{\delta})\right) | Helped |
| Learn from random positive traces and intersect all consistent verifiers | Trustable verifiers with an unrestricted number of gold proofs · γ-TV PAC | sample complexity: O\left(\frac{1}{\eta\epsilon}(|H| + \log \frac{1}{\delta})\right) | Mixed |
| Assume the verifier class is intersection-closed | Intersection of consistent verifiers · γ-TV PAC | sample complexity: O\left(\frac{1}{\eta\epsilon}(\mathsf{VCDim}(H) + \log \frac{1}{\delta})\right) | Helped |
| Require a proper learner with only a soundness guarantee | Trustable verification for finite H · γ-TV PAC | sample complexity: \Omega(|H|) | Hurt |
| Require both soundness and 1/2-completeness, allowing improper learners | Trustable verification for finite H · 1/2-TV PAC | sample complexity: \Omega(|H|) | Hurt |
| Use ERM in the agnostic setting for finite H | Simple verifiers · Agnostic SVPAC | sample complexity: O\left(\frac{1}{\epsilon^2}(\log (|H|) + \log \frac{1}{\delta})\right) | Helped |
| Use ERM with gold-standard examples in the agnostic setting | Trustable verifiers for finite H · Agnostic TVPAC | sample complexity: O\left(\frac{1}{\epsilon^2}(\log (|H|) + \log \frac{1}{\delta})\right) | Helped |
Surprising findings
- For a single gold-standard trace, stepwise trustable verification is equivalent to CoT generation, so a good verifier can be turned into a generator.
- Sample complexity for many-correct-proof trustable verification is necessarily linear in the verifier class size, unlike the logarithmic bound in the single-trace case.
Limitations
- Results are theoretical only; no experiments with LLM verifiers.
- Trustable verifiers only reject traces not matching the gold standard, which may reject legitimate reasoning.
- Assumes realizability in main results; agnostic extensions are weaker.
Experimental setup
Metrics: sample complexity error rate
Builds on: PAC learning closure algorithm autoregressive chain-of-thought generation model
Closest papers by meaning
- Causal Sufficiency and Necessity Improves Chain-of-Thought Reasoning (NeurIPS 2025 · similarity 0.89)
- Premise-Augmented Reasoning Chains Improve Error Identification in Math reasoning with LLMs (ICML 2025 · similarity 0.88)
- VeriThinker: Learning to Verify Makes Reasoning Model Efficient (NeurIPS 2025 · similarity 0.88)
- Reasoning about Reasoning: BAPO Bounds on Chain-of-Thought Token Complexity in LLMs (ICML 2026 · similarity 0.88)
- Transformers Provably Solve Parity Efficiently with Chain of Thought (ICLR 2025 · similarity 0.88)
- Scaling Code-Assisted Chain-of-Thoughts and Instructions for Model Reasoning (NeurIPS 2025 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.