Decomposition Attacks Break Stateful LLM Defences at Scale

Problem

The paper studies decomposition attacks against language-model services: attackers split a harmful task into many individually permissible requests, obtain answers, and combine them off service to realise the harmful capability. Stateless defences that judge only the current request cannot detect such compositions. Stateful monitoring can succeed only if it can group the requests that will be recombined; attackers using unlinkable identities and off-service pooling break that grouping signal. The work asks whether stateful defences can still stop decomposition attacks when attackers can submit requests through fresh, unlinkable identities and learn from Allow/Block feedback, and it quantifies the resulting security–utility tradeoffs.

Approach

The authors develop a formal threat model distinguishing visible linkable groups (what the service can see) from access coalitions (who actually combines answers off service). They analyse an ideal defender that sees the full visible request trace and optionally an oracle mapping requests to exact provided capabilities. The theory derives exact frontiers for the achievable tradeoff between attack success and benign-request denial under fixed strategy and under retry with feedback. Empirically, they build an executable benchmark: 91 protected tasks that a service refuses, 365 distinct operations those tasks require, and 11,393 certified benign requests that each provide the same operations as attack fragments. They replay many legal groupings, permit retries, and evaluate a suite of practical defences plus adaptive attackers that learn from simple Allow/Block bits (UCB1 and Thompson sampling).

Key Findings

• Grouping determines the frontier: if benign requests for the same capability recur in recognisable, persistent visible groups while attack fragments arrive through fresh groups, a defender can achieve low attack success with low false denial; if benign requests also arrive through fresh indistinguishable groups, meaningful separation is impossible without higher benign denial.
• Retry plus feedback removes the favourable operating point: when attackers may retry and observe Allow/Block decisions, adaptive learners using only that binary feedback reach very high attack success (Thompson sampling achieved 99.4% ASR), while a fixed-profile attacker achieved about 47.2% ASR in the same setting.
• Empirical defences fail under realistic caps: with utility caps of 1% matched-control denial and 0.5% background block rate, all ten tested policies, including a privileged policy with exact request-to-operation mapping, either failed to stop attacks or exceeded the budget. On defence-unseen task families, attack success was at least 99% after one attempt and 100% after two.
• Idealised limits and combinatorics: robustly preventing all completions requires blocking a hitting set of request occurrences; the paper relates this to the transversal number of the completion hypergraph and gives exact expressions for one-attempt and retry-limited settings.

Limitations

Results are conditional on the observation boundary: the defender only sees request bodies, visible group labels and metadata, and previous decisions; output text, embeddings or other post-request signals that are causal transforms of that trace do not reveal off-service pooling. The benchmark uses synthetic executable cyber-programming tasks in a sandbox, frozen screening models and constructed benign controls; this provides reproducible mechanism evidence but does not measure real-world prevalence of off-service pooling or account-linkage practices. Some benign controls originally shared a construction prefix that could leak source, though ablations removed that artifact.

Implications

Offensive implications: an attacker can reliably assemble harmful capabilities by distributing decomposition requests across unlinkable identities and learning which request formats pass via Allow/Block feedback; practical learners achieve near-certain success. Therefore, attackers need only simple binary feedback and modest retry budgets to bypass stateful monitors that lack independent grouping signals. Effective defence therefore requires mechanisms that provide independent evidence of pooling or constrain answer use, for example reliable identity linkage, costs for obtaining fresh identities, scoped authorisation, trusted execution/provenance of answers, rate limits, or control over how outputs are executed; without one of those, grouping-based defences cannot both keep benign denial low and stop adaptive decomposition attacks.