CoChat

Advancing mathematics research with AI-driven formal proof search

Open access

The DOI matches its Crossref record; 80 of the 80 references it cites were found in a registry or an index; none of the 41 sources its claims cite is checked for support yet.

Abstract

Large language models (LLMs) increasingly excel at mathematics tasks, but their unreliability limits their utility in mathematics research. A mitigation is to use LLMs to generate formal proofs in languages such as Lean, in which the compiler verifies every proof step. We present the first demonstration of this method’s value in solving open problems at scale. We built an artificial intelligence agent for formal proof search that autonomously resolved nine of 353 open Erdős problems, proved 44/492 On-Line Encyclopedia of Integer Sequences conjectures, and is being deployed in combinatorics, optimization, graph theory, algebraic geometry, and quantum optics research. Even a basic agent alternating LLM-based generation with Lean-based verification replicated the Erdős successes. These findings demonstrate the power of formal proof search as an enabler of autonomous mathematical discovery.

Overview

CoChat Summary

TL;DR

The paper reports a large-scale evaluation of AI-driven formal proof search in Lean, using the AlphaProof Nexus framework to attack open research problems. Its full-featured agent autonomously solved 9 of 353 open Erdős problems, proved 44 of 492 OEIS conjectures, and was deployed in several research areas.

Key findings

  • The full-featured agent solved 9/353 open Erdős problems, including two questions open for 56 years, at a per-problem inference cost of a few hundred dollars.
  • It proved 44/492 OEIS conjectures that manual review found correctly formalized and previously unproven.
  • A basic agent alternating LLM generation with Lean verification replicated the Erdős successes but was costlier on the hardest problems.
  • AlphaProof in standalone tree-search mode and basic agents using smaller models (Gemini 3.0 Flash, Gemini 3.1 Flash-Lite) solved none of the Erdős problems.

Methods

  • The authors built AlphaProof Nexus, an LLM-aided proof-generation framework using Lean compiler feedback, with a basic agent of independent subagents and a full-featured agent adding evolutionary search, Elo-based sketch rating, P-UCB sampling, and AlphaProof as a tool.
  • Evaluation used all 353 Lean formalizations of Erdős problems available in Formal Conjectures, terminating search after 3000 episodes if no proof was found; OEIS evaluation used 492 autoformalized open questions with test lemmas guarding against misformalization.
  • The full-featured agent used Gemini 3.1 Pro for provers and Gemini 3.0 Flash for rater subagents; comparisons across agents used solve rate versus mean inference cost in USD.

Limitations

  • The paper states that successes are concentrated in areas such as combinatorics, convex optimization, and number theory where Lean’s library is mature and tasks decompose into tractable subgoals; most Erdős problems remain out of reach, as do problems requiring extensive new theory.
  • The paper states that agents inherit biases of their underlying LLMs and exhibit high search variance, and that reported costs do not capture the full cost of discovery, including identifying tractable problems.
  • The paper’s failure analysis found that agents often offloaded core difficulty into a single `sorry` in a helper lemma, and that some top sketches relied on hallucinated literature lemmas; the text also notes misformalization risks, including density-interpretation ambiguities that required correction.

Model-written summary. Check it against the paper before relying on it.

Integrity signals

Registry

Crossref · 10.1126/science.aej2213

Cites

80 of 80 references verified0 citation errors · 0 not checkable

Statistics

Nothing to recompute.

Figures

