Decomposition Attacks Across Unlinkable Identities: Limits of Stateful Defenses for LLM Services

TL;DR - This paper establishes fundamental limits on stateful defenses against harmful LLM requests decomposed across unlinkable identities. Without reliable request grouping—and especially when attackers can retry—tested defenses cannot stop attacks while maintaining low denial rates for benign traffic.

• Security and utility depend on whether related benign and malicious requests can be grouped: persistent, recognizable groups enable defense, while fresh, indistinguishable identities do not.
• Allow/Block feedback lets retrying attackers learn which requests pass, eliminating the useful operating point identified for fixed, single-attempt attacks.
• Across 91 executable tasks and 11,393 capability-matched benign requests, all ten policies either failed to stop attacks or exceeded denial budgets.
• On unseen task families, attack success reached at least 99% after one attempt and 100% after two, indicating that effective defenses need identity linkage, fresh-identity costs, or control over answer use.