Provably Overwhelming Transformer Models with Designed Inputs
Lev Stambler, Seyed Sajjad Nezhadi, Matthew Coudron · 2025
Read Provably Overwhelming Transformer Models with Designed Inputs by Lev Stambler, Seyed Sajjad Nezhadi, Matthew Coudron (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2502-06038.txt.
Introduction
Lev Stambler, Seyed Nezhadi, and Matthew Coudron prove in 2025 that a crafted prefix can blind a transformer model to everything after it. They call a model overwhelmed when, past the fixed prefix, its output ignores any added text up to a set length. Their method turns a given trained model plus prefix into a formal proof of that blindness, at modest computing cost.
Along the way they prove a strong form of signal squashing inside the model, which bounds its behavior. Tests ran on a small one-layer model with modern parts, they report. Proven blindness is a stepping stone, the authors argue, toward guarantees about trained models that a regulator could check, not just vibes from sample outputs.
Catalog record
| CREATOR | Lev Stambler, Seyed Sajjad Nezhadi, Matthew Coudron |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 64 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2502-06038
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Provably Overwhelming Transformer Models with Designed Inputs Lev Stambler, Seyed Sajjad Nezhadi, Matthew Coudron Abstract We develop an algorithm which, given a trained transformer model ℳ \mathcal{M} as input, as well as a string of tokens s s of length n f i x n_{fix} and an integer n f r e e n_{free} , can generate a mathematical proof that ℳ \mathcal{M} is “overwhelmed” by s s , in time and space O ~ ( n f i x 2 + n f r e e 3 ) \widetilde{O}(n_{fix}^{2}+n_{free}^{3}) . We say that ℳ \mathcal{M} is “overwhelmed” by s s when the output of the model evaluated on this string plus any additional string t t , ℳ ( s + t ) \mathcal{M}(s+t) , is completely insensitive to the value of the string t t whenever length( t t ) ≤ n f r e e \leq n_{free} . Along the way, we prove a particularly strong worst-case form of “over-squashing” ( Alon & Yahav, 2021 ; Barbero et al., 2024 ) , which we use to bound the model’s behavior. Our technique uses computer-aided proofs to establish this type of operationally relevant guarantee about transformer models. We empirically test our algorithm on a single layer transformer complete with an attention head, layer-norm, MLP/ReLU layers, and RoPE positional encoding. We believe that this work is a stepping stone towards the difficult task of obtaining useful guarantees for trained transformer models. 1 Introduction Decoder-only transformers ( Vaswani et al., 2023 ) have become an enormously popular paradigm in the past few years ( Team, 2024 ; OpenAI, 2024 ; Li et al., 2022 ) . Yet, our theoretical understanding of these models remains limited. Proving mathematically rigorous statements about transformers face challenges due to the high dimensionality and complexity of transformers. To circumvent these problems, current techniques either require simplifying assumption or very specific restrictions on the model/ dataset. In this work we propose a different approach focused toward producing rigorous and operationally relevant guarantees for specific, trained, transformer models. That is, we ask the question: Can we develop an algorithm which can provably bound the behavior of a specific trained transformer model? With this motivation in mind, we design a class of algorithms which can prove when a particular type of “ over-squashing ” phenomenon occurs in a trained transformer model. Over-squashing is a known phenomenon in graph neural networks (GNNs) in which the representation of distinct nodes becomes arbitrarily close as the number of layers grows ( Alon & Yahav, 2021 ; Barbero et al., 2024 ) . Recently, Barbero et al. ( Barbero et al., 2024 ) have shown that over-squashing occurs in the limit for a transformer model without positional embeddings. Over-squashing on its own is an important phenomenon. Yet, it does not directly constrain the model’s output behavior. In this work, we focus on a specific related phenomenon, which we call “overwhelming”. A model is “overwhelmed” by an input string if the model’s output is unchanged by concatenating with any new string of tokens of a fixed length. Definition 1.1 (Overwhelm, Overwhelmed, Overwhelming) . For a given transformer model \mathcal{M} , string of tokens s of length n_{fix} , a fixed final token q 1 1 1 We find it convenient to fix the final token due to its importance in determining the output logits for the transformer architecture. We refer to the final token as the “query token.” , and integer n_{free} we say that \mathcal{M} is “overwhelmed” by s if the output of the model evaluated on s plus any additional string t and fixed final token q , \mathcal{M}(s+t+q) , is the same regardless of the value of the string t whenever length( t ) \leq n_{free} . In this work, we provide concrete algorithms ( algorithm 1 , algorithm 2 ) which can produce a proof that a given token sequence overwhelms a given model, as stated in theorem 1.2 and theorem 1.3 respectively. Our algorithms work in two stages: first we upper bound a quantity which we call worst-case deviation (denoted by \mathcal{W} ), which bounds the extent to which the logit weights output can vary. Second, we lower-bound a quantity which we call peak-to-peak difference which measures the difference in the maximum and second maximum logit weights output by the model. We thus get our first main result: Theorem 1.2 (Formally restated in theorem 4.5 ) . If Algorithm 1 returns “Overwhelmed” when run on a transformer model \mathcal{M} , with a fixed input string of tokens s , final token q , and context length n_{ctx} then \mathcal{M} is, provably, overwhelmed by s . Proving “overwhelming” for transformer models can have many interesting and useful applications. For example, discovering overwhelming strings can be used to find examples of model hallucination. If a fixed string causes the output to disregard even a small set of input tokens, the model will produce the wrong result for highly sensitive functions such as parity and finding bugs in code. Additionally, overwhelming strings can be used to “jailbreak” models by forcing the model to ignore part of the system prompt. Discovering these instances can be relevant in performing safety evaluations of models. Another application would use overwhelming strings to prove no-go results for prompt engineering: no “prompt” of a fixed length can equip a model \mathcal{M} to properly compute a specific function, such as parity. Here the prompt will be the free string and the function input the fixed “overwhelming” string. Finally, we can also use the frequency of overwhelming strings to define a sort of “model complexity” for a given context length; the less overwhelming that occurs for a given context window, the more “powerful” a model is for that context window. Next, we design algorithm 2 , to achieve performance improvements in a restricted setting in which the n_{free} tokens are chosen from the permutation set of a single string (as opposed to arbitrary tokens). This restricted setting is of practical interest because it often occurs with much shorter “overwhelming” strings. Furthermore, the ability of a transformer to distinguish between different permutations of the same string is relevant in many real-world applications. For example, if an LLM cannot distinguish between the two strings in fig. 1 , then, the model cannot identify the variable a as being defined before it is used. ⬇ # Code snippet def my_func (): … a = 1 b = a + 1 … ⬇ # Code snippet def my_func (): … b = a + 1 a = 1 … Figure 1 : Two snippets of code that are identical except for the order of the assignment statements. Theorem 1.3 (Formally restated in theorem 5.2 ) . If algorithm 2 returns “Overwhelmed” when run on a transformer model \mathcal{M} , with a fixed input string of tokens s , permutation string x , query token q , and context length n_{ctx} then \mathcal{M} is, provably, overwhelmed by s when the free string is restricted to be a permutation of x . We focus on single-layer transformers in this paper.