🤖 machine learning

Nazrin: An Atomic Neural Proof Automation Tactic in Lean 4

This paper introduces Nazrin, a graph neural network-based theorem proving agent for Lean 4 that utilizes a novel set of atomic tactics, a transposing atomization algorithm, and the ExprGraph data structure to enable robust, consumer-grade hardware-compatible proof automation.

Original authors: Leni Aniva, Iori Oikawa, David Dill, Clark Barrett

Published 2026-07-01

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Leni Aniva, Iori Oikawa, David Dill, Clark Barrett

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to teach a robot to solve complex math puzzles. The robot's goal is to prove that a mathematical statement is true. In the world of computer science, this is called "Machine-Assisted Theorem Proving."

The paper introduces a new robot named Nazrin (which stands for Neural Atomizer for Inhabitation Problems). Nazrin is designed to be smarter, faster, and more efficient than previous robots at solving these puzzles. Here is how it works, broken down into simple concepts and analogies.

1. The Problem: Too Many Choices

Imagine you are playing a video game where you have to reach a treasure. In the old way of teaching robots, the robot was given a massive, infinite menu of moves. It could say "Jump," "Run," "Fly," "Use a magic spell," or "Combine 50 different spells in a specific order."

Because the menu was so huge and messy, the robot got confused. It didn't know if the human player chose a move because it was the best move, or just because the player felt like it. Also, human-written proofs often skip steps or use fancy shortcuts that look good on paper but are hard for a robot to figure out how to build from scratch.

2. The Solution: Atomic Tactics (The Lego Bricks)

Nazrin solves this by giving the robot a tiny, finite box of Atomic Tactics. Think of these as standard Lego bricks.

Instead of "Build a castle," the robot only has instructions like "Place a red brick," "Place a blue brick," or "Connect two bricks."
These "bricks" are simple, finite, and strictly defined.
The paper claims that if you have the right set of these simple bricks, you can build any valid mathematical proof.

This makes the robot's job much easier. Instead of choosing from an infinite menu, it only has to pick from a small, manageable list of options at every step.

3. The Translator: Transposing Atomization

You might ask, "But how do we teach the robot if all the existing math proofs are written in 'fancy human language' with huge shortcuts?"

The authors created a special translator called Transposing Atomization.

The Analogy: Imagine a human chef who writes a recipe saying, "Make a perfect soufflé." This is the "Presentation View"—it looks great, but it skips the details.
The translator takes that recipe and breaks it down into a step-by-step list of atomic actions: "Crack 3 eggs," "Whisk for 2 minutes," "Add sugar," "Bake at 350 degrees."
This process turns the "fancy" human proofs into a long, detailed sequence of simple "atomic" steps. This gives the robot a massive library of training data to learn from.

4. The Map: ExprGraph

Math expressions can be messy. They often contain the same numbers or variables repeated many times, or they use different names for the same thing.

The Analogy: Imagine a map of a city. In a normal map, every street is drawn separately. But in Nazrin's map (called ExprGraph), if two streets are actually the same road, they are drawn as a single line. If two buildings are the same type, they share a single icon.
This "Essentialization" strips away the confusing details and focuses only on the structure of the math. It helps the robot see the "shape" of the problem without getting distracted by irrelevant information.

5. The Brain: Nazrin Prover

Nazrin is the robot's brain. It is a type of Artificial Intelligence called a Graph Neural Network (GNN).

Because the math problems are turned into these clean "maps" (ExprGraphs), Nazrin can look at the map and predict the next best "Lego brick" (atomic tactic) to place.
The Superpower: Nazrin is incredibly fast. While other robots (like those using large language models) might take seconds to think of one move, Nazrin can generate thousands of moves per minute.
Hardware: It is so efficient that it can run on a standard home computer (a "consumer-grade" machine), not just a massive supercomputer.

6. The Results: How Well Does It Work?

The authors tested Nazrin on two huge libraries of math problems (the "Standard Library" and "Mathlib").

They trained Nazrin on one set of problems and then asked it to solve new, unseen problems from a similar set.
The Outcome: Nazrin successfully proved about 57% of the problems in the standard library and 34% in the larger Mathlib library.
Crucially, Nazrin was able to solve some problems that other famous automated tools (like Aesop and Grind) could not solve. It acts as a different kind of tool that complements the existing ones.

Summary

In short, the paper introduces Nazrin, a theorem-proving robot that:

Breaks down complex math into simple, atomic steps (like Lego bricks).
Translates human-written proofs into these simple steps to learn from them.
Uses a special "map" to understand the structure of math without getting confused by details.
Runs fast on regular computers and can solve math problems that other tools miss.

The authors emphasize that this is a new way to approach math proofs, focusing on the process of finding the solution (the search) rather than just the final written result.

Technical Summary: Nazrin: An Atomic Neural Proof Automation Tactic in Lean 4

Problem Statement

Machine-assisted theorem proving in systems like Lean 4 faces significant challenges when training automated agents on human-written proofs. The primary obstacles include:

