Appendix B — Math: Attention Geometry, KV Cache, and Sampling

Chapter 35 treats cost and latency in production terms. This appendix is the optional math that makes those knobs intuitive. Symbols are defined before use.

Tokens and embeddings

Let the vocabulary be (V). A token sequence is (x_1,\ldots,x_n) with (x_i \in V). An embedding map (E: V \rightarrow \mathbb{R}^{d}) yields vectors (e_i = E(x_i)). Positional information is added by the architecture (absolute, relative, or RoPE-style); details vary by model.

Attention (one head, conceptual)

For queries, keys, values (Q,K,V \in \mathbb{R}^{n \times d_h}):

[ \mathrm{Attention}(Q,K,V) = \mathrm{softmax}!\left(\frac{QK^\top}{\sqrt{d_h}}\right) V ]

Row (i) of the softmax matrix is a distribution over positions that token (i) attends to. Lost-in-the-Middle (Liu et al., 2023) is an empirical observation that mid-context evidence is often under-used — hence context assemblers pin critical constraints at edges and budgets (Ch 3).

KV cache

During autoregressive decode, at step (t) the model has already computed keys and values for positions (1..t-1). The KV cache stores those tensors so step (t) only computes the new row for token (t), then appends it.

Rough memory scale (order-of-magnitude teaching bound):

[ \mathrm{Mem}{\mathrm{KV}} \approx 2 \cdot L \cdot n \cdot d{h} \cdot n_{\mathrm{heads}} \cdot b \cdot q ]

where (L) is layers, (n) sequence length, (b) batch, (q) bytes per element (e.g. 2 for fp16), and the factor (2) counts keys and values. Exact layouts differ (GQA/MQA reduce key/value heads). PagedAttention (Kwon et al., 2023) pages this memory for serving efficiency.

Design implication: long tool traces in context inflate KV memory and latency. Assemblers that summarize or truncate are not cosmetic.

Prompt / prefix cache

Distinct from KV during a single decode: prefix / prompt cache reuses billed or computed prefix state across requests when the leading token bytes are stable. Stable pinned policy blocks (Ch 3, 35) raise hit rates; shuffling the preamble destroys them.

Sampling

Given logits (z \in \mathbb{R}^{|V|}), a temperature (T > 0) scales:

[ p_i = \frac{\exp(z_i / T)}{\sum_j \exp(z_j / T)} ]

Common truncations: top-(k), nucleus (top-(p)) (Holtzman et al., 2020). Sampling is not an oracle. Structured outputs and schema validation exist because samples are stochastic and sometimes ill-formed.

Greedy ((T \rightarrow 0) / argmax) reduces randomness but not hallucination of facts.

Speculative decoding (brief)

A small draft model proposes tokens; a large model verifies in parallel batches — latency trade-off when available. [VERIFY] against your serving stack. Treat as an optimization, not a correctness tool.

What this changes in agent design

References

• Vaswani et al., 2017. Attention Is All You Need. arXiv:1706.03762
• Liu et al., 2023. Lost in the Middle. arXiv:2307.03172
• Kwon et al., 2023. PagedAttention / vLLM (SOSP)
• Holtzman et al., 2020. The Curious Case of Neural Text Degeneration. arXiv:1904.09751
• Vendor prompt-caching docs — [VERIFY per vendor]