AlphaProof Code Agents Write 3 Million Lean Proof Lines to Verify Signal’s Core Encryption

Summary:Google DeepMind introduced AlphaProof Code, an agentic system for deep formal verification of complex software. Working with tools such as Lean, its agents generated approximately three million lines of proofs while verifying core encryption code in Signal’s client. The important shift is not simply higher theorem-proving output, but a verification workflow in which agents decompose difficult proof obligations, search for reusable lemmas, repair failed proofs, and check machine-verifiable artif

---

AlphaProof Code turns code verification into an agentic loop

Google DeepMind has introduced AlphaProof Code, a formal-verification system for complex software. In its flagship case, agents generated approximately three million lines of Lean proofs while verifying core encryption code in Signal’s client. The significance is not the raw proof volume itself, but the shift from proving isolated theorems to performing deep verification against a real, security-sensitive codebase.

Conventional formal verification requires engineers to translate system intent into specifications, construct intermediate lemmas, and repeatedly diagnose failures reported by the proof assistant. AlphaProof Code wraps this workflow into an agentic process: models locate failed proof obligations, retrieve relevant definitions and existing theorems, revise proof drafts, and resubmit them for machine checking. The final trusted artifact is therefore a Lean-checked proof, not a natural-language explanation generated by the model.

This separation defines the system’s engineering value. Agents can reduce the cost of proof search, while the Lean kernel provides deterministic adjudication. The model explores candidate solutions; the prover rejects invalid steps. Together they form a generate–verify–repair loop.

Technical mechanism: from theorem generation to deep verification

Based on the official summary, AlphaProof Code involves at least four major engineering stages.

1. Decomposing a large codebase into verifiable obligations

Signal’s encryption implementation involves protocol states, message encoding, key handling, boundary conditions, and consistency between implementation and specification. An agent cannot answer a single natural-language question and call the task complete. It must continually identify missing proof obligations and turn them into executable targets.

This resembles decomposition in program analysis: first establish what must be proved, then decide how to prove it. The difficulty at repository scale comes from dependency structure and context volume. A local theorem may lack reusable lemmas, while a global target can trigger a deep dependency chain. The proof agent must repeatedly switch among definition search, dependency exploration, and assumption discovery rather than relying solely on mathematical knowledge encoded in model parameters.

2. Driving repair from Lean kernel feedback

A failed Lean proof is rarely just a syntax error. It may result from type mismatches, missing arguments, invalid termination reasoning, inaccessible lemmas, or a mismatch between intermediate goals and system assumptions. Precise error locations from the kernel provide an executable signal for iterative repair.

The approach resembles compiler-feedback-driven code generation, but the proof environment is stricter. A conventional program may pass tests and be accepted, whereas every Lean step must satisfy the type system and logical rules. The final proof term can be checked independently by a small trusted kernel, reducing reliance on the generating model’s own judgment.

3. Multi-agent specialization

A workload producing three million lines of proof cannot realistically rely on a single long-context session. A more plausible architecture assigns code navigation, proof planning, candidate generation, failure repair, specification checking, and deduplication to different agents, with an orchestrator controlling parallel exploration and result merging.

Parallel agents can explore multiple proof routes, but coordination is not free. Different agents may reconstruct the same lemma, locally valid proofs may conflict when merged, and long contexts raise inference costs. Practical deployment requires dependency-aware task partitioning, normalized candidate lemmas, and conflict checks before merging.

4. Independent review remains necessary

A Lean-checked proof does not imply that the specification is complete, or that the intended system behavior was modeled correctly. Three layers of assurance must be distinguished:

• The proof corresponds to the stated mathematical proposition.
• The specification accurately captures the intended security properties.
• The production implementation matches the code that was verified.

If implementation, specification, and build artifacts drift apart, even a complete proof may certify the wrong system. Production pipelines therefore need code-hash binding, pinned compiler and dependency versions, proof provenance, and incremental re-verification after changes.

Engineering trade-offs: proof volume is not security coverage

Three million lines of proof is an impressive output, but it is easy to misinterpret. More proof lines may mean more obligations, helper lemmas, or failed attempts—not necessarily broader security coverage. More meaningful metrics include:

• Coverage of target modules and critical properties;
• Percentage of proofs completed without manual edits;
• Model calls, tokens, GPU time, and compilation time per successful proof;
• Percentage of proofs that remain reproducible after Lean upgrades;
• Failure categories and human repair cost;
• Sensitivity to compiler, library, and source-code changes.

Large proof corpora also create maintenance pressure. Automatically generated proofs may be long, brittle, or dependent on accidental constructions. Even when every step is valid, later code changes can invalidate substantial portions of the proof. A production system should preserve compact, readable, reviewable proofs and maintain proof caches plus incremental verification comparable to software dependency management.

Verification cost is another constraint. The Lean kernel may check an individual proof quickly, but generating candidates, unfolding definitions, discovering lemmas, and processing compiler failures all consume inference resources. Parallel search in a complex repository can produce enormous candidate volumes. Scheduling should therefore optimize verified security obligations rather than maximizing proof generation without bound.

Evaluation credibility: coverage and reproducibility matter more than line count

The headline figures are three million lines of Lean proofs and verification of Signal’s core encryption. To judge generalizability, the evaluation should clarify:

1. Which modules, versions, and commits constitute the “core encryption” target?
2. Which properties were formalized, and where did the specifications come from?
3. How many goals had already been proved by humans?
4. How much of the result came from existing proof libraries and formalization infrastructure?
5. Are there baselines for human experts, individual models, and single-agent workflows?
6. Can third parties recheck the artifacts in a pinned Lean and dependency environment?

In security-critical work, the most important artifacts are reproducible proofs, locked environments, and source-version identifiers—not the narrative summary. Full independent reproduction does not require regenerating the same proofs from scratch. Releasing proof terms, normalized scripts, and hashes would allow third parties to recheck fixed artifacts directly with the kernel.

Deployment guidance

Teams pursuing a similar approach should begin with a small, well-specified component rather than an entire cryptographic protocol. Select modules with existing specifications, strong test coverage, and explicit security properties, then place agents in a loop that:

1. Parses the codebase and existing proof dependencies.
2. Generates structured proof obligations from specifications.
3. Retrieves definitions, lemmas, and verified components.
4. Produces minimal Lean proof drafts.
5. Invokes the compiler and trusted kernel.
6. Classifies failures and repairs them iteratively.
7. Binds accepted proofs to source commits.

A production system also needs a proof registry, incremental dependency tracking, and versioned CI. A model-generated solution should not be treated as a release license; passing Lean checks should be a necessary but insufficient condition, with expert review reserved for specification completeness and long-term proof maintainability.

Industry implications

AlphaProof Code demonstrates a viable path for formal-verification agents: models handle open-ended proof search, while a small trusted kernel provides deterministic adjudication. As agents become better at navigating large codebases, invoking compilers, and recovering from error feedback, the bottleneck in formal verification may shift from writing individual proofs toward deriving sound specifications and maintaining proofs over time.

If the approach is independently reproduced across cryptography, operating systems, and critical infrastructure, it could shorten the path from specification to machine-verifiable artifacts and reduce expert effort. If “deep verification” instead covers a narrow path or depends on extensive manual repair and selection, its general value will be limited. Proof coverage, end-to-end cost, and reproducibility matter more than the size of the generated proof corpus.

---

Source: Google DeepMind Blog (2026-11-10)

— END —

Tags: #AlphaProof Code Follow #Formal Verification Follow #Lean Follow #Code Agents Follow #Signal Follow