h1: A Taste of the Bitter Lesson in Automated Theorem Proving

A Taste of the Bitter Lesson in Automated Theorem Proving

Automated theorem proving (ATP) is a critical frontier in artificial intelligence, aiming to mechanize the rigorous verification of mathematical proofs. Recent advances in large language models (LLMs) have propelled informal mathematical reasoning, yet formal theorem proving—where proofs are precisely checked by systems like Lean 4—has often depended on complex, human-designed workflows. These workflows orchestrate planning, decomposition, and specialized provers around LLMs, raising an important question: can a simple, scalable agentic loop, relying primarily on test-time compute and minimal workflow constraints, match or surpass these specialized systems?

The Problem: Specialized Workflows vs. Simple Scaling

Formal theorem proving requires constructing proofs that a verifier can check step-by-step. Traditional approaches have layered intricate workflows around LLMs to manage the complexity, including breaking problems into subgoals and coordinating multiple agents or provers. However, such workflows can be costly to design and may conflate gains from stronger models or more compute with gains from workflow engineering.

The authors investigate whether a simple harness—a minimal interface that allows an LLM to iteratively edit and check proofs with verifier feedback—can achieve state-of-the-art results by scaling test-time compute alone. This question is motivated by the “bitter lesson” in AI, which suggests that methods that leverage increased computation and generality tend to outperform those relying on human domain knowledge.

The Method: The h1 Harness

The authors introduce h1, a simple harness that interfaces efficiently with the Lean 4 theorem prover. Unlike specialized workflows, h1 imposes no decomposition or planning structure. Instead, it operates as a loop where a multi-turn LLM agent:

  • Edits a persistent working Lean file incrementally.
  • Receives immediate compiler feedback on errors and open goals.
  • Uses optional tools to search the Mathlib library, inspect definitions, and test proof fragments.
  • Submits the proof to an external validator (SafeVerify) for formal verification.
  • On failure, invokes a reflection LLM to compact the transcript and feedback into a summary that guides the next iteration.

This loop continues until the proof is accepted or a budget cap is reached. The design emphasizes efficient interaction, persistence, and context reuse rather than prescribing proof strategies.

Evidence and Results: Simple Scaling Matches Specialized Workflows

The authors evaluate h1 across multiple challenging benchmarks:

  • PutnamBench: 672 problems from the Putnam undergraduate math competition.
  • FATE-X: 100 algebra problems at or beyond PhD qualifying exam level.
  • FormalConjectures100-Solved: 100 formalized research conjectures with known informal solutions.
  • Open problems: 236 open conjectures from Formal Conjectures, including Erdős problems.

Key findings include:

  1. State-of-the-art performance with a simple loop: Using frontier LLMs like GPT-5.6 Sol and Gemini 3.1 Pro, h1 achieves or surpasses the best published results on all major benchmarks. For example, h1 with GPT-5.5 solves 670 of 672 PutnamBench problems in a single run per problem.
  2. Matching or outperforming specialized workflows: At matched models and comparable inference costs, h1 matches or Pareto-dominates systems like Goedel-Architect and AlphaProof Nexus, which rely on complex workflows involving planning and decomposition. For instance, h1 with DeepSeek V4 Flash matches Goedel-Architect’s pass@4 results at lower estimated cost.
  3. Solving open research problems: h1 settles eight previously open conjectures, including variants of Erdős problems and conjectures in quantum information theory.
  4. Longer single attempts can be more efficient than repetition: On Erdős problems, extending a single h1 attempt (pass@1) often achieves higher solve rates at lower cost than multiple independent attempts (pass@k), challenging the common practice of relying on repetition.

What Makes h1 Effective?

The authors emphasize that simplicity alone is insufficient; the harness’s design critically affects efficiency and success rates. Important factors include:

  • Efficient, reliable interface: h1 allows small, incremental edits with immediate feedback, persistent context caching, and robust error handling. This contrasts with other loops that regenerate entire proofs after each edit or suffer from frequent failures.
  • Tool integration: Search tools (LeanExplore, Loogle, grep), the Lean REPL, and language-server features enable the model to retrieve definitions and lemmas effectively.
  • Persistence and reflection: The reflection LLM compacts lessons from failed attempts, discouraging premature giving up and preventing repeated mistakes.
  • Context management: Reusing and compacting context before degradation balances the cost of long contexts and the loss of information from restarts.
  • Detailed prompting: Carefully crafted prompts instruct the model to avoid verifier gaming, to treat incomplete proofs as checkpoints, and to persist on open problems.

Limitations and Considerations

The authors acknowledge several limitations and open questions:

  • Benchmark exposure: Many frontier models are black boxes, and it is difficult to rule out training exposure to benchmark problems or solutions, which could affect results.
  • Scalability beyond single files: h1 currently operates on single Lean files. Larger formalizations, such as entire textbooks or famous theorems like Fermat’s Last Theorem, require managing dependencies across files and parallel agents.
  • Tool coverage: The current tools focus on Lean 4 and do not support numerical computation, simulation, or web search.
  • Human-designed interface: While the bitter lesson discourages human domain knowledge, the authors argue that human effort is currently best spent on designing efficient interfaces rather than workflows.

Practical Implications

This work suggests a paradigm shift for automated formal theorem proving and related structured reasoning tasks:

  • Rather than investing heavily in hand-designed workflows, researchers and practitioners should first evaluate frontier LLMs in simple, efficient loops that leverage test-time compute and verifier feedback.
  • Harness design should focus on enabling persistent, incremental interaction with the environment, robust error handling, and effective context management.
  • Scaling compute at test time can unlock capabilities that specialized workflows attempt to encode, aligning with the bitter lesson that general methods benefiting from scale outperform domain-specific heuristics.
  • For complex formalizations, future work should explore adding parallelism, richer tools, and codebase management without prescribing their use, allowing models to discover efficient strategies.

“Frontier models keep improving their reasoning and adaptation to execution feedback, and harnesses should help these capabilities scale through efficient interaction with the environment rather than impose workflows.”

Summary

The authors demonstrate that a simple agentic loop harness, h1, interfacing efficiently with Lean 4 and leveraging test-time compute scaling, achieves state-of-the-art results in automated formal theorem proving. This approach matches or outperforms specialized workflows that rely on human-designed planning and decomposition, even solving open research problems. The findings extend the bitter lesson to harness design: efficient, persistent interaction and reflection matter more than complex prescribed workflows. These insights encourage reevaluating the role of human domain knowledge in ATP and highlight the importance of scalable, general methods supported by effective harnesses.


Sources

AI-assisted research summary. Check the original paper for complete methods, results, and limitations.

Avatar photo

Tech News

Jeff is a passionate blog writer who shares clear, practical insights on technology, digital trends and AI industries. With a focus on simplicity and real-world experience, his writing helps readers understand complex topics in an accessible way. Through his blog, Jeff aims to inform, educate, and inspire curiosity, always valuing clarity, reliability, and continuous learning.

↑ ↓ navigate Enter open Esc close