Episode 14 — Algorithms Are Logarithmic, AI Is Quadratic: The Hidden Cost of Long Context Windows

A friend's claim: "Algorithms are logarithmic, AI is quadratic"

Sunil Baliga: Token Drop — and I've got an interesting one to talk about this week: context windows. I ran into a good friend of mine at a party, and he said something I thought was interesting enough that I had to write it down before I forgot it: "Algorithms are logarithmic, AI is quadratic." He walked me through it with the sentence "I go to school." In terms of tokens, he said the LLM effectively has to process "I," then "I go," then "I go to," then "I go to school" — and that method of generating and parsing tokens causes cost to blow up as the context window grows, because of quadratic growth in the number of token-to-token comparisons.

He followed up afterward with more detail: a thousand tokens results in roughly a million attention operations, while 100,000 tokens results in about 10 billion attention operations. He contrasted that with something like a database, which scales logarithmically — his point being that AI attention scales quadratically instead. His bottom line: with these models, a large context window can get very expensive very fast because of this. I think I followed what he was saying, but I wanted to put it to you two — what do you think?

Why the attention mechanism really is quadratic

Sajjad Khazipura: He's partially right. I thought about it for a bit and landed here: he's correct that the attention mechanism in an LLM compares every token against every other token in the sequence. It's an autoregressive model, so to generate the next token, it runs this all-vs-all comparison — that's an N² (N-squared) operation.

In computer science, we describe this with Big O notation, which tells you how an algorithm's cost scales as the input grows. The attention mechanism in an LLM is quadratic — effectively N². With 100 tokens, you're doing roughly 100 × 100 operations, which gets expensive fast.

Well-designed algorithms can be efficient, but you can just as easily design a poorly optimized algorithm that also happens to be N². So I assume my friend isn't talking about bad algorithm design — he's talking about algorithms that are designed thoughtfully and still scale well. Those tend to be sub-linear: they don't grow in lockstep with the size of the workload. Databases, in particular, go to great lengths to keep their search and sort algorithms sub-linear — you'll see n·log(n) or log(n) complexity there. Plotted on a chart, the compute required for a given workload is dramatically lower than a quadratic algorithm.

So yes, he's partially right — but where I'd push back is that any algorithm, including a poorly designed one, can be N². We just try not to design algorithms that are N² if we can avoid it.

Newer architectures trying to escape N²

Sunil: He also mentioned newer architectures — linear attention, sparse attention, state-space models —

Sajjad: — attempting to bring this down toward O(n) or O(log n). But standard transformer attention, what most of us are using today, remains O(n²).

Sunil: So it sounds like these newer approaches are trying to do better.

Sajjad: Right — they're asking, do we really need to compare every token with every other token? Are all of those comparisons even relevant? Can we select a smaller, relevant subset of tokens and run the N² comparison against that smaller set instead of the full sequence? Those are all optimizations, but foundationally, it's still an N² algorithm underneath — there's no getting around that.

Which brings up something important: the longer the context, the more you have to process, and processing more has a real economic and environmental cost. So you need other ways to optimize — sparse attention, semantically selecting the right tokens, state-space models. There are a number of architectures that have emerged specifically to mitigate this. Sam, did you want to add something?

Long context vs. retrieval: when each one wins

Sam Pooni: You've covered a lot of the core idea already — attention is quadratic, cost scales with sequence length. This is a structural reason long context is expensive, not just a pricing choice.

But there are other real constraints too: KV cache size is a genuine limiter, and there's also the gap between a model's advertised context length and its effective context length — how much of that window it can actually use well.

So who actually wins with long context? Tasks that need the whole document's structure — exact ordering, cross-section relationships. One coherent artifact — a contract, a codebase — that has to be reasoned over as a single unit. That's where long context wins.

Retrieval wins in a different scenario: question-and-answer work against a large corpus, where you really only need 3 to 5 relevant chunks — say 4,000 to 8,000 tokens — pulled out. That approach skips the "lost in the middle" penalty and cuts cost and latency. Retrieval is also what you want when you need provenance — something you can point back to as the source.