Image 1
CC-BY-NC-ND · From the PDF
Figure 2 Design of the full-featured AlphaProof Nexus agent. The mathematician provides as input a Lean theorem with sorry for a proof, and optionally, natural language context and additional domain knowledge encoded in Lean. The agent architecture consists of a basic generation-validation pipeline and an optional evolutionary framework. An LLM-based prover subagent attempts to solve the problem by refining proof sketches (2) . The subagent may optionally call AlphaProof as a tool; each invocation of AlphaProof on a goal returns whether a proof or disproof was found, or whether it was unsuccessful in resolving the goal. The sketch produced in the end is checked by a validator to ensure the problem statement was not changed unsafely and the proof compiles. If all goals are successfully proved, the agent outputs the final Lean proof. This basic pipeline can be extended with an evolutionary population database and rating mechanism. In this configuration, validated sketches are admitted into the Population Database (3) . Simultaneously, rater subagents sample previous attempts (4) , which are then ranked by an LLM critic in matches. The match results are admitted back into the database (5) to update the Elo scores of the sketches. These scores are then used by the evolutionary algorithm to sample prior sketches from the database, constructing an overall prompt - which includes any optional inputs from the mathematician - to condition new episodes (1) .
Figure 2 Design of the full-featured AlphaProof Nexus agent. The mathematician provides as input a Lean theorem with sorry for a proof, and optionally, natural language context and additional domain knowledge encoded in Lean. The agent architecture consists of a basic generation-validation pipeline and an optional evolutionary framework. An LLM-based prover subagent attempts to solve the problem by refining proof sketches (2) . The subagent may optionally call AlphaProof as a tool; each invocation of AlphaProof on a goal returns whether a proof or disproof was found, or whether it was unsuccessful in resolving the goal. The sketch produced in the end is checked by a validator to ensure the problem statement was not changed unsafely and the proof compiles. If all goals are successfully proved, the agent outputs the final Lean proof. This basic pipeline can be extended with an evolutionary population database and rating mechanism. In this configuration, validated sketches are admitted into the Population Database (3) . Simultaneously, rater subagents sample previous attempts (4) , which are then ranked by an LLM critic in matches. The match results are admitted back into the database (5) to update the Elo scores of the sketches. These scores are then used by the evolutionary algorithm to sample prior sketches from the database, constructing an overall prompt - which includes any optional inputs from the mathematician - to condition new episodes (1) .CC-BY-NC-ND · From the PDF
Figure 3 Solve rate versus mean inference cost (USD) across six Erdős problem instances. The solve rates are evaluated for the four agents: (A) basic (blue circles), (B) basic with AlphaProof (orange squares), (C) basic with evolution (green diamonds), and (D) full-featured (red triangles). Numeric annotations denote the number of independent attempts 𝐾 ∈ { 1 , 3 , 6 , 10 } grouped together; error bars indicate one standard error interval. Due to their higher costs, agents (C) and (D) lack variance estimates, as independent attempts were used to obtain a single point estimate (see main text for details). For agents (A) and (B), each curve traces the cost-performance Pareto frontier as 𝐾 increases, revealing diminishing marginal returns at higher budgets. Agent (B) generally matches or exceeds the solve rate of the basic configuration at comparable cost. Costs reported for (B) and (D) do not include the inference cost of AlphaProof. While for most problems configuration (A) or (B) is the best, for some challenging problems like Erdős #125, the full-featured configuration (D) performs significantly better. Note that accounting for the estimated AlphaProof cost of 60 USD does not change the above outcomes beyond the margin of error.
Figure 3 Solve rate versus mean inference cost (USD) across six Erdős problem instances. The solve rates are evaluated for the four agents: (A) basic (blue circles), (B) basic with AlphaProof (orange squares), (C) basic with evolution (green diamonds), and (D) full-featured (red triangles). Numeric annotations denote the number of independent attempts 𝐾 ∈ { 1 , 3 , 6 , 10 } grouped together; error bars indicate one standard error interval. Due to their higher costs, agents (C) and (D) lack variance estimates, as independent attempts were used to obtain a single point estimate (see main text for details). For agents (A) and (B), each curve traces the cost-performance Pareto frontier as 𝐾 increases, revealing diminishing marginal returns at higher budgets. Agent (B) generally matches or exceeds the solve rate of the basic configuration at comparable cost. Costs reported for (B) and (D) do not include the inference cost of AlphaProof. While for most problems configuration (A) or (B) is the best, for some challenging problems like Erdős #125, the full-featured configuration (D) performs significantly better. Note that accounting for the estimated AlphaProof cost of 60 USD does not change the above outcomes beyond the margin of error.CC-BY-NC-ND · From the PDF
Figure 2 Rater agent prompt (condensed). Elided text is represented by [...] . Text in braces denotes template variables populated at runtime. For example, { player blocks } is replaced by the sketches to be Figure 8 | Full prompt for the basic agent (A). Text in braces denotes template variables populated at runtime. For example, {code} is replaced by the current Lean file.
Figure 2 Rater agent prompt (condensed). Elided text is represented by [...] . Text in braces denotes template variables populated at runtime. For example, { player blocks } is replaced by the sketches to be Figure 8 | Full prompt for the basic agent (A). Text in braces denotes template variables populated at runtime. For example, {code} is replaced by the current Lean file.CC-BY-NC-ND · From the PDF
Image 5
CC-BY-NC-ND · From the PDF
Figure 10 Solve rate versus mean inference cost (USD) across nine Erdős problem instances. Seven system configurations shown: basic (blue circles), basic with AlphaProof (AP) (orange squares), basic with evolution (green diamonds), full (red triangles), full@1 (purple downward triangles), full@3 (brown pluses), and full@6 (pink x), where @S are the variants of full system with a given number of parallel LLM generation threads. Connected curves denote the number of independent attempts 𝐾 . Error bars indicate one standard error interval. For the basic and basic with AlphaProof configurations, each curve traces the cost-performance Pareto frontier as 𝐾 increases, revealing diminishing marginal returns at higher budgets. Note that basic with AlphaProof and full do not include the inference cost of AlphaProof.
Figure 10 Solve rate versus mean inference cost (USD) across nine Erdős problem instances. Seven system configurations shown: basic (blue circles), basic with AlphaProof (AP) (orange squares), basic with evolution (green diamonds), full (red triangles), full@1 (purple downward triangles), full@3 (brown pluses), and full@6 (pink x), where @S are the variants of full system with a given number of parallel LLM generation threads. Connected curves denote the number of independent attempts 𝐾 . Error bars indicate one standard error interval. For the basic and basic with AlphaProof configurations, each curve traces the cost-performance Pareto frontier as 𝐾 increases, revealing diminishing marginal returns at higher budgets. Note that basic with AlphaProof and full do not include the inference cost of AlphaProof.CC-BY-NC-ND · From the PDF
Figure 11 Box plots illustrating the distribution of a wall-clock time for a successful proof for the Erdős problems. Three distinct experimental configurations are compared: basic@K=10 (blue), basic with AlphaProof @K=10 (orange), and full (red). The solid horizontal line within each box denotes the median time, while the upper and lower box boundaries represent the third and first quartiles, respectively. Whiskers extend to the rest of the distribution, and individual circles indicate outlier data points. Triangular markers denote instances with a single data point where only one proof attempt was successful. A cut-off of 48 hours applied to all experiments.
Figure 11 Box plots illustrating the distribution of a wall-clock time for a successful proof for the Erdős problems. Three distinct experimental configurations are compared: basic@K=10 (blue), basic with AlphaProof @K=10 (orange), and full (red). The solid horizontal line within each box denotes the median time, while the upper and lower box boundaries represent the third and first quartiles, respectively. Whiskers extend to the rest of the distribution, and individual circles indicate outlier data points. Triangular markers denote instances with a single data point where only one proof attempt was successful. A cut-off of 48 hours applied to all experiments.CC-BY-NC-ND · From the PDF

