💻 computer science

PROMISE: Proof Automation as Structural Imitation of Human Reasoning

The paper introduces PROMISE, a structure-aware framework that improves automated proof generation for formal verification by reframing the task as a stateful search over proof-state transitions and mining structural patterns for iterative adaptation, achieving significant performance gains over existing methods on the seL4 benchmark.

Original authors: Youngjoo Ahn, Sangyeop Yeo, Gijung Lim, Jongmin Lee, Jinyoung Yeo, Jieung Kim

Published 2026-04-08

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Youngjoo Ahn, Sangyeop Yeo, Gijung Lim, Jongmin Lee, Jinyoung Yeo, Jieung Kim

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 Problem: Building a Castle Brick by Brick

Imagine you are trying to build a massive, impenetrable castle (a piece of critical software like an operating system) where every single brick must be mathematically proven to be perfect. If even one brick is weak, the whole castle could collapse, causing disasters in the real world.

This process is called Formal Verification. It's incredibly safe, but it's also incredibly hard and slow.

The Old Way: Human experts have to manually write a "proof script" for every single brick, explaining exactly why it fits. For a project like the seL4 microkernel (a tiny but super-secure operating system), this took human experts decades of work. It's like trying to build a skyscraper by hand, one brick at a time, without any blueprints.

The Failed Shortcut: The "Google Search" Approach

Recently, we got powerful AI (Large Language Models or LLMs) that are great at writing code and solving math problems. Researchers hoped these AIs could act as super-fast proof writers.

However, early attempts failed when the projects got big. Why?

The Analogy: Imagine you are trying to fix a leak in a giant, complex plumbing system. The old AI approach was like Googling "leak" and getting back a list of articles about leaks.
The Problem: The AI found articles that looked similar (same keywords), but they were about fixing a kitchen sink, not a high-pressure industrial pipe. The AI got confused because it was looking at the words, not the structure of the problem. It tried to copy-paste solutions that didn't fit the specific shape of the leak.

The Solution: PROMISE (The "Master Architect" Approach)

The authors created a new system called PROMISE. Instead of just searching for similar words, PROMISE looks at how the proof evolves step-by-step.

Here is how it works, using a Detective Mystery analogy:

1. The Old Way: "Keyword Matching"

If a detective is trying to solve a murder, the old AI would look at the crime scene and say, "I found a case where the victim was stabbed!" It would then try to apply the solution from that case, even if the current murder happened in a different city with different suspects. It's too shallow.

2. The PROMISE Way: "Structural Imitation"

PROMISE acts like a Master Detective who studies the pattern of solving crimes, not just the crime itself.

The "State Transition": Instead of looking at the final answer, PROMISE looks at the journey. It asks: "How did the detective in the past case move from 'Suspect A' to 'Suspect B'?"
The Analogy: Imagine you are climbing a mountain.
- Old AI: Looks at a photo of someone who climbed a mountain and says, "They wore red boots, so I need red boots." (Wrong! The terrain is different).
- PROMISE: Looks at the path the climber took. "Ah, they had to cross a slippery ice patch, then climb a steep rock face. I see I have a slippery ice patch right here too. I will use the same technique they used to cross the ice."

How PROMISE Actually Works (The 3-Step Engine)

Step 1: The "Blueprint" Search (Structural Retrieval)
When PROMISE gets stuck on a difficult proof step, it doesn't just search for the same words. It searches for proofs that had the same "shape" of problem.

Example: If the current problem is "I need to prove that a door is locked," PROMISE looks for past proofs where the detective had to "prove a door was locked" at the exact same stage of the investigation. It finds the tactic (the move) used there, not just the text.

Step 2: The "Toolbox" Check (Name Retrieval)
Once it knows what move to make (e.g., "apply the lock"), it checks the local toolbox to make sure the specific tool exists in this specific room.

Analogy: It knows you need a "hammer," but it checks if you have a "sledgehammer" or a "tiny tack hammer" available in this specific room before telling you to swing.

