[KongchangAI]
· 4 min read· 2,137 words

Simple Loop Tops Automated Theorem Proving: The Bitter Lesson Revisited

Simple Loop Tops Automated Theorem Proving: The Bitter Lesson Revisited

A minimalist test-time scaling loop, H1, matches or surpasses complex custom theorem-proving systems under the same model and budget, confirming the bitter lesson.

The paper "A Taste of the Bitter Lesson in Automated Theorem Proving" compares two approaches to automated theorem proving: designing complex human-crafted workflows for large models versus relying solely on the model's own reasoning and test-time scaling. The authors propose a minimalist harness, H1—providing only an efficient Lean tool interface. The model reasons, calls tools, and submits for verification in a ReAct loop; after failure, a reflection model compresses the feedback and iteration continues, with no proof structure preset. With matched models and comparable inference costs, H1 often Pareto-dominates custom systems, achieves SOTA on benchmarks such as Putnam and IMO2026, and solves 8 open conjectures; in sequential scaling, extending a single attempt is more cost-effective than repeating many times; even among simple loops, interface quality and reflection design still cause huge gaps.

Automated theorem proving has long been split between two approaches: one designs complex, human-crafted workflows around large models, and the other lets models rely on their own reasoning and test-time scaling capabilities. A recent paper titled A Taste of the Bitter Lesson in Automated Theorem Proving delivers a disruptive conclusion: a minimalist test-time scaling loop, given a matched model and comparable budget, can often match or even surpass carefully engineered custom systems. This provides strong support for Sutton's "bitter lesson" hypothesis in the domain of formal mathematics.

Two Approaches and One Core Question

According to a Bilibili podcast episode, progress in automated theorem proving currently advances along two directions. The first scales the chain-of-thought and reasoning abilities of large models themselves; the second designs complex workflows around large models that include steps such as planning, decomposition, proving, and refinement. Mainstream formal proof tools like Lean natively support structured proof search, and many studies exploit this to build complex harness frameworks—essentially fencing the model into a fixed set of problem-solving steps.

The contradiction is that frontier large models already possess strong reasoning and test-time scaling capabilities. If we set aside complex custom workflows, can a simple test-time scaling loop alone achieve results comparable to or better than complex systems? This is the core question the paper aims to answer.

The practical significance of this question is not to be underestimated. Frontier large models can already generate many research-level mathematical results, but their informal arguments are hard to verify manually, making the mechanically checkable nature of automated theorem proving a necessary component for automated discovery. Many prior studies, when comparing different systems, often conflated stronger models, more compute, and new workflows—or compared against baselines with poor scaling—making it impossible to disentangle whether performance gains came from workflow design or from test-time compute investment.

Time to think it over again

Lean and Mathlib: Lean is an interactive theorem prover based on dependent type theory, and its proof terms are mechanically checked line by line by the kernel—as long as type checking passes, the proposition is true. This is precisely what distinguishes automated theorem proving from informal mathematics. Mathlib is a massive mathematics library jointly built by the Lean community, containing a large number of already-formalized theorems and lemmas ranging from basic algebra and topology to analysis, constituting a "structured resource environment" that models can retrieve and reuse. The Lean Explorer, Lean REPL, and language server that H1 relies on in the paper are essentially interfaces built on top of Mathlib that provide search, snippet testing, and goal-state queries. Whether the model can efficiently invoke these tools directly determines how large a proof space it can explore within a single budget.

H1: The Design Philosophy of a Minimalist Loop

To isolate the influence of workflow design, the authors designed a minimalist harness called H1. It provides only an efficient Linux interface and imposes no decomposition or search structure whatsoever. The model iteratively reasons, calls tools, and submits for verification; upon failure, feedback is consolidated into a new context and it keeps trying until success or until the cost cap is reached. Each iteration essentially appends a period of "wait, let me think again" to the model's thought process, relying entirely on scaling test-time compute to improve performance.

In each iteration of H1, the large model performs reasoning and tool calls in a ReAct loop. If verification fails, a dedicated reflection model compresses the entire conversation history and feedback into a structured summary containing verified progress, lessons from failed attempts, and useful lemma names, while prompting the model not to give up easily. The model then continues working from the current file with the summary in hand. The entire process presets no proof structure whatsoever; the model autonomously decides how to proceed.

