acceptodds
Under review as a conference paper at ICLR 2027

Locally Safe, Globally Unsafe: Composition-Induced Failure in Networked AI Agents

Abstract

Autonomous agents are increasingly certified one at a time and then deployed in groups onto shared infrastructure. We show that this practice certifies almost nothing. Our running case is an autonomous cloud whose deployment, reliability and capacity agents each satisfy their own specification and which, composed, take the service down with no agent making a bad decision. The mechanism is a regenerative dissipative interaction cycle: a loop that rebuilds its own trigger while consuming a shared resource. In a Petri-net formulation we prove a depletion bound and show it is attained, that screening for such a cycle is a linear program rather than a search over markings, that one matrix product per agent pair decides whether a local certificate survives composition, and that a cycle consuming nothing leaves the probability of failure exactly unchanged while inflating the time to it by up to 2 in the running example. The evidence comes from artifacts built by other people. AppWorld's authors wrote, for each of 486 tasks, an assertion naming which database models a correct run may change; read as local certificates, only 21.0% of 235,710 ordered task pairs survive composition, falling to 5.7% once twenty undocumented cross-app effects are counted. Two task executors sharing one live AppWorld account then take the benchmark's own score from 24/24 to 6/24, and cutting exactly the fusions our test flags restores it where the intuitive repair does not. Benchmarks that score one agent at a time cannot certify behavior in a world that agent shares.

Primary area:
alignment, fairness, safety, privacy, and societal considerations
Keywords:
agentic AI, multi-agent systems, compositional safety, Petri nets, formal verification, emergent behavior, AI safety

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_QYFgOpenReview ↗
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
AuthorsOpenReview ↗

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.

  • Alone, the model completed its own footprint in 33, 32, 37 of 40 pairs.
  • In the 20 pairs where Theorem 3's test says AA's certificate survives, AA's footprint clause failed in none, in every configuration. With no failure, the exact one-sided 95% upper bound is 0.139 for independent pairs, 0.162 over 17 AA families and 0.283 over 9 family clusters.
  • One of our own predictions was falsified there. In the inside stratum, BB's declared set is non-empty and inside AA's. There AA's task failed in every pair in which BB wrote, 9 of the 10 in each run, on content the certificate does not cover.

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 AA is gold, which removes AA's own error. And BB runs only after AA, 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.

AuthorsOpenReview ↗

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.

AuthorsOpenReview ↗

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.

Reviewer_PnFyOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

This paper uses Petri nets to study failures caused by composing individually safe AI agents. It proposes interaction-cycle definitions, a linear-programming screen, and an interference test for shared-state systems. The experiments analyze synthetic nets, AppWorld artifacts, and MAST traces.

Critical strengths
  1. The paper gives a clear formal example showing that local safety does not guarantee global safety.
  2. The Petri-net formulation and exact synthetic experiments are relatively systematic and reproducible.
Critical weaknesses
  1. The main empirical claims are not demonstrated on actual LLM agents. The AppWorld analysis is mostly offline, and the main multi-agent experiment uses scripted executors, so the practical relevance to AI-agent behavior is limited.
  2. The proposed linear-programming screen is not a complete safety detector. Its conclusions require additional reachability and executability assumptions, so the paper’s practical guarantees are substantially narrower than its presentation suggests.
Questions for authors
  1. Is the linear-programming screen complete, or does it only generate candidate cycles?
  2. How are the reachability assumptions in Theorem 1 checked in practice?
  3. Why should independently defined AppWorld tasks be treated as simultaneously interacting agents?
  4. Why are no experiments with actual LLM-driven agents included?
  5. How sensitive are the AppWorld results to the manually constructed API-effect library?
5 comments
AuthorsOpenReview ↗

Response to PnFy (1/2): E6b now runs language-model agents; the screen's guarantees are narrowed in the paper itself

Thank you for the precise questions, for separating what the screen proves from how we presented it, and for finding the formal example clear and the synthetic experiments reproducible. ("p. N, l. M" is the revised PDF, "l. M" the submitted version.)

W1 & Q4. The main empirical claims are not demonstrated on actual LLM agents. The AppWorld analysis is mostly offline, and the main multi-agent experiment uses scripted executors, so the practical relevance to AI-agent behavior is limited. Why are no experiments with actual LLM-driven agents included?

