Turing Agent: Agentic Formal Verification for Mathematical Research
Authors: Yang Chen, Qianyi Wang, Ronghui Yang, Zhanhao Li, Yu Cong, Chen Zhang, Hangfan Zhang, Shao Zhang, Shuai Li, Toru Takisaka, Chao Xu, Yi Zhou, Zhihao Tang, Xiao Wang, Bo Zhang, Shuyue Hu
Organizations: Agent Center, Shanghai Artificial Intelligence Laboratory · Algorithms and Logic Group, University of Electronic Science and Technology of China · School of Computing and Data Science, The University of Hong Kong · Institute for Theoretical Computer Science, Shanghai University of Finance and Economics
Large language models (LLMs) are rapidly advancing mathematical discovery, moving beyond benchmark-level problem solving to tackle frontier research problems. This progress is ushering mathematics into an era of proof abundance, raising a fundamental challenge: how can we ensure the correctness of the ever-growing volume of AI-generated proofs and transform them into trustworthy, machine-verified mathematical knowledge? We introduce Turing Agent, an agent harness designed to orchestrate end-to-end formal verification of research-level mathematics. Its wo-scale architecture integrates theorem formalization and proof formalization agents, empowered by structured proof decomposition, parallel verification, accumulated proof experience, and selective semantic review. Leveraging our collaborations with theoretical computer science (TCS) researchers, we focus our evaluation on TCS, a particularly demanding domain characterized by intricate quantification, complex dependencies, and stringent semantic requirements. Against direct generation and general-purpose coding harnesses, including Codex CLI and Claude Code, Turing Agent achieves approximately 57-62% faithful formalization success on Formal TCS Bench and 83% overall pass@1 on a TCS-focused subset of RLMEval, using GLM-5.3 and DeepSeek-V4-Pro. Notably, Turing Agent, built on DeepSeek, successfully completes the formal verification of three previously unresolved TCS tasks from OpenAI's October 2026 collection. One particularly challenging TCS problem required about a hundred formally verified auxiliary claims. Moreover, by actively exploring and refining the formalization process, Turing Agent can uncover simpler alternative proofs, expose unnecessary dependencies in original proofs, and generate reusable mathematical knowledge as a byproduct of verification.
Figures & tables
Figure 1: Three challenges in automated formal verification. The formal statement must preserve the original claim (faithfulness), the code must pass Lean’s syntax and type checks (validity), and the proof must discharge all obligations without gaps (completeness). Our Turing Agent is designed to satisfy these requirements throughout the formalization process.
Figure 2: Turing Agent coordinates theorem formalization (TF) and proof formalization (PF) agents. TF agents provide checked Lean statements and definitions, while PF agents construct proofs and request semantic review when needed. The resulting proof undergoes final verification. In its runtime, Turing Agent coordinates recursive DAG construction, parallel proof formalization, and selective semantic review. Experience from successful and failed attempts is extracted and reused, while checked branch proofs are assembled for final verification.
Figure 3: Research-level TCS verification beyond standard benchmarks. Of the 121 TCS problems in OpenAI’s mathematical research collection, 22 had not been fully verified in Lean. Among these, we highlight three examples formally verified by Turing Agent using DeepSeek-V4-Pro and DeepSeek-V4.1-Flash.
Figure 4: Selective semantic review in the proof DAG. PF agents request TF agents when a concept is unclear or a new definition is introduced. The TF agent checks whether the statement and its definitions preserve the intended meaning.
Figure 5: Experience extraction and reuse during DAG evolution. PF agents use retained records to guide revisions and update the pool when later attempts yield useful findings.
Figure 6: Pass@1 results (%) on Formal TCS Bench and RLMEval. Formal TCS Bench also reports compilation rates. RLMEval results are shown separately for PFR and TLB and combined as Total. PFR covers additive combinatorics and entropy methods from the Polynomial Freiman–Ruzsa project, with applications to linearity testing in TCS. TLB (Testing Lower Bounds) covers information-theoretic lower bounds for statistical hypothesis testing.
Figure 7: A simplified representation of the proof DAG for Problem A uniform influence bound for hypergraph properties . The relationships between nodes are omitted in the figure. Each leaf node represents a lemma or subtheorem, while the intermediate nodes indicate logical categories rather than actual nodes in the DAG. Green terminal nodes indicate those actually used in the proof, while gray nodes indicate those not used in the final proof. Leaf nodes with bold borders represent lemmas or theorems introduced by Turing Agent during the proving process and not present in the original paper. Purple S markers indicate nodes that are selected for semantic review.
Appendix figures & tables2 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 8: A simplified representation of the proof DAG for Problem Uniform Matrix Hitting Points in Every Positive Characteristic .
Figure 9: A simplified representation of the proof DAG for Problem Linear Variance of the Random 3-SAT Hitting Time .
Large language models (LLMs) increasingly excel at mathematical reasoning, but their unreliability limits their utility in mathematics research. A mitigation is using LLMs to generate formal proofs in languages like Lean. We perform the first large-scale evaluation of this method's ability to solve open problems. Our most capable agent autonomously resolved 9 of 353 open Erdős problems at the per-problem cost of a few hundred dollars, proved 44/492 OEIS conjectures, and is being deployed in combinatorics, optimization, graph theory, algebraic geometry, and quantum optics research. A basic agent alternating LLM-based generation with Lean-based verification replicated the Erdős successes but proved costlier on the hardest problems. These findings demonstrate the power of AI-aided formal proof search and shed light on the agent designs that enable it.
George Tsoukalas, Anton Kovsharov, Sergey Shirobokov +18
Recent advances in large language models have significantly improved their ability to perform mathematical reasoning, extending from elementary problem solving to increasingly capable performance on research-level problems. However, reliably solving and verifying such problems remains challenging due to the inherent ambiguity of natural language reasoning. In this paper, we propose an automated framework that integrates natural language reasoning with formal verification to tackle research-level mathematical problems. Our framework consists of two components: an informal reasoning agent, Rethlas, and a formal verification agent, Archon. Rethlas combines reasoning primitives with our theorem search engine, Matlas, to explore solution strategies and construct candidate proofs. Archon, equipped with LeanSearch, translates informal arguments into formalized Lean 4 projects through task decomposition, iterative refinement, and automated proof synthesis, ensuring machine-checkable correctness. Using this framework, we resolve an open problem in commutative algebra and formally verify the resulting proof in Lean 4 with essentially no human involvement. Additional case studies illustrate the capabilities of Rethlas in informal mathematical reasoning and discovery, as well as the ability of Archon to formalize research-level proofs in Lean 4. Our experiments demonstrate that strong theorem retrieval tools enable the discovery and application of cross-domain mathematical techniques, while the formal agent can autonomously fill nontrivial gaps in informal arguments. More broadly, our work illustrates a promising paradigm for mathematical research in which informal and formal reasoning systems, equipped with theorem retrieval tools, operate in tandem to produce verifiable results, reduce human effort, and support human-AI collaborative mathematical research.
Haocheng Ju, Guoxiong Gao, Jiedong Jiang +13
School of Mathematical Sciences, Peking University · IQuest Research · Westlake Institute for Advanced Study, Westlake University +8
While Large Language Models (LLMs) have demonstrated exceptional capabilities in mathematical reasoning, they frequently produce subtle errors that evade human detection. Formal mathematical languages like Lean 4 offer mechanical proof checking, strongly motivating the need for autoformalization: the automatic translation of natural language mathematics into verifiable code. Recent trends indicate that general-purpose LLMs, heavily optimized for standard programming, now outperform smaller models explicitly fine-tuned for Lean. Leveraging this shift, we introduce an agentic autoformalization framework powered by general coding LLMs. At the core of our system is an orchestrator that manages a multi-agent pipeline tailored for research-level mathematics. Because cutting-edge research frequently relies on concepts outside the scope of existing libraries like Mathlib, our system dynamically extends necessary type definitions and validates them via a novel Auxiliary Lemma technique before formalizing the primary theorems. We applied our approach to PutnamBench, producing machine-checked Lean proofs for a random sample of 32 problems. Furthermore, we evaluate our system on five papers from the ACM Symposium on Theory of Computing (STOC) spanning combinatorics, communication complexity, mechanism design, and learning theory, successfully formalizing their main theorems and validating the generated formalizations with human experts; for all five we also formalize the proofs alongside the statements, and notably two of them are proved with no axioms beyond Lean's kernel. All of our formalizations are available at https://beyondthelibrary.github.io/formal_arxiv .
Arshia Soltani Moakhar, Iman Gholami, Max Springer +2