The Quadratic Wall: The Algorithmic Race to Beat O(n²) Attention

Back at university, one exercise showed up in every algorithms course in a slightly different costume: here is the obvious quadratic solution, now can you do better? Sometimes you could drop it to n log n, sometimes only to a smaller constant, and sometimes the honest answer was that the quadratic was inherent and the interesting work was elsewhere. That instinct, look at an O(n²) and ask what it would take to beat it, turns out to be the cleanest way I know to read the modern architecture race.

Because that race is one algorithms story wearing several logos. FlashAttention, sparse attention, linear attention, Mamba and the other state-space models are all answers to the same question: attention is quadratic in the sequence length, so what do we do about it? This is the architecture companion to an earlier post on why the tokens themselves are priced the way they are [1]; here the subject is not the bill but the algorithm underneath it.

The wall: where the n² comes from

Take an input of n tokens. In standard self-attention, every token computes a relevance score against every other token, which is an n × n matrix of scores. Building and applying that matrix is on the order of n² in arithmetic for a fixed head dimension, and the score matrix itself is n² in size if you materialise it [2]. Double the context and you roughly quadruple both the work and that intermediate memory.

Two clarifications keep this honest. This n² describes processing the whole sequence at once — the prefill of a prompt, or training. In cached autoregressive decoding, each new token attends over the stored keys and values in work linear in the tokens seen so far; with a prompt of p tokens and m generated tokens, that totals on the order of O(mp + m²) arithmetic for a fixed head dimension, while the key-value cache grows linearly as O(p + m), not quadratically. That is a separate quantity from the score-matrix memory above. Part 1 walked through that decode-time ledger [1].

That single fact is the wall. It is why doubling a prompt does not merely double its attention cost, why very long contexts feel disproportionately slow and memory-hungry at serving time — where the key-value cache grows with length and competes for the same accelerator memory [3] — and why “just put the whole document in the prompt” stops scaling sooner than people expect. The variable that matters here is n, the sequence length. Keep that fixed in mind, because the whole point of naming the variable is to see which techniques change the exponent on it and which only change the multiplier in front.

Two ways to attack a quadratic

Whenever you meet a quadratic algorithm, two moves are worth separating, because confusing them is how people overstate what a new architecture buys. Treat them as a starting lens, not a clean partition: a single technique can improve one cost axis while leaving another untouched.

The first move improves the constant factor. The algorithm still does O(n²) work in the asymptotic sense, but you make each unit of that work far cheaper, usually by respecting the hardware. This never changes the shape of the curve, yet on real machines it can be the difference between usable and unusable.

The second move improves the asymptotics. You change the algorithm so the exponent itself drops, from n² toward n log n or n. This bends the curve, so the win grows without bound as n increases, but it almost always costs you something the exact algorithm gave you for free.

The catch is that “constant-factor versus asymptotic” is too coarse on its own, because there is more than one thing to be asymptotic about. FlashAttention, as we will see, keeps O(n²) arithmetic yet improves memory asymptotically; a state-space model changes the arithmetic itself. So the sharper question is not “which of the two moves is this,” but “which cost axis does it move” — arithmetic, working memory, memory traffic, or latency. A headline that ignores the axis will tell you a linear-time model is “faster than FlashAttention” without noting they are not even competing on the same one.

FlashAttention: the same wall, climbed efficiently

FlashAttention computes exact attention, the same numbers standard attention would produce, so its arithmetic is still O(n²) in the sequence length. What it changes is memory. Instead of writing the full n × n score matrix out to the accelerator’s main memory and reading it back, it tiles the computation so scores are formed and consumed in fast on-chip memory, and it never materialises the whole matrix at once [4].

That is not merely a constant-factor trick. The arithmetic exponent is untouched, but the working memory drops from O(n²) — a fully materialised score matrix — to O(n), and the traffic to high-bandwidth memory falls sharply. That is an asymptotic improvement, just on a different axis than the one people usually watch. The outputs are the same (modulo the ordinary floating-point reordering any tiled reduction introduces), while far less memory is used and moved. FlashAttention is the clearest reminder that “cost” is several quantities at once: it leaves arithmetic’s exponent alone while lowering memory’s. It made long contexts practical without pretending the arithmetic wall was gone.

Sub-quadratic: bending the curve, at a price

The asymptotic attack is where the interesting architectures live. Sparse attention restricts each token to a subset of others — a local window, a few global tokens, strided patterns — so with w attended positions per token the work grows like O(nw): that is O(n) when w is constant, O(n log n) when w grows like log n, and back to O(n²) when w is proportional to n. Linear attention is a family, not a single method: some variants approximate softmax with kernel feature maps so the operation factorises and never forms the n × n matrix, while others replace softmax with a different attention-like operator entirely. Both aim for linear time in n at a fixed feature dimension. The taxonomy is large enough to have its own survey [5].

State-space models are the sharpest version of the idea. Instead of letting every token look at every other token, a model like Mamba carries a fixed-size state forward through the sequence, updating it token by token. For a fixed state width, that is linear-time sequence modelling, and in the authors’ evaluated setup they report up to roughly 5× higher inference throughput than Transformers, along with scaling to very long sequences [6]. No n × n matrix is ever built, so the wall is sidestepped rather than climbed.

The catch is specific to how these sub-quadratic sequence models get their bound: they constrain, approximate, or replace exact dense all-pairs attention, which introduces task-dependent tradeoffs. A fixed-size running state is a compression of the past, so information a full attention matrix could reach directly may be harder to recover. The Mamba authors themselves noted that earlier state-space models struggled with content-based reasoning, and much of their design went into selectively remembering or forgetting based on the current token [6]. So the tradeoff is real but task-specific rather than universal: on some workloads a sub-quadratic model keeps pace with attention, on others the lost exact global mixing or state-tracking shows up. That unsettledness is exactly why hybrid designs that interleave attention and state-space layers exist, and why the field has not declared a winner.

