acceptodds
Under review as a conference paper at ICLR 2027

Local Evidence, Global Risk: Sharp Bounds on Composition Attacks in LLM Agent Systems

Abstract

Agent systems combine information from memory, messages, and tool outputs. Records that reveal little in isolation can therefore support a harmful objective when brought together. Evidence about individual records leaves two questions unanswered: which records occur together, and where can they meet? We characterise exactly what such local evidence implies about the structural opportunity behind composition attacks. An architecture determines two families of records: opportunity sets, which can meet in one context, and defences, which meet every opportunity set. The largest opportunity probability consistent with record-wise loading rates is the cheapest fractional defence; exchanging loaded and unloaded records exchanges the two families and yields the smallest. The union and Fréchet bounds are exact at every loading vector precisely for ideal architectures. Windows and stars are ideal, whereas in a full pool local evidence can force an opportunity without forcing any particular group. Under path-factorising placement, the same defences certify the ceiling through a Markov union bound. In controlled split-secret experiments across three seeds, six open-weight models receive placements with identical record-wise marginals. Mean window reconstruction is zero under SPREAD, which always leaves a defence unloaded, and ranges from 0.894 to 1.000 under BLOCK, which loads whole opportunity sets. For two of these models, omitting the instruction to preserve codes leaves this reconstruction near baseline, while forbidding codes in final reports lowers it only partly. The bounds quantify structural opportunities for composition; the experiments measure how models turn them into reconstructed secrets.

Primary area:
alignment, fairness, safety, privacy, and societal considerations
Keywords:
Local Evidence, Global Risk: Sharp Bounds on Composition Attacks in LLM Agent Systems

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_wfokOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
1
Soundness
1
Read review
Paper summary

This paper studies the probability that multiple fragmented records co-occur within a single agent's context in multi-agent systems. Given the marginal loading probabilities of individual records and a communication architecture, the authors derive upper and lower bounds on the co-occurrence probability. The theoretical analysis draws on classical probability bounds, combinatorial optimization, and graphical models. For empirical validation, the authors evaluate open-weight LLMs on a synthetic split-secret task involving the reconstruction of three hexadecimal strings.

Critical strengths

The paper presents a relatively complete study, covering problem formulation, theoretical analysis, and empirical evaluation.

Critical weaknesses
  1. Excessive Formalization and Limited Theoretical Novelty

The paper introduces substantial mathematical complexity to address a relatively simple problem: bounding the probability that multiple records co-occur within a shared context given their marginal probabilities. Much of the theoretical development relies on established results from probability theory and combinatorial optimization.

Although the authors derive some architecture-specific results, the paper does not clearly demonstrate sufficient theoretical novelty beyond these existing techniques. The large number of theorems, propositions, and lengthy proofs makes the paper unnecessarily difficult to follow, while providing limited additional insight into the security of LLM agent systems. Overall, I find the theoretical treatment disproportionately complex relative to its demonstrated contributions.

  1. Toy Experimental Setup Disconnected from Real Composition Attacks

A major concern is the substantial gap between the paper's security motivation and its empirical evaluation. While the paper focuses on composition attacks and harmful objectives in LLM agent systems, the experiments primarily test whether models can propagate three six-character hexadecimal strings through a benign work-log summarization workflow.

In the main experiments, agents are explicitly instructed to preserve reference codes verbatim, and success is measured by whether all three fragments appear together in a generated report. Although the authors also experiment with removing the preservation instruction, the task remains essentially one of string copying and information retention. There is no actual malicious objective, semantic composition of harmful instructions, jailbreak dynamics, or tool-use exploitation. Consequently, the experiments mainly measure basic information propagation and copying fidelity rather than realistic composition attacks. This leaves a significant gap between the paper's theoretical security motivation and its empirical validation.

Questions for authors
  1. Can the authors demonstrate the framework on a realistic composition attack, where individually benign fragments must be semantically synthesized to achieve a harmful objective rather than simply copied verbatim?

  2. How well do the theoretical bounds predict actual attack success rates in realistic composition-attack scenarios?

4 comments
AuthorsOpenReview ↗

Response to Reviewer wfok (1/3): is the problem simple, and what is new (W1)

Response to Reviewer wfok (1/3): is the problem simple, and what is new (W1)

Thank you for the review and for noting that the paper is "a relatively complete study, covering problem formulation, theoretical analysis, and empirical evaluation". Your concerns are the weight of the formalism (W1) and the realism of the experiments (W2, Q1, Q2). The new experiments are in the General response (Tables G1–G2 and E3).

W1 (a): "The paper introduces substantial mathematical complexity to address a relatively simple problem: bounding the probability that multiple records co-occur within a shared context given their marginal probabilities."

The problem looks simple, but the simple answers are wrong in identifiable cases, and the paper proves exactly when. Four exact examples:

  1. Local evidence can force an opportunity that no single group reveals. In a full pool with n=9n=9, τ=3\tau=3 and p=1/3p=1/3, an opportunity is forced with probability at least 1/71/7, yet the Fréchet bound of every particular triple is 0 (§5.1, Fig. 3b).
  2. One oversized context breaks both simple bounds. For τ≥2\tau\ge 2, put rates (τ−1)/τ(\tau-1)/\tau on τ+1\tau+1 records of one closure (0 elsewhere). The true interval is [(τ−1)/(2τ),1−1/τ2][(\tau-1)/(2\tau), 1-1/\tau^2], while the union and Fréchet bounds give [0,1][0,1] (Thm 5.1, Fig. 6b).
  3. Natural algorithms fail under local coordination. A dynamic program over (node, state, count) overshoots in 78 of 150 cells, by up to 0.5778. Greedy fixing loses on 378 of 1,560 instances. The intuitive formula min⁡(1,⌊n/τ⌋p)\min(1,\lfloor n/\tau\rfloor p) is false (Prop. B.12–B.13).
  4. Architecture-blind reasoning misses the whole range. At identical marginals, window opportunity is 0 or 1 (Cor. 4.2). Six LLMs then reconstruct 0 vs 0.894–1.000 (Table 1); in the new semantic task the result is 0/500 vs 250/250 (Table G1).

The formalism is what tells an evaluator which case they are in, and it returns the correct number. Its core is short:

  • Thm 4.1: one LP and its blocker;
  • Thm 5.1: when the elementary bounds suffice;
  • Thm 5.3: what local placement changes.

W1 (b): "Much of the theoretical development relies on established results ... the paper does not clearly demonstrate sufficient theoretical novelty beyond these existing techniques."

Several components are classical, and we credit them: Hailperin's LP, blockers, Lehman's theorem, total unimodularity. That choice is what makes the endpoints exact and verifiable. The new parts are tiered in our response to B8nN (1/3) and in General response 3/3:

  • new mathematics for path-factorised placement, which none of these tools covers: the defence-Markov bound (Eq. 5), the closed-form window ceiling with the exact no-loss condition k≤2k\le 2 or p≥1/2p\ge 1/2 (Thm 5.3), and Thm 5.5;
  • new results built on classical tools: the floor as the same LP on the blocker, and the characterisation that the union and Fréchet bounds are exact at every marginal vector iff the architecture is ideal, with each failing at some rate otherwise (example 2 above).

We will add a "what is new" paragraph [Rev: §1] and discuss the closest work, arXiv:2109.01591 [Rev: §2].