A. You are right about the submission. E4 and E5 only read AppWorld's evaluators and its released trajectories, and E6's agent BB was a fixed purchase script, not a second task.

The revision runs E6b on 40 AppWorld task pairs, with Claude Haiku 5.5 (two runs) and Claude Sonnet 5.5 (one run) as BB. The predictions were frozen before the core run. The general comment, part 2, gives the design. Figures below are Haiku run 1, Haiku run 2, Sonnet.

  • BB is an active agent: alone in AA's world it completes its own footprint in 33, 32, 37 of 40 pairs.
  • Where Theorem 3's test says AA's certificate survives (Jij=0J_{ij}=0), AA's footprint clause failed after BB in none of the 20 pairs, in every configuration. With no failure, the exact one-sided 95% upper bound is 0.139 for independent pairs, 0.162 over 17 AA families and 0.283 over 9 family clusters.
  • Where it says the certificate may not survive (Jij≠0J_{ij}\ne0), BB wrote outside AA's declared set in 14/20, 13/20, 16/19 pairs, and AA's footprint clause failed exactly then. The B-family bootstrap 95% intervals are [0.41, 0.95], [0.39, 0.89] and [0.63, 1.00].
  • Under the screen that clause held in every Jij≠0J_{ij}\ne0 pair, with no leak. But AA's task passed in only 17/20, 18/20, 16/19, and BB completed its own footprint in none.
  • One of our own predictions was falsified. In the inside stratum, BB's declared set is non-empty and inside AA's. There AA's task failed in every pair in which BB wrote, 9 of the 10 in each run, on content the certificate does not cover.

We used a gold AA because Haiku as AA passes alone in only 21 of 40 episodes. The price is that E6b says nothing about two fallible agents, beyond an underpowered subset of 15 pairs.

W2. The proposed linear-programming screen is not a complete safety detector. Its conclusions require additional reachability and executability assumptions, so the paper's practical guarantees are substantially narrower than its presentation suggests.

A. We agree, and we have changed the paper accordingly. The submission said that one matrix product per pair "decides" whether a certificate survives (abstract, l. 019–020), and that Prop. 5 "makes the relaxation exact" (l. 452–454). Both were too strong. The screen targets one hazard class, for a chosen interface II and resource vv, relative to the net. It is not a general safety detector: in the Venmo control, system (4) is feasible over an empty interface, and the verdict of contention there is Definition 2's (p. 8, l. 401–404). The revision states what the screen guarantees (§4.3, p. 6, l. 278–283) and what each result does not establish (App H, pp. 31–32, l. 1673–1698). The abstract now calls the certificate test "a sufficient test" and says that such certificates "need not compose", where it had said that the practice "certifies almost nothing" (p. 1, l. 013–031). Q1 and Q2, in part 2 of this reply, answer the two assumptions themselves.

AuthorsOpenReview ↗

Response to PnFy (2/2): the LP screen yields candidates and is exact only when infeasible; how Theorem 1's hypothesis is checked; why tasks are composed; sensitivity to the API-effect library

Q1. Is the linear-programming screen complete, or does it only generate candidate cycles?

A. It generates candidates, and it is exact in the other direction. New Lemma 1 fixes the interface places II, a resource V(M)=v⊤MV(M)=v^\top M with v≥0v\ge0 rational, and agents i≠ji\ne j. System (4) is then feasible if and only if some marking, reachable or not, admits a sequence that uses transitions of both agents, restores πI\pi_I and lowers VV. Infeasibility therefore rules such a cycle out at every reachable marking. A feasible yy is only a candidate. On the meltdown net, for ADA_D and ASA_S, App H shows a returned vector that no reachable marking executes, although that pair does have a genuine cycle (p. 31, l. 1623–1645). Proposition 5 was false as stated. Corrected, it certifies a 0/10/1 candidate whose support has unit arc weights and induces a simple circuit with one place marked and its other inputs marked and untouched (pp. 30–31, l. 1566–1572 and 1647–1656). Other candidates go to exact reachability.

Q2. How are the reachability assumptions in Theorem 1 checked in practice?