So long context and retrieval aren't really competitors. The winning pattern is retrieval plus re-ranking — feeding the model a curated, structured set of the most relevant material rather than dumping 800,000 tokens of largely irrelevant text into every call. Same model, more structured input, lower cost. That's the direction things are headed. So, Sunil, to your original question: yes, attention is quadratic, but there are real ways to mitigate the impact — which is what Sajjad's been describing too.

The real-world cost: doubling context quadruples compute

Sunil: He also told me — this is from his note — that increasing context from 10K to 100K tokens increases attention work by roughly 100x. You increase the token count by 10x, and the attention work goes up 100x. He said doubling the context window roughly quadruples the attention compute and memory required, which I thought was a striking way to put it. So if you're running a large context window on a newer LLM — which is already more expensive per token than an older one — your costs can climb dramatically.

Sajjad: Yes, and we're seeing exactly that. Costs go up quadratically, as you said, because the computation itself is quadratic, and that gets expensive.

But I'll take the flip side of that argument too, which Sam was getting at: yes, it's expensive, but a million-token context length has become table stakes — nearly all the frontier models support it now. I'm sure Anthropic, OpenAI, and the other major labs have invested heavily in R&D to optimize the computational cost of that. But no matter how much they optimize, they're almost certainly doing something like what Sam described — sparse attention, semantically selecting a smaller set of tokens to actually process rather than the full set. Those are statistical shortcuts, and — fittingly, given the name of our podcast — they eventually result in some tokens getting dropped.

Where the dropped tokens go: "lost in the middle"

Sajjad: If we're not processing every token, does that lead to some kind of loss? The observation researchers have made is this: when you give an LLM a million-token document and ask it questions, facts placed in the middle of that document are more likely to get missed. What's near the beginning or the end of the document tends to get answered well and stays factually grounded — what's in the middle sometimes doesn't.

Sunil: Interesting. So — they're dropping tokens, and that's the "donut hole" in the middle?

Sajjad: Essentially, yes — simplistically put, that's likely part of how they manage the N² computation at a million-token context length. You can't fully process N² at that scale, so tokens get dropped somewhere, using algorithms designed to select which tokens matter most.

The result is a well-known evaluation called the "needle in a haystack" test — researchers bury a specific fact in the middle of a long document and see whether the model can retrieve it. Most LLM providers have gotten reasonably good at that basic version. The next question is whether a model can find multiple needles scattered throughout a document. There's a rigorous benchmark for this — I believe it's called NoLiMa — and not every provider publishes their results on it, likely because it's a genuinely hard test. If a model passes it well, that's a strong model. So yes, it's a known, real problem, and people are working on mitigating it in various ways. There are also those who'd ask: do you even need that much context length in the first place?

Does long context actually save you time?

Sunil: That was actually my next question — could you argue that with a long context, you get the answer you want faster? You don't have to ask the LLM ten separate questions; you ask it one question against the whole document, so your total round trip — tokens to get to an answer — is faster and lower overall if you use long context instead of multiple smaller queries.

Sajjad: Ideally, yes. When an LLM has the entire document available and you ask it a question, it can generally reason better and give a better answer than if the document had been chunked — where the burden falls on you to retrieve the right chunks and stitch the answer together yourself. That's exactly why retrieval harnesses, knowledge graphs, and similar tooling exist — to handle that stitching.

But the trade-off remains: at million-token context lengths, providers are almost certainly dropping some tokens — we don't know exactly how or what gets dropped — and that contributes to hallucination. Hallucination doesn't go away with context length; it's somewhat orthogonal to it. Whether it increases or decreases with context length, the evidence suggests it behaves like an asymptotic curve — no matter what mitigations you apply, it never goes fully to zero. It stays present.

Sam: Building on that — the core thesis here is that the million-token context window is basically the "megapixel race" of LLMs: every spec sheet has a big number, but almost no real workload actually uses the full window. The advertised capacity isn't the effective context. Production long-context use is fundamentally an architecture problem we've been looking at, not a model problem.

Here's why: the context window is total tokens per request — system prompt, plus loaded documents, plus the model's own working context. And roughly, a token works out to about 0.75 words. Once you exceed the window, you simply can't send more — so, as we said, you chunk, truncate, or retrieve instead.

