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

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: Next we'll be talking about the paper "Can LLMs Reason Like Automated Theorem Provers for Rust Verification? VCoT-Bench: Evaluating via Verification Chain of Thought".

Jane: The paper was written by Zichen Xie and Wenxi Wang from University of Virginia.

Tom: Stay tuned as we take you through the paper and discuss its implications.

Jane: We also have Lu with us today — senior AI researcher at Tsinghua.

Tom: We also have Meng with us today — lead engineer at a mysterious AI startup.

Jane: We also have Lalam with us today — the in-house Large Language Model.

Tom: Alright, let's get started.

Title: Tom: Welcome back to the show, everyone! Today we're digging into a paper with a title that's a mouthful: "Can LLMs Reason Like Automated Theorem Provers for Rust Verification? VCoT-Bench: Evaluating via Verification Chain of Thought." Jane, I gotta say, just reading that title got me excited.

Jane: It got me excited too, Tom, because it's asking a really fundamental question. We keep hearing that large language models can write code, but can they actually *prove* that code is correct? Not just write something that looks right, but mathematically guarantee it works for every possible input?

Tom: Exactly! And that's where Rust comes in. Rust is this systems programming language that's all about safety and performance. The Linux kernel is adopting it, major tech infrastructure is using it. But even Rust can have logical bugs, right?

Jane: Right, and that's where formal verification enters the picture. There's this tool called Verus that takes Rust code and checks it against formal specifications. It's like having a super-strict math teacher check every step of your homework, not just the final answer.

Tom: So the paper's title is basically asking: when we give LLMs this verification task, are they actually reasoning through the logic like a theorem prover would, or are they just pattern-matching their way to a plausible-looking answer?

Jane: And that's the crux of it. The authors from the University of Virginia, Zichen Xie and Wenxi Wang, they looked at this and said, "You know what? Everyone's been evaluating LLMs on whether they can generate the right proof hints, but they're only looking at pass or fail. Did the program verify or not?"

Tom: Right, it's a black box. You see the output, you see whether it compiled and verified, but you have no idea what the model actually understood. Did it construct a sound deductive chain, or did it just get lucky with syntactic alignment?

Jane: So they came up with this idea of a Verification Chain of Thought, or VCoT. It's like exposing the step-by-step reasoning that the solver does, making it visible and human-readable. And then they built a benchmark around it to test whether LLMs can complete missing pieces of that chain.

Tom: And what they found, Jane, is pretty sobering. We'll get into the details, but spoiler alert: the models are fragile. They lean heavily on context and pattern matching, and when you strip that away, their performance just collapses.

Jane: It's a wake-up call for anyone who thinks LLMs are ready to replace formal verification tools. But it's also a really creative way to open up the black box and actually see what's happening inside. I'm curious how they pulled that off.

Tom: Me too. Let's get into the methodology next, because the way they lifted those low-level solver proofs into something humans can read is genuinely clever.

Summary: Jane: So Tom, before we get into the clever part, let's recap where we are. The paper is "Can LLMs Reason Like Automated Theorem Provers for Rust Verification? VCoT-Bench: Evaluating via Verification Chain of Thought," and the core problem is that verification tools like Z3 produce proofs that are technically correct but practically unreadable.

Tom: Unreadable is an understatement. The paper shows a running example where the Z3 proof is over ten thousand lines long, and more than eighty percent of it is just trivial low-level reasoning. Like, literally proving that a variable equals itself.

Jane: That's the semantic gap. The solver is doing all this fine-grained reasoning, but it's buried under so much noise that you can't see the actual logical structure. So the authors built this framework called VCoT-Lift to lift that low-level reasoning into high-level, human-readable verification steps.

Tom: And how do they do that? They use LLMs themselves, right? That's the twist.

Jane: It is. They use LLMs to transform the Z3 proof into Verus-level proofs. But they don't just ask the model to do it in one shot. They have this four-stage pipeline. First, there's a transformer that synthesizes Verus proofs from the Z3 proofs. Then there's a checker that evaluates completeness, focusing only on the high-level proof rules.

Tom: So it's like a teacher checking whether you covered all the important steps, but ignoring the trivial stuff like "two plus two equals four."

Jane: Exactly. And they have these specialized checker agents for different types of proof rules. Lemma checkers, modus ponens checkers, quantifier checkers. Each one looks at its slice of the Z3 proof and verifies that the transformation captured it.

Tom: And then there's a pruner and a repair stage, right?

Jane: Right. The pruner removes redundant or trivial steps that don't add anything, and the repair stage actually runs the Verus verifier to catch syntax errors and semantic mistakes. So the whole thing is grounded in actually checking whether the transformed proof works.

Tom: That's the soundness guarantee. And the result is this dataset called VCoT-Bench-Org, which has way more proof detail than the original Verus-Bench. Like, six and a half times more proof lines on average.

Jane: And that's what they use to build the benchmark. They dig holes in the proofs at the level of semantic blocks. So you might remove a lemma function, or a set of loop invariants, or a group of assertions, and then ask the LLM to fill in the missing piece.