A. Hypothesis (i) is the one that involves reachability. New Lemma 2 gives a sufficient condition through Proposition 5. Checking it needs no enumeration when V≥Vmin⁡V\ge V_{\min} by itself keeps the circuit's other inputs marked, as it does for the meltdown net and for E2 (App H, p. 31, l. 1657–1671). Otherwise we settle the hazard by exact reachability, as we do for E1 (N=2N=2 to 1212) and for the AppWorld depletion nets (K=2K=2 to 1212; Table L2, p. 38, l. 1999–2021). The remarks after Theorem 1 now say this (p. 32, l. 1705–1713).

Q3. Why should independently defined AppWorld tasks be treated as simultaneously interacting agents?

A. They need not run at the same time, and the revision no longer reads as though they do. The census asks a counterfactual: would task ii's certificate still hold if task jj's correct run landed on the same account? So it measures how strongly the benchmark assumes exclusive access, not how often agents collide (p. 8, l. 391–394). Of its 186,165 failing pairs, 109,890 share no app at all, and such a pair survives only if jj writes nothing. E6b is the case where a language-model BB really does share AA's account, and there BB wrote outside DAD_A in 14/20, 13/20, 16/19 Jij≠0J_{ij}\ne0 pairs. In both E6 and E6b BB runs after AA, so interleaving is untested.

Q5. How sensitive are the AppWorld results to the manually constructed API-effect library?

A. Your concern applies fully to one row, which we withdraw. Three parts:

  • Results that use no library. The census's 21.0% is the declared-set test on the evaluators' own assertions (Table M8, p. 42, l. 2215–2248). E6 and E6b are scored by AppWorld's evaluator. In E6b we read BB's writes from its SQL statement log and from AppWorld's comparison of the final state. The two agreed on whether BB wrote outside DAD_A in every cell.
  • The row we withdraw. The 5.7% row realized each declared model by the first API, in a fixed app order, that writes it, which can be an API the task never calls. In its place we give the floor for runs that pass their own evaluators: 14.8% of pairs survive (21.2% with ignore lists) against 21.0% declared (22.6%). The floor assumes, as the census does, that a task writes the same models in another task's world (p. 8, l. 415–419; Fig. 2a, p. 7, l. 324–339). 5.7% lies below both floors, so it can arise only from writes the writing task's own evaluator would reject.
  • Where the library still matters. It sets the depletion nets, and which calls the screens refuse. E5 measures it on held-out trajectories: recall 0.93, precision 0.70 (Table L6, p. 40, l. 2107–2121). We did not run a perturbation analysis of the library.

Thank you again for questions that made the paper's claims more exact. We hope these answers are helpful, and we would be glad to clarify anything further.

AuthorsOpenReview ↗

Response to PnFy (follow-up): a perturbation analysis of the API-effect library at E5's measured error rates (new Appendix P)

In our reply to Q5 we said we had not run a perturbation analysis of the library. We have now run one, offline, using the paper's own code on AppWorld's data. It is Appendix P of the revised PDF, uploaded today.

Method. We drew 1,000 libraries at E5's measured rates (recall 0.93, precision 0.70; Table L6). In each draw, every write arc is dropped with probability 0.07, and each writing API gains spurious writes to other models of its app, at the rate that brings precision to 0.70. We then recomputed every library-dependent result. The census's 21.0% and the E6 and E6b scores use no library, so they cannot move. Before perturbation, the library reproduces the supplement's results exactly.

Results at E5's rates (Table P19):

  • The J=0J = 0 screen loses 5.9% of its refusals (3.5–8.8% in 95% of draws) and gains 2.4%. Precision errors only add refusals, so they cost completion, not safety. Recall errors remove refusals.
  • E6. place_order writes eight models outside DAD_A and stays refused in every draw. add_product_to_cart writes only the cart entry. It is still refused in 93.0% of draws, and is missed only when that one write is dropped.
  • The cart and Splitwise case studies (safe alone, deplete together, witness length as Corollary 1 predicts) are unchanged in 87.1% and 86.3% of draws. Every change traces to one of the two arcs each cycle runs on: the add and the remove of a cart entry, or of an expense share. With each arc kept with probability 0.93, the expected unchanged share is 0.93² = 0.865. A dropped add hides the depletion (6.9% and 7.1% of draws). A dropped remove lets the spending agent deplete alone, which errs on the safe side (6.0% and 6.6%).
  • Theorem 2's LP screen keeps its verdict and support in 93.1% (cart), 92.9% (Splitwise) and 100% (Venmo) of draws.
  • The Venmo negative control and the block test's direction never change.
  • At twice E5's error rates, the case studies are unchanged in about three draws out of four.

