arXiv:2605.20531v3 cs.LO

자동 증명 검증을 위한 의사 형식화

Pseudo-Formalization for Automatic Proof Verification

Slim Barkallah, Luke Bailey, Kaiyue Wen, Mohammed Abouzaid, Tengyu Ma

제출 2026-05-19

저자 비고

arXiv Comments

31 pages, code available at https://github.com/Slim205/pseudo-formalization

한국어 초록

신뢰할 수 있는 증명 검증은 고난도 수학적 추론에 대한 AI 시스템의 학습(training)과 평가(evaluation)에서 여전히 병목 현상으로 남아 있습니다. Lean과 같은 언어로 작성된 완전한 형식적 증명(fully formal proofs)은 모호하지 않고 모듈화되어 있어 검증하기 쉽습니다. 그러나 대부분의 증명, 특히 AI 시스템이 작성한 증명은 두 가지 특성을 모두 갖추지 못했으며, 이를 형식 언어로 번역하는 것은 많은 프론티어 수학 환경에서 여전히 어려운 과제입니다. 본 논문에서는 자연어의 유연성을 유지하면서도 형식적 증명의 모듈성과 정밀성을 포착하는 증명 형식인 의사 형식화(Pseudo-Formalization, PF)를 제안합니다. 의사 형식적 증명은 독립적인 모듈들로 분해되며, 각 모듈은 전제, 결론 및 증명을 자연어로 명시합니다. 일반 자연어 증명의 정확성을 검증하기 위해, 대규모 언어 모델(LLM)이 이를 의사 형식적 표현으로 변환한 다음 각 모듈을 독립적으로 검증하는 블록 검증(Block Verification, BV) 알고리즘을 사용합니다. 올림피아드 및 연구 수준의 수학을 아우르는 두 가지 벤치마크(benchmark)에서 PF+BV를 평가한 결과, 오류 발견 정밀도(precision)와 재현율(recall) 측면에서 LLM-as-a-judge 베이스라인을 파레토 지배(pareto-dominates)함을 확인했습니다. 향후 연구를 지원하기 위해 연구 수준의 증명 검증 벤치마크인 ArxivMathGradingBench를 공개합니다.

원문 초록

Reliable verification of proofs remains a bottleneck for training and evaluating AI systems on hard mathematical reasoning. Fully formal proofs, in languages like Lean, are easy to verify because they are unambiguous and modular. Most proofs, particularly those written by AI systems, have neither property, and translating them into formal languages remains challenging in many frontier math settings. We propose Pseudo-Formalization (PF), a proof format that captures the modularity and precision of formal proofs while retaining the flexibility of natural language. A Pseudo-Formal proof is decomposed into self-contained modules, each stating its premises, conclusion, and proof in natural language. To verify the correctness of a regular natural language proof, an LLM translates it to Pseudo-Formal and then verifies each module independently, an algorithm we call Block Verification (BV). We evaluate PF+BV on two benchmarks spanning olympiad and research-level mathematics, where it pareto-dominates LLM-as-judge baselines on error-finding precision and recall. To support future work, we release our research-level proof verification benchmark ArxivMathGradingBench.

제출 이력

확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.

  1. arXiv:2605.20531v3

함께 살펴볼 논문

공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.

arXiv:2610.13461v1cs.AI공통 태그 Benchmarking, Math, theorem proving, formal verification

SqueezeBench: 포화에 강건한 수학적 능력 평가

SqueezeBench: Saturation-Resilient Evaluation of Mathematical Capability

AI 시스템은 수학 분야에서 빠르게 발전하고 있지만, 이러한 발전을 측정하기는 어렵다. 이미 풀린 문제들로 구성된 벤치마크(benchmark)는 포화(saturate)되며, 미해결 문제들로 구성된 벤치마크에서는 각 문제가 최초로 단 한 번만 해결될 수 있다. 우리는 포화에 강건한 벤치마크인 SqueezeBench를 제시한다: 성공은 문제를 제거하는 대신 기준을 높인다. 각 문제는 작은 $n$에 대해서만 값이 알려진 정수 함수 $f(n)$을 고정하며, 벤치마크는 이에 대한 하한(lower) 기록과 상한(upper) 기록을 유지한다. 기록(record)은 $f$를 한정(bound)함을 기계 검증된 증명(machine-checked proof)으로 보인 계산 가능한 Lean 함수이다. 제출(submission)은 새로운 함수를 제안하고, 그 함수가 $f$를 한정하며, 모든 $n$에서 현재 기록보다 나쁘지 않고, 일부 $n$에서는 엄밀히 더 우수함을 증명한다. 채택되면 해당 제출은 다음 제출이 넘어서야 할 새로운 기록이 된다. 따라서 이 시스템은 한계값(bound)뿐 아니라 그 증명까지 선택하며, 단일 $n$에서의 기록을 개선할 수도 있고 성장률(growth rate)을 개선할 수도 있다. 모든 $n$에서 두 기록 사이의 간극은 인증된 한계값들이 $f(n)$을 결정하는 데에서 얼마나 떨어져 있는지를 보여준다. 모든 증명은 두 개의 독립적인 Lean 커널에 의해 검증되므로, 심판이 수학적 내용을 검토할 필요가 없다. 검증 과정은 또한 작은 $n$에서 전수 탐색(exhaustive search)으로 $f$를 계산하는 함수를 거부하며, 유지관리자(maintainer)는 제출자의 보고서만 읽고 더 큰 $n$에서 그러한 탐색이 있는지를 확인한다. 우리는 극단적 조합론(extremal combinatorics) 분야의 열 가지 문제를 스무 개의 증명된 초기 기록 및 승인 도구(admission tools)와 함께 공개한다. 기준선(baseline)으로서, 최신(frontier) 언어 모델(language model) 기반 에이전트(agent)는 기록당 최대 한 시간을 사용하여 82건의 제출을 승인받았고 모든 기록을 개선했으며, 이는 기존 발표된 문헌의 범위를 넘어서지는 않았다. 이후 두 개의 더 새로운 모델(model) 기반 에이전트들이 이 기록들로부터 시작하여 60건의 추가 제출을 승인받았고, 20개의 기록 중 19개를 다시 개선했다. 열 가지 문제 중 여덟 가지 문제에서는, 적어도 하나의 기록이 여전히 발표된 최선의 한계값(bound)에 비해 점근적으로(asymptotically) 뒤처져 있다.

