[논문리뷰] h1: A Taste of the Bitter Lesson in Automated Theorem Proving

링크: 논문 PDF로 바로 열기

The paper "A Taste of the Bitter Lesson in Automated Theorem Proving" investigates whether simple agentic loops that scale test-time compute can match human-designed workflows in formal theorem proving. The authors introduce h1, a simple harness providing an efficient interface to Lean 4, allowing models to work through verifier feedback and self-reflection without prescribed decomposition or search structures.

From the paper, I've identified the following metadata: Authors: Skander Moalla, Ahmad Rammal, Niket Patel, Remi Munos, Julia Kempe Keywords: Automated Theorem Proving, Large Language Models, Agentic Systems, Lean 4, Test-Time Scaling, Harness Design, Formal Verification, Bitter Lesson

Now, I will proceed with generating the summary and selecting the figures.

For figures, I'll aim for:

1. Overall system architecture (Figure 2)
2. Key performance comparison (Figure 1, which combines multiple related plots)
3. Quantitative results/scaling (Figure 3)

Let's start writing Part 1.

Part 1: Summary Body (Markdown)

저자: Skander Moalla, Ahmad Rammal, Niket Patel, Remi Munos, Julia Kempe

1. Key Terms & Definitions (핵심 용어 및 정의)

본 논문에서 다루는 핵심 용어 및 정의는 다음과 같습니다:

• Automated Theorem Proving (ATP): 수학적 명제와 증명을 기계적으로 검증할 수 있는 형식 언어로 작성하고, 이를 자동으로 증명하는 분야입니다.
• Harness: 모델을 둘러싼 도구, Context, 그리고 제어 루프를 지칭하며, LLM(Large Language Model)이 Formal Prover와 상호작용하는 방식을 정의합니다.
• Lean 4: 수학적 진술과 증명을 정밀한 언어로 표현하고 기계적으로 검사할 수 있는 Formal Proof Assistant입니다.
• Test-Time Scaling: 모델의 추론 시간에 더 많은 컴퓨팅 자원을 할당하여 성능을 향상시키는 기법으로, 단일 시도 내에서 반복적인 작업이나 Reflection을 통해 문제 해결 능력을 확장합니다.
• Bitter Lesson: 일반적인 방법론이 계산 자원과 함께 확장될 때, 인간의 도메인 지식에 기반한 전문화된 접근 방식보다 궁극적으로 더 뛰어난 성능을 발휘한다는 예측입니다.

2. Motivation & Problem Statement (연구 배경 및 문제 정의)

기존 연구는 Formal Theorem Proving 분야에서 Frontier Language Models의 발전을 활용하기 위해 계획, 분해, 전문화된 Prover 오케스트레이션 등 인간이 설계한 복잡한 Workflow에 의존해 왔습니다. 이러한 접근 방식은 종종 모델의 향상이나 더 많은 컴퓨팅 자원과 혼재되어 Workflow 자체의 기여도를 명확히 파악하기 어렵게 만들었습니다. 저자들은 Formal Verification이 Frontier Models의 발전 속도에 맞춰 확장되어야 하지만, 새로운 Workflow의 효과가 항상 명확하게 입증되지 않는다는 문제점을 제기합니다. 이에 따라, Bitter Lesson의 관점에서 단순한 Agentic Loop가 Test-Time Compute를 확장하여 이러한 복잡한 Workflow와 동등한 성능을 달성할 수 있는지에 대한 근본적인 질문을 던집니다. 즉, Human-Designed Workflows가 필수적인지, 아니면 단순한 Harness와 충분한 Test-Time Compute만으로도 경쟁력 있는 결과를 얻을 수 있는지 탐구하고자 합니다.

3. Method & Key Results (제안 방법론 및 핵심 결과)

본 논문은 Lean 4에 대한 효율적인 Interface를 제공하고, 분해(Decomposition) 또는 검색 구조(Search Structure)를 강요하지 않는 단순한 Harness인 h1을 제안합니다. h1은 모델이 ReAct loop 내에서 Multi-turn reasoning과 Tool-calling을 반복하고, Formal Validator의 Feedback을 통해 작업하며, 실패 시 Reflection LLM이 Transcript를 새로운 Context로 압축하여 다음 Iteration을 위한 요약을 제공하는 방식으로 작동합니다 [Figure 2, cite: 1]. 이러한 루프는 모델이 성공하거나 비용 한도에 도달할 때까지 작업을 지속하도록 합니다.