One error the case studies do not survive. Suppose a spurious write may also delete records. Then a cycle step that "deletes" a model the net starts without can never fire, the depletion disappears, and the cart case study survives in only 20.0% of draws. E5 compares sets of changed models, not verbs, so it cannot bound this error.

Caveats. We apply E5's per-trajectory rates per arc. We treat all of the precision shortfall as library error, although Table L6 attributes most of it to proposals the environment refused. We do not perturb the eight hand-written resource arcs, and every depletion result assumes them.

Read the other way: if the paper's library errs at E5's rates, its screen misses about 6% of the refusals it should make. Theorem 3's guarantee is conditional on the library and does not cover those, and the Limitations paragraph now points to Appendix P. The code and per-draw results are in the supplement (library_sensitivity/).

Reviewer_7ZBXOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

The paper makes a model based on Petri nets to argue that the individual safety of agents might not compose to agents in shared environments. Their theory is centered around cycles competing for the same resources and they demonstrate an LP for detecting these cycles. For empirics, they look at AppWorld and show that task correctness can breakdown on tasks composed in pairs.

Critical strengths

Individually safe agents composing to become potentially unsafe is a very big problem in safety and attempts to model and theoretically understand this problem are valuable.

Critical weaknesses

The theoretical work does not appear very novel, while acknowledged by the authors, the fact that the paper is mainly a theoretical model this is a big weakness. Also the experiments are not on real LLMs or agents which is a big limitation.

Questions for authors

What would you say is technically new?

Why wasn't the LLM experiment run?

3 comments
AuthorsOpenReview ↗

Response to 7ZBX: the LLM experiment is now run (E6b); what is technically new is the formulation and the measurement, not the mathematics

Thank you for your review, for stating your concerns directly, and for agreeing that the failure of individually safe agents under composition is a very big problem in safety. Your second question we can now answer with data. ("p. N, l. M" is the revised PDF, "l. M" the submitted version.)

W2 & Q2. "Also the experiments are not on real LLMs or agents which is a big limitation." "Why wasn't the LLM experiment run?"

A. You are right, and it was a real limitation of the submission. We should also be plain about E6: its agent BB was neither a language model nor an AppWorld task, but a fixed script that added a product to the cart and placed an order in AA's world after AA (§5, p. 8, l. 424–426).

The revision runs E6b (general comment, parts 2 and 3). AppWorld's gold solution is AA; a language model then does its own task in AA's world: Claude Haiku 5.5 (two runs) and Claude Sonnet 5.5 (one run), on 40 task pairs, with predictions frozen before the core run. Figures are Haiku run 1, Haiku run 2, Sonnet.

  • Alone in AA's world, BB completes its own footprint in 33, 32, 37 of 40 pairs. We used a gold AA because Haiku as AA passes alone in only 21 of 40 episodes.
  • Where Theorem 3's test says AA's certificate survives (Jij=0J_{ij}=0), it held after BB in every pair: 0/20 footprint failures each time (exact one-sided 95% upper bound 0.139 for independent pairs).
  • Where it says it may not (Jij≠0J_{ij}\ne0), BB wrote outside AA's declared set in 14/20, 13/20, 16/19 pairs, and AA's footprint clause failed exactly then.
  • The screen kept that clause in every Jij≠0J_{ij}\ne0 pair. But AA's task passed in only 17/20, 18/20, 16/19, and BB completed its own footprint in none.
  • Our own prediction that degradation stays confined to Jij≠0J_{ij}\ne0 pairs is falsified. In the inside stratum (BB's declared set non-empty and inside AA's), AA's task failed in every pair in which BB wrote, 9 of the 10 in each run, on content its certificate does not cover.

E6b's reach is narrow, and the paper says so: one benchmark, 40 pairs, two models of one provider at one effort, a gold AA, and BB only after AA, so interleaving is untested (p. 55, l. 2931–2937).

W1 & Q1. "The theoretical work does not appear very novel ..." "What would you say is technically new?"

