Beating the Transformer Quadratic Wall
Transcript
Made automatically from the audio, so it may contain mistakes. Click a line to play from there.
So when we finally replaced sequential recurrent networks with all the all token attention, I mean it totally unlocked massive GPU training parallelism.
Oh, absolutely. It it changed everything.
Right. But it also slammed us straight into a wall. The quadratic wall. You get this O of N squared scaling for compute and memory, plus, you know, those brutal auto-regressive memory bandwidth bottlenecks.
Yeah, the math is well, it's fundamentally unforgiving. Double the context length, and you literally quadruple the computational complexity.
And the memory footprint.
Exactly.
So welcome back to the deep dive. Since you, our listener, already know the foundations. You've got embeddings, backpropagation, residual connections, and those R and N sequential bottlenecks down, we are entirely skipping the basic definitions today.
Right. No watered down analogies today.
Just the raw mechanical internals of how transformers actually operate. So, okay, let's unpack this. Before we can even compute attention quadratically, we have to define the discrete units that the model is well, actually attending to, right?
Yeah, exactly. The subword tokenization substrate. Because if you feed it raw characters, the sequence becomes just impossibly long.
Which hits that quadratic memory wall instantly.
Right. But if you use whole words, your embedding matrices explode in size. And, you know, you inevitably hit out of vocabulary failures during inference when the model sees a word it wasn't explicitly trained on.
So we need subwords. Mm-hmm. And the sources go pretty deep into bytepair encoding, word piece, and unigram. I mean, BPE is heavily prevalent, right? Especially in the GPT models.
It is, yeah. BPE basically works from the bottom up. So you start with individual characters, or bytes usually, and you just iteratively merge the most frequent adjacent pairs in your training data.
So if E and R appear together constantly, they just become a single token.
Precisely. And you just keep merging until you hit your target vocabulary size, like GPT-2's fifty thousand two hundred and fifty-seven.
And because GPT2 uses byte-level BPE, starting with the 256 base byte values, you mathematically guarantee that it can process literally any text string. No unknown tokens ever.
Yeah. That byte level fallback is crucial. Then you have word piece, which Bert uses. It looks similar, but instead of just raw frequency, it evaluates the statistical likelihood.
Wait, how is that different from frequency?
Well, it actively calculates whether merging two specific tokens will actually increase the probability of the training data overall. So it's looking for highly informative merges, not just like common ones.
Oh, okay, I see. But then Unigram comes in and it's it's like a totally different paradigm.
It really is. Unigram works top down.
Right. It starts with a massive candidate pool and then prunes away the tokens that contribute the least to the overall loss. But okay, let me push back on this a bit. Sure. Because BPE rigidly applies these deterministic merge rules, but Unigram uses probabilistic sampling during training to chop up words differently each time. Doesn't that randomness just introduce noise?
You'd think so, but it's actually an advantage that probabilistically sampling different valid subword splits acts as a really powerful form of subword regularization.
Regularization. So it forces the model to learn the underlying math of the roots and affixes.
Exactly. It's mathematically vital for highly agglutinative languages. Take Turkish, for example. Right. In Turkish, a single long word might represent a complex sentence in English. By probabilistically splitting it during training, the model learns the vector representation of the root, the tense, the plural marker, all independently.
So it can essentially synthesize completely novel grammatically correct words just from those learned components.
Yeah, it's incredibly robust.
Okay. So we've chopped our data into subword IDs, map them to dense embeddings. Now we get to the internal mechanics. The tokens have to interact in a continuous mathematical space.
Right. They get projected into the QKV subspaces.
Query, key, and value. And we're avoiding analogies here. So mechanically, the token embeddings are just multiplied by three separate learned weight matrices, right?
That's right. And the scaled dot product attention computes a weighted sum of the value vectors. That weight is determined by the dot product of the query vector with all the key vectors.
But the formula divides that dot product by the square root of the dimension size. Why do we need that scaling factor? Why not just the raw dot product?
It's to stabilize the gradients.
If your dimension size is large, those raw dot products can grow into huge numbers.
And those feed directly into a softmax function.
Exactly.
And when you feed massive numbers into a softmax, it pushes the output into regions where the gradient is, well, basically zero.
Right. The vanishing gradient problem. The backpropagation just stops.
Yeah. So scaling by the square root of the dimension size keeps the variance stable. And of course, we don't just do this once. We use multi-head self-attention.
Right. So multiple QK and V weight matrices operating in parallel, allowing the model to jointly attend to different representation subspaces at the same time.
Precisely. But in decoder blocks, we have to enforce causal masking.
Because it's auto-regressive. You can't let the queries attend to subsequent future key positions. Or was mathematically cheating.
Right. So the attention matrix is strictly masked. We set the future token positions to negative infinity before the softmax.
So the softmax turns that negative infinity into a literal zero probability. You physically severe the mathematical connection to the future.
Exactly.
Okay, here's where it gets really interesting. QKV allows for these complex spatial relationships, but the matrix multiplication itself is permutation invariant.
Yes. The core math doesn't care about sequence order at all.
Right. If we shuffle all the tokens into sentence, the dot products are identical, just in a different order. So how do we enforce sequence order? The original transformer used sinusoidal positional encoding, right? Adding sine and cosine waves to the embeddings.
It did, yeah. But that additive method struggles heavily with long context extrapolation.
Because when you push past the sequence length it saw during training, those absolute positional additions just look like mathematical noise.
Exactly. Which is why the industry shifted to rope, rotary position embedding.
So how does rope replace the additive encoding?
Instead of adding a value, rope multiplies the key and query matrices by a rotation matrix in Euclidean space. The angle of that rotation is directly proportional to the position index.
Oh wow. So when you take the dot product of a query and a key that have both been geometrically rotated, the absolute angle just cancels out.
Yes. The resulting math explicitly encodes the relative position dependency directly within the dot product itself.
That is mathematically brilliant. Right. And it naturally decays intertoken dependency as the relative distances increase, just like real language.
It's a much more elegant solution for long context windows.
But wait. If rope solves the mathematical representation of relative distance, does it actually solve the hardware constraint of processing those longer distances?
Unfortunately, no. The math works, but the auto-regressive bottleneck is still there.
Right, because in a decoder, recomputing QK and V for every past token at every single generation step results in that catastrophic O of N squared recomputation.
It's completely unscalable.
Which is why we have to use KV caching. So instead of recomputing, KV caching stores the past computations. It turns that O of N squared recomputation into linear reads from high bandwidth memory or HBM.
Correct. But KV caching introduces its own nightmare, massive memory footprint issues.
Right, because it grows with every single token you generate, multiplied by the batch size. Under high concurrency, that's what leads to those out of memory or OOM crashes.
Exactly. So engineers have to rely on different caching strategies. Like you can use dynamic cache, which just grows as you generate.
Or it static cache, which preallocates the maximum size up front, which is great because it allows for just in time compilation, like with torch.compile.
But you end up wasting huge amounts of VRAM on short sequences because you pre-allocated for the max length.
Yeah, that's a huge trade-off. What about offloading?
You can offload the cache to the CPU to avoid OOM crashes, sure. But the latency across the PCIe bus severely degrades throughput.
So instead of just moving the cache around, what if we shrink its architectural footprint? That's where grouped query attention comes in, for right? GQA?
Yes. GQA is the optimal middle ground here.
Because multi-query attention uses a single key value head for all query heads, which hurts quality. But multi-head uses a dedicated KV head for every query head, which kills memory.
Right. So GQA uses an intermediate number of key value heads. Yeah. You get generation quality that's remarkably close to full multi-head attention, but with a much smaller memory footprint and faster inference speed of multi-query attention.
And the most incredible part from the papers is that existing models can be uptrained to GQA using just 5% of their original pre-training compute.
It's a massive efficiency gain. But even with GQA reducing the KV footprint, simply moving the required memory back and forth between the GPU's memory tiers creates this huge latency wall.
The IO wall.
Exactly. Standard attention requires excessive reads and writes to the GPU's high bandwidth memory.
Which brings us to flash attention. The missing principle here is basically I/O awareness, right?
That is exactly it. To compute attention normally, the GPU has to load Q, K, and V from the slow HBM into the fast on-chip SRAM. Compute the scores, write them back to HBM, read them again for the softmax.
Write them back again, read them again to multiply by V. It's just a constant bottleneck of memory transfers.
Right. So flash attention uses a technique called tiling. It computes the exact attention within the much faster, smaller on-chip SRAM by processing the matrices in small blocks or tiles.
So it does the dot product, the softmax, and the value multiplication all on chip for that block and only writes the final output back to HPM.
Exactly. It drastically reduces those memory read-write cycles.
And we should clarify, unlike previous sparse attention methods that traded quality for speed, flash attention is exact. There is no approximation happening.
None at all. It yields massive wall clock speedups. I mean, they saw a 3x speed up on GPT 2.
Wow. And it enables wildly longer contexts too, like achieving better than chance accuracy on the 16k sequence path X challenge.
Yeah, if we connect this to the bigger picture, optimizing memory I.O. fundamentally alters what these models are capable of achieving in production.
Which really brings us to the decision boundaries. Understanding these internal mechanics, the masking, caching, I.O. scaling, it completely dictates how you deploy these architectures in practice.
It really does. You have to look at the trade-offs between bidirectional encoders like the BERT class models and causal decoders like the GPT class.
Right. BERT uses bidirectional conditioning with masked language modeling. It predicts 15% hidden words by looking at both the left and right context simultaneously.
Which makes it ideal for tasks like sentence classification, fact checking, or feature extraction. It sees the whole sequence at once.
But decoder only models are built strictly for auto-regressive generation.
Yes. They are constrained by the causal mask, so they excel at predicting the next token.
So what does this all mean for you, the listener? Well, your choice of architecture and specifically your target context length directly dictates your hardware V RAM budget.
Absolutely.
If you deploy a causal decoder, you must account for the KV cache footprint. You have to utilize tools like flash attention and GQA just to survive the quadratic wall in production.
You can't just look at the parameter count anymore. The context length and the batch size will crash your servers if you aren't optimizing memory I.O.
Yeah. The mechanical constraints are unavoidable.
Although I do want to leave you with one final unexplored concept from the source material.
Oh. What's that?
Well what if the future of long context isn't just optimizing the attention matrix, but entirely bypassing it.
Wait, really? Bypassing self-attention?
Yeah. Models like KNNLM and SPAM, they actually interpolate transformer predictions with an external non-differentiable key value data store.
Oh wow. So instead of fighting quadratic scaling by forcing everything into the attention mechanism, we might just hook transformers up to infinite vector databases, like a search engine?
Exactly. You outsource the long-term memory retrieval. It's a radical shift from everything we just discussed.
That is an incredible thought to end on. Thank you for joining us in the deep end of the math and mechanics today. Hopefully this helps you think critically about the hardware and architectural constraints of the models you use every day. We'll see you in the next deep dive.