🤖 AI

Just Type It in Isabelle! AI Agents Drafting, Mechanizing, and Generalizing from Human Hints

This paper presents a formal metatheoretical account and Isabelle/HOL mechanization of complete and minimal type annotations for rank-one polymorphic $\lambda$ -calculus terms, developed through a collaborative workflow where human and AI agents independently produce proofs that are subsequently autoformalized and generalized with human-guided AI interventions.

Original authors: Kevin Kappelmann, Maximilian Schäffeler, Lukas Stevens, Mohammad Abdulaziz, Andrei Popescu, Dmitriy Traytel

Published 2026-04-20

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Kevin Kappelmann, Maximilian Schäffeler, Lukas Stevens, Mohammad Abdulaziz, Andrei Popescu, Dmitriy Traytel

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

The Big Picture: The "Perfect Translator" Problem

Imagine you have a very complex, high-tech recipe written in a secret code. This recipe includes not just the ingredients (like "flour" or "eggs") but also specific instructions on what kind of flour (e.g., "gluten-free") and what kind of eggs (e.g., "organic").

Now, imagine you want to send this recipe to a friend. You want to write it out in plain English so it's easy to read. However, you have a strict rule: When your friend reads your plain English version and tries to cook it, they must end up with the exact same dish as the original secret code.

If you leave out too many details (like just saying "flour" instead of "gluten-free flour"), your friend might accidentally use regular flour, and the cake will collapse. But if you write every single detail (e.g., "organic, free-range, large, brown-shelled, gluten-free flour"), the recipe becomes a nightmare to read.

The Goal: Find the "Goldilocks" version of the recipe. It needs to have just enough details to ensure the friend cooks the right dish, but no more than necessary so it remains easy to read.

The Real-World Context: Isabelle and Type Annotations

In the world of computer science, specifically with a tool called Isabelle (a proof assistant used to verify math and code), this is exactly the problem the authors tackled.

The "Recipe": A computer program or a mathematical proof.
The "Secret Code": The fully typed version where every variable has a specific type assigned (e.g., this number is an integer, that one is a string).
The "Plain English": The printed version shown to the human user.
The "Details": Type annotations. These are little labels attached to variables telling the computer what they are.

The problem is: If you print a proof without enough labels, the computer's "guessing game" (called type inference) might guess the wrong type, breaking the proof. If you print it with too many labels, it's ugly and hard to read.

The Human vs. The AI Robot

The authors of this paper didn't just solve the problem; they ran a fascinating experiment to see how Humans and AI (specifically a Large Language Model called Claude) handle the job of solving it.

Think of it like a cooking competition between a Master Chef (the Human) and a Super-Intelligent Robot Chef (the AI).

1. The Human Chef (The Experts)

The human experts sat down with pen and paper. They:

Wrote down the rules of the game.
Created a mathematical proof showing exactly how to remove unnecessary labels without breaking the recipe.
Result: They produced a perfect, rigorous proof. But it took them about 5 days of hard work.

2. The Robot Chef (The AI Agent)

The authors gave the AI a messy, informal description of the problem (like a recipe written in a hurry) and asked it to do the same job.

Round 1: The AI tried to write the proof. It got the main ideas right but made some silly mistakes (like saying "flour" when it meant "sugar," or forgetting to define what "flour" even is).
The Review: A human looked at the AI's work and said, "Hey, you missed this step," and "You defined this wrong."
Round 2-4: The AI fixed its mistakes, learned from the feedback, and eventually wrote a proof that was almost as good as the human's.
Result: The AI did it in about 2 hours of computer time and cost only $70 in computing fees.

The "Auto-Translation" Phase

Once both the Human and the AI had their "pen-and-paper" proofs, the authors asked the AI to do one more thing: Translate these proofs into the actual computer code (Isabelle/HOL) that the proof assistant can read and verify.

The Human Proof Translation: The AI successfully translated the human's clean, logical proof into code.
The AI Proof Translation: The AI also successfully translated its own messy-but-improved proof into code.

The Surprise: The AI managed to do all the heavy lifting of writing the formal code for both versions. The humans didn't write a single line of the final code! They just acted as the "editors" and "managers."

The "Generalization" Twist (The Magic Hint)

In the final experiment, the authors gave the AI a "hint." They said, "Hey, this problem you're solving? It's actually just a special case of a famous, generic math problem called an 'Independence System'."

The AI immediately understood. It realized, "Oh! I don't need to reinvent the wheel. I can just use the existing rules for this generic problem to solve my specific problem instantly."

The AI then wrote a new, shorter proof based on this generic rule. It showed that AI can act like a super-smart research assistant that connects dots humans might miss, making the work much faster.

Key Takeaways (The "So What?")

AI is a Great Draftsman: The AI can write complex mathematical proofs and computer code very quickly, but it needs a human to check its work for logic errors. It's like a brilliant intern who writes fast but needs a manager to sign off.
Cost vs. Time: The human took 5 days. The AI took 2 hours and cost $70. For the price of a nice dinner, you can get a draft of a complex mathematical proof.
The Future of Math: This suggests a new way of doing math and computer science. Instead of humans doing everything from scratch, humans can act as "conductors," guiding AI agents to do the heavy lifting of writing proofs, while humans focus on the big ideas and checking the results.
The "Round-Trip" Success: They proved that you can print a computer proof, strip away the clutter, and have the computer perfectly reconstruct the original. It's like shredding a document and having a machine perfectly reassemble it, provided you leave a few specific "glue spots" (annotations) intact.