Verification

Claims the paper makes

0 Valid · 3 Not valid · 29 Not checked · 127 Own results and interpretations

98 more claims

Create a free account to see all 159 claims and every source verdict.

See all claims — free account
  • Probably not a substantial claim. 30
  • It may state two separate claims as one. 31
  • The quote only partly states this claim. 4

Create a free account to see these claims.

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

Each contradiction between two passages listed here was confirmed by an independent check.

1 of 1

Citations

Cites

Show all 80 references

Research works printed but not linked: 10

  1. 10.1006/jcta.2000.3142 · DOI
  2. N. J. Sloane The On-Line Encyclopedia of Integer Sequences in Proceedings of the 14th Symposium on Towards Mechanized Mathematical Assistants: 6th International Conference Calculemus ’07 / MKM ’07 (Springer Berlin Heidelberg) (2007) p. 130.10.1007/978-3-540-73086-6_12 · DOI · Paper page
  3. A. Thakur, G. Tsoukalas, Y. Wen, J. X. Xin, S. Chaudhuri, An in-context learning agent for formal theorem-proving, in Conference on Language Models (2024).
  4. A. Nagda P. Raghavan A. Thakurta Reinforced generation of combinatorial structures: Ramsey numbers. arXiv.2603.09172 [math.CO] (2026). · arXiv
  5. D. Alvarez-Melis, T. Jaakkola, S. Jegelka, Structured Optimal Transport, in Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics (2018).
  6. H. Shugart J. M. Altschuler Negative stepsizes make gradient-descent-ascent converge. arXiv preprint arXiv:2505.01423 (2025). · arXiv
  7. Y. Cai, W. Zheng, Accelerated Single-Call Methods for Constrained Min-Max Optimization, in International Conference on Learning Representations (2023).
  8. S. Lee, D. Kim, Fast extragradient methods for smooth structured nonconvex-nonconcave minimax problems. Adv. Neural Inf. Process. Syst. (2021).
  9. S. Lee D. Kim Semi-Anchored Gradient Methods for Nonconvex-Nonconcave Minimax Problems (2024) https://openreview.net/forum?id=rmLTwKGiSP.
  10. L. Chen, L. Luo, Near-Optimal Algorithms for Makinghe Gradient Small in Stochastic Minimax Optimization. J. Mach. Learn. Res. 25, 1–44 (2024).

