🤖 machine learning

Three Tokens Force Exponential Feature Rank in Nonnegative Kernel Attention

This paper demonstrates that nonnegative kernel attention requires an exponential number of features to solve specific three-token Boolean tasks that full attention or dense softmax can handle efficiently, thereby establishing a fundamental expressivity gap between kernel-based and full attention mechanisms.

Original authors: Vicente Opazo

Published 2026-08-13

📖 7 min read🧠 Deep dive

CC BY 4.0

Original authors: Vicente Opazo

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

The Great Token Showdown: Why "Short and Sweet" Isn't Always Enough

Imagine you are trying to find the perfect match in a crowded room. In the world of artificial intelligence, specifically a field called machine learning, computers do this all the time. They look at a list of items—like words in a sentence or pixels in an image—and try to figure out which ones go together best. This process is often called "attention."

There are two main ways a computer can do this. The first way is like a super-social host who walks up to every single person in the room and shakes hands with everyone, comparing them one by one. This is called "full attention." It's thorough but gets very slow and expensive if the room is huge. The second way is like a host who takes a quick, compressed summary of the whole room—a "sketch"—and then uses that summary to guess who matches with whom. This is called "kernel attention" or "linear attention." It's much faster and designed to handle massive amounts of data, like entire books or long videos.

For a long time, scientists assumed that this "sketch" method was just a slightly less accurate version of the "full" method, but that it would work fine as long as you made the sketch big enough. The big question was: Is there a point where the sketch just cannot do the job, no matter how smart you make it? This paper dives into that question, not by looking at huge, messy real-world data, but by setting up a tiny, very specific puzzle to see exactly where the sketch breaks down.

The Three-Token Trap

The author of this paper, Vicente Opazo, decided to test the limits of these "sketch" models using a game called Min-IP (Minimum Inner Product). Imagine you have a list of secret codes made of zeros and ones. For every code in the list, you have to find the one other code in the list that has the least amount of overlap with it. It's like finding the two people in a room who have the fewest things in common.

The researchers set up a race between two types of AI models:

The Full Attention Model: This model looks at every pair of codes directly. It's like having a magnifying glass for every single comparison.
The Kernel Attention Model: This model tries to solve the puzzle by compressing all the codes into a fixed-size "sketch" (a summary) and then doing the math based on that summary.

The paper asks a simple question: How many codes do you need in the list before the sketch model fails?

The Magic Number is Three

The most surprising discovery in the paper is that the sketch model doesn't fail when the list gets huge. It fails almost immediately.

Length 1 and 2: If the list has only one or two codes, the sketch model is perfect. It can solve the puzzle exactly, even with a very tiny summary (just one "feature"). It's like finding the best match in a room with only two people; it's easy.
Length 3: The moment you add a third code, the sketch model hits a wall. The paper proves that to solve the puzzle correctly for a list of just three codes, the sketch model needs a number of features that grows exponentially with the size of the codes.

To put that in perspective: If your codes are 100 bits long, the sketch model might need billions of features to get it right. If they are 200 bits long, it needs a number so huge it's practically impossible. Meanwhile, the "full attention" model (the one that checks everyone individually) solves the same three-code puzzle easily with a tiny, constant amount of effort.

Why Does This Happen?

The author explains this using a "domino effect" or an "amplification" analogy.

Imagine the sketch model is trying to decide between two candidates, Candidate A and Candidate B.

If the list has only two people, the model just compares A to B. Easy.
If the list has three people (A, B, and C), the model has to compare A against B and A against C.

The paper shows that because the model is forced to compress everything into a single summary, it loses the ability to make a sharp distinction between "very different" and "slightly different." When there are two competing candidates, the model's summary gets confused. To fix this confusion, the model has to make its summary incredibly detailed—so detailed that it basically stops being a summary and becomes a list of every single possibility.

The author proved mathematically that for a list of three items, the number of features required is roughly $2^m$ (where $m$ is the length of the code). This is an exponential explosion. It's the difference between needing a single key to open a door versus needing a key for every possible combination of atoms in the universe.

What About "Signed" Kernels or Multiple Heads?

The paper is very careful to say what it doesn't prove. It focuses on "nonnegative" kernels (where the math only adds things up, never subtracts) and single "heads" (one line of reasoning).

The "Signed" Loophole: If the model is allowed to subtract numbers (use "negative" features), it might be able to bypass the system. The paper says, "We don't know if this approach works for subtraction-based models, but for addition-only models, the wall is real."
The "Multiple Heads" Loophole: If you give the model many different "heads" (many different ways to look at the data at once), they might work together to solve the puzzle. The paper acknowledges this but shows that even then, the total amount of information they need to pass around grows massively.

The Proof and the Experiments

The author didn't just guess this; they proved it mathematically. They showed that for any model trying to solve this specific three-token puzzle with less than a 50% error rate, the number of features must be exponential.

They also ran computer simulations to back this up. They trained AI models on lists of three codes and watched what happened as they increased the "feature rank" (the size of the summary).

Rank 1 to 15: The models failed miserably, making huge mistakes.
Rank 32: Suddenly, the models started getting it right.
This experiment confirmed the theory: there is a sharp "phase transition" where the model suddenly becomes capable once it has enough features to cross the exponential threshold.

The Takeaway

The main lesson here is that speed has a cost, and that cost appears much sooner than we thought.

We often think that linear attention (the fast, sketch-based method) is only a problem when we have too many tokens to process. But this paper shows that the problem isn't the quantity of data; it's the complexity of the choice. As soon as you have a situation where the AI has to choose between two competing options (a list of three), the "sketch" method breaks down unless you give it a massive amount of memory.