W1 (c): "The large number of theorems, propositions, and lengthy proofs makes the paper unnecessarily difficult to follow, while providing limited additional insight into the security of LLM agent systems. Overall, I find the theoretical treatment disproportionately complex relative to its demonstrated contributions."

On length. The main text has eight formal results, and all lengthy proofs are already in App. B–J. We will make it lighter:

  • a worked nine-record window example opening §4;
  • a notation table;
  • a results-to-guidance table;
  • the long proof sketches of Prop. 5.4 (vertex principle) and Thm 5.5 moved to the appendix, with a one-line idea kept beside each [Rev: §4–5].

On security insight.

  • The ceiling never exceeds the loading mass of any defence, so sanitising a cheap defence such as a hub is the direct lever (§7; star ceiling 1/3).
  • No closure should exceed τ\tau records (Thm 5.1).
  • Handovers enlarge the effective context (Fig. 10).
  • Final-report redaction leaves the secret in handovers (Table 2).
  • Per-record audits cannot certify some architectures at all (Cor. 4.2).

On soundness. Every theorem is proved in the appendix. Every theoretical claim that admits a numerical test is also checked in exact rational arithmetic on finite grids, with zero deviations (App. M, B.2, C.2, J): for example, 2,000 duality cells and 972 + 414 + 11,142 path cells. The link between theory and experiments is answered in 2/3 and 3/3; if a specific step concerns you, we will address it directly.

AuthorsOpenReview ↗

Response to Reviewer wfok (2/3): experimental setup (W2)

Response to Reviewer wfok (2/3): experimental setup (W2)

W2 (a): "the experiments primarily test whether models can propagate three six-character hexadecimal strings through a benign work-log summarization workflow."

The split-secret task was chosen as a measuring instrument. The theory's object is structural opportunity: whether the fragments can meet in one context. The task makes opportunity and conversion exactly scorable: a missing shard is guessed with probability 2−242^{-24}, and decoys cannot collide. This allows a clean test of the central prediction: identical record-wise marginals give opposite outcomes, with window reconstruction 0 under SPREAD and 0.894–1.000 under BLOCK across six models and three seeds (Table 1). It is the classical aggregation-disclosure setting (Denning et al., 1979). Because it is a deliberately clean proxy, we now complement it with semantic tasks (W2(c), Q1).

W2 (b): "agents are explicitly instructed to preserve reference codes verbatim ... Although the authors also experiment with removing the preservation instruction, the task remains essentially one of string copying and information retention."

The ablation the review mentions shows that the instruction does not create the effect (§6.4, Table 2):

  • Neutral prompts (no preservation request): 179/180 (Qwen3-4B) and 176/180 (Llama3.2-3B), against baselines of 180/180 and 166/180.
  • Forbidding codes in the final report lowers final-report reconstruction only to 110/180 and 146/180. Some worker handover still holds the full secret in 180/180 and 177/180 of those trials, so a report-level instruction does not remove the composed secret from the system.

The new derived-code task removes copying altogether (E1, Table G1):

  • the target is computed from a rule and two numbers and appears in no record;
  • the prompt is neutral;
  • SPREAD gives 0/500 and window-BLOCK gives 250/250 at identical marginals;
  • across E1+E2 there are 0 successes in 3,495 trials without an opportunity.

W2 (c): "There is no actual malicious objective, semantic composition of harmful instructions, jailbreak dynamics, or tool-use exploitation."

Jailbreaks and harder synthesis act on the second stage, conversion; the bounds govern the first stage, opportunity. Tool use can also change which records reach which context; the theory takes this in through the rates and closures, since any upper bound on the rates and any superset of the closures, such as reach(G)\mathrm{reach}(G), keeps the certified ceiling valid (C1, General response 3/3). For any downstream event that requires all fragments to meet (§3.1), none of these factors can create an opportunity where the fragments never meet. So, with rates and closures upper-bounded as above under attack, a certified ceiling holds against any present or future jailbreak.

We test semantic composition with two synthetic objectives:

  • Derived code. Conversion is 1.000 / 1.000 / 0.987 (Qwen3-14B / 8B / 4B).
  • Re-identification of a person from three quasi-identifiers, as a privacy-harm proxy (General response 1/3).
    • Under the pre-specified strict metric, every model succeeds more often with an opportunity than without: 0.035 vs 0.004 (Qwen3-14B), 0.066 vs 0.028 (4B), 0.143 vs 0.070 (8B, one seed, 256 tokens), with non-overlapping CIs.
    • Strict conversion is the model's stage: Qwen3-14B lists candidates before concluding, which strict scoring counts as failure (post-hoc concluded metric: 0.502 vs 0.004).
    • The residual success without opportunity comes almost entirely from partial contexts that leave 4 candidates (the τ=2\tau=2 event); only Qwen3-4B has hits with at most one identifier (10/5445 agents).

Tool use. Of tool use, we exercise retrieval (E3b): Qwen3-4B/14B reconstruct in exactly the 16/300 sessions where retrieval co-located the fragments, and in 0/284 others. Tool-execution exploits act on placement and jailbreak prompts on conversion, so a ceiling certified over a superset of the closures still bounds them.

We did not build real harmful content, for ethical reasons and because refusal behaviour would confound conversion with alignment.

W2 (d): "This leaves a significant gap between the paper's theoretical security motivation and its empirical validation."

The paper's claim is two-stage: ASR = opportunity × conversion. The theory gives the exact range of the first factor from local evidence, and the experiments measure the second. The new results bear on this gap in three ways:

  • (i) Semantic tasks without copying obey the same placement contrast and the same rule of no success without opportunity (E1).
  • (ii) Under heterogeneous per-type rates, the exact [Floor,Ceil][\mathrm{Floor},\mathrm{Ceil}] is attained at both ends, and ASR tracks opportunity (E2, Table G2).
  • (iii) Loading rates from execution traces give a valid certified ceiling. For example, the star is certified at 0.373–0.406, and the pooled observed ASR is 0.303 (E3).
AuthorsOpenReview ↗

Response to Reviewer wfok (3/3): questions (Q1, Q2)

Response to Reviewer wfok (3/3): questions (Q1, Q2)

Q1: "Can the authors demonstrate the framework on a realistic composition attack, where individually benign fragments must be semantically synthesized to achieve a harmful objective rather than simply copied verbatim?"

We demonstrate it on two harmless proxies of harmful objectives in a synthetic work-log setting (E1/E2, Tables G1–G2), and on a retrieval pipeline over a synthetic 51-record store (E3b). In each, every fragment is benign on its own, and the objective requires synthesis rather than copying.

  1. Derived access code.
    • Setup: a rule record ("the keypad code for room R is quantity B plus quantity C") and two ordinary notes. The code appears nowhere, and the prompt is neutral.
    • At identical marginals, SPREAD gives 0/500 and window-BLOCK gives 250/250 (Table G1).
  2. Re-identification.
    • Setup: day, team and birth year appear in three separate notes, and a 16-person synthetic directory is available. No note names anyone; each identifier alone matches at least 6 people, and only the conjunction identifies one person. This is the classical quasi-identifier privacy harm.
    • Results under the pre-specified strict metric: every model succeeds more often with an opportunity than without, with non-overlapping CIs. Qwen3-14B 0.035 vs 0.004, Qwen3-4B 0.066 vs 0.028, Qwen3-8B 0.143 vs 0.070. The post-hoc concluded metric agrees (0.502 vs 0.004, 0.176 vs 0.029).
  3. A retrieval pipeline whose placement is not designed (E3b).
    • Setup: retrieval decides co-location (top-4, fixed before any LLM call because top-3 never co-located the fragments).
    • Results: Qwen3-4B and Qwen3-14B compose the code in exactly the 16/300 sessions with an opportunity, and in 0/284 others.

