🤖 machine learning

Can LLMs Reason Like Automated Theorem Provers for Rust Verification? VCoT-Bench: Evaluating via Verification Chain of Thought

This paper introduces VCoT-Lift, a framework that transforms low-level solver reasoning into human-readable Verification Chain-of-Thought steps to create VCoT-Bench, a comprehensive benchmark revealing that current Large Language Models lack the robust reasoning capabilities of automated theorem provers for rigorous Rust program verification.

Original authors: Zichen Xie, Wenxi Wang

Published 2026-03-20

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Zichen Xie, Wenxi Wang

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 "Black Box" Problem

Imagine you have a super-smart robot (a Large Language Model, or LLM) that writes code for you. You ask it to write a program for a self-driving car, and it says, "Done! Here is the code."

To make sure the code is safe, you run it through a Formal Verifier (like a strict math teacher named Z3). The teacher checks every single logical step to ensure the car won't crash.

The Old Way: The teacher just gives a grade: Pass or Fail.
The Problem: If the robot gets a "Pass," we don't know why. Did it actually understand the math? Or did it just guess the right words that looked like a solution? It's like a student guessing the answer on a math test and getting it right by luck. We can't tell if they actually learned the material.

The Solution: Opening the "Black Box"

The authors of this paper say, "We need to see the student's scratch work." They want to see the Chain of Thought—the step-by-step reasoning the robot used to prove the code is safe.

They call this a Verification Chain of Thought (VCoT).

The Analogy: The Translator and the Architect

The real "math teacher" (the Z3 solver) speaks a very strange, robotic language. Its proof for a simple program is 10,000 lines long and mostly consists of trivial things like "5 equals 5." It's impossible for a human to read.

The authors built a new tool called VCoT-Lift. Think of this tool as a Master Translator:

It takes the robotic, 10,000-line proof.
It filters out the noise (the "5 equals 5" stuff).
It translates the remaining logic into clear, human-readable steps, like a well-written essay explaining why the code works.

Now, instead of just seeing "Pass," we can see the actual essay the robot wrote.

The Test: VCoT-Bench

Once they had this tool to create "perfect essays" (the ground truth), they built a test called VCoT-Bench.

Imagine a game of "Fill in the Blanks" for a story.

They take a perfect proof (the story).
They rip out chunks of the story (the "proof holes").
They ask the AI: "Can you write the missing parts to finish the story correctly?"

They tested this in three ways:

How much did we remove? (Did we take out 10% of the story or 90%?)
What kind of story was it? (Was it a "Loop" story, an "Assertion" story, or a "Lemma" story?)
Where was the hole? (Was the missing part at the beginning, the middle, or the end?)

The Results: The Robot is Fragile

The researchers tested 10 of the smartest AI models available. The results were shocking.

1. The "Context Crutch" (Fragility)
When the AI was given a story with only a tiny hole (10% missing), it did okay. But as soon as they removed more than 40% of the story, the AI completely collapsed.

Analogy: It's like a student who can solve a math problem if you give them the first three steps. But if you ask them to start from scratch or fill in the middle without the setup, they freeze. They aren't doing math; they are just memorizing patterns.

2. The "Middle" is the Hardest
The AI was surprisingly good at the beginning and the end of the proof, but terrible at the middle.

Analogy: The beginning is like setting the table (easy patterns). The end is like saying "The End" (easy patterns). The middle is where the actual cooking happens—connecting ingredients, adjusting heat, and keeping track of time. The AI gets lost in the middle because it can't track the state of the program over time.

3. Bigger isn't Always Better
Sometimes, the biggest, most expensive AI models performed worse than smaller, simpler ones.

Analogy: The big models were like over-enthusiastic students who started writing a novel when you just asked for a sentence. They got so caught up in "thinking" and adding extra words that they made mistakes. The simpler models just gave the direct answer.

The Conclusion: We Have a Long Way to Go

The paper concludes that current AI models are not yet true "Reasoners."

They are excellent at imitating the look of a proof. They can write code that looks like it has been verified. But they cannot construct the logical chain of reasoning from scratch like a human mathematician or a dedicated theorem prover can.

The Takeaway:
We can't just ask AI to "write safe code" and trust the result. We need to force them to show their work. Until they can consistently fill in the "middle" of the story without help, they are still just very good guessers, not true logical thinkers.

1. Problem Statement

The paper addresses a critical gap in evaluating Large Language Models (LLMs) for Rust program verification. While LLMs are increasingly used to synthesize code and proof hints for formal verification tools like Verus (which relies on the Z3 SMT solver), current evaluation methods are insufficient.

The Black Box Problem: Existing benchmarks (e.g., Verus-Bench) treat verification as a binary outcome: "pass" or "fail." This obscures whether the LLM truly understands the logical deductions required or is merely exploiting statistical patterns to generate syntactically correct hints that happen to work.
The Semantic Gap: When verification succeeds, Z3 produces a proof trace. However, these traces are machine-oriented, extremely verbose (often >10,000 lines for small programs), and dominated by low-level trivial reasoning (e.g., $x=x$ ), making them unintelligible to humans and difficult to use as ground truth for evaluating LLM reasoning.
The Core Question: Do LLMs possess the deductive reasoning capabilities of Automated Theorem Provers (ATPs), or do they fail when the "syntactic scaffolding" is removed?

2. Methodology

