TL;DR
This paper introduces IMO-Steps, a new dataset of 1,329 formalized mathematical lemmas in Lean 4, created by manually proving and decomposing hard International Math Olympiad (IMO) problems. By breaking these complex problems down into smaller, approachable building blocks, the authors provide a much-needed diagnostic benchmark to evaluate where state-of-the-art LLMs fail in multi-step mathematical reasoning.
What Problem Does This Paper Address?
AI models have made massive strides in informal mathematics, but writing formal proofs—code that can be mathematically verified by proof assistants like Lean—remains an incredibly steep hill to climb. The standard community benchmark, miniF2F, contains 20 grueling IMO problems in its test set, but historically, 14 of them lacked any publicly available formal proof.
When a state-of-the-art model fails to solve one of these monolithic problems, it creates an evaluation blind spot: researchers cannot tell where the model failed or if it was even close. Proving an IMO problem requires both high-level planning (devising a proof sketch) and low-level execution (writing the actual Lean code for each step). Current benchmarks evaluate both simultaneously, leading to an "all-or-nothing" result where models fail implicitly without providing diagnostic feedback.
Methods
To bridge this gap, the authors manually wrote complete, original formal proofs in Lean 4 for the 14 missing miniF2F IMO problems, plus 3 additional problems from IMO 2022 and 2023.
They then applied a technique called Lemma Decomposition to break 13 of these complex proofs down into their constituent building blocks. Mechanistically, this involves taking intermediate hypotheses within a long proof and isolating them into standalone lemmas. By granting previous steps as hypotheses to subsequent steps, they created a chain of progressively easier sub-problems. While the authors outline a theoretical framework to automatically extract up to $(3n - 7)$ lemmas from an $n$-line proof, they relied on human mathematical judgment to curate a clean dataset, averaging roughly one lemma per 3.5 lines of proof.
Finally, they evaluated SOTA models using an automated feedback loop. If a model's generated Lean code failed to compile, the system fed the compiler error messages back to the model using a Lean library called REPL, allowing up to 10 rounds of self-correction.
Datasets
The paper introduces IMO-Steps, which builds upon and expands the miniF2F test set:
- Complete IMO Proofs: 17 fully formalized IMO problems consisting of 5,790 lines of Lean 4 code.
- Decomposed Lemmas: 1,329 distinct lemmas spanning over 40,000 lines of Lean code, categorized by topics like algebra and number theory.
The dataset and code are publicly hosted on GitHub.
Key Insights and Ideas
- The "Short-Proof" Ceiling for Specialized Models: State-of-the-art specialized theorem provers like DeepSeek-Prover and Goedel-Prover are highly optimized for short-horizon tasks. They lean heavily on automated Lean tactics (like
nlinarith) to solve 1- or 2-line proofs but drop to a 0% success rate for any lemma requiring more than 10 lines of code. - Generalists vs. Specialists: OpenAI’s
o3-mini(a general-purpose reasoning model) displayed a fundamentally different capability profile. While its baseline accuracy on simple lemmas was lower than the specialized models, it was the only model capable of successfully generating long, complex proof chains (up to 34 lines). This suggests that RL-tuned reasoning models possess superior long-horizon planning capabilities. - The Power of the Compiler Feedback Loop: Providing automated compiler feedback yields massive performance gains. For instance,
o3-mini's zero-shot accuracy on the dataset was a meager 6.0%, but shot up to 23.8% after 10 rounds of interactive feedback. - Proof Bloat: The authors observed that LLMs frequently generate "bloated" proofs—unnecessarily re-proving conditions that were already explicitly provided in the problem statement.
Key Results
The authors benchmarked several leading models on the new IMO-Steps dataset:
- DeepSeek-Prover-v1.5-RL achieved the highest overall accuracy, solving 39.3% (522/1,329) of the lemmas.
- Goedel-Prover followed closely at 37.9% (504/1,329).
- o3-mini solved 23.8% of the lemmas with the help of the feedback loop. In contrast, other leading LLMs not explicitly exposed to formal math training, like Qwen 2.5 Math and Llama 3.1, failed almost entirely (solving 1 and 0 lemmas, respectively).
- An error analysis on
o3-minirevealed that its primary failure modes were "Minor errors" (75.1% of failures, such as missing arguments) and "Wrong implementations" (46.9%, such as calling the wrong lemma from Lean's Mathlib library).
Limitations and Future Work
The primary limitation of this work is its scope: it exclusively covers algebra and number theory problems, omitting other major IMO categories like combinatorics and geometry.
Furthermore, while IMO-Steps successfully isolates the execution phase of theorem proving by providing the intermediate steps, the community still faces the massive challenge of training AI models to perform the high-level planning required to generate these proof sketches autonomously from scratch. The authors hope this dataset serves as the necessary stepping stone toward that goal.
Summary updated