We did not use genuinely harmful content, as an ethics constraint.

Q2: "How well do the theoretical bounds predict actual attack success rates in realistic composition-attack scenarios?"

The bounds are guarantees on the first factor of ASR = opportunity × conversion; they are not point predictors of ASR. For any task that needs every fragment, ASR ≤ opportunity, so the certified ceiling bounds ASR for every model. We measured both factors.

  • No success without opportunity when the task needs every fragment.
    • Derived code: 0 successes in 3,495 such trials (E1+E2, three models).
    • Original study: none in the 3,360 extension trials, and no shard-count violations in 7,586 trials.
  • Opportunity tracks the predicted interval.
    • With heterogeneous rates the endpoints are attained (Table G2); for example, window [3/20,9/10][3/20, 9/10] gives 0.15 and 0.89 observed.
    • Derived-code ASR follows opportunity to within 1 trial in 100.
  • Certified from traces.
    • Star: a certificate of 0.373–0.406 against pooled ASR 0.303.
    • Retrieval: a valid certificate of 0.94 against 16/300 observed. Some law with the same slot marginals has opportunity 2/3 (Thm 4.1), so no certificate from record-wise rates alone can be lower; the rest is finite-sample slack (median 0.80 at N=1000N=1000). A held-out joint bound (0.080) certifies only the observed coupling; the marginal certificate also covers re-routing.
  • Conversion is model- and task-dependent.
    • Derived code: 0.987–1.000.
    • Copying in window and star contexts: 0.875–1.000 (§6.2).
    • Chain handovers lower conversion against complete contexts (0.26 vs 0.84, Table 21).
    • Re-identification is lower again: strict 0.035–0.143.
    • This is why the paper reports both stages: an evaluation that reports only ASR cannot tell a safe architecture from a model that failed to compose.

In short: wherever success requires all fragments (copying and derived code), no success occurred without an opportunity, and the bounds were attained when conversion was high. In re-identification, success is higher with an opportunity than without for every model, and partial contexts permit guessing among the 4 remaining candidates. Almost all of that residual success falls under the τ=2\tau=2 event, whose range Theorem 4.1 again gives exactly; only Qwen3-4B has hits with at most one identifier (10/5445 agents).

We hope these responses and the new experiments address your concerns about formalism, novelty and realism. Could you let us know whether they resolve them, or which point would still need evidence? If they do, we would appreciate it if you would reconsider your overall assessment.

Thanks for the rebuttal and the additional experiments. I appreciate the efforts to clarify the theoretical contributions and to extend the empirical evaluation beyond simple information copying. The newly introduced semantic composition and re-identification tasks provide useful additional evidence.

However, I remain concerned that the empirical evaluation is still largely based on synthetic and controlled settings, leaving a substantial gap between the proposed framework and realistic composition attacks in LLM agent systems. In addition, the theoretical bounds characterize structural opportunities rather than directly predicting attack success rates in general settings. While the rebuttal addresses some of my concerns, I maintain my original rating.

Reviewer_B8nNOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The authors model an agent system as a set of records and a family of information closures, and they ask which range of opportunity probabilities fits the known loading rate of each record. They show that the largest such probability equals the cheapest fractional defence, and the smallest follows from the same result after swapping loaded and unloaded records. They prove that the union bound and the Fréchet bound are exact at all rates if and only if the opportunity family is ideal, and they show that windows and stars are ideal while full pools are not. They also derive exact window ceilings when placement must factorise along a path, and they characterise when this restriction costs nothing for the aggregate event. Experiments on six open models split a synthetic hex secret into three shards and show that placements with equal marginals give reconstruction of 0 under SPREAD and close to 1 under BLOCK. Further studies vary the prompt and the screening question, and they find that redaction only changes the final report and that per record screening stays at chance.

Critical strengths

The opportunity and defence duality is exact and easy to state. The ceiling is the cheapest fractional defence and the floor comes from the same result by complementation, so an evaluator has a concrete quantity to compute for any listed architecture. This matters to me because it turns a vague concern about composition into a precise and checkable number.

The theory is checked with great care. The authors verify the main results in exact rational arithmetic over many cases, and they give clear counterexamples for each assumption, such as the triangle and the four cycle. This gives me high confidence that the stated results are correct.

Critical weaknesses

The technical novelty of the theory is limited. Most results follow directly from known tools, including the Hailperin LP dual, Fulkerson blocking pairs, Lehman’s theorem on ideal clutters, and total unimodularity of interval matrices. I see the framing as the main new step, so the technical contribution feels small for ICLR.

The link to real agent security is weak. The bounds need exact or calibrated loading rates, but the authors’ own screening study shows that per record verdicts stay at chance and cannot supply these rates. The main experiment also places synthetic shards directly and tells agents to preserve codes, so the finding that ASR follows opportunity is close to true by design.

Questions for authors

In a real deployment, how would an evaluator obtain valid simultaneous intervals for the loading rates? If no practical source exists, I would like to know which conclusions still hold.

Which results do the authors see as new mathematics, rather than direct uses of known results on ideal clutters and probability LPs?

Could the authors test a semantic composition task, such as a harmful instruction split across records, with no instruction to preserve content?

4 comments
AuthorsOpenReview ↗

Response to Reviewer B8nN (1/3): novelty (W1, Q2)

Response to Reviewer B8nN (1/3): novelty (W1, Q2)

Thank you for the review, and for finding the duality "exact and easy to state" and the theory "checked with great care". We answer novelty (W1, Q2) here, loading rates (W2a, Q1) in 2/3, and the experiment design (W2b) and semantic composition (Q3) in 3/3; new tables are in the General response.

W1: "Most results follow directly from known tools, including the Hailperin LP dual, Fulkerson blocking pairs, Lehman's theorem on ideal clutters, and total unimodularity of interval matrices. I see the framing as the main new step, so the technical contribution feels small for ICLR." Q2: "Which results do the authors see as new mathematics, rather than direct uses of known results on ideal clutters and probability LPs?"

Several components are classical, and the paper says so ("The n+1-variable dual in Step 1 is standard", App. B.1). We chose these tools because they make the endpoints exact, polynomial-size and checkable in rational arithmetic. The framing is what turns composition into "a precise and checkable number" (your words); it also raises questions the classical tools do not answer by themselves, listed below. Our classification follows, and it will appear in §1 [Rev: §1].

Direct uses of known results.

  • The ceiling of Thm 4.1: Hailperin's dual restricted to an up-set.
  • Prop. 4.3: monotone coupling.
  • Cor. 5.2: total unimodularity of interval matrices, plus a linear-time hitting set.
  • Prop. 5.4: the vertex principle (Fagiuoli–Zaffalon; de Campos–Cozman).

