🤖 machine learning

Understanding the Parameter Space Geometry of Transformers Encoding Boolean Functions

This paper explains why transformers fail to learn sensitive Boolean functions like PARITY by demonstrating that such functions occupy a vanishingly small region in the parameter space, as random initialization almost surely leads to models that compute functions containing low-sensitivity strings, which sensitive functions inherently lack.

Original authors: Blanka Köver, Alexandra Butoi, Anej Svete, Michael Hahn, Ryan Cotterell

Published 2026-06-09

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Blanka Köver, Alexandra Butoi, Anej Svete, Michael Hahn, Ryan Cotterell

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a Transformer (the type of AI behind many modern chatbots) as a giant, complex maze made of adjustable dials and knobs. This maze is the "parameter space." When we train a Transformer, we are essentially trying to find a specific path through this maze that solves a particular puzzle, like determining if a string of 0s and 1s has an even or odd number of 1s (a task called PARITY).

The paper asks a simple but profound question: Just because a path exists in the maze, does it mean we can actually find it?

Here is the breakdown of their findings using everyday analogies:

1. The "Needle in a Haystack" Problem

The authors discovered that for certain tricky puzzles (like PARITY or the "FIRST" function, which only cares about the very first bit), the correct settings for the Transformer's dials are hidden in a vanishingly small region of the maze.

The Analogy: Imagine the parameter space is a massive football stadium. The "easy" puzzles (like counting if there are more 1s than 0s, known as MAJORITY) have a solution area the size of a whole field. But the "hard" puzzles (like PARITY) have a solution area the size of a single grain of sand buried in that stadium.
The Result: When we start training a Transformer, we usually pick a random spot in the stadium (random initialization). The odds of randomly landing on that single grain of sand are effectively zero. Even if the math says the solution exists, the training process (which is like a hiker trying to walk uphill) will almost never find it because the target is too small to hit.

2. The "Sensitivity" Meter

To understand why these solutions are so hard to find, the authors looked at something called sensitivity. This measures how much the answer changes if you flip just one single bit in the input.

High Sensitivity (The Hard Puzzles): For PARITY, flipping any single bit changes the answer. It's like a light switch where touching any wire in the room turns the light on or off. The paper calls these "sensitive" functions.
Low Sensitivity (The Easy Puzzles): For MAJORITY, flipping one bit usually doesn't change the answer unless the count is perfectly tied. It's like a voting system where one extra vote rarely changes the winner unless the race is dead even.

3. The "Low-Sensitivity Bias"

The paper's biggest discovery is about the geometry of the maze. They found that if you pick a random spot in the maze (a randomly initialized Transformer), the machine it builds will almost certainly have a "low-sensitivity bias."

The Metaphor: Imagine the maze is designed so that most random paths lead to a machine that is "stiff" or "lazy." This machine ignores small changes in the input. It only reacts when the input changes a lot.
The Consequence: Because the maze is built this way, a randomly picked machine will almost always have "safe zones" (inputs where flipping a bit does nothing).
- MAJORITY has plenty of these safe zones (exponentially many). So, the machine can easily learn it.
- PARITY and FIRST have zero safe zones. Every single input is sensitive.
- The Conflict: The paper proves that for long inputs, a randomly initialized Transformer must have some safe zones. Therefore, it is mathematically impossible for it to learn PARITY or FIRST, because those functions have no safe zones to match. The machine's "shape" simply doesn't fit the puzzle.

4. What Happens After Training?

You might think, "But if we train it hard enough, won't it find the needle?"

The authors ran experiments and found that even after training, the "low-sensitivity bias" often persists.

For MAJORITY: The training successfully finds the large field of solutions. The machine learns the task.
For PARITY: The training tries to push the machine toward the tiny grain of sand, but because that grain is so small (a "measure-zero" set), the training usually fails or gets stuck. The machine never quite learns the true logic of the puzzle.

Summary of the "Rules"

The paper establishes a clear rule based on the length of the input string ( $N$ ):