Cited by

See all 65

Metadata

Authors
Tsoukalas, G., Kovsharov, A., Shirobokov, S., Surina, A., Firsching, M., Bérczi, G., Ruiz, F. J. R., Suggala, A., Wagner, A. Z., Wieser, E., Yu, L., Huang, A., Horváth, M. Z., Ferraiuolo, A., Michalewski, H., Grosu, C., Lockhart, E., Hubert, T., Balog, M., Kohli, P., & Chaudhuri, S.
Affiliations
  • Google DeepMind (United Kingdom) (GB)
  • Aarhus University (DK)
  • Google DeepMind, London, UK.
  • Google, Mountain View, CA.
Corresponding author
  • Tsoukalas, George
  • Kovsharov, Anton
  • Shirobokov, Sergey
  • Kohli, Pushmeet
  • Chaudhuri, Swarat
Venue
Science
Published
2026-10-08
Volume
394
Issue
6820
Pages
234-239
ISSN
  • 0036-8075 (ISSN-L)
  • 1095-9203
OpenAlex
W7162098200
Cited by
62
References
76
Citations by year
2026: 61
FWCI
97.09
Type
journal article
Language
en
Open access
Licence
cc-by-nc-nd
Locations
  • Science (publishedVersion)
  • PubMed (publishedVersion)
  • arXiv (Cornell University) (submittedVersion, cc-by-nc-nd)
  • arXiv (Cornell University) (cc-by-nc-nd)
Topics
  • Physical Sciences › Computer Science › Computational Theory and Mathematics › Mathematics, Computing, and Information Processing
  • Physical Sciences › Computer Science › Software › Logic, programming, and type systems
  • Physical Sciences › Computer Science › Artificial Intelligence › Artificial Intelligence Applications
Keywords
large language models, Lean theorem prover, AI agents, open problems in mathematics, Erdős problem, proof verification, autonomous reasoning

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

A language model drew the claims from the paper on 2026-11-21, under version 3 of the claim definition (model deepseek-v4.1-flash, prompt extract-v3).

A second model labelled each claim on 2026-11-21 (model jev-1.13-20260917, definition revision gold-guideline-v0.2).

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review

Data sources

Bibliographic data: Semantic Scholar, OpenAlex, Crossref.

Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).

Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.