AI Wiki

AlphaProof Nexus

AI ResearchAI for ScienceGoogle DeepMindMathematics
16 min read
Updated
Suggest editHistoryTalk
RawGraph

Last edited

Fact-checked

Sources

15 citations

Revision

v2 · 3,292 words

Fact-checks are independent of edits: a reviewer re-verifies the article against its sources and stamps the date. How we verify

AlphaProof Nexus is a formal proof search system from Google DeepMind that pairs a general-purpose language model with the Lean proof assistant in an agentic loop, submitting each candidate proof step to the Lean compiler and using the compiler's error messages to steer the next attempt. It was described in the preprint "Advancing Mathematics Research with AI-Driven Formal Proof Search," posted to arXiv as 2605.22763 on 2026-05-21 and revised on 2026-06-08.[1][2] The paper reports that the system's most capable configuration autonomously resolved 9 of 353 formalized open Erdős problems at a per-problem inference cost of "a few hundred dollars," proved 44 of 492 autoformalized conjectures drawn from the Online Encyclopedia of Integer Sequences (OEIS), and was deployed alongside human mathematicians in combinatorics, optimization, graph theory, algebraic geometry and quantum optics.[1] The name deliberately echoes AlphaProof, the reinforcement-learning prover that, working alongside AlphaGeometry 2, reached silver-medal standard at the 2024 International Mathematical Olympiad; the older system survives inside Nexus as an optional subgoal-solving tool rather than as the main engine.[2]

The result landed the same week as an unrelated OpenAI announcement about the Erdős unit distance conjecture, and both arrived roughly seven months after a widely criticized episode in which claims of AI-solved Erdős problems were retracted. Those two events shape how the Nexus numbers should be read, and they are covered below.

Background: from AlphaProof to Nexus

AlphaProof, announced on 2024-07-25 and published in Nature on 2025-11-12, was an AlphaZero-style system. At its core was a proof network, "a 3-billion-parameter encoder-decoder transformer model" that read the Lean tactic state and emitted both a policy over candidate tactics and a value estimate, guiding a specialized tree search with AND nodes for decomposing a goal into independent subgoals.[15] It learned by reinforcement learning "by training on millions of auto-formalized problems": a fine-tuned Gemini 1.5 Pro formalizer converted approximately 1 million natural-language problems into a dataset of around 80 million formal Lean problems, and that dataset was the RL curriculum.[15] Together with AlphaGeometry 2 it solved four of the six 2024 IMO problems for 28 of 42 points, silver-medal standard; AlphaProof itself accounted for three of the five non-geometry problems, including the competition's hardest.[12][15] It was purpose-built for competition mathematics and needed extended search, in some cases three days on a single problem.[12] AlphaProof Nexus inverts that design. The heavy lifting is done by an off-the-shelf frontier large language model, specifically Gemini 3.1 Pro, writing Lean proof sketches in a multi-turn loop; the specialized prover is demoted to a callable tool.[2]

The target also changed. AlphaProof was measured against olympiad problems with known answers. Nexus was pointed at problems that no one had solved, which raises a different and harder question: how do you know the problem was genuinely open?

How the system works

The core object is what the paper calls a Ralph loop. A prover subagent reasons in natural language, edits a Lean file through search-and-replace tools, compiles it, reads the compiler's output, and repeats. A proof counts as complete when the compiler reaches a state with no pending goals and no remaining sorry placeholders; a separate SafeVerify pass performs final validation.[2] Because Lean checks every inference, the loop has an exact binary reward signal, which is the property that makes formal mathematics unusually well suited to this kind of search.

Four configurations were evaluated.

VariantCompositionReported behavior
A (basic)Parallel, independent prover subagents running LLM plus compiler-feedback loops, no shared statePost-hoc analysis found it could prove all nine Erdős problems, but at higher cost on the hardest ones[1][2]
B (basic plus AlphaProof)Adds mid-episode calls to AlphaProof on individual subgoals"Generally matches or exceeds the solve rate" of A at comparable cost[2]
C (evolutionary)Shared population database of proof sketches, Elo ratings from Gemini 3.0 Flash rater subagents aggregated with a Plackett-Luce modelSelection via a P-UCB sampling rule[2]
D (full-featured)Evolution plus AlphaProof, with a global cache keyed on a hash of the exact Lean context and target2x to 5x cheaper on problems #125 and #138, but roughly half as cost-efficient on the rest[2]

