Pessimistic Verification for Open-Ended Math Questions

Motivation

• Known: verification은 math-solving agentic workflow와 reinforcement learning에서 test-time scaling과 훈련 신호로서 핵심적인 역할을 하며, DeepSeekMath-V2, DeepSeek-V3.2 등 다수 최신 연구에서 verification 기반 iterative workflow가 IMO gold-medal 수준 성능 달성에 기여함이 알려져 있다.
• Gap: rule-based verification은 open-ended math question에 적용 불가능하고, LLM-based verification은 절대 정확도가 낮으며 사람의 검증에 여전히 의존하고 있고, 특히 DeepSeekMath-V2/DeepSeek-V3.2류 workflow는 문제당 수천 번의 API 호출을 요구할 정도로 계산 비용이 과도하여 효율적인 자동 검증 방법이 부재하다.
• Why: 수학 문제 해결 agent와 대형 reasoning model의 RL 훈련 모두에서 검증기의 정확성과 비용 효율성이 시스템 전체 성능과 실용성을 좌우하므로, 이를 개선하는 것은 IMO 수준의 contest math 문제 해결 및 연구 수준 수학 보조 AI 시스템 구축에 직접적으로 중요하다.
• Approach: 저자들은 하나의 증명을 여러 verifier가 병렬로 검토하고 그중 하나라도 오류를 발견하면 즉시 기각하는 pessimistic verification 개념을 제시하고, 이를 세분화된 chunk 단위로 반복 적용하는 progressive pessimistic verification으로 확장하여 검증 정확도와 효율을 동시에 높인다.

Achievement

Figure 5. The main benchmark results on IMO-GradingBench,

1. 세 가지 pessimistic verification 변형 제안: simple(전체 증명 반복 검증), vertical(chunk 단위 분할 검증), progressive(반복적 세분화 검증)을 설계하여 비교하고, progressive 방식이 모든 시나리오에서 최고 성능과 효율을 달성함을 보였다.
2. 긴 chain-of-thought 대비 효율성 입증: 제안 방법이 extended long CoT 및 mainstream verification workflow보다 성능과 token efficiency 모두에서 우수함을 보였다.
3. 기존 벤치마크의 한계 발견: Hard2Verify, IMO-GradingBench 등 기존 검증 벤치마크의 annotation 오류로 인해 강력한 모델에서의 실제 검증 효과가 과소평가되고 있음을 사례 분석을 통해 밝혔다.
4. 실전 contest 문제 적용 검증: IMO 2025와 MathArena Apex 2025 데이터셋에 verification 기반 solving workflow를 적용하여 최첨단 모델로 도전적인 contest-level 수학 문제에서 정확도와 효율 모두 큰 개선을 확인했다.

How

Figure 2. The vertical review prompting method used in vertical

• Simple pessimistic verification (pes@n): 표준 verification(전체 증명 검사)을 n회 병렬 반복하고, 하나라도 오류로 판정되면 최종 결과를 오류로 처리하는 mainstream 방식의 baseline.
• Vertical pessimistic verification (vp@k): 증명을 최대 k줄 단위 chunk로 분할하고, 각 chunk에 대해 전체 증명을 context로 제공하면서 해당 chunk만 집중적으로 검토하도록 병렬 review task를 구성. 한 번의 pass만으로도 단일 전체 검증 및 simple pessimistic verification보다 유사 계산 예산 하에서 향상된 오류 탐지 성능을 보임.
• Progressive pessimistic verification (prog@n/k): vertical 검증을 반복적으로 적용하며 chunk를 최소 길이 k까지 최대 n회 세분화하여 재검증, fine-grained proof decomposition을 통해 복잡하고 긴 research-level 증명에서 특히 효과적.
• 평가: Hard2Verify, IMO-GradingBench, 자체 제작 undergraduate-level 수학 검증 데이터셋에서 성능 및 token efficiency 측정, 이어 IMO 2025 및 MathArena Apex 2025에서 verification 기반 solving workflow로 실전 검증.

Originality

• 기존 연구들이 verification의 negative verdict 중요성을 암묵적으로 활용해온 것을 "pessimistic verification"이라는 명시적 패러다임으로 정식화하고 체계적으로 분석한 최초의 시도.
• 단순 반복 검증(simple)과 공간적 분할 검증(vertical)을 결합하여 반복적 세분화(progressive)라는 새로운 차원의 검증 전략을 제시함으로써, "전체를 여러 번 볼 것인가 vs 부분을 깊게 볼 것인가"라는 verification 설계의 trade-off를 통합적으로 다룸.
• 기존 벤치마크(Hard2Verify, IMO-GradingBench)의 annotation 오류를 지적하며 강한 모델 평가 시 벤치마크 신뢰도 문제를 드러낸 메타적 기여.

Limitation & Further Study

• 제안된 세 가지 변형(simple, vertical, progressive)의 하이퍼파라미터(n, k) 선택에 대한 원칙적 가이드라인이 부족해 보이며, 문제 유형별 최적 설정이 추가 연구로 필요.
• 기존 벤치마크의 annotation 오류를 지적했으나, 저자 스스로 새로운 신뢰할 수 있는 대규모 벤치마크를 구축하지는 않아 향후 고품질 contest-level verification benchmark 구축이 필요함.
• IMO 2025, MathArena Apex 2025와 같은 특정 contest 데이터셋에 국한된 실험으로, 다양한 도메인(대수, 해석, 조합 등) 및 연구 수준 수학 증명 전반에 대한 일반화 가능성 검증이 추가로 요구됨.
• pessimistic 접근이 false negative(정확한 증명을 과도하게 기각)를 늘릴 위험에 대한 정량적 분석이 제한적으로 보임.

Evaluation

총평: verification의 핵심 병목을 오류 탐지 능력으로 명확히 진단하고, 이를 개선하는 간단하면서도 효과적인 pessimistic/progressive verification 프레임워크를 제안하여 IMO 수준의 실전 문제에서 효율성과 정확도 개선을 입증한 실용적이고 시의적절한 연구이다.