DeepMind preprint: LLM+Lean agent resolves 9 Erdos problems and 44 OEIS conjectures

Why it matters

Formal-proof agents that can reliably turn LLM reasoning into checked math open a path to scale research beyond toy problems. Even partial wins with full proof artifacts can compound quickly across fields.

Google DeepMind reports that an AI-driven formal proof agent solved 9 of 353 open Erdos problems and proved 44 of 492 OEIS conjectures, according to an arXiv preprint of AlphaProof Nexus, an LLM-plus-Lean framework for research-level mathematics. The paper says the strongest configuration handled solved problems for a few hundred dollars in inference cost and that proofs and select natural-language writeups are publicly available in google-deepmind/alphaproof-nexus-results. The preprint is at arXiv:2605.22763.

AlphaProof Nexus coordinates LLM-based generation with Lean's compiler to check each step. The team evaluated several agents: a basic loop that alternates LLM edits and Lean verification; a version with access to AlphaProof as a focused theorem prover; an evolutionary variant that ranks and recombines sketches; and a full-featured system that combines both. In a post-hoc analysis on the 9 Erdos problems solved by the full system, the basic agent also found all 9 proofs but at higher cost on the hardest instances.

Beyond benchmarks, the authors describe deployments across mathematics: an exact O(1/t) convergence rate for a variant of anchored gradient descent-ascent in convex-concave optimization (by jointly searching the learning schedule and a proof), a proved bipartite variant related to the graph reconstruction program and a separate graph bound on spanning-tree leaves, a long-open log-concavity result for pure O-sequences in codimension 3 and type 2, a resolution of a Green list problem via a counterexample to the intended complex-valued statement, and constructions for certain high-dimensional GHZ-state quantum graphs. The team also notes the agent flagged misformalizations in some Erdos statements (e.g., clarifying uses of lower vs. upper density) that were then corrected and re-solved.

The paper includes a cost-performance comparison across agent designs. It reports that the full-featured configuration materially outperformed simpler loops on the hardest Erdos instances while smaller LLMs and standalone AlphaProof tree search could not solve the evaluated problems. A failure analysis highlights two recurring issues the Lean checker exposed: attempts to hide difficulty behind a single placeholder and appeals to hallucinated lemmas.

Artifacts, including Lean proofs and select natural-language proofs, are in the public repository google-deepmind/alphaproof-nexus-results.

What it means

• For startups: Tool-augmented reasoning that is checked by a verifier looks productizable. The pattern here - LLM search wrapped around a formal checker and a domain prover - can translate to software verification, smart contracts, quantitative finance, and safety-critical engineering where correctness is the product. The results also suggest differentiation will come from proprietary formalizations, libraries, and workflow automation, not just which base model is used. Access to frontier models matters: the paper reports smaller LLMs and standalone search could not solve the evaluated problems, which concentrates advantage with teams that can afford strong models and compute.
• For AI researchers: The study strengthens the case for agentic, tool-using LLMs tightly coupled to formal systems. Architectural choices matter: adding a focused prover and evolutionary search improved performance over a simple edit-verify loop, and the Lean checker surfaced concrete failure modes to target. Public artifacts create a replicable scaffold for ablations on search, training signals, and reward design.
• For the broader public: If robust, systems that produce machine-checkable proofs can accelerate discovery while raising the bar on reliability. That could shift expert time toward problem selection and concept formation, with the agent handling search and verification. It also points to a future where critical infrastructure and scientific claims are routinely proof-checked rather than trust-checked.

Caveats and open questions

• This is a preprint; community review and independent replication are pending. Mathematical significance, novelty, and human-readable exposition will be judged by researchers beyond the formal Lean proofs.
• Cost and accessibility depend on model choice and pricing. The paper notes smaller models failed on these tasks; reproducing results with widely available models remains uncertain.
• Generality is bounded by the formal environment. Coverage outside Lean's libraries and the chosen problem distributions may lag; success can hinge on how statements are formalized.
• The agent exhibited specification issues and hallucinated lemmas before Lean rejected them. That is a strength of formal checking but also a reminder that system design must anticipate such failure modes.
• Credit and collaboration norms around machine-generated proofs are still evolving; how to attribute contributions and encourage open artifacts will matter for adoption.