The tools H1 provides all come from the Lean ecosystem: Lean Explorer for searching Mathlib, Lean REPL for testing proof snippets, a language server for reporting goals and definitions, and Safe Verify for final verification. The model can decide for itself when to use which tool, with no human-specified call order or usage scenarios.

Three Core Conclusions and Experimental Evidence

The paper's core conclusions can be summarized in three points, each backed by corresponding experimental data.

Conclusion 1: Simple test-time scaling can reach the frontier

With the same model and a comparable budget, H1 often matches or even Pareto-dominates customized specialized systems, achieves state-of-the-art results on multiple benchmarks, and solves eight open conjectures.

Specifically, on the Putnam Bench, H1 with the same model as Goedel Architect is cheaper yet performs better. With GPT 5.6 Sol, H1 achieves a 90-100 solve rate on FateX, 178% on FC100 Soft, 23-14% on Formal Core Bench, solves all 6 problems on IMO2026, and correctly solves 670 of the 672 problems on Putnam Bench. Even with open-source models, GPT 4.6 V4 Flash paired with H1 achieves a 43% solve rate on the X line, surpassing the specially optimized LeanStraw 1.5's 34%.

Regarding open conjectures, the paper tested 236 problems from Formal Conjectures, of which H1 with GPT 5.6 Sol solved 8, including variants of Erdos 138 and 337, 3 OEIS conjectures, a proof of the existence of the AME910 state in Open Quantum Problem 35, and two conjectures from Written on the Wall 2. H1 even discovered several formalization errors in Formal Conjectures—where the written formal proposition did not match the originally intended conjecture. For example, the formalization of the Poincaré conjecture omitted an assumption, and H1 directly provided a counterexample to that erroneous formal proposition. These errors have since been fixed upstream.

H1 with GPT 5.6 Sol

Conclusion 2: Extending a single attempt is more efficient than repeating many times

This conclusion is counterintuitive. It is commonly believed that running multiple independent attempts and using pass@k will always improve the success rate, but the paper finds that under sequential test-time scaling, the pass@1 curve can even Pareto-dominate pass@k as the budget increases.

On five public Erdos problems, using the same Gemini 3.1 Pro model, giving H1 a higher budget for a single attempt reached an 82.5% solve rate at $121, whereas APN Basic required three runs to reach 75.4% at a cost of $191; the full AlphaProof Nexus required $317 to reach a 76% solve rate. Even counting the cost of failed attempts, H1's single attempt reaching an 82.5% solve rate costs on average $138 per problem, while running three repetitions costs $202 to reach the same solve rate.

The paper also notes that this balance is not absolute: at particularly high budgets, repeated attempts achieve higher solve rates. The optimal balance between depth and breadth depends on budget, solve rate, and problem type. The paper suggests leaving this choice to the model itself rather than having humans pre-set a fixed budget or number of attempts.

Giving H1 a higher budget for a single attempt

The budget implications of pass@k and pass@1: pass@k means independently sampling k times, with success if any one attempt succeeds—a common evaluation metric in code generation and theorem proving; pass@1 is the success rate of a single attempt. The problem is that the two are not comparable under "equal compute budget": k independent attempts each restart from a blank context, and the experience of failed attempts is completely discarded; sequential test-time scaling concentrates the budget on a single trajectory, where the reflection summary after failure is carried into the next round, forming an accumulable context. The Pareto comparison proposed in the paper unifies the x-axis as API-equivalent cost and then compares solve rates at each budget point, thereby exposing the cost advantage of "depth-first" in the medium-budget range and the boundary at which "breadth-first" overtakes it at very high budgets.

Conclusion 3: Simple does not mean arbitrarily designed

Even among simple loops, different harness designs differ enormously in solve rate and cost. With the same Gemini 3 Flash model and a $20 budget, H1 solves 69 problems on Putnam 100, while AX Prover Base solves only 18. The core difference is that H1 supports incremental file editing, where each edit yields immediate feedback, whereas AX Prover Base regenerates the complete proof every time, wasting a great deal of time on invalid import errors.

