Long-context architectures: Question bank — AI-ML deep dive

This is a question bank. Each line is a trap: a statement that sounds right, or a boundary case people skip. Cover the answer, commit to a reason (not just "true"/"false"), then reveal. If your reason differs from the answer's reason, that's the misconception caught.

Every item here builds on the ideas in the parent note and its prerequisites: Attention Mechanisms, Computational Complexity, Transformer Architecture, Recurrent Neural Networks, Kernel Methods, Retrieval-Augmented Generation, and Information Bottleneck.

Definition Every symbol used on this page (read before the traps)

All the shorthand below appears in the traps — pin it down now so no line ambushes you.

== $w$ == — window size: how many neighbouring tokens a "local" token is allowed to look at (e.g. $w = 512$ ). Picture a small moving box on the sequence.
== $g$ == — number of global tokens: the few special tokens (like [CLS]) that are allowed to look at everything.
== $M$ == — memory size: how many past key–value pairs are stored in an external memory bank.
$ϕ$ — feature map: a function that turns a query/key vector into a new vector, used by linear attention. == $d_{ϕ}$ is the length of that output vector; $d_{v}$ == is the length of each value vector $v_{j}$ .
== $Z$ == — normalizer in linear attention: the vector $\sum_{j} ϕ (k_{j})$ that plays the role softmax's denominator plays in ordinary attention (it makes weights sum to 1).
$S = \sum_{j} ϕ (k_{j}) v_{j}^{⊤}$ — the key–value summary matrix built once and reused by every query.
SSM symbols (State Space Model): the state evolves as $h_{k} = \overset{ˉ}{A} h_{k - 1} + \overset{ˉ}{B} x_{k}$ , output $y_{k} = C h_{k}$ . Here $x_{k}$ is the input at step $k$ , $h_{k}$ the hidden state (a fixed-size memory vector), == $A$ == controls how the state carries forward in continuous time, == $B$ injects the input, $C$ reads the state out. $Δ$ == is the step size (how much continuous time one token represents); the bars in $\overset{ˉ}{A} = e^{Δ A}$ and $\overset{ˉ}{B} = (e^{Δ A} - I) A^{- 1} B$ mark the discretized (per-token) versions. See Recurrent Neural Networks for the same carry-the-state idea.

Two derivations that the traps lean on — worked out once here so the reveals can just cite them.

True or false — justify

Full self-attention over

n

tokens costs

O (n^{2})

because every token compares against every other token.

True. Each of the

n

query tokens forms a dot product with all

n

key tokens, giving

n \times n

comparisons — the grid is fully filled in, so cost grows with the square of

n

Sparse attention always saves training memory, no matter how it is implemented.

False. Sparsity only helps if the implementation skips the masked-out entries. Many frameworks apply a sparse mask on top of a dense $n \times n$ matrix — the full grid is still allocated, so memory is unchanged. Real savings require a specialised kernel (block-sparse, gather/scatter) that never materialises the dropped pairs.

Longformer's sliding window alone (no global tokens) already preserves document-level understanding.

False. A pure local window of size

w

means token

i

can only ever see tokens within

\pm w /2

; information from far-away tokens must hop through many intermediate layers, and shallow models lose it — that's exactly why global tokens are added.

Linear attention is called "linear" because the feature map

ϕ

is a linear function.

False.

ϕ

can be nonlinear (the random-feature

ϕ

above uses

exp

); "linear" refers to the total cost scaling

O (n)

in sequence length, achieved by the associative re-order that summarises keys once instead of comparing them per query.

Replacing

softmax (q \cdot k)

with

ϕ (q)^{⊤} ϕ (k)

leaves the attention output unchanged.

False. As the derivation above shows,

ϕ (q)^{⊤} ϕ (k)

only equals

e^{q \cdot k}

in expectation — it is an unbiased approximation with variance; the efficiency win buys

O (n)

cost at the price of no longer computing the exact softmax kernel (see Kernel Methods).

A State Space Model (SSM) has fixed memory cost regardless of how long the sequence is.

True. The hidden state

h_{k}

is a fixed-dimension vector (e.g. 256 numbers); it is overwritten every step, so storing it does not grow with

n

— unlike attention, which caches a key/value for every past token.

Because an SSM keeps a fixed-size state, it can never lose information from early tokens.

