Brian Reed: Eliza, hey — I want to start with something that made me feel a little stupid this week, if that's okay.
Brian Reed: I kept seeing 'quadratic scaling' in everything I was reading and I was nodding along like I understood it. And then someone asked me to actually explain it and I — let me see — I said something like 'it gets more expensive faster than you'd expect.' Which is technically true and also completely useless.
Eliza Ward: Okay, but here's the concrete version. Take a transformer — the architecture from Vaswani et al., 2017, 'Attention Is All You Need.' The mechanism compares every token to every other token. So for n tokens you have n-squared comparisons. Double n, you don't double the comparisons — you quadruple them. Double again, quadruple again. That's what O(n-squared) means in practice: the cost grows with the square of the length.
Brian Reed: So doubling the context window quadruples the compute bill. Not doubles — quadruples.
Eliza Ward: Both compute and memory, yeah. And this is why GPT and BERT — once they demonstrated what scaled attention could do — also demonstrated the ceiling. You could see the power and the bottleneck in the same systems.
Brian Reed: The part I don't get is — why can't you just build a faster chip and outrun it? I mean, that's been the answer to most hardware problems for decades.
Eliza Ward: Because — and this is the thing that actually reframes everything — attention is memory-bound, not compute-bound. The constraint isn't the arithmetic speed of the chip. It's the speed at which you move data between different kinds of memory. A faster processor doesn't fix a data-movement problem.
Brian Reed: Wait, so the bottleneck isn't what I thought it was at all.
Eliza Ward: It's not a temporary engineering gap. It's a structural mathematical property of how transformers read text — and that's what makes this genuinely hard to escape.
Brian Reed: Okay but — so give me the room version. Like, what does this actually look like if I'm not staring at an equation?
Eliza Ward: Picture a group chat — except everyone in the room has to personally compare notes with every other person before anyone can speak. Every single pair. You add one more person, that's not one more conversation — it's new conversations with everyone already there.
Brian Reed: Double the people, quadruple the conversations.
Eliza Ward: Exactly. That's the n×n score matrix. Every token paired with every other token. Vaswani et al. built this into the architecture in 2017 — the queries and keys get compared via dot product, you rescale by one over the square root of d_k to stop softmax from collapsing at high dimensions, normalize, then weight your values. The matrix is not optional. It's the output.
Brian Reed: But wait — wasn't that the whole point? Like, wasn't the matrix the feature?
Eliza Ward: Yes. That's — yeah, actually, that's the exact right question. The all-pairs comparison is why transformers crushed RNNs. RNNs avoided the quadratic cost, but they had limited long-range memory, optimization difficulties — you couldn't really reach across a long document. Vaswani et al. said: fine, we'll pay the quadratic price and get global context in one layer. That was a deliberate bargain.
Brian Reed: So the thing that made it powerful is the same thing that makes it expensive. Not accidentally — by design.
Eliza Ward: By design. And the score matrix is what makes it structural math, not a gap you close with better chips. Think about a researcher loading a thousand-page trial transcript into a model — every sentence checking in with every other sentence. At 100,000 tokens, that matrix is ten billion pairs. The hardware isn't slow. The math just requires that many comparisons.
Eliza Ward: Ten billion pair-wise comparisons. And then — this is the part people miss — FlashAttention, Tri Dao's tiling approach from 2022, it reduces the memory footprint to linear for the attention step. People hear 'linear' and think the problem is solved.
Brian Reed: It's not, though. The inference latency — the time cost — that's still quadratic in most real deployments, right? Memory got smaller, the computation didn't.
Eliza Ward: Right. FlashAttention is a genuine systems win — it tiles the matrix into blocks that fit in fast on-chip SRAM, never writes the full n×n out to high-bandwidth memory. Real speedup. But the mathematical complexity class is unchanged. O(n²) is O(n²). That's what Mamba and the state-space models are actually trying to escape — not just the memory cost, the math itself.
Brian Reed: But hang on — I want to stay on that word 'linear' for a second, because I think that's where the confusion actually lives. Tri Dao's 2022 paper, FlashAttention — the tiling approach — it reduces the memory footprint for the attention step to linear. And I get why people stop there. Linear sounds like the problem is gone.
Eliza Ward: The memory problem got smaller. The latency problem didn't.
Brian Reed: Walk me through why not, because — I mean, I keep wanting to say: if you're not writing the full n×n matrix to HBM anymore, shouldn't inference get faster too?
Eliza Ward: Okay, the tiling is real — FlashAttention tiles the computation into blocks that fit inside SRAM, avoids writing the full matrix out to high-bandwidth memory, and that does yield wall-clock speedup. Real speedup, not theoretical. But — wait, here's what doesn't change — every new token the model generates still has to attend to every prior token. The math is still quadratic. You just stopped paying the I/O penalty on every read-write to HBM. You didn't remove the reads.
Brian Reed: The part I don't get — so a faster GPU just makes the arithmetic faster. You still move the same volume of data?
Eliza Ward: The ceiling shifts. The scaling class doesn't.
Brian Reed: Okay. So — let me try to make this concrete, because I think it's actually more brutal than it sounds in the abstract. Say it's eleven PM, a paralegal is running a 200-page contract through a long-context model. She's asking it to flag indemnification clauses. Every sentence the model generates—
Eliza Ward: —requires attending back through the full cached document. That's the KV cache. Every prior token's key and value vectors are stored, and each new generated token has to reach across all of them. The cache grows with every output word.
Brian Reed: And FlashAttention doesn't touch that.
Eliza Ward: No. The KV cache is a separate and compounding pressure. Memory for the cache grows linearly with tokens, that part's manageable — but the cost per new token scales with context length. So by the time our paralegal is three-quarters through that contract, each new sentence is slower than the last. Not because the chip degraded. Because the math says every new output attends to a longer history.
Brian Reed: That's — yeah. That's a different kind of bad than I was imagining. I was picturing a flat cost and it's actually an accelerating one.
Eliza Ward: Right, and — actually, this is why the whole 'just throw faster hardware at it' framing breaks down. Attention is memory-bound. The constraint is the data movement between HBM and SRAM, not the arithmetic flops. FlashAttention attacked that bandwidth cost honestly. It's a real systems win. But it's not — it's not a solution to O(n²), it's a solution to a bad memory access pattern inside O(n²).
Brian Reed: Which is why the research community is looking at things like Mamba and linear attention variants at all — and honestly, whether those actually hold up on quality is the part of this conversation I think is going to get uncomfortable.
Eliza Ward: Very uncomfortable. The benchmark evidence on whether those alternatives match transformer quality at long context is still — it's still genuinely unresolved. That's not a hedge, that's the actual state of the research.
Brian Reed: So that's the wall. And the real question is — is anyone actually going around it, or just finding better ways to lean against it?
Eliza Ward: Around it. That's the right frame. Linear attention and Mamba — these aren't optimizations of O(n²), they're structural escapes from it. Different math entirely.
Brian Reed: How different?
Eliza Ward: Linear attention rewrites the attention function using factorized query-key feature maps. Instead of comparing every token to every other token, you accumulate the key-value context incrementally. The n×n matrix never forms. You get O(n) time and O(n) memory — not as an approximation, as the actual computation.
Brian Reed: Wait — never forms? Not 'forms and then gets compressed,' actually never?
Eliza Ward: Never materialized. That's the point. And Mamba — state space models generally — go further. Fixed-size hidden state, updated recurrently. Constant memory regardless of sequence length. Not linear, constant. That's a genuinely different structural departure.
Brian Reed: Constant memory. So a million-token sequence costs the same memory as a thousand-token one?
Eliza Ward: In principle, yes. That's the structural claim. And — I mean, honestly — the benchmark evidence on whether that comes with quality parity is still genuinely unresolved. The research community's position is not 'Mamba is better.' It's 'we don't know yet.'
Brian Reed: Which is the part that should make anyone pause before calling it the solution.
Eliza Ward: Right — and it's not just language. Vision Transformers hit the same wall on high-resolution images. The quadratic bottleneck shows up there too, which confirms this is a property of the mechanism, not something specific to text. If you're doing all-pairs comparison, the domain doesn't save you.
Brian Reed: The part I don't get is — if linear attention and SSMs are structurally better on cost, why aren't production systems using them? Like, picture a genomics lab running sequence alignment on reads that are genuinely millions of tokens long. Why are they still on transformers?
Eliza Ward: Two things. One — sparse and sliding-window attention exist as a middle ground. Restrict each token to a local neighborhood, you cut scored pairs below n². But then you've reintroduced locality constraints — you need depth to propagate information across the full sequence, which is basically the RNN problem wearing different clothes. Two — even setting that aside, the switching cost to Mamba or linear attention is massive. You're not fine-tuning. You're retraining.
Brian Reed: And if the benchmarks are unresolved, no one's absorbing that retraining cost on a bet.
Eliza Ward: Which is actually — wait, this is what I think the frontier actually looks like — hybrid architectures. Interleave a few dense attention layers with SSM or linear layers. The intuition is that full attention is most critical for specific layers, and the rest can go cheaper. Less ideologically clean, but maybe that's where the real answer lives.
Brian Reed: So the question isn't 'transformers or Mamba' — it's 'what's the minimum number of full-attention layers you actually need?'
Eliza Ward: That's the live research question. And nobody has a clean answer yet — which is why asking what's actually shipping in production matters more right now than asking what's theoretically optimal.
Brian Reed: The thing that actually settled for me — and I keep wanting to say this differently but I can't — is that 'we fixed it' and 'we worked around it' are genuinely different claims. FlashAttention is real. The tiling works. Tri Dao solved something hard. But that's a memory access problem solved, not an O(n²) problem solved. And I think most of the conversation in the industry just... doesn't hold that line.
Eliza Ward: No, it doesn't. And what's actually honest is — the proof that an alternative escapes O(n²) without sacrificing quality doesn't exist yet. Mamba is real. Linear attention is real. But demonstrated parity at long context? Still open. That's not pessimism, that's just where the research sits.
Brian Reed: Which means whoever gets there — whoever actually demonstrates quality parity at O(n) scale — that's not incremental. Faster chips couldn't do it. FlashAttention couldn't do it. That's a different category of solved.
Eliza Ward: That's the one I'd watch. Yeah.
Brian Reed: I think that's actually a good place for me to stop turning this over. I feel like I came in with the wrong model of where the wall was, and I'm leaving with a clearer one — even if the clearer one is mostly 'we don't know yet.'
Eliza Ward: 'We don't know yet' is underrated. Thanks for pushing on it.
