- Rating
- 2(+1)
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper proposes a certify-then-act protocol for cooperative LLM agents in stochastic environments. Agents negotiate a finite sequence of joint actions, obtain a probabilistic safety certificate from a model checker, and execute the contract through an enforcement layer. Following a disruption, they negotiate and certify a replacement contract. The evaluation covers a few scenarios and models, with additional experiments on heterogeneous teams, larger budgets and increasing agent counts. The main finding is that enforced certification substantially reduces unsafe terminations, while increasing timeouts under a fixed budget.
Critical strengths
Separating LLM planning from formal verification and runtime enforcement provides a clear way to constrain unreliable action proposals. Joint contracts address interactions that individual agents cannot assess independently.
Comparing absent, optional and enforced verification helps distinguish access to a verifier from an obligation to respect its verdict. The homogeneous study covers a large number of episodes, and the heterogeneous experiments broaden the evaluation beyond identical agents.
Distinguishing unsafe failures from timeouts is valuable and honest. The budget ablation also provides evidence that some completion losses can be recovered by allowing more resources. The authors explicitly acknowledge the assumptions of an accurate environment model, perfect information and cooperative agents.
Critical weaknesses
My main concern is the scalability of the approach. The main evaluation uses six small scenarios with hand-built models. This is reasonable for an initial study, but it leaves substantial uncertainty about larger, more complex problems and time-sensitive operation. Moreover, increasing the number of agents also increases the number of available grippers, which can make task execution easier. The experiment needs to separate additional execution capacity from increasing problem complexity and verification costs.
Related to the above, when dealing with large and complex problems, how to abstract the problem into a manageable model and how to ensure that the abstraction is faithful and useful are critical problems that this paper does not seem to address.
Probabilistic shielding and multi-agent shielding already establish closely related methods for constraining actions using formal models (previous work cited by the paper). The main methodological contribution appears to be integrating these ideas with LLM-negotiated joint contracts. The experiments compare verification regimes within the proposed harness, without establishing the advantage of contracts over a simpler enforced shield.
The paper often correctly limits its guarantee to the duration of a bound contract. Repeatedly accepting contracts with violation probability does not, however, imply an episode-level violation probability. For example, ten segments with independent failure probabilities of 0.05 would produce an overall failure probability of approximately 0.40. CTSR establishes that executed actions were certified; its definition alone does not establish a single risk bound for the complete episode. The paper should state the resulting guarantee across successive contracts and distinguish this explicitly from certification coverage.
Each model–domain–mode cell contains only 15 episodes, drawn from three scenarios. The large reduction in unsafe outcomes is persuasive within the benchmark, but the precise model ordering and heterogeneous-team advantages are less secure.
Questions for authors
What guarantee holds over an entire episode containing multiple certified contracts? Is there an episode-level risk budget?
Does the checked Markov chain include the actual disruption-triggered cancellation and waiting behaviour?
How does multi-step contract certification compare with enforced one-step joint-action certification in safety, completion and verification cost?
What are the model sizes and verification latencies, and how do these change with contract horizon and agent count? How do the proposed method scale to large and complex models and problems?
In the six-agent experiment, how much of the observed performance comes from additional grippers rather than scalable coordination?
6 comments
Separating execution capacity from coordination cost in the multi-agent experiment
Separating execution capacity from coordination cost in the multi-agent experiment - Response to R3 (mAoA) We thank the reviewer for raising this issue. We agree that for , additional agents add both execution capacity and coordination burden, so the improvement in TSR and CTSR from to cannot be attributed to scalable coordination alone. However, the 4_rotate task was designed so that the and settings separate the two effects (Appendix C). Only four legal moves exist at the first step, and the task has a deterministic optimum of 4 joint steps for every . Agents beyond the fourth therefore cannot contribute any parallelism: they can only wait or contend for blocks other agents need. Going from to thus holds useful execution capacity fixed while increasing the number of agents that must negotiate, agree on a byte-identical -wide contract, and be covered by each certificate. This isolates coordination and verification overhead.
In this range, adding agents provides no benefit, and the cost of coordination is visible:
- Under enforced certification, GLM 5.2 maintains a CTSR of 1.0 at and , while DeepSeek V4 Flash drops from 1.0 to 0.8 (Figure 6).
- Game steps do not fall further beyond , while model turns continue to rise (Figure 7), and total input tokens grow from ~2.2M at to ~6.6M at (Appendix C.1).
- Under optional certification, DeepSeek V4 Flash's TSR falls as increases beyond 3, because uncoordinated agents act before a contract is agreed (Appendix C).
So the protocol's safety and success hold up once extra agents stop adding capacity, and the overhead of more agents appears in inference cost rather than in unsafe outcomes. We note that each point is computed over five episodes, so the drop from 1.0 to 0.8 corresponds to a single episode; we read these results as evidence that certified success does not collapse with additional agents.
Does the checked Markov chain include cancellation and waiting?
Does the checked Markov chain include cancellation and waiting? - Response to R3 (mAoA) No. The checker verifies the chain induced by executing the full contract (Definition 5). This is sound: release on disruption only truncates the contract, and a prefix's violation probability is at most that of the full contract. After a release, agents wait until a new certified contract is bound, and wait is deterministic and never disrupted. Without communication, agents still executing their own contracts were certified against any behavior of the others, including waiting. The per-contract and episode-level bounds therefore cover cancellation and waiting.
Verification latency
Verification latency - Response to R3 (mAoA) We agree that the cost of verification is important for assessing practicality, and we will run a controlled scalability study of our verifier and share the results in a follow-up post. This study will use the same Storm-based model checker that the agents call at run time. Each candidate joint contract will be compiled into a discrete-time Markov chain that captures the stochastic wind dynamics and the other agents' moves, and Storm will compute the probability of an obstacle hit or collision within the contract horizon. We will time this check on randomly generated grid worlds with 15% obstacle density, varying (i) grid size from 5×5 to 30×30, (ii) contract length from 4 to 20 steps, and (iii) the number of agents. For each setting we will check randomly sampled contracts across several seeds and report median wall-clock time, along with the size of the generated model and a breakdown into model construction and model checking. Because Storm uses sparse representations, we will report latency and model size separately, without assuming one predicts the other. We will also time the checks on our benchmark scenarios at their actual horizons, so that the results can be read directly against the settings used in our experiments. We will include the full results as tables in a follow-up post and in the final version of the paper.