A. Not the mathematics, and the revision says so: "No proof here needs a new technique". Place fusion and its modular analysis, the state equation, place invariants and structural analysis are classical, and Thm. 3 and Prop. 4 are a precondition-free form of the interference-freedom check for linear certificates (§6, p. 10, l. 487–497). What we claim as new is the formulation and the measurement.

  1. A hazard class, the regenerative dissipative interaction cycle: one cross-agent cycle that rebuilds its own trigger while spending a shared resource. It has a repetition bound that is attained (Thm. 1, Cor. 1), and a linear program whose infeasibility rules it out for a chosen interface and resource (Thm. 2, Lemma 1). A feasible answer is a candidate.
  2. An assumption nobody declares, that nothing replenishes an agent's trigger. We write it down as a monotone linear certificate. One matrix product per agent pair then says whether it still holds after composition. The meltdown needs this form (Prop. 4), because its certificate is not an equality.
  3. Reading a benchmark's per-task assertions as local certificates and composing them (E4), then checking the test's verdicts with the benchmark's own evaluator (E6, E6b). To our knowledge this reading is new (p. 10, l. 506–509).

On your summary, one phrase is worth correcting, and the wording is ours: §3 says "The two cycles compete for the same CPU mark" (l. 191). The hazard is not two cycles competing but one cycle across both agents that rebuilds its own trigger while spending a shared resource; two agents that each exhaust a resource alone are contention, which Definition 2 separates out (the Venmo control, p. 8, l. 401–404).

On soundness, the revision corrects four things: new Lemma 1 states what the screen does and does not guarantee; Proposition 5 was false as stated and is corrected; Theorem 4 carries its hypotheses wherever it is restated; and we withdraw the census row "against realized writes" (5.7%), with contribution (vi)'s 94.3%. On presentation, it states in words what the screen guarantees (§4.3, p. 6, l. 278–283), adds a table in App H of what each result establishes and what it does not (pp. 31–32, l. 1673–1698), rescopes the abstract and contributions, and closes the main text with a Limitations paragraph (§7, p. 10, l. 530–536).

We hope these answers are helpful, and we would be glad to clarify anything further.

I thank the authors for the rebuttal. Unfortunately my main concerns regarding the novelty and impact of the theoretical work remains.

AuthorsOpenReview ↗

Response to 7ZBX (follow-up): what the combination makes testable that no single piece could, and why we see it as a first step

Thank you for reading our response and for replying. Novelty is a judgment, and we will not repeat our earlier answer. But one point there came out too negatively. When we said the tools are classical, we did not mean that the contribution is small. What we claim is the combination: each piece supplies what the others lack, and together they make a question testable that none of them could test alone.

  • Compositional reasoning (assume-guarantee, interference freedom) can check that local guarantees survive composition, but only after each component's assumption about its environment has been written down. Agent benchmarks write none down (p. 9, l. 480–486).
  • Agent benchmarks already contain correctness assertions written by their authors (486 AppWorld tasks in our census). But they score one agent at a time, so these assertions say nothing about composition.
  • Petri nets turn an assertion such as "a correct run changes these database models and nothing else" into a linear certificate on shared state. One matrix product per agent pair (Thm. 3) then says whether another agent's run can break it.

Together they do four things that none of the pieces does alone:

  1. Check composition at scale, against assertions nobody wrote for composition. Across 235,710 ordered AppWorld task pairs, the declared footprints survive in only 21.0% (p. 8, l. 391).
  2. Prescribe a repair that is not the obvious one. After a scripted purchase in the same account, AppWorld's own evaluator scores agent A at 6/24 requirements. The intuitive repair, stopping B from writing A's models, gives 21/24; the cut Theorem 3 prescribes gives 24/24 (E6, three variants of one task; p. 8, l. 422–431, Table M9).
  3. Make a prediction that held with language-model agents. Where the test said A's certificate survives, it survived in every pair: 0/20 in each of three runs (exact one-sided 95% upper bound 0.139; E6b, p. 9, l. 445–447).
  4. Transfer without new theory. The same reading ran unchanged on τ-bench (new Appendix Q). Its evaluator hashes the whole database, so it too assumes exclusive access, although executed collisions there are rare (190 of 15,560 pairs).

Its reach is the clause the test checks, not every failure. In E6b, A's task still failed on content its certificate does not cover, in 9 of 10 inside pairs. That falsified our own prediction, and the paper says so (p. 9, l. 449–452).

