Can we escape \(O(T^2)\) attention?

Dense causal attention lets each token access every earlier token directly.

The number of possible query-key interactions is:

so work scales as \(O(T^2)\).

Sliding-window attention¶

Limit each token to the last \(W\) tokens.

Work becomes:

If \(W\) is fixed, that is effectively linear in sequence length.

For:

rough comparisons are:

instead of roughly:

for the full causal triangle.

But token 90000 cannot directly retrieve token 10.

Information can still propagate¶

Across layers, nearby tokens can relay information onward.

However, repeated compression/relay is not the same as direct random access to exact distant state.

Sparse attention¶

Keep local attention plus selected long-range or global connections.

This is cheaper than full attention but raises a hard question:

How do you know which distant token matters before doing the expensive search that would reveal that?

Fixed recurrent/state models¶

Instead of keeping all K/V pairs, maintain a state:

Now memory can be fixed-size.

This is extremely attractive for million-token histories.

But compression creates a fundamental risk: if an obscure serial number from 900K tokens ago becomes important, the state must have preserved it despite not knowing its future relevance.

The core advantage of attention¶

Attention offers content-addressable memory:

The model can decide later what past information matters.

This yields a difficult triangle: - cheap compute, - small memory, - arbitrary exact-ish retrieval.

Getting all three is hard.

Practical direction¶

Hybrid systems combine: - local attention, - hierarchical summaries, - external retrieval, - compressed state, - selected global memory.

The deeper long-context question is not just “how do we make attention faster?”

It is:

What information from the past deserves to remain directly retrievable?

Why full attention is such a powerful primitive¶

Suppose an early token contains:

Serial number: XQ-4917-Z

and 80K tokens later the user asks:

What was the serial number?

Dense attention can directly compare the current query against the old token representations.

A compressed recurrent state had to decide, at the time it saw the serial number, whether that detail deserved preservation.

That is the random-access advantage.

Hierarchical memory¶

One compromise is to preserve information at several resolutions:

recent tokens → exact
older local chunks → summaries
important facts → selected memory
full archive → external retrieval

Now the system spends dense-attention capacity only where it buys the most value.

Retrieval itself has cost¶

Sparse or external retrieval is not free. The system must: - construct indexes, - choose retrieval queries, - fetch candidates, - sometimes rerank them.

The engineering question becomes where to pay the selection cost.

A useful framing¶

Every long-context architecture performs some form of information selection.

Dense attention delays selection until the query is known, which is flexible but expensive.

State-space compression selects while reading, which is cheap later but risks forgetting.

RAG selects from an external corpus before the main model reasons.

The core trade-off is when and how information is discarded.

There is no free compression¶

Imagine a fixed-size recurrent state of 4096 numbers summarizing a million-token history.

That is an enormous compression ratio.

If the history contains thousands of independent arbitrary facts that might later be queried exactly, a fixed state cannot preserve everything perfectly.

So linear-time long-context methods usually rely on assumptions about which information matters or how language can be compressed.

Dense attention avoids making that compression decision early by storing a representation for every token.

Its \(O(T^2)\) computation is expensive, but the memory itself has rich random-access structure.

Hybrid models acknowledge this trade-off¶

A practical architecture can preserve: - local exact detail, - a compressed long-range state, - a few global tokens, - external retrieval for rare specifics.

That is similar to how humans use working memory, summaries, and external notes rather than keeping every past sensory input equally accessible.

Decode is already closer to linear attention work¶

The \(O(T^2)\) problem is most dramatic when processing an entire long prompt, because every query position interacts with many keys.

During one decode step, there is only one new query position, so attention against a \(T\)-token cache costs roughly:

for that step.

However, generating another \(G\) tokens accumulates work as the cache grows:

So long histories still make generation expensive even though each individual step is not \(T^2\).