New results built on classical tools.

  • The floor in Thm 4.1.
    • Pushing laws forward by x↦1−xx\mapsto 1-x maps no-opportunity configurations onto those whose unloaded set contains a defence.
    • So the floor is the same covering LP for the blocker b(O)b(\mathcal O) at 1−p1-p.
    • Every ceiling therefore has a defence certificate, and every ideal floor has a witness opportunity set.
  • Thm 5.1, as a statement about probability bounds.
    • Idealness is defined by integrality of the cover polyhedron; given Thm 4.1, our content is about the two bounds practitioners actually use: the union bound over one defence and the Fréchet bound over one opportunity set are exact at every marginal vector iff O\mathcal O is ideal; so they are exact together, or each fails at some rate.
    • "Together" follows because the Fréchet bound is the blocker's union bound at 1−p1-p, and Lehman/Fulkerson give that O\mathcal O is ideal iff b(O)b(\mathcal O) is.
    • The converse needs the scaling step in Lemma B.6: recovering integrality from an identity on [0,1]n[0,1]^n that is truncated at 1.
    • Design rule: for τ≥2\tau\ge 2, put rates (τ−1)/τ(\tau-1)/\tau on τ+1\tau+1 records of one closure (0 elsewhere). The true interval is [(τ−1)/(2τ),1−1/τ2][(\tau-1)/(2\tau), 1-1/\tau^2], while both elementary bounds give [0,1][0,1].
    • We did not find this stated as a result about probability bounds.

New mathematics: §5.2–5.3, which the four tools do not cover. Laws that factorise over the communication graph form a non-convex class.

  • Eq. 5. At uniform rates, a path-factorising law restricted to a defence in path order is again a Markov chain. Chaining bivariate Fréchet bounds gives ψm(p)=1−(1−p)am−1\psi_m(p)=1-(1-p)a^{m-1} for any architecture. A block-law lower bound ψν\psi_\nu matches it whenever ν=m\nu=m, for example for windows.
  • Thm 5.3. A closed-form distributed window ceiling, with no loss iff k≤2k\le 2 or p≥1/2p\ge 1/2: a path can make two neighbouring blocks exclusive but not three.
  • Thm 5.5. For the aggregate event on a path, zero slack holds iff n=τn=\tau, n=2τn=2\tau, or n>2τn > 2\tau with p≥1/2p\ge 1/2. The proof uses a block reduction, a saturation lemma, and equality in Markov's inequality.
  • Naive routes fail here: the count-state DP overshoots in 78/150 cells (by up to 0.5778), greedy loses on 378/1,560, and min⁡(1,⌊n/τ⌋p)\min(1,\lfloor n/\tau\rfloor p) is false.

Closest work. Padmanabhan, Ahipasaoglu, Ramachandra & Natarajan (SIAM J. Optim. 2022; arXiv:2109.01591) bound Pr⁡(max⁡x∈Xc⊤x≥r)\Pr(\max_{x\in X}c^\top x\ge r) over laws with given marginals.

  • For Bernoulli cc and listed XX, their Thm 2.3 gives a polynomial-size LP for the upper bound, and their Thm 2.5 shows the lower bound is NP-hard, already for graph edges with r=2r=2.
  • With XX the indicators of O\mathcal O and r=τr=\tau, our ceiling agrees with theirs.
  • We add: the (n+1)(n+1)-variable cover form with its defence certificate; the floor as the blocker's covering LP, whose possible exponential size matches their hardness; and Thm 5.1, which characterises exactly when the floor reduces to one opportunity set's Fréchet bound (polynomial in ∣O∣|\mathcal O|): precisely for ideal O\mathcal O.
  • For their hard instance (edges, r=2r=2), this happens precisely for bipartite graphs. Their hardness result and our Thm 5.1 are thus consistent: the floor is hard in general, and on ideal families it reduces to a single Fréchet bound.
  • The revised PDF will cite and discuss this work [Rev: §2].
AuthorsOpenReview ↗

Response to Reviewer B8nN (2/3): where loading rates come from (W2a, Q1)

Response to Reviewer B8nN (2/3): where loading rates come from (W2a, Q1)

W2a: "The link to real agent security is weak. The bounds need exact or calibrated loading rates, but the authors' own screening study shows that per record verdicts stay at chance and cannot supply these rates."

That per-record verdicts cannot supply the rates is the paper's own finding (App. O.2), and it motivates architecture-level reasoning. We may not have made clear that screening is only one possible input: §3.2 already lets "an audit" supply intervals, but Assumption A.6 is titled "Screening report", and we will reposition it [Rev: §1, §3.2, §6.5, App. A.3]. In fact, rates need not come from verdicts at all, so the link to deployments does not rest on screening.

What the screening study measures.

  • Each LLM sees one record's text, without the secret, its neighbours or labels, and answers "Does this note contain any part of a confidential secret?" (App. N.7).
  • Loaded records and decoys were built to have approximately the same distribution (record-length AUC 0.5049, inside the null band [0.4946, 0.5054]).
  • Under exactly matched classes, Prop. N.1 shows that any screener has a diagonal ROC.
  • So the chance-level result says that content inspection, one record at a time, cannot see fragments. That is consistent with the paper's motivation for architecture-level reasoning; it says nothing about whether loading rates can be measured some other way.