We also see this work as a first step rather than a complete answer. Because the model is a Petri net, more of that toolkit can be brought to agent composition without new foundations, and the paper names the next steps (p. 41, l. 2194–2203): attributing composition-induced risk to individual interfaces, and learning the net from execution logs, which §5 already begins by recovering twenty couplings from AppWorld's recorded writes. Colored marks extend the same analysis from resources to shared beliefs and provenance, where a false-consensus loop is a regenerative cycle whose amplified quantity is epistemic (p. 35, l. 1865–1871).

We understand if you weigh the contribution differently, and we are grateful for your engagement.

Comments on the paper

3 comments
AuthorsOpenReview ↗

To all reviewers and the AC (1/3): the LLM-agent experiment (E6b) is now run; two corrections, one withdrawn result, and what stands

We thank the three reviewers for careful reviews, and for agreeing that the failure of individually safe agents under composition is an important problem that deserves attention (QYFg, 7ZBX). We also appreciate PnFy's note that the formal example clearly shows that local safety does not guarantee global safety, and that the synthetic experiments are systematic and reproducible.

Reviewers PnFy and 7ZBX asked why we had not run an experiment with real language-model agents, and Reviewer QYFg asked for evidence beyond our AppWorld analysis. We have now run that experiment, E6b. We report it here in three parts, because it is one experiment and it bears on all three reviews; each reviewer's own points are answered in their own thread.

Two things in the submission were wrong: we stated the guarantees too broadly, and one census row was not sound. We correct the first and withdraw the second. E6b then falsified one of our own predictions, which part 3 reports.

The rest stands. The depletion bound is unchanged, and so is the proof that it is attained. So is the screen, in the one direction in which it is exact. So is the census: read as local certificates, AppWorld's declared footprints survive composition in 21.0% of 235,710 ordered pairs. So is E6, where a scripted purchase takes AppWorld's own score for three task variants from 24/24 to 6/24, and cutting exactly the fusions our test flags restores it (p. 1, l. 019–030). And in E6b, every pair in which the test says AA's certificate survives kept it, in all 20 such pairs of every run.

Below, "p. N, l. M" is a place in the revised PDF and "l. M" alone a line of the submitted version. Revised text in the PDF is shown in blue. Blue cannot show a deletion, and the PDF does not list its changes, so the list below is the record. Nothing of the submitted version is renumbered.

1. Guarantees. The screen is exact in one direction only. By new Lemma 1, for a chosen interface and resource, infeasibility rules out a regenerative dissipative interaction cycle of the two agents at every reachable marking. A feasible answer is only a candidate. Proposition 5 was false as stated and is corrected, with new Lemma 2 (App H, pp. 30–31, l. 1566–1572 and 1623–1671). Theorem 4 carries its hypotheses wherever it is restated. Theorem 3's test is called sufficient, not one that "decides" (p. 1, l. 020–021; p. 2, l. 081). App H now tabulates what each result establishes and what it does not (pp. 31–32, l. 1673–1698). The reply to PnFy gives the detail.

2. Scope. The abstract and the contributions are rescoped, and a Limitations paragraph closes the main text (§7, p. 10, l. 530–536).

3. Two descriptions corrected. E6's agent BB was a fixed purchase script, run in AA's world after AA. It was not a second AppWorld task (p. 8, l. 421–428). MAST checks only the premise, and tests neither method (p. 9, l. 463–468).

4. A result withdrawn (p. 44, l. 2364–2367). We withdraw the census row "against realized writes" (5.7%; abstract l. 027, l. 404–405), contribution (vi)'s 94.3% (l. 085–089), and "three quarters of the pairs that looked compositionally safe are not". The twenty undocumented cross-app writes stand, as a gap in the documentation (Table L4, p. 39, l. 2053–2073).

5. New runs. The submission specified E6b and did not run it. The revision runs it, and runs the gold pairs as well. On language models, the three statements say this (p. 11, l. 540–569). The reproducibility statement says that in the experiments a language model is invoked only as an agent in E6b, never to score a run or compute a reported number, and that the harness, prompts, nets, transcripts and result files accompany the paper. The ethics statement says the runs call commercial models through their APIs as agents in AppWorld's simulated world, whose people, accounts and messages are synthetic.