Step 3: The "Safety Inspector" (Machine Checking)
PROMISE doesn't just guess. Every time it suggests a step, it runs it through a strict Safety Inspector (the Isabelle proof assistant).

If the step works, it moves forward.
If it fails, it immediately knows, "That didn't work," and tries a different path. It keeps a "beam" of the top 6 best paths open at all times, like a hiker keeping multiple routes in mind in case one path is blocked.

The Results: Why It Matters

The researchers tested PROMISE on the seL4 operating system (the "Mount Everest" of software verification).

The Competition: Other AI systems (like Selene and Rango) were like hikers trying to climb the mountain by guessing. They got stuck often.
PROMISE: By following the structural "footprints" of past successful climbs, PROMISE reached the summit much more often.
- It improved success rates by up to 186% compared to older methods.
- It worked well even with smaller, cheaper AI models, proving that the strategy (the map) is more important than just having a super-powerful brain.

The Takeaway

PROMISE changes the game. It stops treating AI proof generation like a "text completion" task and starts treating it like a guided journey.

Instead of asking the AI, "Write me a proof," it asks, "Here is where we are in the journey. Look at how other successful journeys handled this exact same terrain. Let's use that same strategy to get to the next step."

It turns the AI from a parrot (repeating words it heard) into a navigator (understanding the map and the terrain). This makes it possible to verify massive, life-critical software systems without needing decades of human effort.

1. Problem Statement

Formal verification of large-scale system software (e.g., operating system kernels like seL4) remains a labor-intensive bottleneck. While Large Language Models (LLMs) have shown promise in code generation and small-scale theorem proving, they struggle with scalability in complex verification projects.

Key Challenges Identified:

Deep Dependencies: Large verification artifacts (like seL4) contain thousands of lemmas with deep inter-file dependencies. Proofs are not isolated; they rely on long chains of auxiliary results.
Limitations of Current LLM Approaches: Existing methods typically treat proof generation as:
- Single-shot generation: Attempting to generate a full proof at once.
- Shallow Retrieval-Augmented Generation (RAG): Retrieving static artifacts (lemmas, premises, or full proofs) based on surface-level textual similarity (keywords/embeddings).
The Core Gap: Textual similarity fails to capture the structural dynamics of proof construction. Human engineers do not just match keywords; they recognize proof-state transition patterns (e.g., "rewrite followed by simplification," "case analysis followed by rule application") and adapt these patterns to new contexts. Existing systems fail to retrieve these reusable reasoning trajectories.

2. Methodology: PROMISE Framework

The authors propose PROMISE (PROof Mining via Structural Embeddings), a framework that reframes proof generation as a stateful, iterative search process guided by structural similarity rather than textual similarity.

A. Core Philosophy

Instead of retrieving static proofs, PROMISE mines proof-state transition traces. It views a proof as a sequence of states ( $s_0 \xrightarrow{t_1} s_1 \xrightarrow{t_2} \dots \xrightarrow{t_n} s_{final}$ ), where each step transforms the goal and assumptions. The system retrieves historical traces that structurally resemble the current proof state evolution.

B. System Architecture

PROMISE operates as a Retrieval-Grounded Beam Search over Isabelle/HOL proof states.

Proof-State Search (Beam Search):
- The system maintains a "beam" of active proof nodes. Each node represents a partial proof prefix, the current Isabelle proof state, active assumptions, and the current goal.
- It iteratively expands nodes by generating candidate tactics, verifying them in Isabelle, and selecting the top-scoring successors.
Dual-Channel Retrieval Strategy:
- Structural Retrieval (The Core Innovation):
  - Database Construction: The system pre-processes the verification corpus by executing proofs line-by-line to record intermediate goals and their corresponding remaining proof suffixes. These are embedded into a database.
  - Retrieval Process: For a current goal, the system parses the goal, retrieves top candidates based on structural similarity (embedding distance + lexical overlap of constants), and then reranks them based on semantic similarity (goal alignment and constant overlap).
  - Output: It extracts tactic templates (the shape of the proof) from the retrieved examples, abstracting away specific theorem names to guide the LLM on how to proceed, not just what to use.