Tom: So it's not just "write the whole proof from scratch." It's "here's a mostly complete proof, but this chunk is missing. Can you reconstruct it?"

Jane: Precisely. And they organize these tasks along three dimensions. The ratio dimension asks how much of the proof you remove. The type dimension asks whether you're removing invariants, assertions, or lemmas. And the location dimension asks whether the missing piece is at the front, middle, or end of the proof.

Tom: That's a really thorough way to probe what the models actually understand. And the results, Jane, they're not pretty. Let's talk about what they found.

Jane: Let's do it. Because I think the findings tell us something important about where LLMs stand in formal verification.

Improvements: Tom: So Jane, we've set up the benchmark. Now let's talk about what they actually found when they tested ten state-of-the-art models on this thing. And the first finding is that these models are fragile. Like, really fragile.

Jane: Fragile is the right word. When only ten percent of the proof blocks are missing, the best model, Claude Sonnet four point five, gets about seventy-two percent accuracy. But when you remove everything and ask for the full proof from scratch, that same model drops to about seventeen percent.

Tom: And the weakest model, gpt-oss, starts at thirty-three percent and just falls off a cliff. So the models are clearly not reasoning from first principles. They're leaning on the surrounding context, using it like scaffolding.

Jane: That's exactly what the authors argue. The models are doing pattern matching and syntactic alignment, not genuine deductive reasoning. And there's this interesting threshold effect too. Performance drops sharply from ten to forty percent removal, then levels off.

Tom: That forty percent threshold is fascinating. It suggests that once you remove enough of the structural anchors in the proof, the whole logical continuity collapses. The model can't infer the proof logic anymore, so removing more blocks doesn't really matter.

Jane: And then there's the type dimension. Assertions are the hardest for most models. Claude Sonnet four point five gets about sixty-nine percent on loop invariants but only about forty percent on assertions. That makes sense because assertions require precise, state-specific reasoning. One missing condition and the whole thing fails.

Tom: But loop invariants are the most discriminative, right? The gap between the best and worst model on invariants is almost fifty-nine percentage points. That's a huge spread.

Jane: It is. And the location findings are interesting too. Middle blocks are the hardest. Models handle front blocks that set up constraints and end blocks that follow recognizable closing patterns, but the middle requires connective reasoning. You have to propagate invariants, track state evolution, compose multi-step deductions.

Tom: And that's where even the big models stumble. Gemini three drops from about sixty-three percent on front blocks to thirty-six percent on middle blocks. That's a massive drop.

Jane: One more thing I found surprising: the reasoning variants sometimes hurt. Qwen three's thinking mode actually performed worse than its non-thinking mode. And Gemini three Flash outperformed the larger Gemini three on middle blocks.

Tom: That's counterintuitive, right? You'd think more reasoning tokens would help. But the authors suggest that verbose thinking can introduce hallucinated predicates or semantic drift. In formal proofs, where syntactic precision matters, that extra "thinking" can actually be noise.

Jane: So what does this mean practically? I think it means we're a long way from LLMs replacing automated theorem provers. But the benchmark itself is a valuable contribution because it gives us a way to measure progress.

Tom: And that's the optimistic take. The paper isn't just saying "models are bad." It's providing a tool to evaluate them properly, which is the first step toward improving them. Lu and Meng are going to have thoughts on this, I'm sure.

Conclusion: Jane: Well, we've reached the end of our discussion on "Can LLMs Reason Like Automated Theorem Provers for Rust Verification? VCoT-Bench: Evaluating via Verification Chain of Thought." Tom, I think the biggest takeaway is that the paper gives us a way to see inside the verification process instead of just looking at pass or fail.

Tom: And what they saw inside is that current LLMs are a long way from matching automated theorem provers. They're pattern matchers, not reasoners, at least when it comes to formal verification.

Jane: But the framework they built, VCoT-Lift, and the benchmark, VCoT-Bench, those are real contributions. They open up the black box and give us a concrete way to measure whether models actually understand the logic.

Tom: And that matters beyond just Rust verification. The idea of exposing solver reasoning as a chain of thought could apply to other formal methods, other languages, other verification tools. It's a general approach to evaluating reasoning capability.

Jane: The authors also point toward future work where VCoT could provide supervision signals for training. Instead of just rewarding models for producing proofs that verify, you could reward them for reconstructing the actual reasoning chain. That could push models toward genuine symbolic alignment.

Tom: So the field moves from "does it verify?" to "does the model truly understand the verification logic?" That's a much harder question, but it's the right one to ask.

Jane: And it's a question we should keep asking as these models get bigger and more capable. Because the gap we saw here, between syntactic fluency and semantic understanding, it's not going to close on its own.

Tom: Alright, that's a wrap on this paper. Big thanks to our listeners for sticking with us. Next up, we've got a paper on something completely different, so stay tuned.

Jane: Thanks for joining us, everyone. We'll see you in the next episode.