In short: The paper shows that AI is ready to be a partner in solving hard math and computer science problems, provided humans are there to guide it, review its work, and give it the right hints. It's a "Human + AI" team that is faster and cheaper than humans working alone.

1. Problem Definition

The paper addresses the correct printing problem for terms in the rank-one polymorphic $\lambda$ -calculus, specifically within the context of the Isabelle/HOL proof assistant.

The Core Challenge: When printing a fully typed term (e.g., for display or export), it is crucial to preserve enough type information so that reparsing the text and running type inference yields the exact original term. This is known as the round-trip property.
The Constraint: While type annotations are necessary for the round-trip, they hurt legibility. The goal is to find a minimal set of type annotations that ensures completeness (the round-trip property holds) while being as sparse as possible.
The Context: The paper focuses on the Smolka-Blanchette algorithm, an existing implementation in Isabelle that attempts to solve this via a greedy strategy. However, the original implementation contained bugs (e.g., dropping necessary annotations) and lacked a rigorous formal specification of its correctness guarantees. The authors aim to provide a precise metatheoretical account and formal proofs of completeness and minimality for this problem.

2. Methodology

The authors conducted a series of experiments contrasting human-driven and AI-driven workflows to solve the problem and formalize the solution in Isabelle/HOL. They utilized Claude Opus 4.6, a state-of-the-art Large Language Model (LLM), as an autonomous agent.

The workflow consisted of four distinct phases:

Human Pen-and-Paper Formalization: A human expert developed a rigorous metatheory, defining syntax, typing rules, and proving theorems regarding the algorithm's correctness on paper.
AI Pen-and-Paper Formalization: An AI agent, given only informal descriptions of the algorithm and implementation details, independently generated a LaTeX paper with formal statements and proof sketches. This process involved iterative human review and refinement (simulating a peer-review process).
Autoformalization: A second, disconnected AI agent took both the human and the AI-generated pen-and-paper proofs and translated them into Isabelle/HOL code.
AI Generalization via Human Hints: A human expert provided a high-level hint suggesting the problem could be modeled as an Independence System (IS). The AI agent successfully used this hint to abstract the algorithm, re-prove the minimality result using standard IS theory, and autoformalize this generalized version.

3. Key Contributions

A. Formal Metatheory of Type Annotation

Definitions: The authors formally defined Correct Printing (the round-trip property) and Minimality (sparsity of annotations) for rank-one polymorphic $\lambda$ -calculus.
Algorithm Specification: They provided a precise formal specification of the Smolka-Blanchette algorithm, separating the generic "reverse greedy" component from the specific "coverage test" logic.
Theorems: They proved two main theorems:
1. Completeness: The algorithm produces a term that, when reparsed, recovers the original typing.
2. Minimality: The resulting term is minimal with respect to the annotation subsumption relation (no annotation can be removed without breaking completeness).
Correction of Implementation: The formalization exposed and corrected bugs in the existing Isabelle implementation (e.g., incorrect dropping of annotations on constants).

B. AI-Driven Research Workflow

AI as a Co-Researcher: The paper demonstrates that an LLM can not only generate plausible proof sketches but also discover necessary lemmas (e.g., converse substitution extensionality) and correct its own logical errors through iterative human feedback.
Autoformalization of Metatheory: Unlike previous autoformalization work focused on standard mathematics, this work targets programming language metatheory, a domain with complex syntax and operational semantics.
Generalization: The AI successfully abstracted a specific algorithmic problem into a general mathematical structure (Independence Systems) upon receiving a human hint, then re-proved the results using off-the-shelf theory.

C. Technical Setup and Reproducibility

The authors developed a reusable setup using OpenCode and Isabelle/Q (via Model Context Protocol) to facilitate interaction between the LLM and the Isabelle proof assistant.
All input data, AI-generated proofs, and final Isabelle formalizations are publicly available on Zenodo.

4. Results

Success of AI Formalization: The AI agent successfully produced three distinct Isabelle formalizations of the desired results without the human authors writing a single line of Isabelle code.
- One formalization based on the human paper.
- One based on the AI-generated paper.
- One based on the AI's generalized Independence System approach.
Cost and Efficiency:
- The AI-generated paper cost approximately $70 and took 2 hours of compute time, plus 1 day of human review.
- The human-authored paper took 5 days of human work.
- The final autoformalization costs were roughly $140 per formalization.
Quality: The resulting Isabelle theories were "sorry-free" (fully proven) and idiomatic, though sometimes verbose. The AI-generated proofs required more human review to align theorem statements with the paper definitions compared to the human-generated proofs.
Generalization: The AI successfully reduced the specific algorithm to a standard problem in Independence Systems, proving local minimality using existing theory, demonstrating the ability to "learn" new mathematical connections quickly.

5. Significance

Validation of AI in PL Research: The paper provides strong evidence that LLMs can act as effective "research assistants" in programming language theory, capable of drafting, proving, and formalizing metatheoretical results.
Bridging Informal and Formal: It highlights the potential of using AI to bridge the gap between informal algorithm descriptions (often lacking rigorous proofs) and fully verified formal specifications.
Economic Impact: The study suggests that AI can significantly reduce the time and cost of formal verification and theorem proving, potentially democratizing access to high-assurance formal methods.
Future of Proof Engineering: The authors argue for a future where AI agents are integrated into proof assistants as standard tools (similar to Sledgehammer or Nitpick), capable of natural language interaction and handling complex, non-trivial proof developments.

In summary, the paper is a landmark demonstration of AI-assisted formalization, showing that modern LLMs can not only replicate human reasoning in complex theoretical computer science domains but also generalize concepts and accelerate the entire research lifecycle from informal idea to verified code.