- Name Retrieval:
  - Simultaneously retrieves concrete lemma and definition names available in the current context (e.g., via Isabelle PIDE or character-n-gram matching) to ground the generated tactics in valid, existing facts.
Command Generator & Prompting:
- Constructs a grounded few-shot prompt containing:
  - Current goal and assumptions.
  - Retrieved structural templates (showing the "skeleton" of similar proofs).
  - A role-partitioned inventory of valid theorem names (Definitions, Rules, WP lemmas).
- The LLM is instructed to generate diverse, short tactic sequences (1-2 commands) using apply style, avoiding single-shot by closures.
Verification & Filtering:
- Static Filtering: Normalizes syntax and filters out invalid references before execution.
- Machine-Checked Execution: Candidates are executed in Isabelle via a Scala-Isabelle bridge. Only candidates that make measurable progress (reduce subgoals) or close the proof are retained.
- Safety: The target theorem is explicitly excluded from retrieval to prevent leakage.

3. Key Contributions

Structural View of Proof Generation: Shifts the paradigm from keyword-based retrieval to proof-state transition mining. It identifies structural evolution patterns as the primary unit of reasoning reuse.
PROMISE Framework: A model-agnostic, retrieval-grounded beam search system that combines structural pattern matching with semantic grounding. It operates without fine-tuning the LLM, using off-the-shelf models (e.g., GPT-3.5, Qwen2.5, GPT-4).
Comprehensive Evaluation: A rigorous empirical study on the seL4 microkernel (l4v), a massive, real-world verification benchmark with deep dependencies, comparing against state-of-the-art baselines.

4. Experimental Results

The evaluation was conducted on 223 theorems from the seL4 project (split into P1, P2, and P3 difficulty levels) using multiple LLM backends (Qwen2.5-Coder-7B, GPT-3.5-Turbo, GPT-4.1).

Performance Gains:
- PROMISE consistently outperformed baselines (Selene and Rango).
- On Qwen2.5-Coder-7B, PROMISE achieved 77% success on P1 and 36% on P2, compared to Selene's 30% and 2% respectively.
- Relative Improvement: Achieved up to +26 percentage points (186% relative gain) over the strongest baselines in specific settings.
- P3 (Hardest) Performance: On the most difficult P3 lemmas, PROMISE solved 7/23 (30.4%), more than double the best baseline (Rango at 13%).
Model Robustness:
- PROMISE showed high stability across different model capabilities. The performance gap between a small open-weight model (Qwen-7B) and a large proprietary model (GPT-4.1) was minimal within the PROMISE framework, whereas baselines showed large variance.
Ablation Insights:
- The combination of Structural Retrieval + Name Retrieval + Iterative Beam Search was crucial. Single-shot approaches (Selene) and keyword-based iterative approaches (Rango) failed to scale to the same degree.
- Note: In the specific case of GPT-4.1 on P2, Rango slightly outperformed PROMISE (35% vs 33%). The authors hypothesize that GPT-4.1's superior instruction-following capabilities may have been over-constrained by PROMISE's strict structural scaffolding, whereas Rango's looser prompt allowed GPT-4.1 to leverage its latent reasoning more freely.

5. Significance and Conclusion

Scalability: PROMISE demonstrates that automated theorem proving can scale to industrial-grade systems (like OS kernels) by mimicking human reasoning strategies—specifically, recognizing and reusing structural proof patterns rather than just text.
Beyond Textual Similarity: The paper proves that for formal verification, "how" a proof evolves (state transitions) is more critical than "what" the proof contains (static text).
Practical Impact: By reducing the human burden in constructing proofs for safety-critical systems, PROMISE moves formal verification closer to practical adoption in real-world engineering.
Future Work: The authors plan to apply this to the full seL4 corpus and explore learning-based (RL) strategies to optimize retrieval policies for long-horizon verification tasks.

In summary, PROMISE represents a significant step forward in AI-assisted formal verification by moving from static, keyword-based retrieval to dynamic, structure-aware proof mining, enabling LLMs to tackle the complex, interdependent proofs required for verifying modern operating systems.