When agent B or D calls AlphaProof on a subgoal, the tool returns a proof, a disproof, or a failure notice; proofs are substituted directly into the sketch, and the other two outcomes become feedback text for the language model.[2] Queries are capped at roughly 400 simulations per subgoal, and agent D limits an episode to five AlphaProof calls.[2]

The most striking finding is negative. The elaborate machinery was not required: the basic loop replicated every Erdős success. The authors attribute this to rapid improvement in the underlying language models and to "the power of compiler feedback in grounding LLM reasoning."[2] A critical review by Anatol Wegner treated the same fact less charitably, arguing that the Nexus architecture is largely redundant given that "the basic agent solved all 9 problems."[10]

Results

CategoryAttemptedResolvedNotes
Erdős problems3539Every Lean statement of an Erdős problem in DeepMind's formal-conjectures repository as of early February 2026[2][11]
OEIS conjectures49244Autoformalized by Gemini; the 44 are those a manual review found both correctly formalized and previously unproven[2]
Algebraic geometryCollaborationZanello's conjecture on log-concavity of pure O-sequences[2]One of two of the four open problems settled in that collaboration; press framed it as a 15-year-old Hilbert function question, a duration the paper does not state[6]
Convex optimizationCollaborationExact O(1/t) convergence rate for anchored gradient descent-ascent[2]The agent searched for the parameter schedule and the proof at the same time, finding a novel parameter choice
Quantum opticsCollaborationConjectures on monochromatic quantum graphs, including N = d in {4, 6, 10}[2]Corresponds to N-particle quantum states of local Hilbert space dimension d
Stacks ProjectFormalization effortSeveral proofs, including Lemma 04KM on separable field extensions[2]Agent D filled in material the textbook gives only in outline

The 353 Erdős problems were not chosen by DeepMind. The paper states: "We did not select which problems to attempt; the set was determined entirely by what the open-source community had formalized from the 1200+ problems catalogued on the ErdosProblems site," and acknowledges "a bias towards problems amenable to formalization in Lean."[2] That 1,200-plus figure is the size of the whole catalogue, not the open portion: as of 2026-07-27 the site lists 1,217 problems of which 565, or 46 percent, are marked solved, so the 353 formalized statements cover roughly half of what remains open.[13]

The nine Erdős problems

DeepMind counts nine resolutions by splitting #12 and #741 into two parts each. The community wiki in Terence Tao's erdosproblems repository, which logs AI contributions to Erdős problems and where DeepMind says its results were recorded, grades them somewhat differently. That wiki stopped being updated after 2026-06-30.[2][4]

ProblemPosedSubjectTao wiki classification[4]
#12(i), #12(ii)1970, Erdős and SárközyInfinite sets with divisibility constraints and prescribed density1(c) AI building on literature, citing Erdős and Sárközy (1970); logged as a partial result
#261995Whether some shift of an infinite set divides almost all integers1(c) AI building on literature, citing Ruzsa; solution to a stronger problem
#1251996Whether a sumset has positive lower density1(a) AI standalone; full solution in Lean
#1381957; the part resolved was asked in 1981Growth of van der Waerden numbers; the agent proved W(k+1) is at least W(k)+k1(a) AI standalone; logged as a partial result
#1521994Isolated elements in the sumset of a large finite Sidon set1(b) AI alongside literature discovered afterwards; full solution, in the stronger form of quadratically many such elements
#741(i), #741(ii)1994Decomposability of sets by sumset density, and basis construction1(a) AI standalone; full solution
#8461992Infinite sets avoiding collinearity1(b); full solution, obtained independently by an OpenAI internal model

