A Game-Theoretic Analysis of Attacks on Large Language Models via Compositional Skills

Xinbo Wu, Huan Zhang, Abhishek Umrawal, Lav R. Varshney
Proceedings of the 43rd International Conference on Machine Learning, PMLR 306:137513-137543, 2026.

Abstract

As large language models grow increasingly capable, concerns about their safe deployment have intensified. While numerous alignment strategies aim to restrict harmful behavior, these defenses can still be circumvented through carefully designed adversarial prompts. In this work, we introduce a theoretical framework that formalizes a game between an attacker hiding its intent via compositional skills and a defender. Within this framework, we design a theoretical best-response attack strategy and show that it is closely related to many existing adversarial prompting methods. We further analyze the resulting game, characterize its equilibria, and reveal inherent advantages for the attacker. Drawing on our theoretical analysis, we also derive a provably optimal defense strategy. Empirically, we evaluate a practical instantiation of the theoretically optimal attack and observe stronger performance relative to existing adversarial prompting approaches in diverse settings encompassing different LLMs and benchmarks.

Cite this Paper


BibTeX
@InProceedings{pmlr-v306-wu26bz, title = {A Game-Theoretic Analysis of Attacks on Large Language Models via Compositional Skills}, author = {Wu, Xinbo and Zhang, Huan and Umrawal, Abhishek and Varshney, Lav R.}, booktitle = {Proceedings of the 43rd International Conference on Machine Learning}, pages = {137513--137543}, year = {2026}, editor = {Zhang, Tong and Dudik, Miroslav and Jaggi, Martin and Agarwal, Alekh and Li, Sharon and Schuurmans, Dale and Zhu, Jerry and Berkenkamp, Felix and Dong, Hanze and Bietti, Alberto}, volume = {306}, series = {Proceedings of Machine Learning Research}, month = {06--11 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v306/main/assets/wu26bz/wu26bz.pdf}, url = {https://proceedings.mlr.press/v306/wu26bz.html}, abstract = {As large language models grow increasingly capable, concerns about their safe deployment have intensified. While numerous alignment strategies aim to restrict harmful behavior, these defenses can still be circumvented through carefully designed adversarial prompts. In this work, we introduce a theoretical framework that formalizes a game between an attacker hiding its intent via compositional skills and a defender. Within this framework, we design a theoretical best-response attack strategy and show that it is closely related to many existing adversarial prompting methods. We further analyze the resulting game, characterize its equilibria, and reveal inherent advantages for the attacker. Drawing on our theoretical analysis, we also derive a provably optimal defense strategy. Empirically, we evaluate a practical instantiation of the theoretically optimal attack and observe stronger performance relative to existing adversarial prompting approaches in diverse settings encompassing different LLMs and benchmarks.} }
Endnote
%0 Conference Paper %T A Game-Theoretic Analysis of Attacks on Large Language Models via Compositional Skills %A Xinbo Wu %A Huan Zhang %A Abhishek Umrawal %A Lav R. Varshney %B Proceedings of the 43rd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2026 %E Tong Zhang %E Miroslav Dudik %E Martin Jaggi %E Alekh Agarwal %E Sharon Li %E Dale Schuurmans %E Jerry Zhu %E Felix Berkenkamp %E Hanze Dong %E Alberto Bietti %F pmlr-v306-wu26bz %I PMLR %P 137513--137543 %U https://proceedings.mlr.press/v306/wu26bz.html %V 306 %X As large language models grow increasingly capable, concerns about their safe deployment have intensified. While numerous alignment strategies aim to restrict harmful behavior, these defenses can still be circumvented through carefully designed adversarial prompts. In this work, we introduce a theoretical framework that formalizes a game between an attacker hiding its intent via compositional skills and a defender. Within this framework, we design a theoretical best-response attack strategy and show that it is closely related to many existing adversarial prompting methods. We further analyze the resulting game, characterize its equilibria, and reveal inherent advantages for the attacker. Drawing on our theoretical analysis, we also derive a provably optimal defense strategy. Empirically, we evaluate a practical instantiation of the theoretically optimal attack and observe stronger performance relative to existing adversarial prompting approaches in diverse settings encompassing different LLMs and benchmarks.
APA
Wu, X., Zhang, H., Umrawal, A. & Varshney, L.R.. (2026). A Game-Theoretic Analysis of Attacks on Large Language Models via Compositional Skills. Proceedings of the 43rd International Conference on Machine Learning, in Proceedings of Machine Learning Research 306:137513-137543 Available from https://proceedings.mlr.press/v306/wu26bz.html.

Related Material