AuthorsOpenReview ↗

To all reviewers and the AC (2/3): E6b's design — AppWorld's gold solution as agent A, a language model as agent B, four strata, predictions frozen before the core run

E6b runs E6's design with a language model as the second agent (§5, p. 9, l. 437–461; App O, pp. 48–55, l. 2580–2937).

On each of 40 AppWorld task pairs, AppWorld's gold solution runs as agent AA. A language model BB then does its own task in AA's world. BB is Claude Haiku 5.5 (two runs) or Claude Sonnet 5.5 (one run), at medium effort. Figures in this part and in part 3 are Haiku's run 1, Haiku's run 2, then Sonnet.

A gold AA removes AA's own error: Haiku as AA passes alone in only 21 of 40 episodes. The design the submission specified, Haiku as both agents, ran only on an underpowered subset of 15 pairs.

BB is an active agent. Alone in AA's world it completes its own footprint in 33, 32, 37 of 40 pairs, above the 30% line we had frozen (prediction P0).

AppWorld's evaluator scores two things separately: AA's footprint clause, the assertion E4 reads, and AA's content checks, its other requirements.

The sample. Four strata, ten pairs each:

stratumwhat AA and BB share
overlapJij≠0J_{ij}\ne0: a written model in common
disjointJij≠0J_{ij}\ne0: no app in common
read-onlyJij=0J_{ij}=0: BB declares no writes
insideJij=0J_{ij}=0: BB's declared set DBD_B is non-empty and lies inside AA's, DAD_A

Each pair runs four arms, one episode each:

  • AA alone,
  • unmediated: AA, then BB,
  • the same under the Jij=0J_{ij}=0 screen,
  • BB alone.

The pairs were drawn and gold-filtered before any model call. They are a third draw, with a complete footprint reader. The second draw used the census's reader, which misses 108 of the 147 train and dev footprints. We decided on the redraw after seeing the second draw's gold pairs, and the two draws agree on the headline. One secondary rate moved against the screen: under the Jij=0J_{ij}=0 screen, AA's task passed in 20/20 Jij≠0J_{ij}\ne0 pairs in the second draw and in 18/20 in the redraw (p. 49, l. 2592–2614).

Departures from the specification we submitted, each fixed before any core result (pp. 49–50, l. 2637–2687).

departurewhy
AA is the gold solutionso that the Jij=0J_{ij}=0 claim can be bounded
a fourth arm, BB aloneto measure BB's competence
each side of Jij=0J_{ij}=0 split in two strataoverlap and disjoint; read-only and inside
a reply without code is re-asked, at most twice a turnthe paper's harness ends the episode there; part 3 scores that rule too
16,000 output tokens, and every text block of a reply is readthinking counts toward the cap
a delivery check on every streamed replyit rebuilds the reply from its events and retries on a mismatch
the predictions were frozen, not postedsee the freeze below

The freeze (pp. 50–51, l. 2689–2706). We first froze the predictions at 21:04:21 UTC on 11 November 2026, after the gold pairs had run and before the first model call. We froze the protocol in its final form at 09:39:58 UTC on 12 November, before the competence runs. It has not changed since: sha256 b3c3f7885e5d247ec08caffafb9d19818ecfb27c5dcd6692a532a6e84e77167a. Its opening line still says to fix it before any language-model run and to post the predictions before launch, and neither is quite what we did. We revised it after test runs that called models on two of the 40 pairs, and no test episode is in a table. We amended it before the competence runs, when we decided to post nothing until this reply was complete. No version was revised after a core result. The freeze times rest on our run record, and nothing public timestamps them. The revised supplement contains the protocol file exactly as frozen, so that its sha256 can be checked, together with the E6b and census code, the prompts and the result files. The run rows and transcripts contain AppWorld's data, which its licence allows to be redistributed publicly only in encrypted form, so they ship in a password-protected archive whose password the supplement's README gives.

AuthorsOpenReview ↗

To all reviewers and the AC (3/3): E6b's results — every frozen prediction held; one prediction of the submission was falsified; what E6b does not show

Every prediction we froze, P1 to P4, came out as the protocol said it would, including where it said a failure was possible. The last two rows are the two predictions the submitted version made, in its App M. Counts are pairs, one episode each, under the primary rule (Table O13, p. 50, l. 2647–2677). Below, a bare "l. M" is a line of the submitted version.

