Long-context architectures: Foundations — AI-ML deep dive

This page assumes nothing. Before we can talk about "why $O (n^{2})$ is bad" or "what a hidden state is", we must first agree on what every letter, arrow, and picture means. We build the vocabulary in the order the parent note needs it.

1. A sequence, and what $n$ means

Everything starts with a sequence — an ordered list of pieces of text.

Picture a row of numbered boxes. Box 1 holds the first token, box 2 the second, and so on up to box $n$ . That row is the sequence.

Why does the topic obsess over $n$ ? Because every cost we will meet — memory, compute, speed — is measured as a function of $n$ . When the parent says "contexts beyond ~8k tokens", it means $n > 8000$ . "100k+ token contexts" means $n > 100000$ . The whole chapter is the fight to keep costs small as $n$ grows large.

2. Turning a token into numbers: the embedding vector

A computer cannot multiply the word "cat". It works with numbers, so each token is turned into a list of numbers called a vector.

Picture an arrow floating in space. In everyday life space has 3 directions; here it has $d$ directions. Two tokens with similar meanings point in similar directions.

Why does the topic need this? Because "how related are two tokens?" becomes a geometry question: are their arrows pointing the same way? That question is answered by the next tool.

3. The dot product: measuring "how aligned"

Why this tool and not another? We want one number that says "how much does token $q$ care about token $k$ ?" The dot product is the cheapest, most natural "alignment score" between two arrows — multiply matching entries, add them up. That is exactly the raw material attention is built from. (You will also see it written $q^{T} k$ ; the little $T$ means "written as a row so the multiplication lines up" — same number.)

4. Q, K, V: three roles for the same tokens

Attention gives each token three different vectors, playing three different roles.

Picture a library. Your query is the question in your head. Each book has a spine label — its key. You compare your question against every spine (dot products), and the books you pick hand you their contents — their value.

Why three roles? Because "what I want", "what I advertise", and "what I deliver" are genuinely different things, and letting the model learn them separately is what makes attention expressive.

5. Softmax: turning scores into a weighted average

Dot products give raw scores that can be any size. To combine values we need weights that are positive and add up to 1 — a recipe for a weighted average.

Why the exponential and not just "divide by the sum"? Plain division breaks with negative scores (you could get negative or undefined weights). The exponential $e^{s}$ is always positive and grows fast, so the highest-scoring key dominates gently — a soft version of "pick the maximum", which is why it is called soft-max.

Now the full attention formula the parent opens with reads in plain words: $Attention (Q, K, V) = softmax (\frac{Q K ^{T}}{d _{k}}) V$ "Score every query against every key ( $Q K^{T}$ ), shrink the scores so they don't explode (divide by $d_{k}$ ), turn scores into a weighted average (softmax), then use those weights to blend the values ( $\times V$ )." The $d_{k}$ is just a scaling constant ( $d_{k}$ = key dimension) that keeps the numbers in a sane range.

6. Where $O (n^{2})$ comes from: Big-O and the cost picture

The heart of the whole chapter is one picture: the $n \times n$ attention grid.

Every query (a row) must dot-product with every key (a column). That fills an $n$ -by- $n$ grid of scores — $n \times n = n^{2}$ comparisons. At $n = 100, 000$ that is $1 0^{10}$ (ten billion) comparisons per layer. This single grid is the enemy. Every architecture in the parent note — sparse patterns, linear attention, state-space models, memory banks — is a different way to avoid filling the whole grid. See Computational Complexity for the general language of these growth rates.

7. Two escape hatches you'll meet

Two more ideas make the "escape from $n^{2}$ " possible. You don't need to master them yet — just recognise the words.

Two more names appear as destinations of these tricks: Retrieval-Augmented Generation (fetch relevant chunks instead of reading all of them) and the Information Bottleneck (the theory of what a fixed-size summary is forced to throw away). We only flag them here.

How the foundations feed the topic

Read it top to bottom: sequences become vectors, vectors get compared by dot products, dot products become Q-K-V attention, softmax blends the values, that fills an $n \times n$ grid whose cost explodes as $n^{2}$ — and that explosion is the problem long-context architectures exist to solve, using extra tools like the hidden state $h$ and the feature map $ϕ$ .

Equipment checklist

What does

n

stand for?

The number of tokens in the sequence — the length everything is measured against.

What is

d

The embedding dimension: how many numbers represent one token.

Compute

q \cdot k

for

q = (2, 0, 1)

k = (1, 3, 1)

2 \cdot 1 + 0 \cdot 3 + 1 \cdot 1 = 3

What are the three roles Q, K, V play?

Query = what I'm looking for; Key = what I advertise; Value = what I deliver.

Why does softmax use the exponential

e^{s}

To make every weight positive and let big scores dominate softly, so weights sum to 1.

What does

O (n^{2})

mean in plain words?

The cost grows like the area of a square — double

n

and cost quadruples.

Where does the

n^{2}

in attention come from?

Every one of

n

queries dot-products with every one of

n

keys, filling an

n \times n

grid.

What is a hidden state

h

A fixed-size running summary of everything seen so far — a notepad you overwrite, never growing.

What is a feature map

ϕ

for?

To rewrite vectors so a cheap dot product imitates the expensive

e^{q \cdot k}