Proof Work Split Along Refinement Layers: Multi-Agent Verification of Distributed Protocols

Language-model agents can now write machine-checked proofs for small sequential programs. They cannot yet do so for distributed systems, where proofs are hardest and most needed. Proving a replicated key-value store correct took IronFleet's experts about 3.7 person-years (IronFleet). The difficulty there is not the loop invariants that current agents handle well. It is the chain of refinement proofs, each showing that a lower layer of the system faithfully implements the layer above it. Those proofs span thousands of lines across many files and do not fit in one model's working context.

This note proposes to split the proof work among agents along the system's own refinement structure. Each refinement obligation (one lemma that must be proved) becomes a unit of agent work. The interface lemmas between layers are frozen as contracts. Coordination follows the state-driven "rules, tasks, pools" pattern from distributed systems engineering, not a conversation loop. In two sentences: give each agent one proof obligation with fixed contracts on either side, and let a deterministic scheduler, not an LLM orchestrator, decide what runs next based on what the proof checker currently accepts. The question is whether this decomposition, rather than more agents or more tokens, is what makes distributed-protocol proofs tractable for language models.

Core Claim

We claim that agent decomposition for verification should follow the proof's dependency structure, not human job titles. Concretely, splitting by refinement obligation with frozen contracts will prove substantially more stripped obligations in IronFleet-derived systems than the best existing agentic prover loop at a matched token budget. The advantage should grow with the number of obligations in the system, and it should vanish on single-file sequential benchmarks such as DafnyBench. If both predictions hold, they say where multi-agent decomposition pays for itself. If the advantage also survives when one agent works through the same obligations sequentially, the credit belongs to the decomposition, not to having multiple agents. We treat that outcome as a real and publishable possibility, not a failure.

Where This Sits

The proposal draws on three groups of prior work.

The first supplies the agent method. DafnyProver builds AxDafny, a loop with three parts: a proposer writes code and invariants, a reviewer runs the Dafny verifier and extracts counterexamples, and a memory module stores failed attempts. It reaches 92.7% on DafnyBench and 56.4% on LCB-Pro-Dafny. DafnyPro adds two safeguards. A syntax-tree diff checker stops the model from quietly weakening the specification, and a pruner removes non-inductive clauses. With these, Claude 3.5 Sonnet reaches 86%. We reuse both the counterexample feedback and the diff checker. Both systems, however, target single sequential programs and treat the whole program as one unit of work. We change the unit of work.

The second group motivates the proposal and defines the target. IronFleet establishes the three-layer structure we decompose along: a high-level specification, an abstract protocol, and an imperative implementation. It also introduces reduction arguments that let non-atomic code be reasoned about as atomic protocol steps. Agora shows that a role-specialized multi-agent team finds 15 zero-day bugs in production consensus code where ReAct baselines find none. That is evidence that decomposition matters on distributed protocols. But Agora only hunts bugs and never constructs or proves anything. Why Do Multi-Agent LLM Systems Fail? finds that 44.2% of multi-agent failures come from system design (loops, lost state, missing termination), 32.3% from inter-agent misalignment, and 23.5% from superficial verification. Our design targets each category directly. A deterministic scheduler handles termination. Frozen contracts prevent misalignment, since agents cannot silently drift on shared definitions. The proof checker replaces any LLM judge.

The third group constrains the design. Single-agent or Multi-agent Systems? Why Not Both? shows that multi-agent systems cost 4x to 220x more prefill tokens and lose to single agents on easy tasks. That forces matched-budget comparisons and an explicit test of where decomposition stops helping. An Empirical Study on the Correctness of Formally Verified Distributed Systems found all 16 bugs in IronFleet, Verdi, and Chapar outside the verified core, in the unverified "shim" code that handles parsing, operating-system calls, and networking. A proof pipeline therefore does not deliver a correct deployed system, and we claim nothing about the shim. Compositional Synthesis of Modular Systems decomposes a global temporal-logic specification into per-process assume-guarantee certificates. Our frozen contracts follow the same idea, but we take them from an existing refinement proof rather than synthesizing them, and the processes being decomposed are proof obligations, not system components.

Research Program

Benchmark. We first build IronBench, following DafnyBench's proof-stripping recipe, from IronFleet's IronRSL (a Paxos-based replicated state machine) and IronKV (a sharded key-value store). We produce three difficulty tiers. The first strips only loop invariants and assertions, the DafnyBench-style task. The second strips the bodies of protocol-layer invariant lemmas. The third strips the bodies of refinement and reduction lemmas between the implementation and protocol layers. Specifications and lemma statements stay fixed in every tier, and the diff checker rejects any change to them.

IronFleet is public, so contamination is a serious threat. We address it three ways. First, we test memorization directly by asking each model to reproduce held-out lemma bodies verbatim. Second, we rename identifiers and reorder files. Third, and most important, we write modified protocol variants by hand. Examples include IronKV with a changed key-delegation rule and IronRSL with a different leader-election timeout condition. For these variants we re-derive the lemma statements but have no reference proofs, so their proofs cannot have been memorized.

System. The system parses the Dafny project into a dependency graph of lemmas. Each stripped lemma becomes a task. A task is runnable when every lemma it calls is either verified or admitted as a frozen contract, with its statement fixed and its body temporarily assumed.

The scheduler is written as rules in the style of Toward Common Patterns for Distributed, Concurrent, Fault-Tolerant Code, meaning predicates on shared state that trigger actions. Example rules are "lemma failing and attempts under the limit, so dispatch a worker," "lemma verified, so promote it and wake its dependents," and "worker reports the contract is unprovable, so file a change request." Control passes only between rules, so a crashed or stalled worker simply leaves its task runnable for the next dispatch.

