There’s a line of code at the heart of every major language model that looks innocent until you run it at scale. It computes attention scores between every token and every other token in the input sequence. Double the context length, and that computation doesn’t double. It quadruples. This isn’t a bug or an engineering oversight. It’s the fundamental cost of the architecture that makes these models work.
What Attention Actually Does
The transformer architecture, introduced in the 2017 paper “Attention Is All You Need” by Vaswani et al., replaced the sequential processing of recurrent networks with a mechanism that lets every token look at every other token simultaneously. This is why transformers can understand long-range dependencies so well. The word “it” in a long legal document can attend directly to the noun it refers to, thirty sentences back, without that signal degrading through intermediate processing steps.
The cost is that to compute these relationships, you need a matrix of size N×N, where N is the number of tokens in your context window. At 1,000 tokens, that’s a million attention scores to compute per attention head. At 10,000 tokens, it’s 100 million. At 100,000 tokens, which is now a common advertised context length, you’re computing 10 billion attention scores per head, per forward pass. Modern models have dozens of attention heads.
This is what O(N²) complexity looks like in practice. It’s not an abstraction from a computer science course. It’s a direct explanation for why the API call that processes your 80,000-token legal contract costs an order of magnitude more than the one processing a short email.
The Memory Problem Is Worse Than the Compute Problem
The quadratic scaling shows up in two places: compute time and memory. The memory problem is often the binding constraint. During inference, the KV cache (key-value cache) stores the intermediate attention representations for every token in the context. This cache scales linearly with context length at first glance, but when you’re running many requests in parallel on a GPU, the aggregate memory footprint becomes the practical ceiling.
A100 GPUs, which power much of the current inference infrastructure, have 80GB of HBM memory. A large model’s weights alone can consume 40-70GB. That leaves a narrow margin for the KV cache, which means either limiting batch sizes (reducing throughput and increasing per-token costs) or limiting context lengths. When providers advertise 128k or 200k context windows, they’re not just solving an algorithmic problem. They’re making aggressive bets on hardware configuration and batching strategy to make the economics work.
This is why Anthropic’s Claude, Google’s Gemini, and OpenAI’s GPT-4 models all price tokens at higher rates for longer contexts. It’s not arbitrary. The cost of serving a 100k-token request genuinely is not 100x the cost of a 1k-token request. It’s closer to 10,000x in naive attention computation, though engineering optimizations close that gap considerably.
The Engineering Responses
The industry hasn’t been sitting still. Several approaches attack the quadratic problem from different angles.
FlashAttention, developed by Tri Dao and colleagues at Stanford, reorders the attention computation to minimize memory bandwidth usage rather than FLOPs. It doesn’t reduce the theoretical complexity, but it dramatically reduces wall-clock time by keeping data on the GPU’s faster SRAM rather than shuttling it to slower HBM repeatedly. FlashAttention-2 and FlashAttention-3 have become near-universal in modern inference stacks.
Sparse attention approaches, used in models like Longformer and BigBird, sidestep the full N×N matrix by having tokens attend only to local neighbors and a small set of global tokens. This drops complexity to O(N log N) or even O(N), at the cost of potentially missing long-range relationships. Whether that tradeoff hurts quality depends heavily on the task.
Mixture-of-experts architectures, as used in GPT-4 and Mixtral, don’t directly address attention costs but reduce the compute spent in the feedforward layers, which dominate at shorter contexts. As context grows, attention costs increasingly dominate anyway.
State space models like Mamba take a fundamentally different approach, replacing attention with a recurrent mechanism that processes sequences in linear time. Early benchmarks are promising, but these models are still catching up to transformers on tasks requiring precise recall from earlier in a long context. The quality degradation that comes with extended context is a separate but related problem.
What This Means for Builders
If you’re building applications on top of LLM APIs, the quadratic cost curve should shape your architecture decisions in concrete ways.
Chunking and retrieval-augmented generation (RAG) exist partly as a cost optimization, not just a quality optimization. Instead of feeding an entire document corpus into a context window, you retrieve the relevant passages and send those. The reduction in context length has compounding benefits: lower latency, lower cost, and often better accuracy since the model isn’t searching through irrelevant material.
Be skeptical of “unlimited context” marketing. Every context window has a practical ceiling, and the effective quality of attention degrades before you hit it. Studies on “lost in the middle” phenomena have shown that LLMs perform worse on information buried in the middle of long contexts compared to information at the beginning or end. Long context and useful context are not the same thing.
Context caching, offered now by several providers including Anthropic and Google, lets you pay once to process a stable system prompt or document and reuse those KV cache values across multiple requests. If you have a large, fixed context (a long system prompt, a reference document), caching can cut costs significantly. The savings scale with how often you reuse the cached prefix.
The attention mechanism is genuinely one of the most powerful ideas in recent machine learning history. It’s also one of the most expensive. Understanding why helps you build systems that use it intelligently rather than profligately. The providers are working on the infrastructure side of this problem constantly, but no amount of engineering eliminates the underlying quadratic relationship. You can optimize it. You cannot escape it.