Through controlled experiments, the paper finds that an efficient and reliable Lean interface, a loop that supports repair and reflection, and efficient reasoning and cache reuse—these design points have an enormous impact on performance. In addition, detailed prompts can substantially improve performance: on 6 Erdos problems, a single attempt with detailed proof and reflection prompts outperforms 6 runs with brief prompts. The number of rounds between two reflections also has an optimal range; too many or too few both reduce efficiency.

And Formal Core Bench

Incremental editing vs. full rewriting: In Lean, once an import or definition at the top of a file is wrong, all subsequent content fails to check. Incremental editing allows the model to change only a local snippet and immediately get feedback in the Lean REPL, with errors pinpointed to the line, making repair cheap; full rewriting requires the model to re-output the complete proof every round, and any import or syntax error invalidates the entire file, with large amounts of tokens consumed on repeated generation. This is the main source of the nearly fourfold difference in solve rate between H1 and AX Prover Base under the same model and budget, and it also shows that "minimalist" means not presetting a proof structure, not omitting high-quality engineering interfaces.

Methodology for Fair Comparison

The paper places special emphasis on the importance of comparing by inference cost in its experimental design. Different systems vary enormously in the compute of a single attempt—for example, one attempt by Goedel Architect allows up to 16 proof plan revisions, and one attempt by XProver Base allows 50 agent iterations. Although all are called pass@1, their compute costs differ by several orders of magnitude.

Therefore, the paper compares the efficiency of different harnesses while fixing the model, and compares the progress of different models while fixing the harness. All costs are converted to API-equivalent cost based on actual token usage, with the cost cap per problem set to B, counting the number of problems for which a verified proof is obtained within the budget; the average cost includes all successful and failed attempts. The test environment uses Lean4 and the Mathlib library, and the verification tool uses Safe Verify to ensure the final proof fully conforms to the original proposition, with no missing assumptions or unfinished steps used as placeholders. The benchmark suite covers undergraduate-level Putnam, high-school Olympiad-level IMO2026, PhD qualifying-exam-difficulty FateX and Formal Core Bench, as well as open formalized conjectures with no known solution.

Implications for Agent Design

The significance of this research extends beyond automated theorem proving. According to the podcast summary, any agent that needs to interact with a verifier and work in a rich structured resource environment—scenarios such as software verification and programming in large codebases—can borrow this idea: rather than designing complex workflows for the model, simply provide an efficient and reliable environment interface and a continuous feedback mechanism and let it autonomously advance the task; the results may actually be better.

The paper also contains a noteworthy case: Problem A5 of the 2025 Putnam competition. The previous Numina system specially designed a sub-agent workflow for this problem, using an orchestrator to assign tasks such as blueprint, decomposition, draft, and proof to different sub-agents, and also used GPT5.2 to provide hints, with a budget of $1,000; yet GPT5.2 solved this problem in a single round of attempts within H1, costing only $81.52. If a single H1 run fails, simply repeating it a few times closes most of the gap, with no workflow adjustment needed—just rerunning from a blank context. Of the 12 problems in the 2025 Putnam, H1 with Opus4.7 solved 11 in a single run, and retrying the remaining one 6 times solved all of them, at a lower cost than the specialized custom system.

Even for gaps that cannot be closed by repetition, updating to the next-generation model catches up. On Formal Core Bench, Merlin with Opus4.7 achieves 10 out of 23, while H1 with Opus4.7 reaches at most 9 out of 23; but with Opus4.8, H1 directly achieves 13 out of 23, at less than half the cost of Merlin. This is a typical manifestation of the bitter lesson: improvements in the model's own capabilities directly benefit a general, simple framework.

In the field of formal mathematics, scalable general simple frameworks will ultimately surpass customized complex workflows. This conclusion once again validates Sutton's bitter lesson hypothesis and provides a valuable reference direction for future agent design.

One-line Summary

A minimalist test-time scaling loop, H1, matches or surpasses complex custom theorem-proving systems under the same model and budget, confirming the bitter lesson.

#automated theorem proving#bitter lesson#test-time scaling#Lean#Mathlib#AI agent design#formal mathematics
Share:

Related articles