Press coverage led with the claim that two of the nine had been open for 56 years, which refers to the two parts of #12 posed in 1970.[6] The wiki files that same problem under "AI building on literature," with the 1970 Erdős and Sárközy paper listed as prior work and the contribution marked partial. Wegner's review reads that entry as evidence that the novelty claim was overstated.[10] Readers should note the two framings do not agree, and that neither the paper nor the wiki claims all nine are standalone novel resolutions.

What "solving an Erdős problem" actually means

The Erdős problems are a curated list maintained by Thomas Bloom at erdosproblems.com, drawn from the problems Paul Erdős posed across a very long career. They are not a graded benchmark. The disclaimers page attached to the AI tracking wiki is blunt about this: Erdős problems "vary widely in difficulty, by several orders of magnitude," absence of past progress "may reflect obscurity rather than difficulty," and a designation of a problem as open "is always provisional," because "it has happened many times that an AI system solved a problem listed as open, only to find that the problem was already solved in the literature."[5]

Writing on Mathstodon in December 2025, five months before the Nexus preprint, Tao offered a theory: AI tools "are now becoming capable enough to pick off the lowest hanging fruit amongst the problems listed as open in the Erdos problem database," where by lowest hanging he meant "amenable to simple proofs using fairly standard techniques." He added that this is also the category most likely to have already been solved in some obscure corner of the literature.[14] The disclaimers page adds that reporting of AI contributions is likely incomplete with respect to negative results, that problems can be stated incorrectly on the list, that a solution may exploit a technicality rather than address what Erdős meant, and that an AI-found solution does not automatically merit journal publication.[5] A raw count of solved problems, in other words, carries much less information than the headline suggests.

The wiki's own taxonomy exists precisely to keep this straight. Primary contributions are split into 1(a) AI standalone, 1(b) AI alongside literature discovered afterwards, 1(c) AI building on literature known beforehand, and 1(d) AI collaborating with humans; secondary contributions cover literature search, formalization, rewriting and computation.[4] The wiki explicitly states that sections 1(a) through 1(d) are meant as equally important, not as a ranking.[4]

Why Lean changes the epistemics, and what it does not fix

A proof accepted by Lean is correct by construction. The system cannot bluff its way past the compiler the way a chat model can produce a fluent but wrong argument, so for the proof itself the hallucination problem is closed.[2] This is the central reason automated theorem proving in a formal language is treated differently from an unverified natural-language proof.

The guarantee is narrower than it first appears. Lean certifies that the Lean statement follows from the axioms, not that the Lean statement is the problem a mathematician had in mind. Nexus produced concrete examples of that gap in both directions. On problems #125 and #741(i), the agent found proofs that exploited a reading of "density" as natural density, and the informal statements were subsequently amended to "lower density" and "upper density" respectively.[2][10] The paper presents this as the agent serving "as a tool for detecting and fixing misformalizations"; Wegner presents it as the system exploiting loopholes in ambiguous statements.[2][10] Both descriptions fit the same events.

For the OEIS batch, where 492 statements were autoformalized by Gemini rather than by humans, the guard was to require the agent to prove test lemmas checking the first few terms of each sequence against its formal definition, followed by manual review of the successful cases.[2] Formal statement fidelity for the Erdős problems was checked by experts on the team after each solve.[2] The disclaimers page notes that formalization is encouraged but carries its own risks, including unproved axioms and misformalization.[5]

A third failure mode is more uncomfortable. The paper reports that on several problems, the highest-rated sketches leaned on lemmas marked sorry that the agent asserted were established results in the literature, and that on manual inspection "these lemmas proved to be hallucinations."[2] Formal verification catches this at compile time, since a sorry is not a proof, but it shows that the language model's literature claims are unreliable even inside a formal pipeline.

Reception

The paper attracted attention quickly but, as of 2026-07-27, no dedicated Google DeepMind blog post accompanied it. The release consisted of the arXiv preprint plus a public GitHub repository, google-deepmind/alphaproof-nexus-results, containing the Lean proofs and natural-language write-ups under Apache 2.0 and CC-BY licenses, organized by domain and including a list of which Erdős problems were attempted.[3] Publishing the attempt list matters: it makes the denominator auditable, which is the specific thing that was missing from earlier claims.

