TL;DR
Turing Agent is a novel "agent harness" designed to automate the end-to-end formal verification of research-level mathematics using the Lean proof assistant. By coordinating specialized agents for theorem formalization and proof decomposition, it successfully verified complex theoretical computer science (TCS) problems that had previously remained unresolved by frontier AI systems.
What Problem Does This Paper Address?
We are entering what mathematician Terence Tao calls the era of "proof abundance." Large Language Models (LLMs) are now capable of generating mathematical breakthroughs and solving long-standing conjectures at an unprecedented scale. However, this creates a massive verification bottleneck: how do we know these AI-generated proofs are actually correct?
Formal verification—translating math into machine-checkable code like Lean—is the gold standard for trust, but it faces three major hurdles:
- Faithfulness: A formal statement might compile but subtly change the meaning of the original claim (e.g., misinterpreting a quantifier).
- Validity: The code must pass strict syntax and type checks.
- Completeness: The proof must be "gapless," with no unresolved "sorry" placeholders.
Current automated theorem provers often struggle with "semantic drift," where the formalization slowly loses touch with the intended mathematical meaning during long, complex proofs.
Methods
Turing Agent employs a two-scale architecture that treats verification as an agentic orchestration problem rather than a simple code-generation task.
- Two-Agent System: It splits the work between a Theorem Formalization (TF) Subagent, which ensures the Lean statements are semantically faithful to the natural language, and Proof Formalization (PF) Subagents, which build the actual proofs.
- Recursive DAG Construction: Instead of writing one long proof, the agent decomposes the main theorem into a Directed Acyclic Graph (DAG) of intermediate claims. It verifies that these sub-claims logically imply the parent theorem before attempting to prove the sub-claims themselves.
- Selective Semantic Review: To prevent semantic drift, the system triggers a "semantic check" whenever a new definition is introduced or a concept is unclear, comparing the formal code back to the original natural language.
- Experience Pool: The agent extracts "lessons learned" from both successful and failed proof attempts, storing them in a pool to guide future reasoning and prevent repetitive errors.
Datasets
The authors focused their evaluation on Theoretical Computer Science (TCS), a domain known for intricate quantification and complex dependencies.
- Formal TCS Bench: A new benchmark of 143 problems pairing informal research statements with reference Lean formalizations.
- RLMEval (TCS subset): A 248-theorem evaluation set drawn from the Polynomial Freiman–Ruzsa (PFR) and TestingLowerBounds (TLB) projects.
- OpenAI’s October 2026 Collection: A set of 722 AI-generated math manuscripts. Turing Agent was tested on 22 TCS problems that OpenAI's internal systems had failed to fully verify.
Key Insights and Ideas
- Harness vs. Model: The paper argues that for research-level math, the "harness" (the agentic workflow) is just as important as the underlying LLM. Turing Agent significantly outperformed general-purpose coding agents (like Claude Code) using the same base models.
- Proof Adaptation: The agent doesn't just blindly copy the original proof. It often discovers simpler alternative constructions. For example, if an original proof uses a complex $C = \max(A, B)$, the agent might choose $C = A + B + 1$ to make subsequent linear arithmetic easier for the solver.
- Knowledge as a Byproduct: By decomposing proofs, the agent generates dozens (sometimes over a hundred) of verified auxiliary lemmas. These represent reusable mathematical knowledge that can be added to formal libraries like Mathlib.
- The "Semantic Gap": The results highlight a massive gap between "compilation" (validity) and "faithfulness." A proof that passes Lean's kernel check is worthless if it proves the wrong theorem.
Key Results
Turing Agent, powered by models like DeepSeek-V4-Pro and GLM-5.3, demonstrated state-of-the-art performance:
- Benchmark Success: Achieved 57–62% faithful formalization on Formal TCS Bench and an 83% overall pass@1 on the RLMEval subset.
- Solving the "Unsolvable": Successfully verified three previously unresolved TCS tasks from OpenAI’s research collection.
- Scale: One of these verified problems required the construction and verification of over 100 auxiliary claims, demonstrating the agent's ability to handle long-horizon reasoning.
Limitations and Future Work
While powerful, the authors note that Turing Agent is currently specialized for TCS. Future work includes:
- Broadening Domains: Extending the agent to other areas of mathematics and science.
- Improving Semantic Checks: Refining the "semantic review" process to be even more robust against subtle misinterpretations.
- Discovery Integration: Moving beyond verifying existing proofs to tightly integrating formal verification with the discovery of entirely new mathematical results.
Summary updated