Workers are AxDafny-style proposer-reviewer loops confined to one lemma and its contracts. A worker that believes a contract is false or too weak cannot edit it. It must file a change request. The scheduler then routes the request to a worker on the parent lemma and invalidates everything that depended on the old statement. This is the mechanism meant to prevent the misalignment failures documented by the multi-agent failure study.

Analysis. Beyond success rates, we record where proofs fail by tier, how often change requests are filed and accepted, how much work is wasted through invalidations, and how token cost scales with the number of obligations.

Baselines

The naive reference point is single-shot generation. A frontier model receives the full stripped project in long context and produces all proofs at once. This is the analogue of the 11.6% single-shot baseline that DafnyProver reports on LCB-Pro-Dafny. It establishes how much of IronBench is trivially recoverable, including through memorization.

The strongest existing competitor is AxDafny itself, run on the whole project as one unit with its proposer, reviewer, and memory module intact. It reports 92.7% on DafnyBench and 56.4% on LCB-Pro-Dafny (DafnyProver). We found no reported result on Lacuna for any LLM prover on IronFleet or any other distributed-protocol proof benchmark, so we must measure all IronBench numbers ourselves. AxDafny is the strongest competitor because it already has everything except decomposition: verifier feedback, counterexamples, and memory. We also run DafnyPro (86% on DafnyBench with Claude 3.5 Sonnet, DafnyPro) with its hint augmentation.

We also include a role-based team in the style of Self-collaboration Code Generation via ChatGPT, with analyst, prover, and tester agents but no obligation decomposition. It tests whether any multi-agent split helps.

Two ablations isolate the key ingredient. The first is a single agent that walks the same dependency graph sequentially, with the same contracts and scheduler but one context and one worker. It separates obligation decomposition from parallel agents. The second removes contract freezing, so workers may edit shared lemma statements subject only to the diff checker on the top-level specification. It measures what frozen contracts buy.

Fair comparison means the same base model, the same Dafny version and verifier timeouts, and the same total token budget. We report full success-versus-tokens curves rather than single operating points, with three seeds per configuration. Our method beats the competition if it proves a significantly larger fraction of tier-two and tier-three obligations than AxDafny across the budget range, on the unseen protocol variants as well as on the originals.

Why not just…?

Why not just use one frontier model with a long context? This is the main threat on tier one. Single-agent or Multi-agent Systems? Why Not Both? shows the multi-agent advantage shrinking as models get stronger. In the setting closest to ours, though, single ReAct agents found zero protocol bugs where Agora's team found 15 (Agora). Our prediction is that long context matches us on tier one and on DafnyBench but falls behind on refinement lemmas, where the relevant facts are spread across layers. The single-shot and AxDafny baselines measure this directly. If they match us on tier three, the claim is wrong.

Why not just cascade: run a cheap single agent first and escalate only on failure? Cascades cut cost by up to 88.1% in Single-agent or Multi-agent Systems? Why Not Both?, and here the verifier gives a perfect escalation signal, so a cascade is a strong option. We run one: AxDafny on the whole project, escalating each still-failing lemma to our decomposed system. We expect this hybrid to be the best cost-accuracy point in practice. The scientific question is whether escalation helps at all, which it can only do if the decomposed system solves lemmas the whole-project loop cannot.

Why not just fix the orchestration bugs: add termination authority and a verification step? The multi-agent failure study reports +9.4% from giving ChatDev's CEO agent final termination authority and +15.6% from adding an objective verification step (Why Do Multi-Agent LLM Systems Fail?). Our system already includes both fixes, in a stronger form: rules decide termination, and the proof checker is the verifier. What those patches lack is a guard against agents disagreeing about shared definitions. The contract-freezing ablation tests whether that guard matters.

Why not just write unverified Go and fuzz it with a model-guided fuzzer? Model-Guided Fuzzing of Distributed Systems explores more abstract states than random or reinforcement-learning testing and found 12 new bugs. But fuzzing finds bugs and cannot certify their absence, so the two approaches answer different questions. We run a small check anyway. We seed protocol bugs into the IronKV variants and confirm that our pipeline refuses to verify them, then compare against what model-guided fuzzing catches. We expect the two to be complementary rather than competing, and fuzzing remains the right tool for the shim layer.

Proposed Experiments

The decisive experiment is success versus tokens on tiers two and three of IronBench's unseen protocol variants. We compare our system, AxDafny, the cascade, and the sequential-single-agent ablation, all on one base model, then replicate the key comparison on a second model family. There are three distinct outcomes. If decomposition beats AxDafny and the sequential ablation matches it, then obligation decomposition is the active ingredient and parallel agents are a throughput detail. If our system beats both, separate contexts matter. If neither beats AxDafny, the bottleneck in distributed proofs lies elsewhere, most likely in the reduction arguments themselves, and the per-lemma failure analysis should show where.

A second check runs everything on DafnyBench and LCB-Pro-Dafny. The prediction is no gain, or a small loss from overhead, which would confirm that decomposition helps only when the proof graph is large.

A third check measures the scaling trend. We compare IronKV against the larger IronRSL and against variants with more stripped lemmas, testing whether our margin over AxDafny grows with obligation count.

Finally, we report memorization-probe results alongside every IronBench number. Any gain that appears only on the public originals and not on the hand-written variants will be treated as contamination, not capability.