- Rating
- 3
- Confidence
- 2
- Informativeness
- 3
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
This paper studies a failure mode in multi-agent systems where agents are safe in isolation but unsafe after composition. The authors use Petri nets to model shared state and agent interactions. They define regenerative dissipative interaction cycles and give a depletion bound. They also propose a linear-program screen for such cycles and a matrix-based test for whether local certificates remain valid after composition. The paper validates the analysis on a cloud example, AppWorld, and MAST.
Critical strengths
The paper studies an important problem. As AI agents increasingly act on shared environments, local guarantees may not remain valid after composition. I think this problem is valuable and deserves more attention.
Critical weaknesses
The empirical validation is somewhat limited in breadth. AppWorld provides the main direct validation of the proposed analysis. The MAST study gives useful independent evidence about multi-agent failures, but it does not directly test the main screening and certificate-preservation methods. As a result, I would like to see stronger evidence that the proposed analysis applies beyond the AppWorld setting.
Questions for authors
None
4 comments
Response to QYFg (follow-up): the census repeated on τ-bench (new Appendix Q) — the exclusive-access assumption recurs, executed collisions are rare
Our reply said that no second benchmark had been run. We have now repeated the census (E4) on τ-bench, using its retail and airline test splits: 165 tasks and 15,560 ordered pairs. It is Appendix Q of the revised PDF, uploaded today. Each task's gold actions are replayed with τ-bench's own tool code. No model is called, and nothing is sampled. Every pair was also re-run on a full copy of the database and judged by τ-bench's own hash, with no disagreement.
τ-bench's certificate. τ-bench's evaluator hashes the entire database and compares it with the state the gold actions produce (calculate_reward in envs/base.py). That is a stricter certificate than AppWorld's declared models. It survives another task's correct run in 14.5% of pairs (retail 9.7%, airline 40.2%). In all but 24 of those pairs the other task writes nothing, so this number mostly restates the evaluator's design and is not independent evidence. It does show that the exclusive-access assumption is built into a second benchmark's scoring.
The paper's declared-set test. At record level it keeps 15.1% of pairs (AppWorld: 21.0% declared, 14.8% floor). At table level it keeps 73.7%, because τ-bench has only three tables. The comparison with AppWorld therefore depends on granularity, and Table Q20 reports both.
Executed collisions are rare. In 98.8% of pairs, the second task's gold actions still succeed and leave its records as they would alone. The 190 pairs that do not fall into two groups:
- 150 are same-customer pairs. In most of them the first task has already moved an order out of the status, pending or delivered, that the second task's write requires. Two deplete a shared travel certificate.
- 40 come from
book_reservation's fixed reservation IDs, which assume one task per database.
So τ-bench corroborates that benchmarks assume exclusive access, not that agents often collide. Over all 635 retail tasks, the census's figure falls to 2.7%, because only 2.7% of those tasks are read-only. The code and full results are in the supplement (tau_census/).
Thank you for the thoughtful responses and additional experiments. I appreciate the new τ-bench analysis and the clearer scope of the empirical claims. While the direct validation of the core methods remains primarily within AppWorld, these revisions are helpful. My overall assessment remains positive, and I will maintain my original rating.
Response to QYFg: thank you
Thank you for reading our responses and the new analyses, and for your continued support of the paper. We agree with your reading: beyond the formal examples, the screen and the certificate test are validated directly only on AppWorld, and the τ-bench analysis repeats only the census. The Limitations paragraph of the revised PDF states this (p. 10, l. 535–536). We are grateful for your engagement throughout the discussion.
Response to QYFg: agreed — no second benchmark was run; we narrowed the claims (MAST checks only the premise) and added LLM-agent evidence within AppWorld
Thank you for recognizing the importance of the problem, and for naming the weakness precisely. It is the one concern we cannot fully resolve in this revision. ("p. N, l. M" is the revised PDF, "l. M" the submitted version.)
W1. The empirical validation is somewhat limited in breadth. AppWorld provides the main direct validation of the proposed analysis. The MAST study gives useful independent evidence about multi-agent failures, but it does not directly test the main screening and certificate-preservation methods. As a result, I would like to see stronger evidence that the proposed analysis applies beyond the AppWorld setting.
A. We agree, and we did not close this gap: no other benchmark was run for this revision. Instead we narrowed what the paper claims and added evidence inside AppWorld. Three things changed.
MAST no longer counts as validation. The submission counted it as such (contribution (vi), l. 085–089; §5, l. 355–358). Contribution (vi) and §5's opening now say that MAST checks only the premise (p. 2, l. 091–092; p. 7, l. 357–358). E7 says that it tests neither method, and that its labels are MAST's LLM judge's (p. 9, l. 463–468). Table L5's caption says that no net is built (p. 39, l. 2075–2077).
The scope is now stated. §5 says that we check the theory on our own nets (E1 to E3) and test the methods on AppWorld (E4 to E6) (p. 7, l. 355–358). The Limitations say that beyond the nets of §3 both methods are tested only on AppWorld (p. 10, l. 535). The four compositions of App E are constructions, not incident reports (p. 23, l. 1230–1231).
More evidence on the same benchmark, not beyond it. E6b adds 40 task pairs with a language model as the second agent, against predictions frozen before the core run. The gold pairs run the same 40 pairs with no model. The general comment, part 2, gives the design. Figures are Haiku run 1, Haiku run 2, Sonnet.
E6b's reach is narrow, and the paper says so. It is one benchmark, 40 pairs, and two models of one provider at one effort. Its A is gold, which removes A's own error. And B runs only after A, so interleaved schedules are untested (p. 55, l. 2931–2937).
Two corrections and one withdrawal also bear on soundness. New Lemma 1 states what the screen does and does not guarantee. Proposition 5 was false as stated and is corrected. And we withdraw the census row "against realized writes" (5.7%).
We appreciate your encouraging assessment of the problem, and we would be glad to clarify anything further.