Positive assessments centered less on the solve count than on the workflow. The authors report that "our mathematician collaborators found that proof attempts by our agents enhanced their understanding of a problem, even when an agent could not prove the claim at hand," and that because the sketches were formal, "experts could focus on the unresolved subgoals rather than re-verifying the entire argument."[2] The stated ambition is human-machine partnership: "We built AlphaProof Nexus with the belief that the future of mathematics lies in human-machine partnership, where interactive AI tools serve to expand a mathematician's creative capacity."[2]

The main published critique, Wegner's review of 2026-05-31, raises four objections: that some problems counted as open were building on known literature, that formalization ambiguity was exploited rather than solved, that the system hallucinated references to nonexistent results, and that the elaborate architecture was unnecessary given agent A's performance.[10] It also argues that the approach is structurally limited because it depends on humans pre-formalizing the problems and on Mathlib already containing the needed machinery.[10] The first and fourth points are supported by the paper's own text and by the Tao wiki; the framing of them as misrepresentation is Wegner's.

Secondary coverage attributed a remark that the system is "still not AGI" to DeepMind leadership. That line traces only to aggregator write-ups, and no primary source for it was located; the preprint itself makes no claim about general intelligence and explicitly says that "even most Erdős problems remain out of reach, let alone problems that require extensive new theory."[2]

Context: the 2025 retraction

On 2025-10-18, OpenAI vice president Kevin Weil posted that "GPT-5 found solutions to 10 (!) previously unsolved Erdős problems and made progress on 11 others."[7] It had not. The model had located references to solutions already in the literature. Bloom, who maintains the list, called the post "a dramatic misrepresentation" and explained that "open" on his site means he personally was unaware of a paper solving the problem, not that the problem was unsolved. Weil deleted the post. Demis Hassabis of Google DeepMind called the episode "embarrassing"; Meta's Yann LeCun was less restrained.[7] OpenAI researcher Sebastien Bubeck acknowledged that "only solutions in the literature were found" while arguing that the literature search itself had value.[7]

That episode is the reason the Nexus paper's bookkeeping deserves attention rather than assumption. Nexus differs from the 2025 claim in three concrete ways: proofs are machine-checked in Lean rather than asserted, the full attempted set and the proofs are published, and results were logged on a third-party community wiki that independently classifies how much of each contribution was novel.[2][3][4] It does not, however, describe a systematic literature search or automated novelty check beyond expert validation that the Lean statement matched the informal conjecture.[2]

Context: the parallel OpenAI unit distance result

Around 2026-05-20, OpenAI announced that an internal reasoning model had produced the core ideas and a draft disproof of the Erdős unit distance conjecture, a discrete geometry question Erdős posed in 1946.[8] A group of mathematicians including Noga Alon, Thomas Bloom, Timothy Gowers, Daniel Litt, Will Sawin, Arul Shankar, Jacob Tsimerman, Victor Wang and Melanie Matchett Wood posted a "short, digested, human-verified version of the recent OpenAI-generated counterexample" as arXiv 2605.20695 on 2026-05-20, noting that the argument relies on ideas attributable to Ellenberg-Venkatesh, Golod-Shafarevich, and Hajir-Maire-Ramakrishna.[9]

The two results are easy to conflate and should not be. Different labs, different problems, and materially different epistemics: Nexus produces Lean-checked proofs of comparatively obscure problems, while the OpenAI output was a natural-language argument on a famous problem that required human mathematicians to verify, compress and publish. Reported reactions to the OpenAI result were warmer, with Gowers saying no previous AI-generated proof had come close to publication standard and Litt calling it the unique interesting result produced autonomously by AI to date, alongside caveats that the model did not show its construction was optimal, that human cleanup was essential, and that the AI failed to properly credit similar prior work.[8]

Limitations and cost

