🤖 AI

Pessimistic Verification for Open Ended Math Questions

This paper introduces "pessimistic verification," an agentic workflow that rejects math solutions if any parallel verifier detects an error, and its enhanced "progressive" variant using fine-grained proof decomposition, which significantly outperforms existing methods in accuracy and token efficiency on challenging open-ended math problems while revealing that current benchmarks may underestimate strong models due to annotation errors.

Original authors: Yanxing Huang, Zihan Tang, Zejin Lin, Peng Li, Yang Liu

Published 2026-06-23

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Yanxing Huang, Zihan Tang, Zejin Lin, Peng Li, Yang Liu

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a teacher grading a stack of math exams. Your goal isn't just to see if the final answer is right, but to check if the student's logic is sound. If the student made a single mistake in step 3, the whole proof is wrong, even if they magically got the right number at the end.

This paper introduces a new way for AI to act as that teacher. The authors call it "Pessimistic Verification."

Here is the simple breakdown of their idea, using everyday analogies:

1. The Problem: The "Optimistic" AI

Currently, when AI tries to check math proofs, it often acts like an optimistic friend. It reads the whole proof, thinks, "Hmm, looks mostly good," and gives it a passing grade.

The Flaw: AI is bad at spotting hidden errors. It often misses small mistakes because it's trying to be "nice" or because it gets overwhelmed by long, complex arguments.
The Cost: To be safe, current systems try to check the proof dozens of times. This is like asking 64 different friends to read the same essay. It works, but it's incredibly expensive and slow (like burning a lot of money on coffee for all those friends).

2. The Solution: The "Pessimistic" AI

The authors propose a Pessimistic approach. Imagine a strict, paranoid security guard at a bank.

The Rule: "If anyone finds a single flaw, the whole thing is rejected immediately."
How it works: Instead of asking the AI to write a long essay about why the proof is good, you ask it: "Is there a mistake?"
The Magic: It is much easier for an AI to find a mistake than to prove something is perfect. By focusing only on finding errors, the AI becomes much sharper. If it finds a mistake, it stops and says, "False." If it doesn't find one after a few tries, it says, "True."

3. The Three Variations (The Tools)

The paper tests three ways to apply this "Pessimistic" mindset:

Simple Pessimistic (The "Repeat" Method):
- Analogy: You ask the same security guard to read the whole proof 10 times in a row.
- Result: Better than once, but still a bit wasteful because the guard reads the whole thing every time.
Vertical Pessimistic (The "Zoom-In" Method):
- Analogy: Instead of reading the whole book, you cut the proof into small paragraphs. You ask the guard to look only at paragraph 1, then only at paragraph 2.
- Result: This helps find tiny, hidden typos that get lost in a long read. But it can be slow if you cut the proof into too many tiny pieces.
Progressive Pessimistic (The "Smart Detective" Method):
- Analogy: This is the winner. The detective starts by scanning the whole proof quickly. If they don't see a big obvious error, they zoom in on a specific paragraph. If they still don't see it, they zoom in even further on a single sentence.
- Why it wins: It's efficient. It doesn't waste time zooming in on parts that are clearly fine. It only digs deep where it suspects trouble. It finds errors faster and uses less computing power than the other methods.

4. The Big Surprise: The "Grading Key" was Wrong

One of the most interesting findings in the paper is about the "answer keys" used to test these AI systems.

The Discovery: The researchers found that the "correct" answers in the test datasets were actually wrong.
The Analogy: Imagine a teacher's answer key says a student's proof is "A+." But the new "Pessimistic AI" looks at it and says, "Wait, there's a math error here!"
The Result: The researchers checked the proofs manually and realized the AI was right. The human graders (and the answer keys) had missed the errors.
Takeaway: The current tests for AI math skills are actually underestimating how good the smartest AIs are, because the tests themselves contain mistakes.

5. The Final Test: Solving Real Olympiad Problems

The authors didn't just stop at grading; they let their AI try to solve the hardest math problems in the world (like the International Math Olympiad).

They used their "Progressive Pessimistic" method to check the AI's work as it solved the problems.
Outcome: The AI solved more problems correctly and did it using fewer computer resources (tokens) than previous methods. It was like having a team of detectives that could solve a mystery faster and cheaper than anyone else.

Summary

The paper argues that to verify math, we shouldn't try to be perfect; we should try to be suspicious. By teaching AI to aggressively hunt for errors and break proofs into smaller, manageable chunks, we can make them smarter, faster, and more reliable. And in the process, they discovered that many of our current "correct" math answers are actually incorrect.

Technical Summary: Pessimistic Verification for Open-Ended Math Questions

1. Problem Statement

Automatic verification is a critical bottleneck in building math-solving agents and reinforcement learning systems for large language models (LLMs). While rule-based verification is efficient, it is restricted to problems with deterministic answers, failing to address open-ended mathematical questions which require proof evaluation. Conversely, LLM-based automatic verification suffers from three primary limitations:

Inadequate Accuracy: Current models lack sufficient self-verification capabilities, often requiring human expert guidance.
High Computational Cost: Existing workflows (e.g., DeepSeekMath-V2, DeepSeek-V3.2) often generate vast numbers of candidate proofs and subject them to extensive parallel verification (e.g., 64 rounds), consuming thousands of API calls per problem.
Benchmark Reliability: The paper argues that existing benchmarks may underestimate the capabilities of stronger models due to inherent annotation errors, where human annotators miss subtle or critical errors in proofs.