what we predictedHaiku 1Haiku 2Sonnetoutcome
P1Jij=0J_{ij}=0: AA's footprint clause fails after BB in no pair0/200/200/20held
P1read-only: AA's task never fails0/100/100/10held
P2the footprint clause fails exactly when BB writes outside DAD_A40/4040/4039/39held
P2ww: how often BB wrote outside DAD_A in a Jij≠0J_{ij}\ne0 pair (no value predicted)14/2013/2016/19measured
P3under the screen, AA's footprint clause passes in every Jij≠0J_{ij}\ne0 pair20/2020/2019/19held
P3at BB's cost: BB writes all of DBD_B under the screen0/200/200/19held
P4content checks never fail in disjoint pairs with BB inside DBD_B0/90/90/7held
P4nor in read-only pairs0/100/100/10held
P4overlap: content checks may fail4/103/105/10occurred
App Mdegradation confined to Jij≠0J_{ij}\ne0 pairs: inside, AA's task fails9/109/109/10falsified
App Mthe screen recovers the isolated score: AA's task passes17/2018/2016/19not met

Four notes on those rows. P1 saw no failure in 20 pairs, so its exact one-sided 95% upper bound is 0.139 for independent pairs, 0.162 over the 17 AA families and 0.283 over 9 family clusters. For ww, the B-family bootstrap 95% intervals are [0.41, 0.95], [0.39, 0.89] and [0.63, 1.00]. Theorem 3's test assumes agents write only inside their declared sets. BB left its own in 3, 2, 4 unmediated episodes, none in a Jij=0J_{ij}=0 pair, so the P1 count excludes nothing. Sonnet lost one disjoint pair to the output cap, so its Jij≠0J_{ij}\ne0 cells hold 19 pairs, and its disjoint P4 cell holds only 7, too few to conclude anything from.

What was falsified. We predicted that degradation is confined, up to the model's own error rate, to Jij≠0J_{ij}\ne0 pairs (l. 425–426). It is not. With a gold AA, AA's task failed in every inside pair in which BB wrote. That is 9 of the 10 in each run. In the tenth pair BB wrote nothing. The failures were on content BB was entitled to change, and the footprint clause was intact. The frozen protocol listed this as possible, but its predictions were first frozen after the gold pairs had already shown it. Gold BB, with no model at all, failed AA's task in all 10 inside pairs (App O, p. 54, l. 2904–2915). The certificate covers the footprint clause, not content another agent may legitimately change. The abstract and contribution (vi) now say so (p. 1, l. 029–030; p. 2, l. 089–091).

What was not met. We also predicted that the screen recovers the isolated score on Jij≠0J_{ij}\ne0 pairs (App M l. 2169–2170). It kept the footprint clause in every pair, but not the task: the rest failed on content in overlap pairs.

Under the paper's own no-code rule, which ends an episode at a reply without code where E6b asks again (pre-specified; Table O15, p. 53, l. 2809–2825), three of BB's own numbers fall.

primary rulethe paper's rule
P0: BB alone completes its own footprint, of 4033, 32, 3728, 29, 34
BB alone finishes, of 4040, 40, 4035, 35, 36
ww with BB alone, of 2015, 14, 1812, 11, 16

Every other row of Table O15 moves by at most one pair, and P1's footprint clause, P2, ww unmediated and P3's footprint clause not at all (p. 51, l. 2747–2751).

What E6b does not show (p. 55, l. 2931–2937; §7, p. 10, l. 535–536).

  • It is one benchmark, and two models of one provider at one effort.
  • Its AA is gold, so beyond the underpowered subset it says nothing about two fallible agents.
  • BB runs only after AA has finished, so interleaving is untested.
  • The gold filter keeps only pairs in which gold BB can act after AA. It dropped 28 of the 68 pairs we tried.
  • Pairs within a task family are not independent. The family and cluster bounds address that only in part.
  • BB always acts on another simulated user's account.

It measures how often a language-model agent makes the writes JijJ_{ij} flags, and what they do to AA's score. The mechanism it tests is the one E6 tested.

We thank the reviewers again; their questions led directly to this experiment, and we would be glad to answer any questions about it.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.