False. The opposite: a fixed-size state is an Information Bottleneck — old information must be compressed into the same 256 numbers, so distant details can be squeezed out, whereas attention keeps a separate cached vector per token.

The convolutional form of S4 and its recurrent form compute different outputs.

False. They are two views of the same linear recurrence

h_{k} = \overset{ˉ}{A} h_{k - 1} + \overset{ˉ}{B} x_{k}

: the kernel

\overset{ˉ}{K}_{k} = C \overset{ˉ}{A}^{k} \overset{ˉ}{B}

unrolls the recurrence into a convolution, so outputs match — the convolution is just chosen for parallel training.

Memory-augmented models achieve

O (n)

overall because nearest-neighbour lookup over a memory of size

M

is roughly

O (lo g M)

True — with a caveat. Approximate nearest-neighbour search (e.g. FAISS) is sub-linear per query, so total cost is

O (n w) + O (n lo g M)

; this is

O (n)

only while

w

and

lo g M

stay much smaller than

n

(i.e.

M ≪

exponential-in-

n

; see the edge case below).

Spot the error

"We use a sliding window of size

w = n

to be safe, and still enjoy

O (n)

complexity."

Error: if

w = n

the window is the whole sequence, so cost is

n \cdot w = n^{2}

— you've reverted to full attention. The linear win requires

w ≪ n

"Linear attention precomputes

S = \sum_{j} ϕ (k_{j}) v_{j}^{⊤}

separately for each query, one

S

per query."

Error:

S

is computed once, globally, shared by all queries (see the associative re-order above). Recomputing it per query would reintroduce the

O (n^{2})

scan and defeat the entire method.

"In linear attention we can drop the denominator

ϕ (q_{i})^{⊤} Z

since it's just a scaling constant."

Error: that denominator is the softmax-style normalizer

Z = \sum_{j} ϕ (k_{j})

; different queries have different denominators, so dropping it removes the normalization and gives unbounded, wrongly-weighted outputs.

"The SSM matrix

\overset{ˉ}{A} = e^{Δ A}

, so a bigger step size

Δ

always means the state changes more slowly."

Error: the effect depends on the sign/magnitude of

A

's eigenvalues. For stable systems (

Re (λ) < 0

), larger

Δ

makes

e^{Δ λ}

smaller, so the past decays faster — the state forgets more quickly, not more slowly.

"S4 chooses

A

diagonal-plus-low-rank purely to reduce the number of parameters."

Error: the structure

A = Λ - p q^{⊤}

exists to make the matrix exponential and the convolution kernel fast to compute (diagonal exp + Woodbury correction); parameter count is a minor side effect, computability is the point.

"A [CLS] global token costs the same as any other token in Longformer."

Error: a global token attends to all

n

tokens (cost

n

), while a regular token attends to only

w

(cost

w

). That's why the budget is

O (n w + g n)

, with the

g n

term paying for the

g

global tokens.

"Memory-augmented attention retrieves the top-

k

nearest neighbours, so it always sees the single most relevant past token."

Error: it uses approximate nearest-neighbour search — for speed it may miss the exact top match; you trade a small recall error for

O (lo g M)

lookup, similar to retrieval in Retrieval-Augmented Generation.

Why questions

Why does full attention hit a wall around 2k–8k tokens even though a modern GPU has plenty of raw FLOPs?

Because the bottleneck is memory, not FLOPs: the

n \times n

score matrix must be stored, and at large

n

it exceeds GPU RAM long before compute becomes the limit.

Why can't we just make the window

w

grow slowly with

n

(say

w = n

) and call it

O (n)

You can, but then

C_{total} = n \cdot n = O (n^{1.5})

— that's the "

O (n n)

" sparse regime, better than

O (n^{2})

but not truly linear.

Why does the associativity trick

(\sum_{j} ϕ (k_{j}) v_{j}^{⊤})

before multiplying by

ϕ (q_{i})

save so much?

Because it changes the order of a matrix product: summarising keys+values first builds the fixed-size matrix

S

(and normalizer

Z

); each query then multiplies by

S

O (d_{ϕ} d_{v})

time, so the expensive scan over

n

happens once instead of per query — exactly the algebra in the formula callout above.

Why do SSMs offer a convolutional training form but a recurrent inference form?