Reported inference cost is a few hundred dollars per solved Erdős problem for the full agent, with high variance because the search is stochastic.[1][2] AlphaProof, when invoked as a tool, costs roughly 27.5 TPU hours, about $60, per problem on v6e TPUs.[2] These figures exclude the cost of discovery: running the full agent across all 353 problems was itself a large computational investment, and the paper says so.[2]

The paper's own limitations section is unusually candid. Successes concentrate in combinatorics, convex optimization and number theory, "where Lean's mathematics library is mature and tasks often decompose into tractable subgoals."[2] A recurring failure pattern is the agent offloading a problem's core difficulty into a single sorry inside a helper lemma that restates the target in slightly different words.[2] The agents inherit their language models' biases and show high search variance.[2] And the system operates only on problems the community has already formalized, which is a bias in what gets attempted before any search begins.[2]

See also

References

  1. "Advancing Mathematics Research with AI-Driven Formal Proof Search." arXiv:2605.22763 (abstract page), 2026-05-21. https://arxiv.org/abs/2605.22763 ↩
  2. Tsoukalas, G., Kovsharov, A., Shirobokov, S., et al. "Advancing Mathematics Research with AI-Driven Formal Proof Search" (full text, v2). arXiv, 2026-06-08. https://arxiv.org/html/2605.22763v2 ↩
  3. "google-deepmind/alphaproof-nexus-results." GitHub, 2026. https://github.com/google-deepmind/alphaproof-nexus-results ↩
  4. "AI contributions to Erdős problems." teorth/erdosproblems wiki, GitHub, 2026. https://github.com/teorth/erdosproblems/wiki/AI-contributions-to-Erd%C5%91s-problems ↩
  5. "Disclaimers and caveats." teorth/erdosproblems wiki, GitHub, 2026. https://github.com/teorth/erdosproblems/wiki/Disclaimers-and-caveats ↩
  6. "Google Deepmind's AlphaProof Nexus solves decades-old math problems for a few hundred dollars." The Decoder, 2026-05-25. https://the-decoder.com/google-deepminds-alphaproof-nexus-solves-decades-old-math-problems-for-a-few-hundred-dollars/ ↩
  7. "OpenAI's 'embarrassing' math." TechCrunch, 2025-10-19. https://techcrunch.com/2025/10/19/openais-embarrassing-math/ ↩
  8. "AI Just Solved an 80-Year-Old Erdős Problem, and Mathematicians Are Amazed." Scientific American, 2026-05-21. https://www.scientificamerican.com/article/ai-just-solved-an-80-year-old-erdos-problem-and-mathematicians-are-amazed/ ↩
  9. Alon, N., Bloom, T. F., Gowers, W. T., et al. "Remarks on the disproof of the unit distance conjecture." arXiv:2605.20695, 2026-05-20. https://arxiv.org/abs/2605.20695 ↩
  10. Wegner, A. "DeepMind's AlphaProof Nexus: a critical review." AI Chats (Substack), 2026-05-31. https://aichats.substack.com/p/deepminds-alphaproof-nexus ↩
  11. "google-deepmind/formal-conjectures." GitHub, 2026. https://github.com/google-deepmind/formal-conjectures ↩
  12. "AI achieves silver-medal standard solving International Mathematical Olympiad problems." Google DeepMind blog, 2024-07-25. https://deepmind.google/discover/blog/ai-solves-imo-problems-at-silver-medal-level/ ↩
  13. Bloom, T. F. "Erdős Problems." Accessed 2026-07-27. https://www.erdosproblems.com/ ↩
  14. Tao, T. Post on AI-solved Erdős problems and the literature. Mathstodon, 2025-12-26. https://mathstodon.xyz/@tao/115788262274999408 ↩
  15. Hubert, T., Mehta, R., Sartran, L., et al. "Olympiad-level formal mathematical reasoning with reinforcement learning." Nature, 2025-11-12. https://doi.org/10.1038/s41586-025-09833-y ↩

Improve this article

Add missing citations, update stale details, or suggest a clearer explanation. Every suggestion is reviewed for sourcing before it goes live.

1 revision by 1 contributors · full history

Suggest edit

What links here

AlphaProof