AlphaProof Nexus Solves Decades-Old Erdős Problems for a Few Hundred Dollars Each
Agentic AIGoogle DeepMind’s AlphaProof Nexus solved 9 of 353 Erdős open problems, including two that had remained unresolved for 56 years. The cost per problem: a few hundred dollars.
What AlphaProof Nexus Actually Did
The results are specific enough to be worth unpacking. Nine problems from Paul Erdős’s list of open combinatorics and number theory questions, including two that mathematicians hadn’t cracked since 1970. Beyond the Erdős set, the system proved 44 of 492 open conjectures in the Online Encyclopedia of Integer Sequences (OEIS), settled a 15-year-old question about Hilbert functions in algebraic geometry, and improved a known bound in convex optimization.
These aren’t automated proofs of known theorems. They’re new results in genuinely open research problems—verified formally in Lean, a proof assistant whose compiler checks each step and rejects incorrect reasoning. The formal verification is what separates this from language model outputs that sound like proofs but contain errors. When Lean’s compiler says a proof is correct, it is correct.
The Compiler Feedback Loop
The mechanism is less exotic than the results suggest. AlphaProof Nexus uses Gemini 3.1 Pro to generate proof steps, which the Lean compiler then checks. When a step is wrong, the compiler returns the specific error. That error goes back into the model, which generates a revised step. The loop continues until the proof succeeds or the system exhausts its approach.
The architecture includes four agent variants of increasing complexity—from a basic LLM-plus-compiler setup (Agent A) through fully equipped combinations incorporating reinforcement learning, evolutionary components, and sub-agents sharing proof sketches rated by Elo scoring (Agent D). The finding that matters: Agent A, the simplest version using only the language model and compiler feedback, could prove all nine of the solved Erdős problems.
The implication is that compiler feedback in grounding LLM reasoning may be the critical mechanism—not specialized mathematical training or complex multi-agent orchestration. The reinforcement learning components from the original AlphaProof (trained on olympiad mathematics) are present in the more complex variants, but the baseline agent handles the core results.
The So What
The cost figure—a few hundred dollars per problem—is notable not because it’s cheap in absolute terms, but because it places frontier mathematical research on a cost curve that will continue to decline. Problems requiring years of mathematical intuition can now be approached systematically with formal verification loops that don’t lose context or tire.
The practical application for most AI engineers isn’t mathematical research—it’s the underlying pattern. Agentic systems with tight, formal feedback loops outperform those relying on the model’s internal judgment alone. When an external validator tells the system it’s wrong with a specific, actionable error, the system corrects. That’s a different reliability property than asking a model to evaluate its own reasoning in natural language.
For engineers thinking about where agentic reliability actually comes from, AlphaProof Nexus is a useful case study: verifiable intermediate outputs, formal feedback on each step, and iteration until correctness—applied to a domain where correctness is provable. The same principle extends to code verification, logical reasoning chains, and any domain where external validators can be built.
Photo by Vitaly Gariev on Pexels
Source: The Decoder
Content created with AI assistance and reviewed for accuracy.
Join the conversation
Stack Insiders is our free community for readers who want to go deeper — share resources, ask questions, and connect with others across every vertical we cover.
Join Stack Insiders →