- 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
- 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.
- 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
-
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?
-
How well do the theoretical bounds predict actual attack success rates in realistic composition-attack scenarios?
4 comments
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 , 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 , 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 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 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).
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.
- 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).
- 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).
- 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 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 ). 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 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.
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).
The problem looks simple, but the simple answers are wrong in identifiable cases, and the paper proves exactly when. Four exact examples:
The formalism is what tells an evaluator which case they are in, and it returns the correct number. Its core is short:
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:
We will add a "what is new" paragraph [Rev: §1] and discuss the closest work, arXiv:2109.01591 [Rev: §2].
On length. The main text has eight formal results, and all lengthy proofs are already in App. B–J. We will make it lighter:
On security insight.
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.