Tamarin-based formal verification of security protocols requires expert-authored multiset rewriting rules and temporal-logic lemmas. Translating a natural-language protocol description into a complete formal model with an LLM is hard because syntactic, reachability, and property-level errors compound across the multi-step modeling process, and a single agent that both authors and self-evaluates cannot reliably localize them. We present MASTA, a multi-agent system that addresses these difficulties through three innovations. First, an operational--evaluative role decomposition assigns rule modeling to an Architect, property modeling to an Auditor, and pure dispatch to a dedicated Arbiter that holds no authoring duties. Second, the Arbiter implements a Tamarin-anchored scheduler that dispatches the next agent based on the latest verifier verdict and routes problem-tagged fixes through a modification list, with a six-class problem taxonomy and an LLM deduplication check preventing routing deadlock. Third, we construct a benchmark of 10 protocols paired with 139 mutation variants and five fine-grained metrics that jointly assess model correctness (M1--M3) and completeness (M4--M5). On this benchmark, MASTA on Qwen 3.5-plus improves over OpenCode on the same backbone by up to +0.27 on individual metrics and ranks first on both the correctness and completeness averages, surpassing Codex (GPT-5.5) and Claude Code (Opus 4.7) despite using a weaker LLM. Ablations on five protocols confirm that removing the Arbiter collapses property and verification scores to zero.
Figures & tables
Figure 1: Architectural overview of Masta : three agents (Architect, Auditor, Arbiter) sharing file I/O and Tamarin invocation; four operational jobs (J1–J4) and one continuous scheduling job (J5); the Arbiter dispatches the next agent based on the latest Tamarin verdict, including fix-job routing, under a one-hour per-protocol budget.
Job
Owner
Input
Output
J1 Action serialization
Architect
Protocol document
Structured action blocks
J2 Security-requirement extraction
Auditor
Protocol document
Structured security requirements
J3 Rule modeling
Architect
Action blocks
Tamarin rules + exec. verdicts
J4 Property modeling
Auditor
Security requirements
Tamarin lemmas + lemma verdicts
J5 Workflow scheduling
Arbiter
State + verdicts
Dispatch instruction
Table 1: The five jobs of Masta . J1–J4 are operational jobs that produce formal models; J5 is a continuous scheduling job whose only output is a dispatch instruction.
System
LLM
M1
M2
M3
Avg(Corr)
M4
M5
Avg(Comp)
Codex
GPT-5.5
0.615
0.586
0.534
0.578
0.757
0.961
0.859
Claude Code
Opus 4.7
0.724
0.643
0.594
0.654
0.758
0.753
0.756
OpenCode
Qwen 3.5-plus
0.762
0.430
0.526
0.573
0.668
0.866
0.767
Masta (Ours)
Qwen 3.5-plus
0.829
0.699
0.567
0.698
0.745
1.000
0.873
Table 2: Main comparison on the 10-protocol evaluation set ( n=10 protocols). Avg(Corr) and Avg(Comp) are the means of M1 – M3 and M4 – M5 , respectively. Bold entries indicate the best value per column.
Figure 2: Per-protocol M1 – M5 heatmap for the four systems of Table 2 . Rows are the 10 benchmark protocols (sorted by id), columns are the five metrics, and cells give per-protocol scores.
Variant
M1
M2
M3
Avg(Corr)
M4
M5
Avg(Comp)
Masta (Ours)
0.898
0.553
0.363
0.605
0.811
1.000
0.905
w/o Role Specialization
0.580
0.339
0.167
0.362
0.511
0.571
0.541
w/o Arbiter
0.358
0.000
0.000
0.119
0.321
0.000
0.161
Table 3: Ablation results on n=5 protocols. Differences should be read as descriptive rather than confirmatory given the small scope.
System
Tamarin calls
Wall-clock time
API tokens
Masta
1,567
52.3 h
111.1 M
Codex
863
8.7 h
81.5 M
Claude Code
966
55.4 h
184.0 M
OpenCode
3,728
39.6 h
424.5 M
Table 4: Cost of each system (Tamarin calls, wall-clock time, and API tokens from session logs).
Appendix figures & tables4 assets
Supplementary material from the paper’s appendix.
Appendix
Type
Semantics
Receive
Receive a message from the network; bind its subterms to local variables.
GenerateNonces
Sample fresh random values (nonces, session keys).
Compute
Apply cryptographic functions (encryption, hash, signature, MAC, DH exponentiation) to produce new terms.
Assertion
Check a condition on local state (e.g., signature verification, equality test); abort the block if the check fails.
Send
Transmit a term over the network (or ⟨\textscEnd⟩ if no message is sent).
Appendix
Table 5: The five operation types inside an action block.
Backbone
M1
M2
M3
Avg(Corr)
M4
M5
Avg(Comp)
Sonnet 4.6
0.816
0.703
0.723
0.747
0.839
1.000
0.920
Qwen 3.5-plus
0.967
0.643
0.604
0.738
0.956
1.000
0.978
Appendix
Table 6: Masta with two backbones on the same 20-task subset.
SAPIC [ 14 ]
AutoSM [ 20 ]
Masta
Input
applied-pi process written by the user
natural-language document
natural-language document
Modeling
done by the user; SAPIC only translates it
generated, with user interaction in the Repairer stage
generated, no human involvement
Repair signal
not applicable
static analysis and user interaction
Tamarin verdicts
Security properties
supplied by the user
taken from the reference model
generated, then verified
Evaluation
not applicable
18 protocols; a model is correct when the properties verified on the reference still hold on it
149 tasks; 5 metrics covering process structure, properties, verdicts, and mutation completeness
Appendix
Table 7: Qualitative comparison of Masta with SAPIC and AutoSM.
Multi-Agent Systems (MAS) built on Large Language Models (LLMs) often exhibit high variance in their reasoning trajectories. Process verification, which evaluates intermediate steps in trajectories, has shown promise in general reasoning settings, and has been suggested as a potential tool for guiding coordination of MAS; however, its actual effectiveness in MAS remains unclear. To fill this gap, we present MAS-ProVe, a systematic empirical study of process verification for multi-agent systems (MAS). Our study spans three verification paradigms (LLM-as-a-Judge, reward models, and process reward models), evaluated across two levels of verification granularity (agent-level and iteration-level). We further examine five representative verifiers and four context management strategies, and conduct experiments over six diverse MAS frameworks on multiple reasoning benchmarks. We find that process-level verification does not consistently improve performance and frequently exhibits high variance, highlighting the difficulty of reliably evaluating partial multi-agent trajectories. Among the methods studied, LLM-as-a-Judge generally outperforms reward-based approaches, with trained judges surpassing general-purpose LLMs. We further observe a small performance gap between LLMs acting as judges and as single agents, and identify a context-length-performance trade-off in verification. Overall, our results suggest that effective and robust process verification for MAS remains an open challenge, requiring further advances beyond current paradigms. Code is available at https://github.com/Wang-ML-Lab/MAS-ProVe.
We present TraceFix, a verification-first pipeline for Large Language Model (LLM) multi-agent coordination. An agent synthesizes a protocol topology as a structured intermediate representation (IR) from a task description, generates PlusCal coordination logic, and iteratively repairs the protocol using counterexamples from the TLA+ model checker (TLC) until verification succeeds. Verified process bodies are compiled into per-agent system prompts and executed under a runtime monitor that rejects out-of-topology coordination operations. On 48 tasks spanning 16 scenario families, all tasks reach full TLC verification; 62.5% pass on the first attempt and none requires more than four repair iterations. State spaces span six orders of magnitude yet verification completes in under 60 s for every task. A 3,456-run runtime comparison shows that topology-monitored execution achieves the highest task completion (89.4% average, 81.5% full) and that runtimes using the verified protocol degrade at roughly half the rate of prompt-only and chat-only baselines when model capability is reduced. A paired ablation under a fixed runtime shows that TLC-verified protocols cut deadlock/livelock (DL/LL) from 31.1% to 14.1%, with the largest separation under fault injection.
Large-language-model multi-agent systems (LLM-MAS) introduce a characteristic reliability problem: an error produced by one agent can be accepted as context by downstream agents and propagate across the workflow. Many proposed safeguards rely on learned or LLM-based judges whose verdicts are themselves probabilistic; we ask whether a deterministic layer can instead stop contract-detectable handoff defects. We present Maat, a runtime governance layer that validates agent-to-agent handoffs against a versioned workflow contract, or anchor, with no language model in the validation or scoring path. We evaluate it in six controlled domain workflows (6-15 agents, 522 trials) with injected data-level defects and a deterministic seven-check rubric. Version 1 reported gains in all six workflows (2.9-26.5%). A post-publication audit found that three benchmark scorers credited any early halt as a prevented defect. On paired trials where the governed run completed or halted on a finding attributable to a verified defect, the rubric score changes by +7.7% to +29.1% in five workflows and is flat in software development; model-call cost falls 17-53% where attributable halts occur early. A hand review of all 94 governed-arm halts found 35 false alarms (37%), caused by validator defects rather than model behaviour; counting those halts as failed work, the governed arm scores below the ungoverned arm in four of six workflows. The results support deterministic handoff validation for contract-expressible defects and show that validator configuration and halt attribution must themselves be tested; they do not establish universal correctness, hallucination detection, or model-independent effectiveness.