Where rates come from: provenance gives an upper bound, without content judgements.

  • Let zi=1z_i=1 when record or slot ii holds content from an untrusted source (user upload, web or tool output, another principal's memory).
  • Under the trust boundary, fragments arrive only through untrusted sources. Hence x≤zx\le z coordinatewise, and each rate pip_i is at most Pr⁡(zi=1)\Pr(z_i=1).
  • The orchestrator logs this rate. By monotonicity (Corollary C1, General response 3/3), CeilG\mathrm{Ceil}_G evaluated at bounds on these rates is a valid, more conservative certificate.
  • No verdict is involved. Eq. (8) already separates the latent loading xx from the verdict YY, and App. N.8 builds the box from labels, not answers.

Q1: "In a real deployment, how would an evaluator obtain valid simultaneous intervals for the loading rates? If no practical source exists, I would like to know which conclusions still hold."

(1) One-sided bounds suffice (C1).

  • Both endpoints are nondecreasing in pp (Prop. 4.3). On the event p≤up\le u, the opportunity probability is at most CeilG(p)\mathrm{Ceil}_G(p), which is at most CeilG(u)\mathrm{Ceil}_G(u). So simultaneous coverage 1−α1-\alpha of uu gives the same coverage for the certificate.
  • Per-record one-sided Clopper–Pearson at level α/n\alpha/n with Bonferroni is valid under arbitrary cross-record dependence, given i.i.d. runs, applied to the logged untrusted-source indicators above.
  • With a defence fixed in advance, only its records need bounds (C2).

(2) Executed (E3, General response 2/3).

  • From the paper's logged traces, the certified star ceiling is 0.406, or 0.373 with the hub fixed. The truth is 1/3 and the blind bound is 1. Coverage in re-simulation is 0.993–1.000 with full Bonferroni and 0.927–1.000 defence-only.
  • In a non-designed retrieval pipeline the certificate (0.94) is valid. Its distance from the true 0.06 is mostly the identification gap (some law with those marginals reaches 2/3), plus finite-sample slack.
  • For the window at p=1/3p=1/3 the certificate is 1, which is correct.

(3) Without any rates (C4), the following still hold.

  • If every closure has fewer than τ\tau records, opportunity is 0 under every law and adversary.
  • A defence whose records cannot be loaded gives 0. Examples are trusted-only sources and a hub that receives only sanitised content.
  • Handover chains reach the full pool: "direct context width does not bound cumulative access" (Fig. 10).
  • Monitoring only the final report misses composition: under final-report redaction, handovers still hold the full secret in 180/180 and 177/180 trials (Table 2).

Negatively, at some rates (e.g. window, p=1/3p=1/3) no per-record audit, however accurate, can certify anything (Cor. 4.2).

AuthorsOpenReview ↗

Response to Reviewer B8nN (3/3): experimental design (W2b) and semantic composition (Q3)

Response to Reviewer B8nN (3/3): experimental design (W2b) and semantic composition (Q3)

W2b: "The main experiment also places synthetic shards directly and tells agents to preserve codes, so the finding that ASR follows opportunity is close to true by design."

(a) Conversion is not built in, and the preserve instruction does not create it (§6.4, Table 2).

  • With neutral prompts that never mention codes, reconstruction stays at 179/180 (Qwen3-4B) and 176/180 (Llama3.2-3B).
  • Forbidding codes in the final report lowers it only to 110/180 and 146/180, while some worker handover still holds the full secret in 180/180 and 177/180 trials.
  • Conversion visibly drops where transport is hard. Every trial offers an opportunity, yet chain succeeds on 1–29 of 60 trials against 14–59 for complete (Table 8); pooled conversion is 0.26 vs 0.84 (Table 21). Llama converts 0.894 of window-BLOCK opportunities (by seed 0.950 / 0.817 / 0.917).

(b) What is guaranteed by design is exactly what makes the bound valid.

  • "No reconstruction without opportunity" holds because a guessed shard succeeds with probability 2−242^{-24}. This inequality is why the ceiling bounds ASR.
  • Placing shards directly is the controlled manipulation the claim needs. Identical marginals can give opposite outcomes (Cor. 4.2), and testing that requires holding the marginals fixed while varying the coupling.

(c) New: composition without copying (E1, Table G1).

  • In the derived-code task the answer is in no record; it must be computed from a rule and two numbers. The prompt is neutral.
  • At identical marginals, SPREAD gives 0/500 and window-BLOCK gives 250/250.
  • Over E1+E2 there are 0 successes in 3,495 trials without an opportunity. Conversion given an opportunity is 1.000 / 1.000 / 0.987 (Qwen3-14B / 8B / 4B).

Q3: "Could the authors test a semantic composition task, such as a harmful instruction split across records, with no instruction to preserve content?"

We ran two semantic tasks with no preserve instruction (E1, E2). We used synthetic, harmless objectives rather than a real harmful instruction, for three reasons:

  • (i) Ethics. We would otherwise publish working split-instruction attacks.
  • (ii) Scoring. A harmful completion needs an LLM judge, which adds a noisy third stage; our tasks are scored exactly.
  • (iii) Confounding. Refusal training would confound conversion with alignment, whereas the bounds concern opportunity.

For any downstream event contained in the opportunity event (§3.1), harder or harmful synthesis keeps ASR at or below the same certified ceiling.

  • Derived code (computation, no copying): see (c). Under heterogeneous per-type rates (E2), ASR follows opportunity, which attains both ends of the exact interval.
  • Re-identification (joining three quasi-identifiers against a 16-person directory): a harder second stage, reported for all three models (General response 1/3).
    • Under the pre-specified strict metric, every model succeeds more often with an opportunity than without, with non-overlapping Wilson CIs: Qwen3-14B 21/602 = 0.035 vs 6/1398 = 0.004; Qwen3-4B 40/602 = 0.066 vs 39/1398 = 0.028; Qwen3-8B 43/301 = 0.143 vs 49/699 = 0.070.
    • The post-hoc concluded metric agrees (0.502 vs 0.004 and 0.176 vs 0.029 for 14B / 4B).
    • Absolute conversion is low, which is the model's stage.
    • Hits outside the τ=3\tau=3 opportunity come almost entirely from agents holding 2 of 3 identifiers (4 candidates). That is success under the τ=2\tau=2 objective, whose range is again the Thm 4.1 LP.

This is the two-stage picture of §6.2: the architecture fixes opportunity, and the model fixes conversion.

We hope this shows that the result is not built in, and that rates can be obtained without verdicts. Could you let us know whether E1–E3 and the positioning against arXiv:2109.01591 address your concerns? If they do, we would appreciate it if you would reconsider your rating.

Thank you for the detailed response and the new experiments in Appendix R. The neutral-prompt results and E1 convince me that the preserve instruction does not drive reconstruction, and the provenance-based bounds give a valid way to obtain loading rates without content verdicts. The classification of results and the comparison with Padmanabhan et al. (2022) are also helpful. My concern about technical novelty remains, since by the authors' own classification the main theorems are known results restated as probability bounds, and the new mathematics in §5.2–5.3 is narrower. I also note that the certificate can be loose in practice: in E3b it is 0.941 against a true opportunity of about 0.06, which I suggest discussing in the limitations. Overall, the response resolves my concerns about the experimental design and the source of the rates, so I am raising my rating from 2 to 3.

Reviewer_89usOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies composition attacks in LLM multi-agent systems, where information that appears harmless individually may become harmful when combined across agents. The authors propose a mathematical framework to estimate composition risk using record-level loading probabilities and agent architecture. They derive upper and lower bounds on composition opportunities and investigate how different architectures and coordination assumptions affect these bounds.

Critical strengths
  1. The topic is interesting and the overall motivation is clear.

  2. The paper provides theoretical insights into how information-flow structures and dependencies between records affect composition risk in multi-agent systems.

Critical weaknesses
  1. The framework assumes that record-level loading probabilities and information-flow structures are known or can be accurately estimated. This may be unrealistic in practical LLM agent systems with dynamic communication, memory retrieval, and tool interactions.

  2. The presentation is heavily mathematical and difficult to follow, particularly in Sections 4 and 5. Several important results rely on specialized concepts from probability theory and combinatorial optimization, with limited intuitive explanation. Many proof details are deferred to the appendix.

Questions for authors
  1. How can record-level loading probabilities and agent architecture be reliably obtained in real agent systems?

  2. How does the framework handle attacks requiring distinct fragments with different probabilities or semantic roles? Can the authors provide experiments with heterogeneous loading probabilities and fragment types?

2 comments
AuthorsOpenReview ↗

Response to Reviewer 89us (1/2): obtaining loading rates and architectures (W1, Q1)

Response to Reviewer 89us (1/2): obtaining loading rates and architectures (W1, Q1)

Thank you for the review, and for finding the motivation clear and the theory informative about "how information-flow structures and dependencies between records affect composition risk". We answer the inputs question (W1/Q1) first, then presentation (W2) and heterogeneity (Q2); the new tables are in the General response.

W1: "The framework assumes that record-level loading probabilities and information-flow structures are known or can be accurately estimated. This may be unrealistic in practical LLM agent systems with dynamic communication, memory retrieval, and tool interactions."

We may not have been clear enough here. The framework needs neither exact rates nor an exact architecture. Upper bounds on both suffice, and some conclusions need no rates at all.

(1) Rates: one-sided upper bounds suffice.

  • Both endpoints of Thm 4.1 are nondecreasing in pp (Prop. 4.3). So simultaneous upper confidence bounds uu give a valid certified ceiling CeilG(u)\mathrm{Ceil}_G(u) (Corollary C1, General response 3/3).
  • One-sided Clopper–Pearson bounds with Bonferroni are valid under any dependence between records, so no model of the joint law is needed.
  • With a defence fixed in advance, only its records need bounds (C2). For a star, that is the hub alone.

(2) Architectures: any superset of the closures is safe for the ceiling.

  • The ceiling can only grow when closures are added. So one may use reach(G)\mathrm{reach}(G), the transitive closure of the communication graph (Def. A.2), or the union of closures over all routings the orchestrator can choose.
  • Dynamic communication, retrieval and tool calls are therefore handled by over-approximation.
  • The communication graph is a design artifact of the deployment (memory access rules, routing, handovers), not a latent quantity.

(3) Demonstration (E3, General response 2/3).

  • From 180 logged traces the certified star ceiling is 0.406, or 0.373 with the hub fixed as the defence. The truth is 1/3 and the architecture-blind bound is 1.
  • Pooled ASR of the six panel models is below it: 327/1080 = 0.303.
  • In a non-designed retrieval pipeline the certificate is valid; most of its distance from the truth is the identification gap, which no certificate from record-wise rates can close (General response 2/3).

(4) Conclusions that need no rates (C4).

  • If every closure has fewer than τ\tau records, there is no opportunity under any law. All 20 such cells in Fig. 11 have ASR 0.
  • A defence whose records can never be loaded gives 0.
  • Handover chains reach the full pool.

Q1: "How can record-level loading probabilities and agent architecture be reliably obtained in real agent systems?"

Rates: provenance gives a valid upper bound without knowing which records are adversarial.

  • Let zi=1z_i=1 when record or slot ii holds content from an untrusted source: a user upload, web or tool output, or another principal's memory.
  • Under the trust boundary, fragments can arrive only through untrusted sources. Hence x≤zx\le z coordinatewise, so each rate pip_i is at most Pr⁡(zi=1)\Pr(z_i=1).
  • The orchestrator logs this rate per run. One-sided bounds on it, combined with C1 monotonicity, give a valid (more conservative) certified ceiling.
  • E3b reads fragment ids directly, because the testbed knows them; in deployment the untrusted-source indicator plays that role.
  • App. N.8 already shows the pipeline from labels to a simultaneous box to a bound, and E3 now runs it on execution traces.

Architecture: from the deployment configuration, using its transitive closure as a safe superset.

We will add a paragraph "Obtaining the inputs" to §3.2 [Rev: §3.2] and the E3 protocol [Rev: App. R].

AuthorsOpenReview ↗

Response to Reviewer 89us (2/2): presentation (W2) and heterogeneous fragments (Q2)

Response to Reviewer 89us (2/2): presentation (W2) and heterogeneous fragments (Q2)

W2: "The presentation is heavily mathematical and difficult to follow, particularly in Sections 4 and 5 ... limited intuitive explanation. Many proof details are deferred to the appendix."

We will make §§4–5 easier to read through the six changes below. The core results are already illustrated on the same nine-record example: Figs. 1–4 show SPREAD/BLOCK, packing vs defence, the star and triangle polyhedra, and one defence certifying both ceilings. The revised PDF will connect them through a single worked example.

Changes in the revised PDF [Rev: §4–5]:

  • (i) A worked example opening §4: window agents over nine records.
    • The seven windows are the opportunity sets, and {3, 6, 9} is a defence.
    • The ceiling is 3×1/3=13\times 1/3=1, which BLOCK attains.
    • Swapping loaded and unloaded records gives the floor 0, which SPREAD attains.
    • A star hub gives 1/31/3, a full pool [1/7,1][1/7,1], and a path 5/65/6.
  • (ii) A notation table.
  • (iii) A results-to-guidance table, for example:
    • Thm 4.1: solve one (n+1)(n+1)-variable LP and report the defence as the certificate.
    • Thm 5.1: the union bound over the cheapest defence is exact at every rate iff the architecture is ideal (e.g. windows, stars); a closure with more than τ\tau records rules this out.
    • §6: measure opportunity and conversion separately, and monitor handovers.
  • (iv) Short intuitions:
    • a fractional defence spreads the clearing budget across records;
    • complementation swaps opportunity sets and defences;
    • idealness means "one group at a time suffices";
    • a path can make two neighbouring blocks exclusive but not three (Fig. 8a will move to the main text, as Fig. 4c).
  • (v) Terms defined before first use.
  • (vi) The long proof sketches of Prop. 5.4 (vertex principle) and Thm 5.5 move to the appendix; a one-line idea stays beside each.

On proofs: each main-text theorem keeps its proof idea next to it, such as the dual-feasibility argument after Thm 4.1 and the defence-chain argument for Eq. 5. The full proofs are in App. B–J because of the page limit. Every theoretical claim that admits a numerical test is also checked in exact rational arithmetic on finite grids, with zero deviations (App. M, B.2, C.2, J).

Q2: "How does the framework handle attacks requiring distinct fragments with different probabilities or semantic roles? Can the authors provide experiments with heterogeneous loading probabilities and fragment types?"

Theory.

  • Heterogeneous rates are the general case. Thm 4.1, Thm 5.1, Cor. 5.2 and Prop. 4.3 hold for every p∈[0,1]np\in[0,1]^n.
    • For example, p=(1/2,1/10,9/10,9/10,1/10,1/2)p=(1/2,1/10,9/10,9/10,1/10,1/2) has ceiling 1/51/5 through the cheap defence {2, 5} (Cor. 5.2 proof).
    • Exact checks cover 204 heterogeneous window/star instances and 345 heterogeneous star instances.
  • Fragments with distinct roles: Corollary C3 uses (record, type) units, with opportunity sets the type-complete sets inside a closure. Thm 4.1 applies because its proof uses only that the event is an up-set generated by a set family. This covers any monotone composition rule, such as "rule plus two quantities" or "three identifiers". Physical constraints, such as one type per record, keep the bounds valid but possibly not tight.
  • Uniform rates are assumed only for the closed forms: the path-factorised results (Eq. 5, Thm 5.3, 5.5) and the full-pool interval (§5.1). We state this as their scope. The global bounds used for certification are fully heterogeneous.

Experiments (new E1/E2, Table G2).

  • Roles. Three semantically distinct fragment roles: rule, quantity B and quantity C for the derived code; day, team and birth year for re-identification. Per-type rates: (1/5, 1/2, 4/5) on window and star, (3/10, 9/10, 19/20) on window, (1/2, 4/5, 9/10) on star. Types are fixed by position.
  • The exact interval is attained at both ends. Window [3/20,9/10][3/20, 9/10]: observed 0.15 (min law) and 0.89 (max law). Star [1/5,1/2][1/5, 1/2]: 0.24 and 0.51.
  • All 20 cells are consistent with the interval. In every cell the Wilson CI of observed opportunity overlaps the interval; point estimates above Ceil are within sampling error.
  • Derived-code ASR tracks opportunity. Qwen3-14B's ASR equals it in every cell, and there is no success without opportunity in 3,000 trials.
  • Re-identification: conversion is model-dependent and low under the strict metric. Success is still higher with an opportunity than without for every model (General response 1/3).

We hope these changes address your concerns about inputs, presentation and heterogeneity. We will post a note when the revised PDF, with changes colour-marked, is uploaded before the discussion closes. If these changes resolve your concerns, we would appreciate it if you would reconsider your rating.

Comments on the paper

3 comments
AuthorsOpenReview ↗

General response (1/3): new experiments on semantic composition (E1)

General response (1/3): new experiments on semantic composition (E1)

We thank all reviewers. We are encouraged that reviewers found that the duality turns "a vague concern about composition into a precise and checkable number", with "high confidence that the stated results are correct" (B8nN). 89us noted the "theoretical insights" into information flow, and wfok called the study "relatively complete".

The shared concerns are three:

  • (A) copying hex strings under a preserve instruction (B8nN, wfok);
  • (B) obtaining the inputs (89us, B8nN);
  • (C) novelty (B8nN, wfok) and presentation (89us, wfok).

We ran three experiments, E1–E3. E1 and E2 use Qwen3-4B/8B/14B, greedy decoding, 2 seeds × 50 trials per cell (Qwen3-8B one seed); E3 uses the paper's logged traces (six panel models) and a retrieval pipeline (Qwen3-4B/14B). Each new table appears once here; individual responses refer to it [Rev: App. R].

E1: semantic tasks with neutral prompts and no preserve instruction. Each closure is one agent answering the user's request from its own notes; there is no handover.

  • Derived code. Record A states a rule ("the keypad code for room R is quantity B plus quantity C"), and records B and C are ordinary notes containing the numbers. The answer is in no record and must be computed.
  • Re-identification. Three records each give one quasi-identifier (day, team, birth year) of a person in a 16-person synthetic directory. Exactly 1 person matches all three identifiers, and 4 match any two.

The system prompt is "Answer the user's request based on the material you were given". All laws have pi=1/3p_i=1/3 (n=9n=9, τ=3\tau=3).

Table G1 (derived code, three models pooled).

archlawexact opp.observed opp.success
windowSPREAD00/2500/250
windowuniform1/124/2504/250
windowindep.395/218731/25031/250
windowBLOCK1250/250250/250
starSPREAD00/2500/250
staruniform1/215/2505/250
starindep.2465/1968335/25034/250
starBLOCK1/3 (hub ceiling)82/25082/250

Counts are per model-trial; placements are shared across models within a seed (100 distinct per row; window-uniform realised 2/100 against 1/12, while the paper's 180 logged uniform traces give 13/180 = 0.072).

  • Same marginals, opposite outcomes: 0/500 under SPREAD vs 250/250 under window-BLOCK (Cor. 4.2), with no copying.
  • No success without opportunity (E1+E2): 0 of 3,495 such trials, and 0 hits in 24,143 agent answers missing a fragment. A single-agent control with one fragment removed gives 0/250.
  • Conversion given opportunity (E1+E2): Qwen3-14B 602/602, Qwen3-8B 301/301, Qwen3-4B 594/602 = 0.987.

Re-identification: the model-dependent second stage.

  • The user query ends "If your notes do not identify a single person, say so instead of guessing". We added this clause to the task after an 8-trial pilot, in which models named someone even with no clue.
  • Successes per trial (E1+E2, Wilson 95% CI). A trial succeeds if any of its 4–7 agents succeeds. Strict (pre-specified): the answer names exactly one person, the target. Concluded (post-hoc): the last name given is the target, with no abstention.
modelmetricwith opp.without opp.
Qwen3-14Bstrict21/602 = 0.035 [0.023, 0.053]6/1398 = 0.004 [0.002, 0.009]
Qwen3-4Bstrict40/602 = 0.066 [0.049, 0.089]39/1398 = 0.028 [0.020, 0.038]
Qwen3-8B (1 seed, 256 tok.)strict43/301 = 0.143 [0.108, 0.187]49/699 = 0.070 [0.053, 0.091]
Qwen3-14Bconcluded302/602 = 0.502 [0.462, 0.541]6/1398 = 0.004 [0.002, 0.009]
Qwen3-4Bconcluded106/602 = 0.176 [0.148, 0.209]40/1398 = 0.029 [0.021, 0.039]
  • Under the pre-specified strict metric, every model succeeds more often with an opportunity than without, and the CIs do not overlap: 0.035 vs 0.004, 0.066 vs 0.028 and 0.143 vs 0.070. The post-hoc concluded metric agrees (0.502 vs 0.004, 0.176 vs 0.029).
  • Strict conversion (0.035–0.143) is the model's stage, which the paper measures separately from opportunity. Qwen3-14B lists candidates before concluding, which strict scoring counts as failure. It has 0/400 in the four cells with no opportunity at all.
  • Success without an opportunity comes almost entirely from agents holding 2 of the 3 identifiers, who face the 4 remaining candidates. Agent hit rates are 0.4% / 1.6% / 4.2% (14B / 4B / 8B). Only Qwen3-4B has hits with at most one identifier (10/5445 agents).
  • The 2-of-3 hits are success under the τ=2\tau=2 objective "narrow to 4 candidates", and Thm 4.1 again gives its range exactly. The τ=3\tau=3 opportunity governs the composition-attributable excess.
  • Derived code: a partial context leaves the answer undetermined, so ASR ≤ opportunity holds exactly.
AuthorsOpenReview ↗

General response (2/3): heterogeneous rates (E2) and rates from execution traces (E3)

General response (2/3): heterogeneous rates (E2) and rates from execution traces (E3)

E2: heterogeneous per-type rates and typed fragments.

  • Each record carries the fragment of its position's type (rule, quantity B, quantity C), so the typed event equals the untyped one; the general typed reduction (Corollary C3, part 3/3) follows from the proof of Thm 4.1.
  • For each rate profile we computed the exact [Floor,Ceil][\mathrm{Floor},\mathrm{Ceil}] from the Theorem 4.1 LP in rational arithmetic, with the floor via the blocker.
  • Laws with exactly these marginals: floor-attaining (min), independent, and ceiling-attaining (max).

Table G2. Exact P(opp) / observed opportunity frequency; 100 trials per cell.

archtype rates[Floor,Ceil][\mathrm{Floor},\mathrm{Ceil}]min lawindep.max law
window1/5, 1/2, 4/5[0, 3/5]0 / 0.000.306 / 0.300.600 / 0.67
window3/10, 9/10, 19/20[3/20, 9/10]0.150 / 0.150.629 / 0.680.900 / 0.89
star1/5, 1/2, 4/5[0, 1/5]0 / 0.000.174 / 0.190.200 / 0.18
star1/2, 4/5, 9/10[1/5, 1/2]0.200 / 0.240.497 / 0.560.500 / 0.51
  • Consistent with the interval. In all 20 E1/E2 cells, the Wilson CI of observed opportunity overlaps the exact interval. Point estimates above Ceil (0.67 vs 3/5; 0.56 and 0.51 vs 1/2) are within sampling error, and both endpoints are attained.
  • Derived-code ASR tracks opportunity.
    • Qwen3-14B equals it in every cell; Qwen3-4B is at most 1/100 below (e.g. window, second profile: 0.15 / 0.67 / 0.88 within [0.15, 0.90]); Qwen3-8B converts every opportunity.
    • There is no success without opportunity in 3,000 E2 trials.
  • Re-identification. Qwen3-14B's per-cell conversion is 0.00–0.06 under the strict metric and 0.39–0.87 under the post-hoc concluded metric (pooled contrast in part 1/3).

E3: loading rates from execution traces. Both endpoints are nondecreasing in pp (Prop. 4.3), so one-sided simultaneous upper bounds uu give a valid certified ceiling CeilG(u)\mathrm{Ceil}_G(u). We use one-sided Clopper–Pearson at level α/n\alpha/n with Bonferroni, valid under any dependence between records.

  • E3-lite (the paper's logged placements, 180 traces per law).

    • Star: the SPREAD/BLOCK traces certify 0.406, or 0.373 with the hub fixed in advance as the defence. The uniform-law traces certify 0.446. The truth is 1/3 and the architecture-blind bound is 1.
    • Pooled frequencies lie below the certificate: star-BLOCK opportunity 56/180 = 0.311, and ASR over the six panel models 327/1080 = 0.303.
    • Single seeds vary (15–23 of 60). One seed reaches 23/60 = 0.383, which is unsurprising for a 60-trial frequency when the true probability is 1/3.
    • Coverage in re-simulation: 0.993–1.000 with full Bonferroni; 0.927–1.000 defence-only. The lowest value comes from 150 resamples and is within Monte Carlo error of 0.95.
    • Window at p=1/3p=1/3: the certificate is 1, which is correct, because the true ceiling is 1 (Cor. 4.2).
  • E3b (a non-designed retrieval pipeline over a synthetic 51-record store).

    • Setup: a router sends sub-queries to 3 workers, and each retrieves its top-4 records by bge-base-en-v1.5. Top-3 never co-located the 3 fragments, so we fixed top-4 before any LLM call.
    • Loading is read from record ids, which the testbed knows. In deployment, an untrusted-source indicator upper-bounds loading (89us 1/2, B8nN 2/3), and Corollary C1 keeps the certificate valid.
    • Closures are 3 blocks of 4 slots with τ=3\tau=3, which is non-ideal.
    • From 300 retrieval-only traces the certificate is 0.94; it covered the true opportunity probability in every resample. At the true rates the exact LP ceiling is 2/3, against a union bound of 0.75, as Thm 5.1 allows for non-ideal families.
    • In 300 held-out sessions opportunity occurred 16/300 times. Qwen3-4B and Qwen3-14B produced the code in exactly those 16 sessions and in 0/284 others.
    • Gap between 0.94 and the true 0.060: most of it is the identification gap (some law with these slot marginals has opportunity 2/3, Thm 4.1). The rest (0.94 vs 2/3) is finite-sample slack, which falls with NN (median certificate 0.80 at N=1000N=1000).
    • Joint evidence: the held-out 16/300 gives a direct one-sided bound of 0.080, using joint observations as in App. A.6. But a direct estimate certifies only the coupling that was observed. The marginal certificate holds for every coupling with these rates, including a future routing or an adversary that re-correlates the same records.
AuthorsOpenReview ↗

General response (3/3): corollaries, novelty, revisions

General response (3/3): corollaries, novelty, revisions

Four operational corollaries [Rev: §4.2, App. C.3], each following directly from results already proved.

  • C1 (monotone plug-in). Ceil and Floor are nondecreasing in pp (Prop. 4.3); Ceil is also monotone in the closure family.
    • If Pr⁡(p≤u)≥1−α\Pr(p\le u)\ge 1-\alpha simultaneously, then with probability at least 1−α1-\alpha, opportunity is at most CeilG(u)\mathrm{Ceil}_G(u). Symmetrically, ℓ\ell gives a floor.
    • For the ceiling, any superset of the closures, such as reach(G)\mathrm{reach}(G), and any upper bound on the rates are safe. A certified floor needs a subset of the closures.
  • C2 (defence-only). For a defence DD fixed in advance, opportunity is at most p(D)p(D). With probability at least 1−α1-\alpha it is at most u(D)u(D), using simultaneous upper bounds on DD's records alone (for the star, the hub).
  • C3 (typed fragments). Use (record, type) units; opportunity sets are the type-complete sets inside a closure.
    • The event is still an up-set generated by a set family, which is all the proof of Thm 4.1 uses, so the ceiling and floor are exact for any monotone composition predicate.
    • Joint constraints (e.g. one type per record) keep them valid, possibly not tight.
    • Thm 5.1 is not claimed for typed families.
  • C4 (no rates needed).
    • If every closure has fewer than τ\tau records, there is no opportunity under any law.
    • A defence whose records are never loaded gives 0.
    • Handover chains reach the full pool (Lemma D.2).
    • Negatively: at some rates (e.g. window, p=1/3p=1/3) no per-record audit can certify anything (Cor. 4.2).

Novelty. (1) is new mathematics; (2, 3) are new results built on classical tools, which make the quantities exact, polynomial-size and verifiable.

  1. Path-factorised (distributed) ceilings, §5.2–5.3. No tool named in the reviews covers this.
    • At uniform rates, a defence read along the path is a Markov chain, which bounds RealG\mathrm{Real}_G by ψm(p)\psi_m(p) (Eq. 5) for any architecture. A block-law lower bound matches it when the disjoint-interval count equals mm, e.g. for windows.
    • Closed-form window ceiling; no loss iff k≤2k\le 2 or p≥1/2p\ge 1/2 (Thm 5.3).
    • Zero slack for the aggregate event on paths (Thm 5.5).
  2. Thm 5.1 as a statement about probability bounds. Idealness is defined by integrality of the cover polyhedron; given Thm 4.1, our statement concerns the two bounds practitioners use:
    • the union bound over one defence and the Fréchet bound over one opportunity set are exact at every marginal vector iff the architecture is ideal, and otherwise each fails at some rate (the Fréchet side is the blocker's union bound, via Lehman);
    • for τ≥2\tau\ge 2, at rates (τ−1)/τ(\tau-1)/\tau on any τ+1\tau+1 records in one closure (0 elsewhere), the true interval is [(τ−1)/(2τ),1−1/τ2][(\tau-1)/(2\tau), 1-1/\tau^2], while both elementary bounds give [0,1][0,1];
    • we did not find this stated for probability bounds.
  3. The floor as the same covering LP on the blocker at 1−p1-p (Thm 4.1). Every ceiling comes with a defence certificate, and every ideal floor with a witness opportunity set.

Closest work: Padmanabhan, Ahipasaoglu, Ramachandra & Natarajan (SIAM J. Optim. 2022; arXiv:2109.01591).

  • They bound Pr⁡(max⁡x∈Xc⊤x≥r)\Pr(\max_{x\in X}c^\top x\ge r) over laws with given marginals. For Bernoulli cc and listed XX, their Thm 2.3 gives a polynomial-size LP for the upper bound, and their Thm 2.5 shows the lower bound is NP-hard, already for graph edges with r=2r=2.
  • With XX the indicators of O\mathcal O and r=τr=\tau, our ceiling agrees with theirs. We add three things:
    • the (n+1)(n+1)-variable cover form, whose dual optimum is an explicit defence certificate;
    • the floor as the covering LP on the blocker, whose possible exponential size matches their hardness;
    • Thm 5.1, which characterises exactly when the floor is one opportunity set's Fréchet bound (polynomial in ∣O∣|\mathcal O|): precisely for ideal O\mathcal O. On their hard instance (graph edges), this means bipartite graphs.

Summary of revisions. [Rev: X] marks where an item will appear in the revised PDF, which we will upload with changes colour-marked before the discussion closes; a note will follow here when it is up.

changewherefor
E1–E3 protocols and tables[Rev: App. R]all
"Obtaining the inputs" (provenance bound, C1)[Rev: §3.2]89us, B8nN
Screening repositioned (Assumption A.6)[Rev: §1, §3.2, §6.5, App. A.3]B8nN
Corollaries C1–C4[Rev: §4.2, App. C.3]89us, B8nN, wfok
"What is new" paragraph; discussion of arXiv:2109.01591[Rev: §1], [Rev: §2]B8nN, wfok
Worked nine-record window example opening §4; notation and results-to-guidance tables; terms defined before first use; intuition after Thm 4.1/5.1/5.3; Fig. 8(a) in the main text[Rev: §4–5]89us, wfok
Long proof sketches of Prop. 5.4/Thm 5.5 to the appendix; one-line idea kept[Rev: §5, App.]89us, wfok

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.