So if every model now advertises a million tokens, why do teams still get burned? There's a gap between advertised and effective context — a model's window is its stated capacity, but effective context is the length over which output quality actually holds up. Every long-context benchmark published shows a gap here, for a few reasons:

1. "Lost in the middle" — documented since 2023, and reproduced across every generation of models since. Models retrieve reliably from the beginning and end of a context window; accuracy in the middle drops somewhere in the range of 20–40%. So a 200K window doesn't perform uniformly across its full 200K.
2. Multi-needle, multi-hop collapse — finding a single fact ("single needle") is one thing, but tests like MRCR v2 (an 8-needle test at 1 million tokens) show scores fall off sharply once you need to find and connect multiple related facts, not just one.

Doing the math: what does a million tokens actually mean?

Sunil: You said roughly 0.75 words per token?

Sam: Right, about 0.75 words per token.

Sunil: So one word is roughly 1.3-ish tokens. Meaning if I have a million tokens —

Sam: — that's about 750,000 words.

Sunil: Right — so I did a quick back-of-the-envelope calculation: at roughly 250 words per page, that's somewhere around 3,000 to 4,000 pages. That's a pretty hefty document to actually need that much context for. So where would you actually use a million-token context? What's the real use case?

Sam: The place you'd use it is for tasks that need the whole document's structure — exact ordering, cross-section relationships. Think of it as one coherent artifact: a contract, a codebase, something that has to be reasoned over as a single unit. That's when it's warranted. Most of the time, over a large corpus, retrieval ends up doing more of the work than long context.

Sunil: It sounds like use cases involving comparing across multiple documents, or pulling answers from many documents at once, are what would actually generate a million tokens — you're stuffing multiple documents into the window at the same time. Searching a single document probably wouldn't get you there unless it's an unusually large one, but multiple documents — emails, records, that kind of thing — could realistically add up to a million tokens.

Sajjad: Right — I think legal use cases are a good example: case law, precedent research for a given case, all the accumulated evidence. Some court cases run for months or years and generate a huge volume of content that needs to be understood accurately to surface the right answers. I could see the legal domain genuinely needing that much context — provided the results are reliable and dependable. It really comes down to which business use cases actually need that scale of context.

Sam: Right — and in practice, about 95% of real workloads live under 128K tokens. The takeaway is: pick your model and approach based on the retrieval shape of the actual job, not the headline context-length number. If you just go by the headline number, you run into exactly this disconnect — advertised capacity isn't effective context. Production long-context use is an architecture problem, not a model problem, like I said.

Wrapping up

Sunil: Okay, I think you two answered my question. I'll go back to my friend and tell him to listen to this episode — see what he has to say. Maybe we'll have him on sometime if he's got something to push back with.

Sajjad: One more thing worth noting — this isn't unique to LLMs. Even a basic sort algorithm that compares every number against every other number is N² by design, and it's inefficient the same way. It might be fine at small scale, but sorting 1,000 or 100,000 numbers with an N² algorithm gets painfully slow. So whether it's an LLM or a classic algorithm, N² complexity will eventually catch up with you. That's exactly why database vendors invest so heavily in efficient searching and sorting algorithms — so they can scale their compute sub-linearly even at very high volume.

Sunil: Very interesting. Anything else on this, or should we wrap up?

Sam: One last thing — let me close by answering four questions you raised along the way:

1. Does a bigger context window make retrieval (RAG) obsolete? No. The "lost in the middle" penalty and cost/latency scaling work against you at large context sizes, so narrowing what the model has to attend to still matters — long context and retrieval work together.
2. For something like a 200-page contract with six interrelated questions, what should you use? A 32K–128K "multi-needle zone" is usually the right tool, not the full million-token window.
3. Is a 10-million-token context "real"? It's advertised, yes — but there isn't public evidence yet of anyone running quality workloads reliably near that scale.
4. How do you measure your own effective context? Build a domain-specific "needle" test — and it needs to be multi-needle, with the needles related to each other, not just a single isolated fact.

Bottom line: even with a large advertised context window, the effective context you can actually rely on is smaller — and that gap is the thing to design around.

Sajjad: Thanks, Sam.

Sunil: Alright — thanks, everyone.