Training sees the whole sequence at once, so the convolution

y = \overset{ˉ}{K} * x

parallelises across all positions on a GPU; inference generates tokens one at a time, so the step-by-step recurrence

h_{k} = \overset{ˉ}{A} h_{k - 1} + \overset{ˉ}{B} x_{k}

(carry state forward) is the natural, memory-cheap mode — the same duality that motivates Recurrent Neural Networks.

Why do memory-augmented models still keep a local sliding window instead of relying entirely on retrieved memory?

Local, recent tokens carry fine-grained syntactic dependencies that retrieval (built for coarse semantic similarity) often misses; the window guarantees nearby context is always attended to, regardless of what the memory returns.

Why is calling any sub-quadratic method "just as good as full attention" misleading?

Every method trades exactness for cost: sparse patterns drop token pairs, linear attention approximates the kernel, SSMs compress into a bottleneck. They approach full-attention quality on many tasks but can fail on tasks needing exact, arbitrary long-range pairwise lookups.

Edge cases

What happens to Longformer's cost accounting if every token is made a global token (

g = n

The

g n

term becomes

n^{2}

, so complexity collapses back to

O (n^{2})

— global attention is only cheap when the global set

g

is tiny.

What is the attention cost when

n

is smaller than the window

w

(a short sequence)?

Each token can attend to at most

n

tokens, so the effective window saturates at

n

; sparse and full attention coincide, and there is no efficiency gain — sparsity only helps once

n > w

What does linear attention's output become if every value

v_{j}

is identical, say

v_{j} = c

The numerator becomes

ϕ (q)^{⊤} (\sum_{j} ϕ (k_{j})) c = c \cdot ϕ (q)^{⊤} Z

, and dividing by the normalizer

ϕ (q)^{⊤} Z

gives exactly

c

— normalization guarantees the output is the constant, matching intuition that averaging identical values returns that value.

What happens to an SSM's state as

n \to \infty

if the largest eigenvalue of

\overset{ˉ}{A}

has magnitude

> 1

The state

h_{k} = \overset{ˉ}{A} h_{k - 1} + \overset{ˉ}{B} x_{k}

grows without bound (each step amplifies), so outputs blow up — this is why S4 constrains eigenvalues to keep

∣ e^{Δ λ} ∣ < 1

for a stable, decaying memory.

What is the memory-lookup cost when the memory bank

M

is empty (start of a long document)?

There is nothing to retrieve, so only the local window contributes; cost per token is just

w

, and the model behaves like a plain sliding-window model until enough context is stored.

What if the memory bank grows with the sequence, e.g.

M \propto n

(store every token)?

Then

O (n lo g M)

becomes

O (n lo g n)

— not linear. The advertised

O (n)

holds only under the unstated assumption

M ≪ n

(a compressed, bounded memory); an ever-growing memory quietly reintroduces a

lo g n

factor.

What breaks if the feature-map dimension

d_{ϕ}

in linear attention is chosen as large as

n

The per-query cost

O (d_{ϕ} d_{v})

then scales with

n

, so total cost returns to

O (n^{2})

— the linear guarantee holds only while

d_{ϕ}

is a fixed small constant, independent of sequence length.

Recall One-line summary of the whole trap set

Every efficient long-context method wins by not filling the full $n \times n$ grid — sparse drops pairs, linear reorders sums, SSM compresses to a fixed state, memory retrieves a few neighbours — and each win comes with a specific failure mode when its " $≪ n$ " assumption is violated.

Pictures behind the traps

Text alone hides geometry. These four figures are the visual anchors the traps refer back to.

The $n \times n$ grid and what each method keeps. Full attention fills the whole square (every token-pair). The red cells are the only comparisons each efficient method actually computes.

Sliding window vs global tokens. A local token sees a red band around the diagonal; a global token (top row/left column, red) sees the entire sequence.

SSM: one recurrence, two shapes. The same $h_{k} = \overset{ˉ}{A} h_{k - 1} + \overset{ˉ}{B} x_{k}$ can be unrolled left-to-right (recurrent, red arrows) or flattened into a single convolution kernel $\overset{ˉ}{K}$ (red) applied to all inputs at once.

Memory-augmented lookup. The current query (red) attends to a small local window plus the top- $k$ neighbours pulled from a bounded memory bank — never to the whole past.