In the real world, this suggests that while fast attention models are great for summarizing long documents, they might struggle with tasks that require precise, sharp comparisons between a few specific items. The "full attention" model, while slower, is the only one that can handle these sharp choices without needing an impossible amount of computing power. The paper concludes that the "exponential gap" between the fast model and the accurate model is a fundamental law of how these specific types of AI work, not just a bug that can be easily fixed.

Technical Summary: Three Tokens Force Exponential Feature Rank in Nonnegative Kernel Attention

Problem Statement
The paper investigates the expressive power of kernelized linear attention compared to full self-attention. While full attention explicitly computes $N^2$ pairwise scores, kernel attention compresses a sequence into a fixed-dimensional "sketch" (sufficient statistics) via a feature map, avoiding the pairwise matrix. The central question is whether this compressed, additive representation can replace explicit token-to-token comparison for specific tasks.

The author isolates this question using the Minimum Inner Product (Min-IP) task over Boolean inputs. Given a sequence of Boolean tokens $X = (x_1, \dots, x_N)$ where $x_i \in \{0, 1\}^m$ , the model must compute the target $t_i(X) = \min_{1 \le j \le N} \langle x_i, x_j \rangle$ for every position $i$ . The task focuses solely on the comparison operation, removing complications related to key-value routing or output encoding. The study specifically examines the context length phase transition: how the required feature dimension changes as the sequence length grows from 2 to 3 tokens.

Methodology
The paper employs theoretical lower-bound proofs and controlled experiments to analyze normalized nonnegative kernel attention. The architecture consists of:

Feature Maps: $\phi_Q, \phi_K: \{0, 1\}^m \to \mathbb{R}^r$ inducing a nonnegative kernel $\alpha(x, z) = \langle \phi_Q(x), \phi_K(z) \rangle \ge 0$ .
Attention Mechanism: A normalized weighted sum of values $v(x_j)$ , where weights are determined by the kernel.
Readout: An arbitrary query-dependent affine map applied to the attention output.

The theoretical approach relies on three main techniques:

Gap Domination: Proving that for a model to succeed with error $< 1/2$ on sequences of length $n \ge 3$ , the kernel weight for a "better" candidate (lower inner product) must strictly dominate the weight of a "worse" candidate by a factor dependent on the gap in their overlaps.
Amplification: Iterating this domination condition over intermediate Boolean overlaps to exponentially amplify the required ratio between kernel weights.
Rank Lower Bounds: Utilizing a constant-weight code and an approximate identity lemma to convert these weight ratios into a lower bound on the feature dimension $r$ .

Additionally, the paper derives a finite-precision information bound for deterministic multilayer sketch models with finite-alphabet cross-token channels, proving a transcript lower bound linear in the number of independent answers and logarithmic in their alphabet size.

Key Contributions and Results

Sharp Three-Token Phase Transition:
- Length 1 & 2: A rank-1 normalized kernel attention head is sufficient to solve Min-IP exactly for sequences of length up to 2. At length 2, the query has only one cross-token candidate, allowing a simple average to retain sufficient information.
- Length 3: For sequences of length 3, where a query must choose between two competing candidates, any single normalized nonnegative kernel-attention head achieving error strictly below $1/2$ requires $2^{\Omega(m)}$ features.
- This lower bound holds even with arbitrary finite-dimensional token values, arbitrary query-dependent affine readouts, position-dependent token maps, and causal final-query formulations.
Comparison with Dense Softmax:
- Dense softmax attention solves the same length-3 task using only $m$ -dimensional scores and constant temperature.
- The paper demonstrates that the exponential feature requirement is specific to the nonnegative kernel constraint. A dense softmax implementation effectively exposes all pairwise comparisons, whereas the kernel approach attempts to compress them.
- The lower bound approaches the exact $2^m$ feature realization as the fixed context length grows, nearly matching the theoretical endpoint for exact positive-feature realizations.
Finite-Precision Information Bound:
- For broader deterministic multilayer sketch models (multiple heads/layers) with finite-alphabet cross-token channels, the paper proves that the total communicated information (transcript) must scale as $q \log_2(s+1)$ bits, where $q$ is the number of independent answers and $s$ relates to the alphabet size. This establishes that even with multiple heads, the total information capacity must grow to solve these tasks.

Experimental Validation
The author conducted experiments on finite families of length-3 sequences:

Witness Suite: Training models on a constructed family of 1,272 inputs derived from 24-bit vectors. Results showed that models with feature rank $r < 8$ failed to solve the task (error $> 0.80$ ), while models with $r=32$ solved it exactly. This aligns with the theoretical lower bound of $r \ge 8$ for the specific construction used.
OOD Scaling: Experiments on larger, disjoint training/testing pools showed a sharp transition in exact-sequence accuracy as feature dimension increased. The transition point shifted from $r=8$ to $r=16$ to $r=64$ as the problem scale increased, while dense attention remained exact across all seeds.

Significance and Claims
The paper claims that the limitation of kernel attention is not merely a consequence of compressing long contexts, but a fundamental obstruction that appears at the very first context length containing two competing candidates.

The separation is unconditional (not relying on complexity conjectures like the Orthogonal Vectors Conjecture).
The result highlights that nonnegativity is a critical constraint; signed kernels or multiple heads can circumvent this specific rank bound by canceling terms or specializing.
The work provides a rigorous theoretical justification for why linear attention mechanisms may struggle with tasks requiring explicit comparison of multiple candidates, even in short contexts, unless the feature dimension scales exponentially with the token dimension.

The author explicitly notes that their theorem applies to single-head, nonnegative kernel attention with affine readouts. They do not claim that all linear attention models are incapable of these tasks, but rather that the specific mechanism of compressing via nonnegative features into a fixed sketch faces an exponential barrier for Min-IP at length 3.