Understanding the Parameter Space Geometry of Transformers Encoding Boolean Functions

Transformers consistently fail to learn certain simple functions that are provably expressible with specific parameter settings. This gap between learnability and expressivity is particularly prominent for sensitive functions---functions whose output is likely to change if a single bit of the input is flipped---for example, Parity. While prior work has established that transformers exhibit a bias toward functions with low average sensitivity, the precise mechanism underlying this bias remains poorly understood. To shed light on this phenomenon, we study the geometry of transformers' parameter space. We show that sensitive functions---even when representable---occupy a vanishingly small region that random initialization is very likely to miss. Specifically, we shift the focus from average sensitivity to the full sensitivity profile---the distribution of sensitivity values across all inputs---and prove that randomly initialized transformers almost surely compute functions which have low-sensitivity strings. Consequently, any function that lacks such strings is provably unlearnable.

Large language models (LLMs) such as ChatGPT are built on a technology called transformers. While researchers have shown that transformers can theoretically handle many kinds of tasks---such as checking whether a word appears more often than another in a sentence, or detecting some other pattern in a text---they often fail to learn them in practice, even with plenty of training data. A striking example is the Parity function: deciding whether a binary string has an even or odd number of ones. Transformers can represent this function in principle, yet consistently fail to learn it. We explain this mystery by studying the space of all possible ways a transformer can be configured---think of it as a vast mountainous terrain, where each point in the landscape represents a model with a slightly different behavior. We prove that almost the entire terrain corresponds to models that are highly insensitive to individual input changes, and that the region encoding sensitive functions like Parity is a tiny, hidden valley. A randomly initialized transformer almost surely lands far from this valley, and training cannot easily navigate there either. Our framework predicts which functions are learnable and which are not, and our experiments confirm these predictions. This gives researchers a tool for understanding---and anticipating---the blind spots of the transformers behind modern LLMs before deploying them.