arXiv:2610.00885v1cs.SE공통 태그 Math, theorem proving, formal verification

형식 수학 및 소프트웨어 검증에서 감사 가능한 추론을 위한 FORALL-LEAN-AGENT

FORALL-LEAN-AGENT for Auditable Reasoning in Formal Mathematics and Software Verification

코딩 에이전트(agent)는 Lean 증명 개발을 점점 더 자동화하고 있지만, 컴파일 성공만으로는 후보 증명이 허용 가능한 가정 하에서 의도한 명제를 증명한다는 점을 확증하지 못합니다. 본 논문에서는 형식 수학 및 소프트웨어 검증에서 감사 가능한 추론을 위한 프런트엔드 독립적 프레임워크인 FORALL-LEAN-AGENT를 제시합니다. 이 프레임워크는 격리된 작업 공간, Lean 도구, 새로운 검토를 명제 비교, 공리 감사, 그리고 지원되는 경우 독립적인 증명 검사와 결합합니다. 검증 증거와 검토자의 결정은 동일한 후보 아티팩트에 바인딩되어 수락 과정을 추적할 수 있도록 합니다. 우리는 VeriSoftBench, PutnamBench, 그리고 Lean Eval 소프트웨어 검증 트랙의 두 문제 모두에서 이 프레임워크를 평가합니다. 100개 과제로 구성된 VeriSoftBench 하위 집합에서, FORALLLEAN-AGENT와의 통합은 GPT-5.6 Sol의 벤치마크 규칙 성공을 낮은 노력으로 93개에서 100개로 높이는 동시에 비용을 69달러에서 62달러로 절감합니다. PutnamBench 평가에서는 전체 672개 문제를 평균 4.72달러에 모두 통과시킵니다. 이러한 결과는 에이전트 하네스 설계가 총 해결 횟수를 넘어서는 증거를 제공하는 동시에 정확성과 효율성을 향상시킬 수 있음을 보여줍니다.

arXiv:2610.13632v1cs.AI공통 태그 Math, theorem proving

올림피아드 에이전트의 인간화: Solve, Review, Wiki, Verify를 활용한 올림피아드 문제 해결용 다중 세션 워크플로

Humanize Olympiad Agents: A Multi-Session Workflow for Olympiad Problem Solving with Solve, Review, Wiki, Verify

대규모 언어 모델(LLM) 에이전트는 장기적인 과학 및 올림피아드 과제에서 빠르게 발전하고 있습니다. 최근 시스템들은 나비에-스토크스(Navier--Stokes) 문제에 대한 Lean 정형화 해법과 에르되시 추측(Erdős Conjectures) 데이터베이스의 4개 미해결 문제에 대한 자율적 해법을 제시했습니다. 그러나 두 시스템 모두 기반 모델과 완전한 추론 스택을 동시에 공개하지는 않았습니다. 더 넓게 보면, 단일 에이전트 세션은 고난도 문제에서 여전히 취약합니다. 초기 오류가 전파될 수 있고, 도메인 지식 부족으로 진행이 중단될 수 있으며, 겉보기의 성공이 원래 과제에 대한 오해나 조건 완화를 감추고 있을 수도 있습니다. 본 연구에서는 상호보완적인 세 가지 피드백 채널을 통해 다중 에이전트 세션을 조율하는 공개 플로우 수준 프레임워크인 HOA(Humanize Olympiads Agent)를 소개합니다. 첫째, 독립적인 검토자(reviewer)가 각 후보 해법을 평가하고 실행 가능한 피드백을 제공합니다. 둘째, 구조화된 위키가 모델 사전학습에서 누락되었거나 신뢰할 수 없는 과제 특화 지식을 제공합니다. 셋째, 검증기(verifier)가 생성된 Lean 증명을 신뢰할 수 있는 문제 명제와 대조하여 확인합니다. GPT-5.6 Sol을 적용한 HOA는 IMO, IPhO, IOI 2026에서 만점을 기록하고, IChO 2026 문제 세트에서 만점에 근접한 점수를 얻었으며, PutnamBench의 672개 문제 전체(100%)를 해결했습니다. Lean-Eval 리더보드에서 HOA는 304개 문제 중 251개(82.6%)를 해결하여 1위를 기록했습니다. 나아가 오픈 모델을 활용해 HOA를 평가했습니다. Kimi-K3를 사용했을 때 HOA는 IMO, IPhO, IOI에서 만점을 달성하고 IChO에서 97.1%의 금메달 수준 점수를 획득했습니다. 이러한 결과는 IMO와 IPhO에서 폐쇄형 GPT-5.6 Sol + /Goal 기준선과 거의 일치하는 동시에 IChO와 IOI에서는 이를 능가하여, 체계적인 피드백이 기본 모델 역량의 상당한 격차를 해소하는 데 기여할 수 있음을 보여줍니다.

토론

이 논문과 연결된 포럼 글이 아직 없습니다.