If a function has very few "safe" inputs (where flipping a bit doesn't change the answer), like PARITY or FIRST, a Transformer will provably fail to learn it as the input gets longer. The solution is too small to find.
If a function has many "safe" inputs, like MAJORITY, the Transformer can learn it because the solution area is large enough to be found by chance and refined by training.

In short: The paper explains that Transformers aren't just "bad" at certain tasks; they are structurally biased against them. The landscape of their learning is shaped like a mountain range where the peaks for "sensitive" tasks are so tiny they are invisible to a random search, while the peaks for "robust" tasks are broad and easy to climb.

Technical Summary: Understanding the Parameter Space Geometry of Transformers Encoding Boolean Functions

Problem Statement
Transformers exhibit a well-documented gap between expressivity (the existence of parameter settings that can compute a function) and learnability (the ability of optimization algorithms to find those settings). While theoretical work has established that transformers can express certain Boolean functions, empirical evidence shows they consistently fail to learn sensitive functions—those where flipping a single input bit is likely to change the output. A canonical example is the PARITY function. Prior work has attributed this to a bias toward functions with low average sensitivity, yet the precise mechanism linking sensitivity to the geometry of the parameter space remains unclear. Specifically, it is unknown whether the unlearnability of sensitive functions arises because they occupy a vanishingly small volume in the parameter space, making them unlikely to be found by random initialization or gradient-based optimization.

Methodology
The authors analyze the geometry of the parameter space $\Theta$ of soft-attention transformers encoding Boolean functions over a binary alphabet. The analysis is divided into two cases based on the layer-norm stabilizing constant $\epsilon$ in the denominator of the normalization term:

Case $\epsilon > 0$ : The authors first establish that when $\epsilon$ is bounded away from zero, the transformer is uniformly Lipschitz continuous with respect to its parameters. This uniform stability implies that the cumulative "blowup" (amplification of input changes) is bounded independently of input length $N$ . Consequently, for sufficiently large $N$ , the influence of flipping any single bit on the output vanishes ( $O(1/N)$ ). This leads to a packing argument showing that the number of recognizable Boolean functions is bounded by a constant independent of $N$ , rendering non-constant Boolean functions asymptotically unrecognizable.
Case $\epsilon = 0$ : This is the primary focus of the paper. Here, the layer-norm denominator can approach zero, potentially causing unbounded blowup. The authors develop a measure-theoretic framework to analyze the probability that a randomly initialized transformer computes a function with specific sensitivity properties.
- Sensitivity Profile: Instead of relying solely on average sensitivity, the authors introduce the sensitivity profile, defined as the distribution of sensitivity values across all input strings.
- Blowup Analysis: They prove that for a fixed input string $x$ , the blowup is bounded with high probability over a random perturbation of parameters, provided the variance of the layer-norm inputs does not become too small.
- Measure-Theoretic Argument: By covering the parameter space with small cubes and applying probabilistic bounds on the blowup within each cube, they extend the result to the entire parameter space. They utilize the first Borel–Cantelli lemma to aggregate these results across all sufficiently large input lengths $N$ .

Key Contributions and Results

Measure-Zero Unlearnability: The central theoretical result (Theorem 4.5) proves that for any sufficiently large input length $N$ , a randomly initialized transformer almost surely computes a function that possesses a significant number of strings with sensitivity zero (specifically, at least $N^{\frac{D-1}{2L} - 5}$ such strings).
Sensitivity Profile Constraint: Consequently, any Boolean function that lacks sensitivity-zero strings (i.e., functions where every input has non-zero sensitivity) occupies a Lebesgue-measure-zero subset of the parameter space.
Unlearnability of Specific Functions: Based on the above, the authors prove that functions such as PARITY, m-SPARSE PARITY, and DICTATOR functions (including FIRST) are provably unlearnable for large $N$ by randomly initialized transformers. These functions have minimum sensitivity $\ge 1$ (or $m$ for sparse variants), meaning they possess zero strings of sensitivity zero.
Distinction from Average Sensitivity: The analysis reveals that average sensitivity is insufficient to predict learnability. For instance, the FIRST function has a low average sensitivity (equal to 1), yet it is unlearnable for large $N$ because it lacks sensitivity-zero strings. Conversely, MAJORITY has a low average sensitivity but possesses an exponential number of sensitivity-zero strings, allowing it to occupy a positive-measure region of the parameter space.
Conjecture on MAJORITY: The authors conjecture that MAJORITY is learnable because its abundance of sensitivity-zero strings corresponds to a positive-measure subset of the parameter space.
Empirical Validation: Experiments on randomly initialized and trained transformers confirm that sensitivity spectra are heavily skewed toward zero. Even after training on tasks like PARITY, models fail to achieve the correct sensitivity profile, whereas models trained on MAJORITY and FIRST (at moderate lengths) successfully learn the tasks and exhibit the predicted sensitivity clustering.

Significance
The paper provides a theoretical explanation for the observed inductive bias of transformers toward low-sensitivity functions. By shifting the focus from average sensitivity to the full sensitivity profile and analyzing the measure-theoretic properties of the parameter space, the authors demonstrate that the unlearnability of functions like PARITY is not merely a failure of optimization but a fundamental geometric constraint: the parameter settings required to represent such functions occupy a set of measure zero. This implies that random initialization will almost surely miss these settings, and gradient-based optimization, constrained by the initialization prior, is unlikely to reach them. The work clarifies the boundary between expressivity and learnability, showing that for sufficiently long inputs, transformers are fundamentally incapable of recognizing languages that lack sensitivity-zero strings.