실험 결과는 다음과 같습니다:

• State-of-the-Art (SOTA) Performance: h1은 PutnamBench, FATE-X, FormalConjectures100-Solved 등 여러 벤치마크에서 State-of-the-Art 결과를 달성했습니다. 특히 GPT-5.6 Sol과 함께 FATE-X에서 90/100, FC100-solved에서 78/100, FormalQualBench에서 14/23, 그리고 IMO 2026의 모든 6개 문제를 해결했습니다 [Figure 3, cite: 1]. PutnamBench에서는 GPT-5.5를 사용하여 672개 문제 중 670개를 해결했습니다. 이러한 결과는 복잡한 Workflow 없이도 단일 실행으로 달성되었으며, 더 큰 Inference Budget을 통해 가능했습니다.
• Specialized Workflows 능가: 동일한 모델에서, h1은 Goedel-Architect 및 AlphaProof Nexus와 같은 전문화된 시스템과 비교하여 동등하거나 더 우수한 성능을 더 낮은 비용으로 달성했습니다 [Figure 1, cite: 1]. 예를 들어, PutnamBench에서 DeepSeek V4 Flash를 사용한 h1은 Goedel-Architect의 Pass@4 (Informal Proof Seeding) 결과인 597 solves를 598 solves로 능가하면서도 문제당 비용은 $1.47에서 $1.08로 낮았습니다 [Figure 1, cite: 1]. 또한, Numina-Lean-Agent가 특정 난이도 문제에 Hand-Designed Workflow를 사용한 반면, h1은 GPT-5.2만을 사용하여 동일한 Putnam 2025의 12문제를 모두 해결했으며, A5 문제의 비용은 $1,000에서 $81.52로 크게 절감되었습니다.
• Longer Attempts vs. Repetition: h1은 Open Problem에 대해서도 단일 시도(Pass@1)를 연장하는 것이 여러 번 반복하는 것(Pass@kk)보다 효율적일 수 있음을 보여주었습니다. 5개의 Open Erdős Problem에서 h1의 단일 시도(Pass@1)는 AlphaProof Nexus의 기본 Agent(APN basic, Pass@3)보다 낮은 평균 성공 비용으로 더 높은 해결률을 달성했으며, 전체 APN 시스템을 Pareto-Dominate했습니다 [Figure 1, cite: 1].
• Harness Design의 중요성: 단순한 루프 내에서도 Harness Design은 해결률과 비용에 큰 영향을 미칩니다. 효율적인 Lean Interface, 신뢰할 수 있는 Feedback, 지속적인 진행을 가능하게 하는 루프, 그리고 효과적인 Reasoning 및 Cache Reuse가 중요함을 AxProverBase, Claude Code, Humanfia 등과의 비교를 통해 확인했습니다.

4. Conclusion & Impact (결론 및 시사점)

본 연구는 Frontier Models를 위한 Harness가 Human-Designed Workflows를 강요하기보다, 단순한 루프와 충분한 Budget을 제공해야 한다는 결론을 내립니다. h1이라는 단순한 루프는 효율적인 Lean Interface를 통해 State-of-the-Art 결과를 달성하고, 동일한 모델 및 유사한 비용에서 Hand-Designed Workflows와 동등하거나 더 나은 성능을 보였습니다. 특히, Open Problem에 대해서는 단일 시도를 연장하는 것이 반복보다 더 효율적일 수 있음을 입증했습니다.

이 연구는 Automated Theorem Proving 분야에 Bitter Lesson을 확장하며, Harness Design의 중요성을 강조합니다. 미래 연구에서는 Workflow를 설계하기 전에 Frontier Models를 효율적인 실행 Feedback을 갖춘 단순한 루프에서 현실적인 Budget으로 평가해야 할 필요성을 시사합니다. 이는 Formal Verification, Software Verification, 그리고 대규모 라이브러리 및 코드베이스에서의 Coding과 같이 검증자와 함께 작동하는 Long-Horizon Agent의 개발에 중요한 영향을 미칠 것입니다.

⚠️ 알림: 이 리뷰는 AI로 작성되었습니다.