The core contention of the work is that the primary limitation of automatic verification lies not in generating solutions, but in the ability to detect errors within a proof.

2. Methodology

The authors propose Pessimistic Verification, a paradigm where a solution is rejected if any of multiple parallel verifiers identifies a flaw. This approach prioritizes error detection over consensus. The paper introduces three variants of this method:

2.1. Simple Pessimistic Verification

This variant repeats the standard verification process $n$ times in parallel. If any of the $n$ independent checks finds an error, the proof is marked as incorrect. This serves as a baseline representing current mainstream approaches but lacks structural optimization.

2.2. Vertical Pessimistic Verification

Instead of reviewing the whole proof repeatedly, this method partitions the proof into chunks of a fixed length $k$ . It employs a specific prompting strategy (illustrated in Figure 2) where the LLM is instructed to focus exclusively on a specific chunk while retaining the full proof for context. This allows for deeper, fine-grained examination of specific sections. While it improves error detection over single-pass verification, it incurs high costs due to fixed granularity, potentially wasting tokens on easily verifiable sections.

2.3. Progressive Pessimistic Verification

This is the core contribution, combining the mechanisms of Simple and Vertical methods. It employs a multi-scale verification strategy:

Iterative Decomposition: The process begins with a verification of the complete proof. If no error is found, the proof is subdivided (e.g., halved), and each part is verified separately.
Pruning: Proofs where errors are detected are immediately filtered out. Verification continues only on the remaining proofs.
Parameters: The method uses $n$ to control the maximum number of iterations and $k$ to set a lower bound on segmentation size, preventing over-segmentation.
Efficiency: This dynamic approach allows the system to quickly filter out obvious errors at the macro level and then drill down into detailed steps only where necessary, significantly reducing token consumption compared to fixed-granularity methods.

3. Key Contributions

Identification of Cost Inefficiencies: The study highlights the widespread cost inefficiencies in current math reasoning workflows and provides a new perspective focused on error-centric verification.
Novel Verification Variants: The proposal of three pessimistic verification methods (Simple, Vertical, Progressive) that significantly enhance the verification ability of LLMs with higher efficiency than scaling long Chain-of-Thought (CoT).
Empirical Validation and Benchmark Analysis: Comprehensive experiments on verification benchmarks (IMO-GradingBench, Hard2Verify) and problem-solving tasks (IMO 2025, MathArena Apex 2025). Crucially, the authors demonstrate that existing benchmarks often contain annotation errors, leading to an underestimation of strong models' verification capabilities.

4. Experimental Results

The experiments were conducted on three datasets: IMO-GradingBench (human-graded IMO solutions), Hard2Verify (competition problems with human annotations), and QiuZhen-Bench (undergraduate-level problems annotated by GPT-5).

Performance Metrics: The primary metrics were True Negative Rate (TNR), True Positive Rate (TPR), and Balanced F1 Score.
Scaling Efficiency: Progressive pessimistic verification consistently achieved the highest performance and token efficiency across all models (ranging from Qwen3-1.7B to GPT-5 and Gemini 3 Pro). It outperformed standard long CoT and simple parallel verification in both accuracy and cost.
Error Detection vs. Consensus: The results confirmed that error detection (TNR) is the key differentiator between strong and weak verifiers, whereas TPR remains relatively stable across models.
Case Studies on Annotation Errors: Detailed analysis of False Negative (FN) cases revealed that state-of-the-art models (e.g., GPT-5, Gemini 3 Pro) frequently identified critical errors in proofs that were originally labeled as correct (7/7 points) by human annotators. This suggests that current benchmarks are unreliable for cutting-edge models and that the "TPR loss" observed in some metrics is often an artifact of flawed ground truth rather than model failure.
Problem Solving: In agentic workflows on IMO 2025 and MathArena Apex 2025, the progressive pessimistic verification workflow significantly improved both the final accuracy and the efficiency (measured in equivalent output tokens) compared to direct solving or naive parallel verification. For instance, on the IMO 2025 dataset, the progressive method achieved a total score of 22/42 compared to 13/42 for direct solving, with lower token usage than the simple pessimistic baseline.

5. Significance and Claims

The paper claims that Progressive Pessimistic Verification offers a viable compromise between the strict rigor of formal theorem provers (which are computationally expensive and require complex autoformalization) and the limitations of informal verification.

Error-Centric Philosophy: The work emphasizes that verification outcomes identifying errors possess higher information content and warrant prioritization. This philosophy facilitates algorithmic pruning, enhancing efficiency.
Segment-Wise Scrutiny: The method argues that effective verification requires meticulous examination of minute details within a process rather than repeated, superficial reviews of the whole.
Practical Impact: The authors posit that once informal verification achieves sufficient performance, it can satisfy the requirements of most practical applications in mathematical research and software engineering (e.g., debugging code without executing test cases).
Future Potential: The method is presented as a way to push the capability frontier of state-of-the-art models, potentially serving as a component in training pipelines to improve rigorous reasoning and verification abilities in LLMs.

The authors conclude that their approach provides a scalable, cost-effective alternative to current verification workflows, capable of handling the complexity of research-level mathematical problems while exposing the limitations of existing human-annotated benchmarks.