The complexity lens: count the right thing

The reason this stays confusing in public discussion is that several different quantities all get called “cost,” and they do not move together. It is worth separating them the way you would in an exam answer.

Arithmetic is the number of floating-point operations. Standard attention is O(n²) here; FlashAttention is the same; state-space models are roughly O(n). Memory movement is how many bytes cross between memory tiers, which is what FlashAttention attacks without touching the arithmetic. Peak memory is how much must be resident at once, where materialising the n × n matrix hurts and streaming or state-based methods help. Latency is wall-clock time, which depends on all of the above plus batching and the hardware. And billing, on a token-metered API, tracks tokens submitted and generated, which is yet another axis [1].

Naming which of these a technique changes is the whole discipline. FlashAttention changes memory movement and peak memory, not arithmetic scaling. Linear attention and state-space models change the arithmetic scaling by constraining the interaction operator, with task-dependent quality and expressivity tradeoffs rather than a guaranteed loss. A discount on token prices changes the billing coefficient, not any complexity class at all. Keep the ledgers apart and most of the overclaiming in this space dissolves.

The oldest optimisation: don’t trigger the quadratic

There is a move that predates all of these architectures and often pays off first: reduce n. If attention cost grows with the square of the sequence length, the cheapest attention is the attention you never run because the prompt was shorter.

That is one thing retrieval can buy. Instead of pushing an entire corpus through the context window, retrieval selects a few relevant passages and sends only those, which shrinks the n that attention sees. It is not free: you add an indexing and retrieval step, some latency, and the risk of fetching the wrong passages, so whether it is a net win is an end-to-end question to measure rather than assume. But when the alternative is brute-forcing a very long prompt, trimming n attacks the cost at its most expensive point, and it composes with every architectural improvement above rather than competing with them. I worked through the mechanics of that lever when moving vector search onto managed infrastructure [7].

If You’re Running This on AWS

The architecture race sets what is possible; your job on a real workload is to pick a context strategy deliberately and let the platform carry the rest. On Amazon Bedrock, that means favouring models and context patterns that match your sequence lengths, and leaning on retrieval so you send the passages that matter instead of the whole archive. The long-context capabilities that managed models expose reflect this line of algorithmic work — alongside other enabling techniques such as positional-encoding scaling, KV-cache optimisation, and parallelism — offered as a feature you can use rather than infrastructure you have to build. Check the model’s documented context limit rather than assuming a number.

When you host a model yourself on Amazon SageMaker AI or Amazon EC2, the lower-level levers become yours, and hardware is one of them. AWS Inferentia is purpose-built for inference, and AWS Trainium targets large-scale training while also serving inference; both lines expose instances that pair accelerators with large high-bandwidth-memory pools to keep long-context state close to the compute [8] [9]. That silicon does not repeal the n²; it makes the remaining work run faster and gives sub-quadratic and memory-frugal methods more room to pay off. Treat these as capabilities that widen what you can afford to run, and measure the value of any single lever against your model, context lengths, and latency target — ideally on the specific instance generation you plan to use — rather than assuming it.

A thread worth pulling

What made the university version of this exercise stick was how rarely the answer was a clean asymptotic victory. Usually it was a constant factor here, a bent curve there, and a reminder that the best optimisation is the work you avoid. The modern long-context race reads the same way. FlashAttention climbs the wall more efficiently, state-space models find a path around part of it, and retrieval quietly lowers it. The useful move is not to root for one of them but to name the variable, separate arithmetic from memory from latency from the bill, and reach for the lever that attacks the cost you actually have.

Part 1 asked why the tokens cost what they cost; this one asks why the sequence length is the axis so much of the architecture race turns on. Which limit bites first in your workloads: the arithmetic of long attention, the memory it demands, or simply the number of tokens you are sending in the first place?

Sources

• [1] Stefan Christoph, “Why AI Tokens Are So Expensive — and What Actually Makes Them Cheaper” — the cost companion to this post: prefill vs decode, the KV cache, and prompt caching.
• [2] Vaswani et al., “Attention Is All You Need” — the transformer and the attention operation whose cost is quadratic in sequence length.
• [3] Kwon et al., “Efficient Memory Management for Large Language Model Serving with PagedAttention” — SOSP 2023; the memory pressure that long contexts create at serving time.
• [4] Dao et al., “FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness” — 2022; exact attention with O(n²) arithmetic but linear auxiliary memory in sequence length and reduced, IO-optimal HBM traffic.
• [5] Tay et al., “Efficient Transformers: A Survey” — 2022 edition; the taxonomy of sparse and linear “X-former” attention variants.
• [6] Gu and Dao, “Mamba: Linear-Time Sequence Modeling with Selective State Spaces” — 2023; linear-time sequence modelling, reported ~5× inference throughput, and the content-based-reasoning tradeoff.
• [7] Stefan Christoph, “Vector Search, From the Whiteboard to the Cloud” — retrieval as a way to shrink the context you send.
• [8] Amazon Web Services, “AWS Trainium” — training-focused accelerator that also supports large-scale inference.
• [9] Amazon Web Services, “AWS Inferentia” — inference-purpose-built accelerator.

About the Author

Stefan Christoph is a Principal Solutions Architect at AWS, focused on agentic AI, media & entertainment, and helping builders move from demo to production. He writes about AI architecture, developer productivity, and the future of software.

This is a personal blog. Opinions expressed here are my own and do not represent the views or positions of my employer.

Learn more →

• AI
• LLMs
• Attention
• StateSpaceModels
• AmazonBedrock