From first principles to research-level detail — for every reader.
For a 10th grader: Computers can't read words. Each word (or sub-word "token") is first looked up in a giant vocabulary table and converted to a unique integer ID. Then that ID is mapped to a long list of 768 or 4096 numbers called an embedding vector — the model's internal representation of that word.
For a researcher: Token IDs are projected through a learned embedding matrix E ∈ ℝ^(V×d). Positional encodings (sinusoidal or RoPE) are added to inject sequence order. The result is X ∈ ℝ^(n×d) — the input to the first transformer layer.
For a 10th grader: Imagine you're at a library. Your Query is the question you ask ("find me books about cats"). Each book has a Key (its title/description). The library matches your query to keys and returns the most relevant book's Value (the actual content). Attention does exactly this — every token asks a question (Q), every other token has a label (K) and content (V).
For a researcher: For each layer, three learned projection matrices map the input: Q = XW_Q, K = XW_K, V = XW_V where W_Q, W_K, W_V ∈ ℝ^(d×d_k). The attention score for token i attending to token j is:
For a 10th grader: The dot products QKᵀ give a raw "how relevant is token j to token i?" score. Softmax converts these into probabilities that sum to 1.0. High probability = "pay a lot of attention to this token." Low probability = "mostly ignore this."
For a researcher: The pre-softmax logits are scaled by 1/√d_k to prevent gradient vanishing in deep layers (Vaswani et al., 2017). A causal mask sets future positions to −∞ before softmax. The output distribution reveals which past tokens each query attends to — this is what we analyze in Proactive Cache.
For a 10th grader: Instead of one librarian answering your question, imagine 12 or 32 parallel librarians, each looking for different things — one looks for grammar connections, one for semantic meaning, one for nearby context. Their answers are combined at the end. This is Multi-Head Attention.
For a researcher: MultiHead(Q,K,V) = Concat(head_1, ..., head_h) W_O where head_i = Attention(QW_Qi, KW_Ki, VW_Vi). With GPT-2 large: h=16 heads, d_k=64. With LLaMA-3.1-8B: h=32 heads, d_k=128. Each head independently learns to attend to different structural, syntactic, or semantic patterns — confirmed by our Phase 0 experiments.
For a 10th grader: When generating text word-by-word, the model needs to look at all previous words every step. Recomputing K and V for all previous tokens every step would be incredibly slow. Instead, we save (cache) K and V after computing them once — the KV Cache. But this cache grows with every new token, eating GPU memory.
For a researcher: KV cache memory is O(n · L · h · d_k · 2 · sizeof(dtype)) bytes, where n=seq length, L=layers, h=heads. For LLaMA-3.1-8B at n=4096 in FP16: ~2 GB of KV cache alone. This is the primary memory bottleneck for long-context inference and the direct motivation for cache eviction.
Strategy: Keep the first 4 "sink" tokens + a sliding window of the most recent tokens.
Complexity: O(1) per decode step ✅
Problem: The entire middle of the document is evicted. Long-range dependencies (e.g., a character's name mentioned 2000 tokens ago) are permanently lost.
PPL at budget=512 on books: 156.22 (+803%)
Strategy: At every decode step, compute query-key dot products against all cached tokens. Keep the top-k highest-scoring ones.
Complexity: O(n) per decode step ❌ → O(n²) total
Problem: The scoring itself requires a full attention pass over cached tokens — exactly the computation we were trying to avoid. SnapKV collapses to PPL 55,540 under 75% eviction.
H2O PPL at budget=128: 214.06 (+997%)
Strategy: Offline, profile attention patterns on WikiText. Cluster key-state vectors into spatial prototypes. At inference, score tokens against prototypes once during prefill — no runtime scoring ever.
Complexity: O(1) per decode step ✅ (zero query overhead)
Result: Retains sinks + long-range semantic anchors + recency window simultaneously — best of all worlds.
PPL at budget=512 on books: 26.14 (5.98× better than StreamingLLM)
OFFLINE PROFILING (done once, ~1 minute):
for doc in wikitext_corpus[:300]:
run forward pass, collect K-states per (layer, head)
cluster K-states with K-Means into B prototype vectors
INFERENCE (prefill, O(n)):
for each token t in prompt:
compute score(t) = max_prototype cosine_similarity(K_t, prototypes)
mark top-B tokens as RETAIN, rest as EVICT
INFERENCE (decode, O(1) per step):
for each new generated token:
attention only over RETAINED tokens (fixed budget B)
→ constant-time regardless of total sequence length!
TL;DR for PhD Reviewers: Proactive Cache exploits the empirically-validated frozen structure of attention distributions across documents to replace dynamic O(n) per-step importance scoring with a static, query-free, pre-computed token mask. This reduces decode-step attention from O(n²) total to O(n·B) where B≪n is a fixed constant — empirically achieving 3.09× wall-clock speedup and 5.98× perplexity improvement over StreamingLLM at budget=512 on long-form text.
O(1) Decode-Step Attention for Any Transformer via Training-Free Proactive KV Cache Eviction
Standard cache pruning strategies (SnapKV, H2O) calculate query-key scores at every single decode step, resulting in O(n) attention cost per step and overall quadratic complexity. Proactive Cache learns token importance patterns offline once. During generation, each decode step only attends to a fixed constant budget B of key-value tokens, reducing the per-step attention calculation to O(1) constant time with absolutely zero query matching overhead!