Unbounded Action Spaces: Human proofs utilize an infinite variety of tactics with arbitrary parameters (e.g., simp with long argument lists, use with arbitrary witnesses), creating a noisy and difficult-to-learn search space.
Presentation vs. Search Views: Human-written proofs often prioritize conciseness and readability (Presentation View), obscuring the incremental, backward-reasoning steps (Search View) actually required to discover the proof. This includes "mysterious jumps" and the elision of intermediate steps.
Metavariable Coupling: In Lean, goals often depend on one another (coupled metavariables). A naive tree search fails to account for the fact that solving one goal may instantaneously solve another or render a path impossible, complicating the search on a Directed Acyclic Graph (DAG) rather than a simple tree.
Hardware Constraints: Existing neural theorem provers often require significant computational resources, limiting their accessibility and the scale of training data they can process.

Methodology

The paper introduces Nazrin (Neural Atomizer for Inhabitation Problems), a graph neural network (GNN) based theorem proving agent. The methodology relies on three core pillars:

1. Atomic Tactics

The authors define a small, finite set of "atomic tactics" capable of proving any provable statement in Lean. These tactics are designed to have a bounded parameter space, ensuring the action space for the agent is finite.

Completeness: The set covers all top-level expression constructors in Lean (e.g., intro for lambda abstraction, exact/apply for constants, cases for inductive types).
Properties: The tactics are invariant (do not change assigned metavariables without backtracking), complete, progressive (always make progress), and deterministic.
Minimization of Cross-Section: The set is chosen to minimize "cross-sections" (the number of coupled goals), reducing the difficulty of the guidance generation problem.

2. Transposing Atomization

To train the agent, the authors developed a novel algorithm to convert existing human-written proofs (Presentation View) into sequences of atomic tactics (Search View).

Atomization: The algorithm translates arbitrary proof terms into a series of atomic steps. It uses the ground-truth proof term to guide the construction of a new proof using only atomic tactics.
Transposition: The algorithm reorders the execution of tactics to match the "Search View." It prioritizes "successor" goals (goals whose solutions inform predecessors) over "predecessor" goals. This mimics the backward reasoning used in discovery (e.g., $\epsilon$ - $\delta$ proofs) rather than the forward presentation.
State-Level and Goal-Level Transposition: The system reorders tactic dispatch to avoid dead ends. For instance, it allows non-conflicting "semigrade" tactics (acting on parts of a target or free variable) to be dispatched in arbitrary order, even if the coupled goals are not yet instantiated.

3. ExprGraph and Neural Architecture

The agent uses a Graph Neural Network (GNN) to process Lean expressions, represented as ExprGraphs.

Essentialization: Expressions are converted into graphs where irrelevant technical distinctions (e.g., specific variable names, metadata) are erased. The graph preserves fundamental symmetries (e.g., $\alpha$ -equivalence) and ensures that subexpressions correspond to subgraphs.
Neural Probabilistic Automaton (NPA): Instead of a standard generative model, Nazrin uses an NPA. The GNN conditions the transition probabilities of a finite-state automaton.
- Kind State: Selects the tactic type (e.g., intro, apply).
- Descendant States: Specialized GNN heads generate arguments (e.g., selecting a constant for apply or a free variable).
Efficiency: The model is small (1.5M parameters for standard library, 11M for Mathlib) and runs on consumer-grade CPU hardware, generating thousands of tactics per minute.

Key Contributions

Atomic Tactics: A finite, complete set of tactics that reduces the theorem proving action space to a manageable size, enabling efficient reinforcement learning and supervised training.
Transposing Atomization Algorithm: A method to generate large-scale training data by converting existing formalized mathematics into atomic, search-view proofs, effectively teaching the agent how to find proofs rather than how to present them.
ExprGraph: A reduced graph-based representation of Lean expressions that exploits mathematical symmetries and variable references, explicitly mimicking attention mechanisms found in language models.
Nazrin Prover: A low-resource, GNN-based agent that successfully trains on atomized data and generalizes to new theorems.
Evaluation Framework: A rigorous evaluation mimicking the development of new theories, where the agent is trained on one slice of the library and tested on the next to ensure no information leakage.

Results

The authors evaluated Nazrin on Lean's standard library and Mathlib:

Atomization Success: Approximately 58% of 170,180 theorems were successfully atomized.
Generalization:
- Trained on Standard Library Slice 1, Nazrin achieved 57% accuracy on Slice 2.
- Trained on Mathlib Slice 3, Nazrin achieved 34% completion on Slice 4.
Comparison: Nazrin demonstrated the ability to prove theorems that existing automation tactics (Aesop and Grind) could not discharge within a 15-second time limit.
Performance: The system operates efficiently on consumer-grade hardware, contrasting with the resource-heavy requirements of many LLM-based provers.

Significance and Claims

The paper claims that Nazrin addresses the fundamental mismatch between the structure of human-written proofs and the requirements of automated search. By enforcing a finite action space through atomic tactics and generating training data via transposing atomization, the authors demonstrate that:

Machine learning agents can be trained to discover proofs incrementally without needing to generate complex, arbitrary parameters from scratch.
Graph-based representations are effective for capturing the structural symmetries of mathematical proofs.
High-performance theorem proving is achievable on modest hardware, making the technology more accessible.

The authors note that while the system is promising, it currently does not cover all theorems (atomization fails for some high cross-section proofs), and the architecture has not been fully tuned. They suggest future work could focus on improving atomization coverage, reducing cross-sections, and refining the neural architecture to handle multi-parameter conditioning and non-symbolic data (numbers/strings) more robustly.