The authors propose a two-part framework: VCoT-Lift (a tool to generate ground truth) and VCoT-Bench (a benchmark for evaluation).

A. VCoT-Lift: From Solver Traces to Human-Readable Logic

VCoT-Lift is an LLM-based framework designed to "lift" low-level Z3 solver reasoning into high-level, human-readable Verification Chain-of-Thought (VCoT) steps. It transforms the opaque Z3 proof into a structured Verus proof consisting of loop invariants, assertions, and lemmas.

Pipeline Architecture:
1. Proof Transformer: Converts raw Z3 proofs into Verus-level steps. To handle long contexts, it uses a Z3 Rule Hierarchy to categorize rules into High, Medium, and Low importance, guiding the LLM to focus on semantically critical steps.
2. Proof Checker: Validates the completeness of the transformation. It uses specialized agents for different rule categories (e.g., Lemma, Modus Ponens) and employs an Abstraction Filter to ignore trivial/redundant steps (like reflexivity) that do not contribute to the core logic.
3. Transformer-Checker Loop: An iterative process where the transformer regenerates the proof if the checker finds missing high-level steps, ensuring global consistency.
4. Proof Pruner: Removes redundant or trivial steps to ensure conciseness.
5. Proof Repair: Interacts with the Verus compiler to detect and fix syntactic or semantic errors, using expert knowledge and error messages to guide the LLM.
Output: The result is a VCoT, a step-by-step deductive chain that serves as the "ground truth" for verification reasoning.

B. VCoT-Bench: The Evaluation Benchmark

Using VCoT-Lift, the authors constructed VCoT-Bench, a comprehensive benchmark containing 1,988 tasks derived from 150 verified Verus programs.

Task Construction: The benchmark creates "proof holes" by removing semantic blocks (Loop Invariants, Assertions, Lemma Functions) from the ground-truth VCoT.
Three Orthogonal Dimensions:
1. Ratio: Varying degrees of information loss (10% to 100% of blocks removed).
2. Type: Removing specific proof types (all invariants, all assertions, or all lemmas).
3. Location: Removing blocks from the Front, Middle, or End of the proof sequence.
Metrics: Evaluation uses Syntactic Accuracy, Semantic Accuracy (via a specialized LLM judge), and a weighted Overall Accuracy that prioritizes semantic correctness.

3. Key Contributions

Concept (VCoT): Introduction of the "Verification Chain-of-Thought," a structured, step-by-step representation of formal verification logic that bridges the gap between machine proofs and human reasoning.
Tool (VCoT-Lift): The first framework capable of automatically lifting low-level Z3 proofs into high-level, sound, and concise Verus verification steps, providing a transparent ground truth.
Benchmark (VCoT-Bench): A rigorous benchmark with nearly 2,000 tasks designed to test LLMs on fine-grained reasoning rather than binary pass/fail outcomes.
Empirical Study: A comprehensive evaluation of 10 state-of-the-art LLMs (including GPT-5, Claude 4.5, Gemini 3, DeepSeek, and Qwen) revealing significant limitations in their deductive capabilities.

4. Key Results

The study of 10 SOTA models reveals that current LLMs are severely fragile compared to automated theorem provers:

Fragility to Context Loss: Performance drops sharply as proof blocks are removed. Even with only 10% of blocks missing, the best model (Claude Sonnet 4.5) achieves only ~71% accuracy. When all blocks are removed (requiring full reconstruction), accuracy collapses to near zero for most models.
The "40% Threshold": A critical drop in performance occurs between 10% and 40% removal. Once structural anchors are lost, logical continuity collapses, and models cannot infer the remaining logic.
Proof Type Difficulty:
- Assertions are the hardest: Models struggle most with precise, state-dependent assertions (lowest accuracy).
- Loop Invariants are most discriminative: While generally the "easiest" for models, the performance gap between top and bottom models is widest here, effectively separating models with genuine reasoning from those relying on pattern matching.
Location Sensitivity: Models perform significantly worse on Middle blocks (connective reasoning) compared to Front (setup) or End (closing) blocks. This indicates an inability to track state evolution and compose multi-step deductions.
Scale vs. Reasoning: Larger models generally perform better, but "reasoning" variants (e.g., "thinking" modes) sometimes underperform simpler models, suggesting that verbose reasoning can introduce noise in formal verification contexts.
Syntactic vs. Semantic Imbalance: Some models exhibit high syntactic accuracy (correct grammar) but low semantic accuracy (incorrect logic), highlighting a disconnect between code fluency and verification understanding.

5. Significance

Paradigm Shift: The paper moves the field from "Can the model pass the verifier?" to "Can the model reconstruct the verification logic?" This exposes that current LLMs are largely syntactic mimics rather than logical reasoners in the context of formal verification.
Diagnostic Tool: VCoT-Bench provides a granular diagnostic tool to identify specific weaknesses (e.g., inability to handle middle-step connective reasoning) in LLMs.
Future Training Signal: The VCoT framework offers a concrete supervision signal for training future models. Instead of just learning to pass verification, models can be trained to reconstruct the explicit deductive steps, potentially leading to systems that achieve true symbolic alignment with automated theorem provers.
Safety Implications: The findings suggest that relying on current LLMs for critical safety-critical Rust verification is risky, as they lack the robustness to handle partial information or complex deductive chains without heavy scaffolding.