{
 "cells": [
  {
   "cell_type": "raw",
   "metadata": {},
   "source": [
    "---\n",
    "execute:\n",
    "  enabled: false\n",
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=kv-cache-md-1 fw=all -->\n",
    "\n",
    "# Generation and the KV Cache\n",
    "\n",
    "The `generate` method of that section was left deliberately naive:\n",
    "every new token reruns the full forward pass over the whole history. This\n",
    "section measures that waste, eliminates it, and then studies what the fix\n",
    "costs. The fix is the *KV cache*: because causal attention never lets the\n",
    "past depend on the future, the keys and values of every token already\n",
    "generated are final the moment they are computed, and can simply be stored.\n",
    "Caching makes the dominant dense-layer work linear in the generated length\n",
    "— attention itself still reads the whole growing cache at every step, so\n",
    "its cumulative cost stays quadratic, a term that is real but subdominant at\n",
    "the sizes we run — and it converts a compute problem into a *memory*\n",
    "problem, so the second half of this section is about the bill. We derive\n",
    "the cache-size formula and check it against the allocator, see why\n",
    "generating tokens is bound by memory\n",
    "bandwidth while reading a prompt is bound by arithmetic, and then shrink\n",
    "the cache three ways: sharing keys and values across heads (MQA and GQA),\n",
    "compressing them to a low-rank latent (the idea behind MLA), and bounding\n",
    "the context with a sliding window, which works only together with a\n",
    "counterintuitive companion, the *attention sink*. Everything runs on the\n",
    "`d2l.GPT` class of the previous section, including the real GPT-2, which\n",
    "supplies the phenomena that our one-minute character models are too small\n",
    "to show."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "kv-cache-generation-and-the-kv-cache"
   },
   "source": [
    "%matplotlib inline\n",
    "from d2l import jax as d2l\n",
    "from flax import nnx\n",
    "import jax\n",
    "from jax import numpy as jnp\n",
    "import math\n",
    "import optax\n",
    "from safetensors import numpy as safetensors_numpy\n",
    "import tiktoken\n",
    "from tiktoken.load import data_gym_to_mergeable_bpe_ranks\n",
    "import time"
   ],
   "execution_count": 1,
   "outputs": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=kv-cache-md-2 fw=all -->\n",
    "\n",
    "## From Recompute to Cache\n",
    "\n",
    "Start with the accounting. A forward pass of a model with $N$ parameters\n",
    "over $t$ tokens costs about $2Nt$ floating-point operations — every\n",
    "parameter participates in one multiply–add per token — plus the attention\n",
    "score work of that section, which is quadratic in $t$\n",
    "but subdominant at the model sizes we run here. Naive generation calls\n",
    "this forward pass once per token, over a history that grows by one each\n",
    "step: producing $T$ tokens after a prompt costs roughly\n",
    "$\\sum_{t} 2Nt \\approx N T^2$ operations, quadratic in the length of the\n",
    "text, for logits of which all but the last row are thrown away.\n",
    "\n",
    "Almost all of that work is literally repeated. At step $t$ the model\n",
    "needs, in every layer, the attention output for one new query\n",
    "$\\mathbf{q}_t$ against the keys and values $\\mathbf{k}_{1..t},\n",
    "\\mathbf{v}_{1..t}$. The causal mask guarantees that positions\n",
    "$1, \\ldots, t-1$ never see position $t$, so their hidden states — and\n",
    "therefore their keys and values — are the same at step $t$ as they were at\n",
    "step $t-1$. The fix writes itself: keep a per-layer buffer of all keys and\n",
    "values computed so far, and at each step run the transformer on *one*\n",
    "token, appending its $\\mathbf{k}_t, \\mathbf{v}_t$ to the buffer and\n",
    "attending against the whole of it. the figure contrasts the\n",
    "two schedules. The cost of a cached step is one forward pass over a single\n",
    "token, about $2N$ operations, independent of $t$.\n",
    "\n",
    "![One decoding step at context length $t$. Naive generation recomputes every key, value, and score row of the prefix and then uses only the last row. With a KV cache, the past keys and values are read from memory, and the step computes a single new key, value, and score row.](../img/mdl-transformers-kv-cache.svg)\n",
    "\n",
    "### The Cached Forward Pass\n",
    "\n",
    "Two details need care. First, positions: RoPE rotates queries and keys by\n",
    "their *absolute* position, so the attention step must know where in the\n",
    "sequence its tokens sit — the `_rope` helper of `d2l.GPT` always counted\n",
    "from zero, and we now need an `offset`. (A learned position table needs\n",
    "the same offset, one line in the model forward.) Second, the interface:\n",
    "the step receives only the *new* tokens plus the cache, instead of the\n",
    "whole history."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=kv-cache-md-3 fw=jax -->\n",
    "\n",
    "Growing a tensor by one slot per step would be poison for JAX: every new\n",
    "length is a new shape, and every new shape triggers a fresh XLA\n",
    "compilation. The naive `generate` of that section already solved\n",
    "this problem once, by allocating the token buffer at its final size and\n",
    "overwriting it. The cache follows the same discipline, and it is exactly\n",
    "how production JAX serving works: preallocate K and V buffers of shape\n",
    "`(layers, batch, max_len, heads, head_dim)`, write each step's keys and\n",
    "values into their slots with `dynamic_update_slice`, and mask attention\n",
    "so that queries only see filled positions. The function compiles once\n",
    "for the prompt shape and once for the single-token step, and the decode\n",
    "loop then reuses that compilation at every step — static shapes are not a\n",
    "limitation here but the feature that makes the compiled path possible."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "kv-cache-the-cached-forward-pass-1"
   },
   "source": [
    "def rope(x, offset=0):\n",
    "    \"\"\"Rotary rotation of x at absolute positions offset, offset+1, ...\"\"\"\n",
    "    d = x.shape[-1]\n",
    "    pos = offset + jnp.arange(x.shape[1])\n",
    "    inv_freq = 10000.0 ** (-jnp.arange(0, d, 2) / d)\n",
    "    theta = pos[:, None] * inv_freq[None, :]\n",
    "    cos = jnp.cos(theta)[:, None, :]  # broadcast over heads\n",
    "    sin = jnp.sin(theta)[:, None, :]\n",
    "    x1, x2 = x[..., 0::2], x[..., 1::2]\n",
    "    return jnp.stack([x1 * cos - x2 * sin,\n",
    "                      x1 * sin + x2 * cos], -1).reshape(x.shape)\n",
    "\n",
    "def init_cache(model, batch_size, max_len):\n",
    "    \"\"\"Preallocated K and V buffers, one slab per layer.\"\"\"\n",
    "    attn = model.blks[0].attention\n",
    "    head_dim = attn.W_o.in_features // attn.num_heads\n",
    "    shape = (len(model.blks), batch_size, max_len, attn.num_heads, head_dim)\n",
    "    return jnp.zeros(shape), jnp.zeros(shape)"
   ],
   "execution_count": 2,
   "outputs": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=kv-cache-md-4 fw=all -->\n",
    "\n",
    "The model-level step walks the blocks the way `d2l.GPT.forward` does,\n",
    "handing each block's attention its cache; a `generate_cached` then\n",
    "repeats the sampling loop of that section, prefixed by a single\n",
    "prefill call, with each subsequent step feeding in one token."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "kv-cache-the-cached-forward-pass-2"
   },
   "source": [
    "@nnx.jit\n",
    "def cached_forward(model, ks, vs, X, t):\n",
    "    \"\"\"Logits for the last of the new tokens X at positions t, t+1, ...;\n",
    "    writes their keys and values into the cache slots at those positions.\"\"\"\n",
    "    B, T = X.shape\n",
    "    H = model.token_emb(X)\n",
    "    if model.pos == 'learned':\n",
    "        H = H + model.pos_emb(t + jnp.arange(T))\n",
    "    mask = (jnp.arange(ks.shape[2])[None, :]\n",
    "            <= (t + jnp.arange(T))[:, None])[None, None]\n",
    "    for i, blk in enumerate(model.blks):  # pre-norm arrangement\n",
    "        attn, Y = blk.attention, blk.norm1(H)\n",
    "        q, k, v = jnp.split(attn.W_qkv(Y), 3, axis=-1)\n",
    "        q, k, v = (u.reshape(B, T, attn.num_heads, -1) for u in (q, k, v))\n",
    "        if attn.rope:\n",
    "            q, k = rope(q, t), rope(k, t)\n",
    "        # Callers must keep t + T <= max_len: an out-of-range write does\n",
    "        # not fail here -- dynamic_update_slice clamps its start index\n",
    "        # silently. (t is traced under jit, so generate_cached asserts.)\n",
    "        ks = jax.lax.dynamic_update_slice(ks, k[None], (i, 0, t, 0, 0))\n",
    "        vs = jax.lax.dynamic_update_slice(vs, v[None], (i, 0, t, 0, 0))\n",
    "        Y = jax.nn.dot_product_attention(q, ks[i], vs[i], mask=mask)\n",
    "        H = H + attn.W_o(Y.reshape(B, T, -1))\n",
    "        H = H + blk.ffn(blk.norm2(H))\n",
    "    return model.token_emb.attend(model.norm(H))[:, -1], ks, vs\n",
    "\n",
    "@d2l.add_to_class(d2l.GPT)\n",
    "def generate_cached(self, prefix, num_tokens, seed=0, temperature=1.0,\n",
    "                    top_k=None):\n",
    "    \"\"\"Sample as generate does, but never recompute the prefix.\"\"\"\n",
    "    assert len(prefix) + num_tokens <= self.max_len, 'cache overflow'\n",
    "    ks, vs = init_cache(self, 1, self.max_len)\n",
    "    logits, ks, vs = cached_forward(self, ks, vs,\n",
    "                                    jnp.asarray(prefix)[None], jnp.array(0))\n",
    "    ids, key = list(prefix), jax.random.key(seed)\n",
    "    for t in range(len(prefix), len(prefix) + num_tokens):\n",
    "        l = logits[0] / temperature\n",
    "        if top_k is not None:\n",
    "            l = jnp.where(l < jnp.sort(l)[-top_k], -jnp.inf, l)\n",
    "        key, sub = jax.random.split(key)\n",
    "        ids.append(int(jax.random.categorical(sub, l)))\n",
    "        logits, ks, vs = cached_forward(self, ks, vs,\n",
    "                                        jnp.asarray([[ids[-1]]]),\n",
    "                                        jnp.array(t))\n",
    "    return ids"
   ],
   "execution_count": 3,
   "outputs": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=kv-cache-md-5 fw=all -->\n",
    "\n",
    "### Same Logits, Measured\n",
    "\n",
    "A cache is an optimization, and the first duty of an optimization is to\n",
    "change nothing. We compare the cached path against the full forward pass\n",
    "on both positional schemes: prefill sixteen tokens, then decode one at a\n",
    "time, and stack the resulting logits against those of a single\n",
    "whole-sequence call."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "kv-cache-same-logits-measured-1"
   },
   "source": [
    "with jax.default_matmul_precision('highest'):\n",
    "    for pos in ('rope', 'learned'):\n",
    "        model = d2l.GPT(vocab_size=97, num_hiddens=128, num_heads=4,\n",
    "                        num_blks=3, pos=pos, rngs=nnx.Rngs(0))\n",
    "        model.eval()\n",
    "        x = jax.random.randint(jax.random.key(1), (1, 48), 0, 97)\n",
    "        full = model(x)\n",
    "        ks, vs = init_cache(model, 1, 64)\n",
    "        logits, ks, vs = cached_forward(model, ks, vs, x[:, :16],\n",
    "                                        jnp.array(0))\n",
    "        outs = [logits]\n",
    "        for t in range(16, 48):\n",
    "            logits, ks, vs = cached_forward(model, ks, vs, x[:, t:t + 1],\n",
    "                                            jnp.array(t))\n",
    "            outs.append(logits)\n",
    "        err = jnp.abs(jnp.stack([o[0] for o in outs]) - full[0, 15:]).max()\n",
    "        print(f'{pos}: max |full - cached| = {err:.2e}')"
   ],
   "execution_count": 4,
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "rope: max |full - cached| = 9.39e-07\n"
     ]
    },
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "learned: max |full - cached| = 8.34e-07\n"
     ]
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=kv-cache-md-6 fw=jax -->\n",
    "\n",
    "(We pin matrix multiplications to full fp32 for the comparison, as in\n",
    "that section: by default they run in TF32 on this\n",
    "hardware, which perturbs the two computation orders differently at the\n",
    "$10^{-4}$ level and would obscure the fact that they are the same\n",
    "computation.)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=kv-cache-md-7 fw=all -->\n",
    "\n",
    "Agreement to floating-point rounding. Now the payoff. We time a single\n",
    "generation step at growing context length on a GPT-2-sized instance of\n",
    "our class — 124M parameters, untrained, since arithmetic does not care\n",
    "what the weights are. The naive step is a full forward pass over $n$\n",
    "tokens; the cached step is a forward pass over one token against a cache\n",
    "of length $n-1$."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "kv-cache-same-logits-measured-2"
   },
   "source": [
    "model = d2l.GPT(vocab_size=50257, num_hiddens=768, num_heads=12,\n",
    "                num_blks=12, max_len=4096, rngs=nnx.Rngs(0))\n",
    "model.eval()\n",
    "n_params = sum(p.size for p in jax.tree.leaves(nnx.state(model, nnx.Param)))\n",
    "print(f'{n_params / 1e6:.1f}M parameters')\n",
    "\n",
    "@nnx.jit\n",
    "def naive_step(model, buf, t):\n",
    "    \"\"\"The step inside the naive generate: a full forward pass.\"\"\"\n",
    "    return model(buf)[0, t - 1]\n",
    "\n",
    "def timeit(f, reps=10):\n",
    "    f().block_until_ready()         # warm up (and compile)\n",
    "    t0 = time.time()\n",
    "    for _ in range(reps):\n",
    "        f().block_until_ready()\n",
    "    return (time.time() - t0) / reps\n",
    "\n",
    "lengths, t_naive, t_cached = [512, 1024, 2048, 4096], [], []\n",
    "for n in lengths:\n",
    "    buf = jnp.zeros((1, n), dtype=jnp.int32)\n",
    "    t_naive.append(\n",
    "        timeit(lambda: naive_step(model, buf, jnp.array(n - 1))) * 1e3)\n",
    "    ks, vs = init_cache(model, 1, n)\n",
    "    one = jnp.zeros((1, 1), dtype=jnp.int32)\n",
    "    t_cached.append(timeit(lambda: cached_forward(\n",
    "        model, ks, vs, one, jnp.array(n - 1))[0]) * 1e3)\n",
    "    print(f'n={n:5d}: naive {t_naive[-1]:6.2f} ms/token, '\n",
    "          f'cached {t_cached[-1]:5.2f} ms/token')\n",
    "d2l.plot(lengths, [t_naive, t_cached], 'context length', 'ms per token',\n",
    "         legend=['naive', 'cached'], xscale='log', yscale='log')"
   ],
   "execution_count": 5,
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "123.6M parameters\n"
     ]
    },
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "n=  512: naive  31.27 ms/token, cached 11.53 ms/token\n"
     ]
    },
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "n= 1024: naive  14.83 ms/token, cached 11.30 ms/token\n"
     ]
    },
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "n= 2048: naive  42.23 ms/token, cached 12.44 ms/token\n"
     ]
    },
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "n= 4096: naive  76.04 ms/token, cached 12.12 ms/token\n"
     ]
    },
    {
     "output_type": "display_data",
     "data": {
      "image/svg+xml": "<?xml version=\"1.0\" encoding=\"utf-8\" standalone=\"no\"?>\n<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n  \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n<svg xmlns:xlink=\"http://www.w3.org/1999/xlink\" width=\"272.175904pt\" height=\"183.35625pt\" viewBox=\"0 0 272.175904 183.35625\" xmlns=\"http://www.w3.org/2000/svg\" version=\"1.1\">\n <metadata>\n  <rdf:RDF xmlns:dc=\"http://purl.org/dc/elements/1.1/\" xmlns:cc=\"http://creativecommons.org/ns#\" xmlns:rdf=\"http://www.w3.org/1999/02/22-rdf-syntax-ns#\">\n   <cc:Work>\n    <dc:type rdf:resource=\"http://purl.org/dc/dcmitype/StillImage\"/>\n    <dc:date>2026-07-19T15:13:48.025412</dc:date>\n    <dc:format>image/svg+xml</dc:format>\n    <dc:creator>\n     <cc:Agent>\n      <dc:title>Matplotlib v3.10.8, https://matplotlib.org/</dc:title>\n     </cc:Agent>\n    </dc:creator>\n   </cc:Work>\n  </rdf:RDF>\n </metadata>\n <defs>\n  <style type=\"text/css\">*{stroke-linejoin: round; stroke-linecap: butt}</style>\n </defs>\n <g id=\"figure_1\">\n  <g id=\"patch_1\">\n   <path d=\"M 0 183.35625 \nL 272.175904 183.35625 \nL 272.175904 0 \nL 0 0 \nz\n\" style=\"fill: #ffffff\"/>\n  </g>\n  <g id=\"axes_1\">\n   <g id=\"patch_2\">\n    <path d=\"M 62.478125 145.8 \nL 257.778125 145.8 \nL 257.778125 7.2 \nL 62.478125 7.2 \nz\n\" style=\"fill: #ffffff\"/>\n   </g>\n   <g id=\"matplotlib.axis_1\">\n    <g id=\"xtick_1\">\n     <g id=\"line2d_1\">\n      <path d=\"M 128.512268 145.8 \nL 128.512268 7.2 \n\" clip-path=\"url(#p01c68ec550)\" style=\"fill: none; stroke: #b0b0b0; stroke-width: 0.8; stroke-linecap: square\"/>\n     </g>\n     <g id=\"line2d_2\">\n      <defs>\n       <path id=\"me9db1c838f\" d=\"M 0 0 \nL 0 3.5 \n\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </defs>\n      <g>\n       <use xlink:href=\"#me9db1c838f\" x=\"128.512268\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_1\">\n      <!-- $\\mathdefault{10^{3}}$ -->\n      <g transform=\"translate(119.712268 160.398438) scale(0.1 -0.1)\">\n       <defs>\n        <path id=\"DejaVuSans-31\" d=\"M 794 531 \nL 1825 531 \nL 1825 4091 \nL 703 3866 \nL 703 4441 \nL 1819 4666 \nL 2450 4666 \nL 2450 531 \nL 3481 531 \nL 3481 0 \nL 794 0 \nL 794 531 \nz\n\" transform=\"scale(0.015625)\"/>\n        <path id=\"DejaVuSans-30\" d=\"M 2034 4250 \nQ 1547 4250 1301 3770 \nQ 1056 3291 1056 2328 \nQ 1056 1369 1301 889 \nQ 1547 409 2034 409 \nQ 2525 409 2770 889 \nQ 3016 1369 3016 2328 \nQ 3016 3291 2770 3770 \nQ 2525 4250 2034 4250 \nz\nM 2034 4750 \nQ 2819 4750 3233 4129 \nQ 3647 3509 3647 2328 \nQ 3647 1150 3233 529 \nQ 2819 -91 2034 -91 \nQ 1250 -91 836 529 \nQ 422 1150 422 2328 \nQ 422 3509 836 4129 \nQ 1250 4750 2034 4750 \nz\n\" transform=\"scale(0.015625)\"/>\n        <path id=\"DejaVuSans-33\" d=\"M 2597 2516 \nQ 3050 2419 3304 2112 \nQ 3559 1806 3559 1356 \nQ 3559 666 3084 287 \nQ 2609 -91 1734 -91 \nQ 1441 -91 1130 -33 \nQ 819 25 488 141 \nL 488 750 \nQ 750 597 1062 519 \nQ 1375 441 1716 441 \nQ 2309 441 2620 675 \nQ 2931 909 2931 1356 \nQ 2931 1769 2642 2001 \nQ 2353 2234 1838 2234 \nL 1294 2234 \nL 1294 2753 \nL 1863 2753 \nQ 2328 2753 2575 2939 \nQ 2822 3125 2822 3475 \nQ 2822 3834 2567 4026 \nQ 2313 4219 1838 4219 \nQ 1578 4219 1281 4162 \nQ 984 4106 628 3988 \nL 628 4550 \nQ 988 4650 1302 4700 \nQ 1616 4750 1894 4750 \nQ 2613 4750 3031 4423 \nQ 3450 4097 3450 3541 \nQ 3450 3153 3228 2886 \nQ 3006 2619 2597 2516 \nz\n\" transform=\"scale(0.015625)\"/>\n       </defs>\n       <use xlink:href=\"#DejaVuSans-31\" transform=\"translate(0 0.765625)\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(63.623047 0.765625)\"/>\n       <use xlink:href=\"#DejaVuSans-33\" transform=\"translate(128.203125 39.046875) scale(0.7)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_2\">\n     <g id=\"line2d_3\">\n      <defs>\n       <path id=\"m475a14514f\" d=\"M 0 0 \nL 0 2 \n\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </defs>\n      <g>\n       <use xlink:href=\"#m475a14514f\" x=\"69.330449\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_3\">\n     <g id=\"line2d_4\">\n      <g>\n       <use xlink:href=\"#m475a14514f\" x=\"84.897304\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n     <g id=\"text_2\">\n      <!-- $\\mathdefault{6\\times10^{2}}$ -->\n      <g transform=\"translate(66.797304 158.798438) scale(0.1 -0.1)\">\n       <defs>\n        <path id=\"DejaVuSans-36\" d=\"M 2113 2584 \nQ 1688 2584 1439 2293 \nQ 1191 2003 1191 1497 \nQ 1191 994 1439 701 \nQ 1688 409 2113 409 \nQ 2538 409 2786 701 \nQ 3034 994 3034 1497 \nQ 3034 2003 2786 2293 \nQ 2538 2584 2113 2584 \nz\nM 3366 4563 \nL 3366 3988 \nQ 3128 4100 2886 4159 \nQ 2644 4219 2406 4219 \nQ 1781 4219 1451 3797 \nQ 1122 3375 1075 2522 \nQ 1259 2794 1537 2939 \nQ 1816 3084 2150 3084 \nQ 2853 3084 3261 2657 \nQ 3669 2231 3669 1497 \nQ 3669 778 3244 343 \nQ 2819 -91 2113 -91 \nQ 1303 -91 875 529 \nQ 447 1150 447 2328 \nQ 447 3434 972 4092 \nQ 1497 4750 2381 4750 \nQ 2619 4750 2861 4703 \nQ 3103 4656 3366 4563 \nz\n\" transform=\"scale(0.015625)\"/>\n        <path id=\"DejaVuSans-d7\" d=\"M 4488 3438 \nL 3059 2003 \nL 4488 575 \nL 4116 197 \nL 2681 1631 \nL 1247 197 \nL 878 575 \nL 2303 2003 \nL 878 3438 \nL 1247 3816 \nL 2681 2381 \nL 4116 3816 \nL 4488 3438 \nz\n\" transform=\"scale(0.015625)\"/>\n        <path id=\"DejaVuSans-32\" d=\"M 1228 531 \nL 3431 531 \nL 3431 0 \nL 469 0 \nL 469 531 \nQ 828 903 1448 1529 \nQ 2069 2156 2228 2338 \nQ 2531 2678 2651 2914 \nQ 2772 3150 2772 3378 \nQ 2772 3750 2511 3984 \nQ 2250 4219 1831 4219 \nQ 1534 4219 1204 4116 \nQ 875 4013 500 3803 \nL 500 4441 \nQ 881 4594 1212 4672 \nQ 1544 4750 1819 4750 \nQ 2544 4750 2975 4387 \nQ 3406 4025 3406 3419 \nQ 3406 3131 3298 2873 \nQ 3191 2616 2906 2266 \nQ 2828 2175 2409 1742 \nQ 1991 1309 1228 531 \nz\n\" transform=\"scale(0.015625)\"/>\n       </defs>\n       <use xlink:href=\"#DejaVuSans-36\" transform=\"translate(0 0.765625)\"/>\n       <use xlink:href=\"#DejaVuSans-d7\" transform=\"translate(83.105469 0.765625)\"/>\n       <use xlink:href=\"#DejaVuSans-31\" transform=\"translate(186.376953 0.765625)\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(250 0.765625)\"/>\n       <use xlink:href=\"#DejaVuSans-32\" transform=\"translate(314.580078 39.046875) scale(0.7)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_4\">\n     <g id=\"line2d_5\">\n      <g>\n       <use xlink:href=\"#m475a14514f\" x=\"98.058892\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_5\">\n     <g id=\"line2d_6\">\n      <g>\n       <use xlink:href=\"#m475a14514f\" x=\"109.459978\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_6\">\n     <g id=\"line2d_7\">\n      <g>\n       <use xlink:href=\"#m475a14514f\" x=\"119.516448\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_7\">\n     <g id=\"line2d_8\">\n      <g>\n       <use xlink:href=\"#m475a14514f\" x=\"187.694086\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n     <g id=\"text_3\">\n      <!-- $\\mathdefault{2\\times10^{3}}$ -->\n      <g transform=\"translate(169.594086 158.798438) scale(0.1 -0.1)\">\n       <use xlink:href=\"#DejaVuSans-32\" transform=\"translate(0 0.765625)\"/>\n       <use xlink:href=\"#DejaVuSans-d7\" transform=\"translate(83.105469 0.765625)\"/>\n       <use xlink:href=\"#DejaVuSans-31\" transform=\"translate(186.376953 0.765625)\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(250 0.765625)\"/>\n       <use xlink:href=\"#DejaVuSans-33\" transform=\"translate(314.580078 39.046875) scale(0.7)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_8\">\n     <g id=\"line2d_9\">\n      <g>\n       <use xlink:href=\"#m475a14514f\" x=\"222.31323\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n     <g id=\"text_4\">\n      <!-- $\\mathdefault{3\\times10^{3}}$ -->\n      <g transform=\"translate(204.21323 158.798438) scale(0.1 -0.1)\">\n       <use xlink:href=\"#DejaVuSans-33\" transform=\"translate(0 0.765625)\"/>\n       <use xlink:href=\"#DejaVuSans-d7\" transform=\"translate(83.105469 0.765625)\"/>\n       <use xlink:href=\"#DejaVuSans-31\" transform=\"translate(186.376953 0.765625)\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(250 0.765625)\"/>\n       <use xlink:href=\"#DejaVuSans-33\" transform=\"translate(314.580078 39.046875) scale(0.7)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_9\">\n     <g id=\"line2d_10\">\n      <g>\n       <use xlink:href=\"#m475a14514f\" x=\"246.875904\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n     <g id=\"text_5\">\n      <!-- $\\mathdefault{4\\times10^{3}}$ -->\n      <g transform=\"translate(228.775904 158.798438) scale(0.1 -0.1)\">\n       <defs>\n        <path id=\"DejaVuSans-34\" d=\"M 2419 4116 \nL 825 1625 \nL 2419 1625 \nL 2419 4116 \nz\nM 2253 4666 \nL 3047 4666 \nL 3047 1625 \nL 3713 1625 \nL 3713 1100 \nL 3047 1100 \nL 3047 0 \nL 2419 0 \nL 2419 1100 \nL 313 1100 \nL 313 1709 \nL 2253 4666 \nz\n\" transform=\"scale(0.015625)\"/>\n       </defs>\n       <use xlink:href=\"#DejaVuSans-34\" transform=\"translate(0 0.765625)\"/>\n       <use xlink:href=\"#DejaVuSans-d7\" transform=\"translate(83.105469 0.765625)\"/>\n       <use xlink:href=\"#DejaVuSans-31\" transform=\"translate(186.376953 0.765625)\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(250 0.765625)\"/>\n       <use xlink:href=\"#DejaVuSans-33\" transform=\"translate(314.580078 39.046875) scale(0.7)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"text_6\">\n     <!-- context length -->\n     <g transform=\"translate(123.755469 174.076563) scale(0.1 -0.1)\">\n      <defs>\n       <path id=\"DejaVuSans-63\" d=\"M 3122 3366 \nL 3122 2828 \nQ 2878 2963 2633 3030 \nQ 2388 3097 2138 3097 \nQ 1578 3097 1268 2742 \nQ 959 2388 959 1747 \nQ 959 1106 1268 751 \nQ 1578 397 2138 397 \nQ 2388 397 2633 464 \nQ 2878 531 3122 666 \nL 3122 134 \nQ 2881 22 2623 -34 \nQ 2366 -91 2075 -91 \nQ 1284 -91 818 406 \nQ 353 903 353 1747 \nQ 353 2603 823 3093 \nQ 1294 3584 2113 3584 \nQ 2378 3584 2631 3529 \nQ 2884 3475 3122 3366 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-6f\" d=\"M 1959 3097 \nQ 1497 3097 1228 2736 \nQ 959 2375 959 1747 \nQ 959 1119 1226 758 \nQ 1494 397 1959 397 \nQ 2419 397 2687 759 \nQ 2956 1122 2956 1747 \nQ 2956 2369 2687 2733 \nQ 2419 3097 1959 3097 \nz\nM 1959 3584 \nQ 2709 3584 3137 3096 \nQ 3566 2609 3566 1747 \nQ 3566 888 3137 398 \nQ 2709 -91 1959 -91 \nQ 1206 -91 779 398 \nQ 353 888 353 1747 \nQ 353 2609 779 3096 \nQ 1206 3584 1959 3584 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-6e\" d=\"M 3513 2113 \nL 3513 0 \nL 2938 0 \nL 2938 2094 \nQ 2938 2591 2744 2837 \nQ 2550 3084 2163 3084 \nQ 1697 3084 1428 2787 \nQ 1159 2491 1159 1978 \nL 1159 0 \nL 581 0 \nL 581 3500 \nL 1159 3500 \nL 1159 2956 \nQ 1366 3272 1645 3428 \nQ 1925 3584 2291 3584 \nQ 2894 3584 3203 3211 \nQ 3513 2838 3513 2113 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-74\" d=\"M 1172 4494 \nL 1172 3500 \nL 2356 3500 \nL 2356 3053 \nL 1172 3053 \nL 1172 1153 \nQ 1172 725 1289 603 \nQ 1406 481 1766 481 \nL 2356 481 \nL 2356 0 \nL 1766 0 \nQ 1100 0 847 248 \nQ 594 497 594 1153 \nL 594 3053 \nL 172 3053 \nL 172 3500 \nL 594 3500 \nL 594 4494 \nL 1172 4494 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-65\" d=\"M 3597 1894 \nL 3597 1613 \nL 953 1613 \nQ 991 1019 1311 708 \nQ 1631 397 2203 397 \nQ 2534 397 2845 478 \nQ 3156 559 3463 722 \nL 3463 178 \nQ 3153 47 2828 -22 \nQ 2503 -91 2169 -91 \nQ 1331 -91 842 396 \nQ 353 884 353 1716 \nQ 353 2575 817 3079 \nQ 1281 3584 2069 3584 \nQ 2775 3584 3186 3129 \nQ 3597 2675 3597 1894 \nz\nM 3022 2063 \nQ 3016 2534 2758 2815 \nQ 2500 3097 2075 3097 \nQ 1594 3097 1305 2825 \nQ 1016 2553 972 2059 \nL 3022 2063 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-78\" d=\"M 3513 3500 \nL 2247 1797 \nL 3578 0 \nL 2900 0 \nL 1881 1375 \nL 863 0 \nL 184 0 \nL 1544 1831 \nL 300 3500 \nL 978 3500 \nL 1906 2253 \nL 2834 3500 \nL 3513 3500 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-20\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-6c\" d=\"M 603 4863 \nL 1178 4863 \nL 1178 0 \nL 603 0 \nL 603 4863 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-67\" d=\"M 2906 1791 \nQ 2906 2416 2648 2759 \nQ 2391 3103 1925 3103 \nQ 1463 3103 1205 2759 \nQ 947 2416 947 1791 \nQ 947 1169 1205 825 \nQ 1463 481 1925 481 \nQ 2391 481 2648 825 \nQ 2906 1169 2906 1791 \nz\nM 3481 434 \nQ 3481 -459 3084 -895 \nQ 2688 -1331 1869 -1331 \nQ 1566 -1331 1297 -1286 \nQ 1028 -1241 775 -1147 \nL 775 -588 \nQ 1028 -725 1275 -790 \nQ 1522 -856 1778 -856 \nQ 2344 -856 2625 -561 \nQ 2906 -266 2906 331 \nL 2906 616 \nQ 2728 306 2450 153 \nQ 2172 0 1784 0 \nQ 1141 0 747 490 \nQ 353 981 353 1791 \nQ 353 2603 747 3093 \nQ 1141 3584 1784 3584 \nQ 2172 3584 2450 3431 \nQ 2728 3278 2906 2969 \nL 2906 3500 \nL 3481 3500 \nL 3481 434 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-68\" d=\"M 3513 2113 \nL 3513 0 \nL 2938 0 \nL 2938 2094 \nQ 2938 2591 2744 2837 \nQ 2550 3084 2163 3084 \nQ 1697 3084 1428 2787 \nQ 1159 2491 1159 1978 \nL 1159 0 \nL 581 0 \nL 581 4863 \nL 1159 4863 \nL 1159 2956 \nQ 1366 3272 1645 3428 \nQ 1925 3584 2291 3584 \nQ 2894 3584 3203 3211 \nQ 3513 2838 3513 2113 \nz\n\" transform=\"scale(0.015625)\"/>\n      </defs>\n      <use xlink:href=\"#DejaVuSans-63\"/>\n      <use xlink:href=\"#DejaVuSans-6f\" transform=\"translate(54.980469 0)\"/>\n      <use xlink:href=\"#DejaVuSans-6e\" transform=\"translate(116.162109 0)\"/>\n      <use xlink:href=\"#DejaVuSans-74\" transform=\"translate(179.541016 0)\"/>\n      <use xlink:href=\"#DejaVuSans-65\" transform=\"translate(218.75 0)\"/>\n      <use xlink:href=\"#DejaVuSans-78\" transform=\"translate(278.523438 0)\"/>\n      <use xlink:href=\"#DejaVuSans-74\" transform=\"translate(337.703125 0)\"/>\n      <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(376.912109 0)\"/>\n      <use xlink:href=\"#DejaVuSans-6c\" transform=\"translate(408.699219 0)\"/>\n      <use xlink:href=\"#DejaVuSans-65\" transform=\"translate(436.482422 0)\"/>\n      <use xlink:href=\"#DejaVuSans-6e\" transform=\"translate(498.005859 0)\"/>\n      <use xlink:href=\"#DejaVuSans-67\" transform=\"translate(561.384766 0)\"/>\n      <use xlink:href=\"#DejaVuSans-74\" transform=\"translate(624.861328 0)\"/>\n      <use xlink:href=\"#DejaVuSans-68\" transform=\"translate(664.070312 0)\"/>\n     </g>\n    </g>\n   </g>\n   <g id=\"matplotlib.axis_2\">\n    <g id=\"ytick_1\">\n     <g id=\"line2d_11\">\n      <defs>\n       <path id=\"m7d59ebbe47\" d=\"M 0 0 \nL -2 0 \n\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </defs>\n      <g>\n       <use xlink:href=\"#m7d59ebbe47\" x=\"62.478125\" y=\"101.760061\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n     <g id=\"text_7\">\n      <!-- $\\mathdefault{2\\times10^{1}}$ -->\n      <g transform=\"translate(20.878125 105.55928) scale(0.1 -0.1)\">\n       <use xlink:href=\"#DejaVuSans-32\" transform=\"translate(0 0.684375)\"/>\n       <use xlink:href=\"#DejaVuSans-d7\" transform=\"translate(83.105469 0.684375)\"/>\n       <use xlink:href=\"#DejaVuSans-31\" transform=\"translate(186.376953 0.684375)\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(250 0.684375)\"/>\n       <use xlink:href=\"#DejaVuSans-31\" transform=\"translate(314.580078 38.965625) scale(0.7)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_2\">\n     <g id=\"line2d_12\">\n      <g>\n       <use xlink:href=\"#m7d59ebbe47\" x=\"62.478125\" y=\"74.964623\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n     <g id=\"text_8\">\n      <!-- $\\mathdefault{3\\times10^{1}}$ -->\n      <g transform=\"translate(20.878125 78.763842) scale(0.1 -0.1)\">\n       <use xlink:href=\"#DejaVuSans-33\" transform=\"translate(0 0.684375)\"/>\n       <use xlink:href=\"#DejaVuSans-d7\" transform=\"translate(83.105469 0.684375)\"/>\n       <use xlink:href=\"#DejaVuSans-31\" transform=\"translate(186.376953 0.684375)\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(250 0.684375)\"/>\n       <use xlink:href=\"#DejaVuSans-31\" transform=\"translate(314.580078 38.965625) scale(0.7)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_3\">\n     <g id=\"line2d_13\">\n      <g>\n       <use xlink:href=\"#m7d59ebbe47\" x=\"62.478125\" y=\"55.952958\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n     <g id=\"text_9\">\n      <!-- $\\mathdefault{4\\times10^{1}}$ -->\n      <g transform=\"translate(20.878125 59.752177) scale(0.1 -0.1)\">\n       <use xlink:href=\"#DejaVuSans-34\" transform=\"translate(0 0.684375)\"/>\n       <use xlink:href=\"#DejaVuSans-d7\" transform=\"translate(83.105469 0.684375)\"/>\n       <use xlink:href=\"#DejaVuSans-31\" transform=\"translate(186.376953 0.684375)\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(250 0.684375)\"/>\n       <use xlink:href=\"#DejaVuSans-31\" transform=\"translate(314.580078 38.965625) scale(0.7)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_4\">\n     <g id=\"line2d_14\">\n      <g>\n       <use xlink:href=\"#m7d59ebbe47\" x=\"62.478125\" y=\"41.206364\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_5\">\n     <g id=\"line2d_15\">\n      <g>\n       <use xlink:href=\"#m7d59ebbe47\" x=\"62.478125\" y=\"29.15752\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n     <g id=\"text_10\">\n      <!-- $\\mathdefault{6\\times10^{1}}$ -->\n      <g transform=\"translate(20.878125 32.956739) scale(0.1 -0.1)\">\n       <use xlink:href=\"#DejaVuSans-36\" transform=\"translate(0 0.684375)\"/>\n       <use xlink:href=\"#DejaVuSans-d7\" transform=\"translate(83.105469 0.684375)\"/>\n       <use xlink:href=\"#DejaVuSans-31\" transform=\"translate(186.376953 0.684375)\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(250 0.684375)\"/>\n       <use xlink:href=\"#DejaVuSans-31\" transform=\"translate(314.580078 38.965625) scale(0.7)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_6\">\n     <g id=\"line2d_16\">\n      <g>\n       <use xlink:href=\"#m7d59ebbe47\" x=\"62.478125\" y=\"18.970367\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_7\">\n     <g id=\"line2d_17\">\n      <g>\n       <use xlink:href=\"#m7d59ebbe47\" x=\"62.478125\" y=\"10.145854\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"text_11\">\n     <!-- ms per token -->\n     <g transform=\"translate(14.798437 109.438281) rotate(-90) scale(0.1 -0.1)\">\n      <defs>\n       <path id=\"DejaVuSans-6d\" d=\"M 3328 2828 \nQ 3544 3216 3844 3400 \nQ 4144 3584 4550 3584 \nQ 5097 3584 5394 3201 \nQ 5691 2819 5691 2113 \nL 5691 0 \nL 5113 0 \nL 5113 2094 \nQ 5113 2597 4934 2840 \nQ 4756 3084 4391 3084 \nQ 3944 3084 3684 2787 \nQ 3425 2491 3425 1978 \nL 3425 0 \nL 2847 0 \nL 2847 2094 \nQ 2847 2600 2669 2842 \nQ 2491 3084 2119 3084 \nQ 1678 3084 1418 2786 \nQ 1159 2488 1159 1978 \nL 1159 0 \nL 581 0 \nL 581 3500 \nL 1159 3500 \nL 1159 2956 \nQ 1356 3278 1631 3431 \nQ 1906 3584 2284 3584 \nQ 2666 3584 2933 3390 \nQ 3200 3197 3328 2828 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-73\" d=\"M 2834 3397 \nL 2834 2853 \nQ 2591 2978 2328 3040 \nQ 2066 3103 1784 3103 \nQ 1356 3103 1142 2972 \nQ 928 2841 928 2578 \nQ 928 2378 1081 2264 \nQ 1234 2150 1697 2047 \nL 1894 2003 \nQ 2506 1872 2764 1633 \nQ 3022 1394 3022 966 \nQ 3022 478 2636 193 \nQ 2250 -91 1575 -91 \nQ 1294 -91 989 -36 \nQ 684 19 347 128 \nL 347 722 \nQ 666 556 975 473 \nQ 1284 391 1588 391 \nQ 1994 391 2212 530 \nQ 2431 669 2431 922 \nQ 2431 1156 2273 1281 \nQ 2116 1406 1581 1522 \nL 1381 1569 \nQ 847 1681 609 1914 \nQ 372 2147 372 2553 \nQ 372 3047 722 3315 \nQ 1072 3584 1716 3584 \nQ 2034 3584 2315 3537 \nQ 2597 3491 2834 3397 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-70\" d=\"M 1159 525 \nL 1159 -1331 \nL 581 -1331 \nL 581 3500 \nL 1159 3500 \nL 1159 2969 \nQ 1341 3281 1617 3432 \nQ 1894 3584 2278 3584 \nQ 2916 3584 3314 3078 \nQ 3713 2572 3713 1747 \nQ 3713 922 3314 415 \nQ 2916 -91 2278 -91 \nQ 1894 -91 1617 61 \nQ 1341 213 1159 525 \nz\nM 3116 1747 \nQ 3116 2381 2855 2742 \nQ 2594 3103 2138 3103 \nQ 1681 3103 1420 2742 \nQ 1159 2381 1159 1747 \nQ 1159 1113 1420 752 \nQ 1681 391 2138 391 \nQ 2594 391 2855 752 \nQ 3116 1113 3116 1747 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-72\" d=\"M 2631 2963 \nQ 2534 3019 2420 3045 \nQ 2306 3072 2169 3072 \nQ 1681 3072 1420 2755 \nQ 1159 2438 1159 1844 \nL 1159 0 \nL 581 0 \nL 581 3500 \nL 1159 3500 \nL 1159 2956 \nQ 1341 3275 1631 3429 \nQ 1922 3584 2338 3584 \nQ 2397 3584 2469 3576 \nQ 2541 3569 2628 3553 \nL 2631 2963 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-6b\" d=\"M 581 4863 \nL 1159 4863 \nL 1159 1991 \nL 2875 3500 \nL 3609 3500 \nL 1753 1863 \nL 3688 0 \nL 2938 0 \nL 1159 1709 \nL 1159 0 \nL 581 0 \nL 581 4863 \nz\n\" transform=\"scale(0.015625)\"/>\n      </defs>\n      <use xlink:href=\"#DejaVuSans-6d\"/>\n      <use xlink:href=\"#DejaVuSans-73\" transform=\"translate(97.412109 0)\"/>\n      <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(149.511719 0)\"/>\n      <use xlink:href=\"#DejaVuSans-70\" transform=\"translate(181.298828 0)\"/>\n      <use xlink:href=\"#DejaVuSans-65\" transform=\"translate(244.775391 0)\"/>\n      <use xlink:href=\"#DejaVuSans-72\" transform=\"translate(306.298828 0)\"/>\n      <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(347.412109 0)\"/>\n      <use xlink:href=\"#DejaVuSans-74\" transform=\"translate(379.199219 0)\"/>\n      <use xlink:href=\"#DejaVuSans-6f\" transform=\"translate(418.408203 0)\"/>\n      <use xlink:href=\"#DejaVuSans-6b\" transform=\"translate(479.589844 0)\"/>\n      <use xlink:href=\"#DejaVuSans-65\" transform=\"translate(533.875 0)\"/>\n      <use xlink:href=\"#DejaVuSans-6e\" transform=\"translate(595.398438 0)\"/>\n     </g>\n    </g>\n   </g>\n   <g id=\"line2d_18\">\n    <path d=\"M 71.355398 72.223628 \nL 130.537216 121.544769 \nL 189.719034 52.36867 \nL 248.900852 13.5 \n\" clip-path=\"url(#p01c68ec550)\" style=\"fill: none; stroke: #1f77b4; stroke-width: 1.5; stroke-linecap: square\"/>\n   </g>\n   <g id=\"line2d_19\">\n    <path d=\"M 71.355398 138.170926 \nL 130.537216 139.5 \nL 189.719034 133.144299 \nL 248.900852 134.886705 \n\" clip-path=\"url(#p01c68ec550)\" style=\"fill: none; stroke-dasharray: 5.55,2.4; stroke-dashoffset: 0; stroke: #bf00bf; stroke-width: 1.5\"/>\n   </g>\n   <g id=\"patch_3\">\n    <path d=\"M 62.478125 145.8 \nL 62.478125 7.2 \n\" style=\"fill: none; stroke: #000000; stroke-width: 0.8; stroke-linejoin: miter; stroke-linecap: square\"/>\n   </g>\n   <g id=\"patch_4\">\n    <path d=\"M 257.778125 145.8 \nL 257.778125 7.2 \n\" style=\"fill: none; stroke: #000000; stroke-width: 0.8; stroke-linejoin: miter; stroke-linecap: square\"/>\n   </g>\n   <g id=\"patch_5\">\n    <path d=\"M 62.478125 145.8 \nL 257.778125 145.8 \n\" style=\"fill: none; stroke: #000000; stroke-width: 0.8; stroke-linejoin: miter; stroke-linecap: square\"/>\n   </g>\n   <g id=\"patch_6\">\n    <path d=\"M 62.478125 7.2 \nL 257.778125 7.2 \n\" style=\"fill: none; stroke: #000000; stroke-width: 0.8; stroke-linejoin: miter; stroke-linecap: square\"/>\n   </g>\n   <g id=\"legend_1\">\n    <g id=\"patch_7\">\n     <path d=\"M 69.478125 44.55625 \nL 137.442187 44.55625 \nQ 139.442187 44.55625 139.442187 42.55625 \nL 139.442187 14.2 \nQ 139.442187 12.2 137.442187 12.2 \nL 69.478125 12.2 \nQ 67.478125 12.2 67.478125 14.2 \nL 67.478125 42.55625 \nQ 67.478125 44.55625 69.478125 44.55625 \nz\n\" style=\"fill: #ffffff; opacity: 0.8; stroke: #cccccc; stroke-linejoin: miter\"/>\n    </g>\n    <g id=\"line2d_20\">\n     <path d=\"M 71.478125 20.298438 \nL 81.478125 20.298438 \nL 91.478125 20.298438 \n\" style=\"fill: none; stroke: #1f77b4; stroke-width: 1.5; stroke-linecap: square\"/>\n    </g>\n    <g id=\"text_12\">\n     <!-- naive -->\n     <g transform=\"translate(99.478125 23.798438) scale(0.1 -0.1)\">\n      <defs>\n       <path id=\"DejaVuSans-61\" d=\"M 2194 1759 \nQ 1497 1759 1228 1600 \nQ 959 1441 959 1056 \nQ 959 750 1161 570 \nQ 1363 391 1709 391 \nQ 2188 391 2477 730 \nQ 2766 1069 2766 1631 \nL 2766 1759 \nL 2194 1759 \nz\nM 3341 1997 \nL 3341 0 \nL 2766 0 \nL 2766 531 \nQ 2569 213 2275 61 \nQ 1981 -91 1556 -91 \nQ 1019 -91 701 211 \nQ 384 513 384 1019 \nQ 384 1609 779 1909 \nQ 1175 2209 1959 2209 \nL 2766 2209 \nL 2766 2266 \nQ 2766 2663 2505 2880 \nQ 2244 3097 1772 3097 \nQ 1472 3097 1187 3025 \nQ 903 2953 641 2809 \nL 641 3341 \nQ 956 3463 1253 3523 \nQ 1550 3584 1831 3584 \nQ 2591 3584 2966 3190 \nQ 3341 2797 3341 1997 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-69\" d=\"M 603 3500 \nL 1178 3500 \nL 1178 0 \nL 603 0 \nL 603 3500 \nz\nM 603 4863 \nL 1178 4863 \nL 1178 4134 \nL 603 4134 \nL 603 4863 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-76\" d=\"M 191 3500 \nL 800 3500 \nL 1894 563 \nL 2988 3500 \nL 3597 3500 \nL 2284 0 \nL 1503 0 \nL 191 3500 \nz\n\" transform=\"scale(0.015625)\"/>\n      </defs>\n      <use xlink:href=\"#DejaVuSans-6e\"/>\n      <use xlink:href=\"#DejaVuSans-61\" transform=\"translate(63.378906 0)\"/>\n      <use xlink:href=\"#DejaVuSans-69\" transform=\"translate(124.658203 0)\"/>\n      <use xlink:href=\"#DejaVuSans-76\" transform=\"translate(152.441406 0)\"/>\n      <use xlink:href=\"#DejaVuSans-65\" transform=\"translate(211.621094 0)\"/>\n     </g>\n    </g>\n    <g id=\"line2d_21\">\n     <path d=\"M 71.478125 34.976562 \nL 81.478125 34.976562 \nL 91.478125 34.976562 \n\" style=\"fill: none; stroke-dasharray: 5.55,2.4; stroke-dashoffset: 0; stroke: #bf00bf; stroke-width: 1.5\"/>\n    </g>\n    <g id=\"text_13\">\n     <!-- cached -->\n     <g transform=\"translate(99.478125 38.476562) scale(0.1 -0.1)\">\n      <defs>\n       <path id=\"DejaVuSans-64\" d=\"M 2906 2969 \nL 2906 4863 \nL 3481 4863 \nL 3481 0 \nL 2906 0 \nL 2906 525 \nQ 2725 213 2448 61 \nQ 2172 -91 1784 -91 \nQ 1150 -91 751 415 \nQ 353 922 353 1747 \nQ 353 2572 751 3078 \nQ 1150 3584 1784 3584 \nQ 2172 3584 2448 3432 \nQ 2725 3281 2906 2969 \nz\nM 947 1747 \nQ 947 1113 1208 752 \nQ 1469 391 1925 391 \nQ 2381 391 2643 752 \nQ 2906 1113 2906 1747 \nQ 2906 2381 2643 2742 \nQ 2381 3103 1925 3103 \nQ 1469 3103 1208 2742 \nQ 947 2381 947 1747 \nz\n\" transform=\"scale(0.015625)\"/>\n      </defs>\n      <use xlink:href=\"#DejaVuSans-63\"/>\n      <use xlink:href=\"#DejaVuSans-61\" transform=\"translate(54.980469 0)\"/>\n      <use xlink:href=\"#DejaVuSans-63\" transform=\"translate(116.259766 0)\"/>\n      <use xlink:href=\"#DejaVuSans-68\" transform=\"translate(171.240234 0)\"/>\n      <use xlink:href=\"#DejaVuSans-65\" transform=\"translate(234.619141 0)\"/>\n      <use xlink:href=\"#DejaVuSans-64\" transform=\"translate(296.142578 0)\"/>\n     </g>\n    </g>\n   </g>\n  </g>\n </g>\n <defs>\n  <clipPath id=\"p01c68ec550\">\n   <rect x=\"62.478125\" y=\"7.2\" width=\"195.3\" height=\"138.6\"/>\n  </clipPath>\n </defs>\n</svg>\n"
     },
     "metadata": {}
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=kv-cache-md-8 fw=all -->\n",
    "\n",
    "Read the plot from the right. At long contexts the naive step grows\n",
    "roughly linearly with $n$, as $2Nn$ arithmetic says it must, while the\n",
    "cached step stays flat; at a context of four thousand tokens the gap in\n",
    "our runs is about a factor of five, and it doubles with every further\n",
    "doubling of context. At short contexts the two curves *merge* — below\n",
    "about a thousand tokens this model is so small that a step of either kind\n",
    "is dominated by launching a dozen blocks' worth of GPU kernels, not by\n",
    "computing. The cache is not a magic constant factor; it removes a term\n",
    "that grows with context, and pays off precisely when that term dominates.\n",
    "End to end, the effect on `generate` is what the per-step curve promises:"
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "kv-cache-same-logits-measured-3"
   },
   "source": [
    "prefix = list(range(3584))\n",
    "for name, gen in (('naive ', model.generate),\n",
    "                  ('cached', model.generate_cached)):\n",
    "    t0 = time.time()\n",
    "    gen(prefix, 256, seed=0)\n",
    "    dt = time.time() - t0\n",
    "    print(f'{name}: 256 tokens after a 3584-token prompt: {dt:4.1f}s '\n",
    "          f'= {256 / dt:5.1f} tokens/s')"
   ],
   "execution_count": 6,
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "naive : 256 tokens after a 3584-token prompt: 24.5s =  10.5 tokens/s\n"
     ]
    },
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "cached: 256 tokens after a 3584-token prompt:  8.8s =  29.2 tokens/s\n"
     ]
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=kv-cache-md-9 fw=jax -->\n",
    "\n",
    "Several times faster at this prompt length — each timing includes one XLA\n",
    "compilation for its shapes, so the steady-state gap is larger still, as\n",
    "the per-step curve above shows. Production serving systems generate this\n",
    "way; \"time to first token\" is our prefill call, and \"tokens per second\"\n",
    "is the cached decode loop."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=kv-cache-md-10 fw=all -->\n",
    "\n",
    "## The Memory Bill\n",
    "\n",
    "The cache is not free; it is a rent paid in the scarcest resource a GPU\n",
    "has. Each of the $n_\\textrm{layers}$ layers stores one key and one value\n",
    "vector of dimension $n_\\textrm{kv} \\cdot d_\\textrm{head}$ per token, so a\n",
    "batch of $b$ sequences of length $n$ holds\n",
    "\n",
    "$$\n",
    "\\textrm{cache bytes} \\;=\\; 2 \\cdot n_\\textrm{layers} \\cdot n_\\textrm{kv}\n",
    "\\cdot d_\\textrm{head} \\cdot n \\cdot b \\cdot (\\textrm{bytes per element}),\n",
    "$$\n",
    "\n",
    "where the leading 2 counts K and V and $n_\\textrm{kv}$ is the number of\n",
    "key-value heads (equal to the number of query heads, for now: the next\n",
    "section breaks that equality). For our GPT-2-sized model in fp32 that is\n",
    "$2 \\cdot 12 \\cdot 12 \\cdot 64 \\cdot 4$ bytes $= 72$ KiB per token: at a\n",
    "context of 4096 the cache holds 288 MiB, more than half the size of the\n",
    "124M-parameter model itself. Scale the formula up to a modern deployment\n",
    "— dozens of layers, contexts in the hundreds of thousands, batches of\n",
    "concurrent users — and the cache, not the weights, is what fills the\n",
    "accelerator; the exercises make this concrete for a 70B model. Formulas\n",
    "should be checked, not trusted:"
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "kv-cache-the-memory-bill"
   },
   "source": [
    "ks, vs = init_cache(model, 1, 4096)\n",
    "formula = 2 * 12 * 12 * 64 * 4096 * 4\n",
    "print(f'cache buffers: {(ks.nbytes + vs.nbytes) / 2**20:.0f} MiB, '\n",
    "      f'formula says {formula / 2**20:.0f} MiB')"
   ],
   "execution_count": 7,
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "cache buffers: 288 MiB, formula says 288 MiB\n"
     ]
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=kv-cache-md-11 fw=jax -->\n",
    "\n",
    "In JAX the check is almost circular, and that is itself the lesson: the\n",
    "fixed-size discipline forces the entire bill to be allocated up front, so\n",
    "the equation is not a prediction about hidden allocator\n",
    "behavior but the literal size of two arrays you created. A serving\n",
    "configuration that does not fit fails at initialization, not mid-request."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=kv-cache-md-12 fw=all -->\n",
    "\n",
    "### Prefill Is Compute-Bound, Decode Is Memory-Bound\n",
    "\n",
    "Why obsess over the size of a buffer that merely *sits* in memory?\n",
    "Because at generation time it does not sit — it moves. Every decoded\n",
    "token must read every cached key and value once, and, more importantly,\n",
    "must read *every parameter of the model* once: that is what \"a forward\n",
    "pass over one token\" means. The useful lens is *arithmetic intensity*:\n",
    "FLOPs performed per byte of memory traffic. A decode step performs about\n",
    "$2N$ FLOPs and moves at least the $4N$ bytes of fp32 weights plus the\n",
    "cache, an intensity below one FLOP per byte. A prefill over $n$ tokens\n",
    "performs $2Nn$ FLOPs against the *same* weight traffic (the weights are\n",
    "read once and reused for every token in the batch of positions), an\n",
    "intensity roughly $n$ times higher. A modern GPU is balanced at far\n",
    "higher intensities (an RTX 4090 delivers up to about $83$ TFLOP/s of\n",
    "fp32 compute but only about $1$ TB/s of memory bandwidth, a ridge near\n",
    "80 FLOPs per byte), so prefill lands comfortably compute-bound while\n",
    "single-stream decode cannot even in principle keep the arithmetic units\n",
    "busy: it is a memory-bandwidth workload\n",
    "[@Pope.Douglas.Chowdhery.ea.2023]. The two phases of one `generate`\n",
    "call live on opposite sides of the roofline."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "kv-cache-prefill-is-compute-bound-decode-is-memory-bound"
   },
   "source": [
    "N = n_params\n",
    "x = jnp.zeros((1, 2048), dtype=jnp.int32)\n",
    "ks, vs = init_cache(model, 1, 2048)\n",
    "t_prefill = timeit(\n",
    "    lambda: cached_forward(model, ks, vs, x, jnp.array(0))[0], reps=5)\n",
    "one = jnp.zeros((1, 1), dtype=jnp.int32)\n",
    "t_decode = timeit(\n",
    "    lambda: cached_forward(model, ks, vs, one, jnp.array(2047))[0])\n",
    "print(f'prefill: 2048 tokens in {t_prefill * 1e3:4.0f} ms = '\n",
    "      f'{2048 / t_prefill:6.0f} tokens/s')\n",
    "print(f'decode:  one token in {t_decode * 1e3:6.2f} ms = '\n",
    "      f'{1 / t_decode:6.0f} tokens/s')\n",
    "cache = 2 * 12 * 12 * 64 * 2048 * 4\n",
    "flops, moved = 2 * N, 4 * N + cache\n",
    "print(f'decode intensity: {flops / 1e6:.0f} MFLOP / {moved / 1e6:.0f} MB '\n",
    "      f'= {flops / moved:.1f} FLOP/byte (GPU ridge is near 80)')\n",
    "print(f'prefill intensity: about {flops * 2048 / moved:.0f} FLOP/byte')\n",
    "print(f'bandwidth ceiling for decode: about '\n",
    "      f'{1.0e12 / moved:.0f} tokens/s')"
   ],
   "execution_count": 8,
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "prefill: 2048 tokens in   34 ms =  60455 tokens/s\ndecode:  one token in  14.44 ms =     69 tokens/s\ndecode intensity: 247 MFLOP / 645 MB = 0.4 FLOP/byte (GPU ridge is near 80)\nprefill intensity: about 784 FLOP/byte\nbandwidth ceiling for decode: about 1550 tokens/s\n"
     ]
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=kv-cache-md-13 fw=all -->\n",
    "\n",
    "The measurement is blunt: this model reads a two-thousand-token prompt at\n",
    "tens of thousands of tokens per second and then generates at about a\n",
    "hundred — three orders of magnitude apart, on identical hardware, running\n",
    "identical layers. Note also the gap between our measured decode rate and\n",
    "the bandwidth ceiling the arithmetic promises: a Python loop that\n",
    "launches every kernel of every block one token at a time pays overheads\n",
    "that production engines eliminate with compiled decode loops and CUDA\n",
    "graphs, and the ceiling is what they climb toward. The structural point\n",
    "survives sloppy plumbing, though: decode speed is set by *bytes that must\n",
    "move per token*, weights plus cache, so every byte shaved off the cache\n",
    "is decode speed, longer feasible contexts, or more concurrent users. That\n",
    "is why the rest of this section is about making the cache smaller.\n",
    "\n",
    "## Sharing Keys and Values across Heads\n",
    "\n",
    "Look again at the equation: the factor $n_\\textrm{kv}$ is\n",
    "the number of key-value heads, and nothing in the attention mechanism\n",
    "forces it to equal the number of query heads. Queries do the asking;\n",
    "keys and values are the library being consulted. *Multi-query attention*\n",
    "(MQA) keeps all $H$ query heads but a single shared key-value head\n",
    "[@Shazeer.2019], shrinking the cache by a factor of $H$ at a\n",
    "usually slight cost in quality. *Grouped-query attention* (GQA)\n",
    "interpolates: $H_{kv}$\n",
    "key-value heads, each serving a contiguous group of $H / H_{kv}$ query\n",
    "heads [@Ainslie.Lee-Thorp.Jong.ea.2023]. the figure shows\n",
    "the sharing patterns. GQA with $H_{kv} = H/4$ to $H/8$ is close to the\n",
    "universal choice of current open models — Llama 3 runs 32 query heads\n",
    "against 8 key-value heads, Mistral 7B the same\n",
    "[@Grattafiori.Dubey.Jauhri.ea.2024; @Jiang.Sablayrolles.Mensch.ea.2023].\n",
    "\n",
    "![Query heads and the key-value heads they read. Multi-head attention gives every query head its own key-value head; grouped-query attention shares one per group of query heads; multi-query attention shares a single one across all of them. The cache scales with the number of key-value heads.](../img/mdl-transformers-gqa.svg)\n",
    "\n",
    "### A Pluggable Implementation\n",
    "\n",
    "`GQAAttention` below generalizes the causal attention of\n",
    "that section: `W_q` still produces $H$ query heads, but `W_k` and\n",
    "`W_v` produce only $H_{kv}$ heads, and the fused kernel broadcasts each\n",
    "key-value head across its query group (in PyTorch via `enable_gqa`; the\n",
    "JAX kernel accepts grouped shapes natively). We keep the\n",
    "`(queries, keys, values, valid_lens)` call shape of\n",
    "`d2l.MultiHeadAttention`, so the class drops into\n",
    "`d2l.TransformerBlock`'s `attn_factory` hook — the seam\n",
    "that section built for exactly this purpose — and,\n",
    "with `rope=True`, into `d2l.GPT`. Setting $H_{kv} = H$ recovers standard\n",
    "multi-head attention exactly."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "kv-cache-a-pluggable-implementation-1"
   },
   "source": [
    "class GQAAttention(nnx.Module):\n",
    "    \"\"\"Causal multi-head attention with num_kv_heads shared KV heads.\"\"\"\n",
    "    def __init__(self, num_hiddens, num_heads, num_kv_heads, bias=False,\n",
    "                 rope=False, causal=True, rngs=None):\n",
    "        rngs = nnx.Rngs(0) if rngs is None else rngs\n",
    "        assert num_hiddens % num_heads == 0\n",
    "        assert num_heads % num_kv_heads == 0\n",
    "        self.num_heads, self.num_kv_heads = num_heads, num_kv_heads\n",
    "        self.head_dim = num_hiddens // num_heads\n",
    "        self.rope, self.causal = rope, causal\n",
    "        self.W_q = nnx.Linear(num_hiddens, num_hiddens, use_bias=bias,\n",
    "                              rngs=rngs)\n",
    "        self.W_k = nnx.Linear(num_hiddens, num_kv_heads * self.head_dim,\n",
    "                              use_bias=bias, rngs=rngs)\n",
    "        self.W_v = nnx.Linear(num_hiddens, num_kv_heads * self.head_dim,\n",
    "                              use_bias=bias, rngs=rngs)\n",
    "        self.W_o = nnx.Linear(num_hiddens, num_hiddens, use_bias=bias,\n",
    "                              rngs=rngs)\n",
    "\n",
    "    def _rope(self, x):  # the rotation of d2l.GPT, kept self-contained\n",
    "        d = x.shape[-1]\n",
    "        pos = jnp.arange(x.shape[1], dtype=jnp.float32)\n",
    "        inv_freq = 10000.0 ** (-jnp.arange(0, d, 2) / d)\n",
    "        theta = pos[:, None] * inv_freq[None, :]\n",
    "        cos = jnp.cos(theta)[:, None, :]\n",
    "        sin = jnp.sin(theta)[:, None, :]\n",
    "        x1, x2 = x[..., 0::2], x[..., 1::2]\n",
    "        return jnp.stack([x1 * cos - x2 * sin,\n",
    "                          x1 * sin + x2 * cos], -1).reshape(x.shape)\n",
    "\n",
    "    def __call__(self, queries, keys, values, valid_lens=None):\n",
    "        B, T, D = queries.shape\n",
    "        q = self.W_q(queries).reshape(B, T, self.num_heads, -1)\n",
    "        k = self.W_k(keys).reshape(B, -1, self.num_kv_heads, self.head_dim)\n",
    "        v = self.W_v(values).reshape(B, -1, self.num_kv_heads,\n",
    "                                     self.head_dim)\n",
    "        if self.rope:\n",
    "            q, k = self._rope(q), self._rope(k)\n",
    "        mask, causal = None, self.causal\n",
    "        if valid_lens is not None:      # mask padding (and causality)\n",
    "            S = k.shape[1]\n",
    "            if valid_lens.ndim == 1:\n",
    "                valid_lens = jnp.broadcast_to(valid_lens[:, None], (B, T))\n",
    "            mask = (jnp.arange(S)[None, None, :]\n",
    "                    < valid_lens[:, :, None])[:, None]\n",
    "            if causal:\n",
    "                i, j = jnp.arange(T)[:, None], jnp.arange(S)[None, :]\n",
    "                mask = mask & (j <= i + S - T)\n",
    "            causal = False\n",
    "        Y = jax.nn.dot_product_attention(q, k, v, mask=mask,\n",
    "                                         is_causal=causal)\n",
    "        return self.W_o(Y.reshape(B, T, -1)), None"
   ],
   "execution_count": 9,
   "outputs": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=kv-cache-md-14 fw=all -->\n",
    "\n",
    "It honors the block contract, and its parameter count records where the\n",
    "saving comes from: `W_k` and `W_v` shrink with $H_{kv}$ (attention\n",
    "parameters go from $4d^2$ toward $2d^2$), while the cache line of\n",
    "the equation shrinks in proportion."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "kv-cache-a-pluggable-implementation-2"
   },
   "source": [
    "X = jnp.ones((2, 10, 256))\n",
    "blk = d2l.TransformerBlock(\n",
    "    256, num_heads=8,\n",
    "    attn_factory=lambda rngs: GQAAttention(256, 8, 2, causal=False,\n",
    "                                           rngs=rngs))\n",
    "d2l.check_shape(blk(X, jnp.array([7, 4])), X.shape)\n",
    "for G in (8, 4, 2, 1):\n",
    "    attn = GQAAttention(256, 8, G)\n",
    "    n = sum(p.size for p in jax.tree.leaves(nnx.state(attn, nnx.Param)))\n",
    "    print(f'H_kv={G}: {n:6d} parameters, '\n",
    "          f'cache {2 * G * 32 * 4:4d} bytes per token per layer')"
   ],
   "execution_count": 10,
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "H_kv=8: 262144 parameters, cache 2048 bytes per token per layer\n"
     ]
    },
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "H_kv=4: 196608 parameters, cache 1024 bytes per token per layer\nH_kv=2: 163840 parameters, cache  512 bytes per token per layer\n"
     ]
    },
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "H_kv=1: 147456 parameters, cache  256 bytes per token per layer\n"
     ]
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=kv-cache-md-15 fw=all -->\n",
    "\n",
    "### Cache Against Quality\n",
    "\n",
    "What does the sharing cost in modeling power? We train the\n",
    "that section configuration on the character-level Time Machine at\n",
    "every group count from $H_{kv} = 8$ (full multi-head) down to $1$ (MQA),\n",
    "swapping the attention in each block after construction. Because the\n",
    "validation loss of this small model bottoms out within a few hundred\n",
    "steps and then climbs into memorization (that section), we compare\n",
    "models at their *best* validation loss over a fixed 600-step budget."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "kv-cache-cache-against-quality"
   },
   "source": [
    "data = d2l.TimeMachine(batch_size=64, num_steps=128, tokenization='char',\n",
    "                       num_train=100000, num_val=3000)\n",
    "\n",
    "@nnx.jit\n",
    "def batch_loss(model, X, Y):\n",
    "    logits = model(X)\n",
    "    return optax.softmax_cross_entropy_with_integer_labels(\n",
    "        logits.reshape(-1, logits.shape[-1]), Y.reshape(-1)).mean()\n",
    "\n",
    "def val_loss(model, data):\n",
    "    model.eval()\n",
    "    losses = [float(batch_loss(model, jnp.asarray(X), jnp.asarray(Y)))\n",
    "              for X, Y in data.val_dataloader()]\n",
    "    model.train()\n",
    "    return sum(losses) / len(losses)\n",
    "\n",
    "for G in (8, 4, 2, 1):\n",
    "    rngs = nnx.Rngs(0)\n",
    "    lm = d2l.GPT(len(data.vocab), num_hiddens=256, num_heads=8,\n",
    "                 num_blks=6, rngs=rngs)\n",
    "    for blk in lm.blks:\n",
    "        blk.attention = GQAAttention(256, 8, G, rope=True, rngs=rngs)\n",
    "    optimizer = nnx.Optimizer(lm, optax.adamw(1e-3, weight_decay=0.0),\n",
    "                              wrt=nnx.Param)\n",
    "    best = float('inf')\n",
    "    for chunk in range(6):\n",
    "        d2l.train_lm(lm, data, optimizer, 100)\n",
    "        best = min(best, val_loss(lm, data))\n",
    "    print(f'H_kv={G}: best validation loss {best:.2f}, '\n",
    "          f'cache {2 * 6 * G * 32 * 4 / 1024:4.1f} KiB per token')"
   ],
   "execution_count": 11,
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "H_kv=8: best validation loss 1.55, cache 12.0 KiB per token\n"
     ]
    },
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "H_kv=4: best validation loss 1.51, cache  6.0 KiB per token\n"
     ]
    },
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "H_kv=2: best validation loss 1.51, cache  3.0 KiB per token\n"
     ]
    },
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "H_kv=1: best validation loss 1.54, cache  1.5 KiB per token\n"
     ]
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=kv-cache-md-16 fw=all -->\n",
    "\n",
    "The cache shrinks eightfold from top to bottom of the table; the loss\n",
    "column does not move outside run-to-run noise (rerunning any row with a\n",
    "different seed shifts it by a few hundredths, about the spread of the\n",
    "whole column). At this scale the sharing costs nothing we can measure.\n",
    "That conclusion would be too strong to carry to large models on our\n",
    "evidence alone, but the large-scale literature reaches a similar verdict\n",
    "by more careful means: full MQA costs a measurable sliver of quality,\n",
    "while GQA at $H/8$ matches multi-head attention in the ablations of\n",
    "@Ainslie.Lee-Thorp.Jong.ea.2023 — and an existing multi-head\n",
    "checkpoint can be *uptrained* into a grouped one for a small fraction of\n",
    "its original compute, which is how GQA spread through the open-model\n",
    "world so quickly.\n",
    "\n",
    "## Compressing the Cache Further\n",
    "\n",
    "Sharing heads is one axis. This closing section looks at the two other\n",
    "levers deployed systems pull — compressing the *width* of each cached\n",
    "token further, and bounding the *length* of what is cached — and at the\n",
    "failure mode that makes the second one subtle. Our minute-trained\n",
    "character models are too small to exhibit these phenomena, so we probe\n",
    "the real GPT-2, reloading it exactly as in that section (weights\n",
    "and tokenizer files are already pinned in `d2l.DATA_HUB`), along with the\n",
    "raw text of *The Time Machine* as a 1024-token evaluation passage."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "kv-cache-compressing-the-cache-further-1"
   },
   "source": [
    "HF_URL = 'https://huggingface.co/openai-community/gpt2/resolve/main/'\n",
    "d2l.DATA_HUB['gpt2-weights'] = (\n",
    "    HF_URL + 'model.safetensors',\n",
    "    '89a76996d7c6ee89b86618a265483aab73e61d50')\n",
    "d2l.DATA_HUB['gpt2-merges'] = (\n",
    "    HF_URL + 'merges.txt', '396d4d8ec90cb02f4d56e049e0e4add868bcd943')\n",
    "d2l.DATA_HUB['gpt2-encoder'] = (\n",
    "    HF_URL + 'vocab.json', 'f0223209235343bc067d7da838328bced8085ae1')\n",
    "enc = tiktoken.Encoding(\n",
    "    'gpt2', explicit_n_vocab=50257,\n",
    "    pat_str=d2l.BPETokenizer.GPT2_PATTERN,\n",
    "    mergeable_ranks=data_gym_to_mergeable_bpe_ranks(\n",
    "        d2l.download('gpt2-merges', '../data/gpt2'),\n",
    "        d2l.download('gpt2-encoder', '../data/gpt2')),\n",
    "    special_tokens={'<|endoftext|>': 50256})\n",
    "\n",
    "gpt2 = d2l.GPT(vocab_size=50257, num_hiddens=768, num_heads=12,\n",
    "               num_blks=12, max_len=1024, pos='learned', norm='layer',\n",
    "               act='gelu', pre_norm=True, bias=True)\n",
    "weights = safetensors_numpy.load_file(\n",
    "    d2l.download('gpt2-weights', '../data/gpt2'))\n",
    "gpt2.token_emb.embedding[...] = jnp.asarray(weights['wte.weight'])\n",
    "gpt2.pos_emb.embedding[...] = jnp.asarray(weights['wpe.weight'])\n",
    "gpt2.norm.scale[...] = jnp.asarray(weights['ln_f.weight'])\n",
    "gpt2.norm.bias[...] = jnp.asarray(weights['ln_f.bias'])\n",
    "for i, blk in enumerate(gpt2.blks):\n",
    "    for norm, key in ((blk.norm1, f'h.{i}.ln_1'),\n",
    "                      (blk.norm2, f'h.{i}.ln_2')):\n",
    "        norm.scale[...] = jnp.asarray(weights[key + '.weight'])\n",
    "        norm.bias[...] = jnp.asarray(weights[key + '.bias'])\n",
    "    for linear, key in ((blk.attention.W_qkv, f'h.{i}.attn.c_attn'),\n",
    "                        (blk.attention.W_o, f'h.{i}.attn.c_proj'),\n",
    "                        (blk.ffn.W_1, f'h.{i}.mlp.c_fc'),\n",
    "                        (blk.ffn.W_2, f'h.{i}.mlp.c_proj')):\n",
    "        linear.kernel[...] = jnp.asarray(weights[key + '.weight'])\n",
    "        linear.bias[...] = jnp.asarray(weights[key + '.bias'])\n",
    "gpt2.eval()\n",
    "\n",
    "fname = d2l.download(d2l.DATA_URL + 'timemachine.txt', '../data',\n",
    "                     '090b5e7e70c295757f55df93cb0a180b9691891a')\n",
    "ids = enc.encode(open(fname).read())[:1024]\n",
    "x = jnp.asarray(ids)[None]\n",
    "print(f'{len(ids)} tokens of The Time Machine')"
   ],
   "execution_count": 12,
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "1024 tokens of The Time Machine\n"
     ]
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=kv-cache-md-17 fw=all -->\n",
    "\n",
    "Each experiment below changes only what happens *inside* attention, so\n",
    "one helper suffices: a forward pass that walks GPT-2's blocks exactly as\n",
    "the class does, but lets us substitute the attention computation per\n",
    "block. First a sanity check that the helper with stock attention\n",
    "reproduces the model, and a baseline loss on the second half of the\n",
    "passage (positions 512 onward, so every evaluated token has a long\n",
    "history to draw on)."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "kv-cache-compressing-the-cache-further-2"
   },
   "source": [
    "def forward_blocks(model, X, attn_fn):\n",
    "    \"\"\"GPT-2 forward with a pluggable attention computation per block.\"\"\"\n",
    "    H = model.token_emb(X) + model.pos_emb(jnp.arange(X.shape[1]))\n",
    "    for i, blk in enumerate(model.blks):\n",
    "        A, Y = blk.attention, blk.norm1(H)\n",
    "        B, T, D = Y.shape\n",
    "        q, k, v = (u.reshape(B, T, A.num_heads, -1)\n",
    "                   for u in jnp.split(A.W_qkv(Y), 3, axis=-1))\n",
    "        H = H + A.W_o(attn_fn(q, k, v, i).reshape(B, T, D))\n",
    "        H = H + blk.ffn(blk.norm2(H))\n",
    "    return model.token_emb.attend(model.norm(H))\n",
    "\n",
    "def tail_loss(logits):\n",
    "    \"\"\"Mean per-token loss on the second half of the passage.\"\"\"\n",
    "    return optax.softmax_cross_entropy_with_integer_labels(\n",
    "        logits[0, 512:-1], x[0, 513:]).mean()\n",
    "\n",
    "stock = lambda q, k, v, i: jax.nn.dot_product_attention(q, k, v,\n",
    "                                                        is_causal=True)\n",
    "logits = forward_blocks(gpt2, x, stock)\n",
    "print(f'helper vs stock forward: max deviation '\n",
    "      f'{jnp.abs(logits - gpt2(x)).max():.1e}')\n",
    "full = tail_loss(logits)\n",
    "print(f'full attention: loss {full:.2f}, perplexity {jnp.exp(full):.0f}')"
   ],
   "execution_count": 13,
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "helper vs stock forward: max deviation 0.0e+00\n"
     ]
    },
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "full attention: loss 3.58, perplexity 36\n"
     ]
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=kv-cache-md-18 fw=all -->\n",
    "\n",
    "### Low-Rank Keys and Values\n",
    "\n",
    "GQA shrinks the cache by storing fewer key-value heads. A different bet:\n",
    "keep all heads, but suppose the concatenated key and value vectors of a\n",
    "token — for GPT-2, $2 \\times 768 = 1536$ numbers — do not really span\n",
    "1536 dimensions, and store only their coordinates in some\n",
    "lower-dimensional subspace. That is the idea behind *multi-head latent\n",
    "attention* (MLA), the mechanism DeepSeek built its V2 and V3 models\n",
    "around [@DeepSeek-AI.2024]: a trained projection compresses each\n",
    "token's keys and values jointly into one latent vector (rank 512, versus\n",
    "tens of thousands of raw KV dimensions, in DeepSeek-V2), the cache\n",
    "stores only the latent, and per-head keys and values are reconstructed\n",
    "by trained up-projections at read time.\n",
    "\n",
    "We can test the load-bearing assumption — that realized keys and values\n",
    "are approximately low-rank — directly on GPT-2. In each layer we take\n",
    "the actual K and V matrices of our passage, replace them by their best\n",
    "rank-$r$ approximation (via SVD, jointly across the concatenated KV\n",
    "width of 1536), and run the model with every layer so truncated. This\n",
    "uses an oracle factorization computed on the very sequence being\n",
    "evaluated, so it is an upper bound on what a fixed trained projection\n",
    "could do; MLA's contribution is making the projection trainable, and\n",
    "handling the one real obstacle: RoPE's position-dependent rotation does\n",
    "not commute with a shared down-projection, which MLA solves by carrying\n",
    "a small separate rotary component per token. None of that machinery is\n",
    "needed to check the premise:"
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "kv-cache-low-rank-keys-and-values"
   },
   "source": [
    "def lowrank_kv(r):\n",
    "    def attn_fn(q, k, v, i):\n",
    "        B, T, H, hd = k.shape\n",
    "        KV = jnp.concatenate([k.reshape(T, -1), v.reshape(T, -1)], axis=1)\n",
    "        U, S, Vh = jnp.linalg.svd(KV, full_matrices=False)\n",
    "        KVr = (U[:, :r] * S[:r]) @ Vh[:r]     # best rank-r approximation\n",
    "        kr = KVr[:, :H * hd].reshape(1, T, H, hd)\n",
    "        vr = KVr[:, H * hd:].reshape(1, T, H, hd)\n",
    "        return jax.nn.dot_product_attention(q, kr, vr, is_causal=True)\n",
    "    return attn_fn\n",
    "\n",
    "for r in (256, 128):\n",
    "    loss = tail_loss(forward_blocks(gpt2, x, lowrank_kv(r)))\n",
    "    print(f'rank {r} of 1536 ({1536 // r}x smaller cache): '\n",
    "          f'loss {loss:.2f}, perplexity {jnp.exp(loss):.0f}')"
   ],
   "execution_count": 14,
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "rank 256 of 1536 (6x smaller cache): loss 3.49, perplexity 33\n"
     ]
    },
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "rank 128 of 1536 (12x smaller cache): loss 3.66, perplexity 39\n"
     ]
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=kv-cache-md-19 fw=all -->\n",
    "\n",
    "At rank 256 — a cache six times smaller — the loss on this passage is\n",
    "indistinguishable from the full model's (the tiny difference between the\n",
    "two numbers is single-passage noise, and we make nothing of it). At rank\n",
    "128 the model measurably worsens but remains coherent. The premise\n",
    "holds: what attention actually reads back from its cache lives in a far\n",
    "lower-dimensional space than the cache stores. The six-fold saving is\n",
    "notional here — our SVD basis is fitted to this very passage and would\n",
    "itself need storing — and that is exactly what MLA supplies: one\n",
    "projection, trained once and shared globally, that the model learns to\n",
    "write through, pushing the compression much further than after-the-fact\n",
    "truncation can.\n",
    "\n",
    "### A Window Needs a Sink\n",
    "\n",
    "The remaining lever is length: cap the cache at the last $w$ tokens,\n",
    "evicting the oldest as generation proceeds, and memory is bounded\n",
    "forever — the rolling-buffer form of the sliding-window attention of\n",
    "that section. Before evicting anything, it is worth\n",
    "asking where a trained model actually *sends* its attention. We measure\n",
    "the average weight that GPT-2's queries (from position 64 on) place on\n",
    "the single first token of the sequence:"
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "kv-cache-a-window-needs-a-sink-1"
   },
   "source": [
    "masses = []\n",
    "def watch(q, k, v, i):\n",
    "    qh, kh, vh = (u.transpose(0, 2, 1, 3) for u in (q, k, v))\n",
    "    scores = qh @ kh.swapaxes(-1, -2) / math.sqrt(q.shape[-1])\n",
    "    j = jnp.arange(scores.shape[-1])\n",
    "    scores = jnp.where(j[None, :] > j[:, None],\n",
    "                       jnp.finfo(scores.dtype).min, scores)\n",
    "    alpha = jax.nn.softmax(scores, axis=-1)\n",
    "    masses.append(float(alpha[..., 64:, 0].mean()))\n",
    "    return (alpha @ vh).transpose(0, 2, 1, 3)\n",
    "\n",
    "forward_blocks(gpt2, x, watch)\n",
    "print('mean attention weight on token 0 (uniform would be ~0.003):')\n",
    "print('  '.join(f'layer {i}: {m:.2f}' for i, m in enumerate(masses)))"
   ],
   "execution_count": 15,
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "mean attention weight on token 0 (uniform would be ~0.003):\nlayer 0: 0.00  layer 1: 0.01  layer 2: 0.11  layer 3: 0.30  layer 4: 0.32  layer 5: 0.51  layer 6: 0.46  layer 7: 0.57  layer 8: 0.48  layer 9: 0.48  layer 10: 0.45  layer 11: 0.34\n"
     ]
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=kv-cache-md-20 fw=all -->\n",
    "\n",
    "From the middle of the stack upward, GPT-2 parks a *third to a half* of\n",
    "its entire attention mass on the first token — a hundred times more than\n",
    "an even spread would give it, and mostly regardless of what that token\n",
    "is. This is the *attention sink* [@Xiao.Tian.Chen.ea.2024]: softmax\n",
    "must hand out probability mass that sums to one, a head that currently\n",
    "has nothing to retrieve needs somewhere harmless to put it, and training\n",
    "converges on the one position every query can always see. The first\n",
    "token becomes the designated dumping ground — an observation about the\n",
    "attention *weights*; how much its value vector actually contributes to\n",
    "the output is a separate quantity, which we have not measured.\n",
    "\n",
    "Now the trap springs. Evict that token, as a naive rolling buffer of the\n",
    "most recent $w$ entries would, and every head's dumping ground vanishes:\n",
    "the discarded mass is renormalized onto tokens the head actively chose\n",
    "not to attend to. StreamingLLM's fix is embarrassingly small — keep the\n",
    "first few tokens in the cache forever, alongside the sliding window\n",
    "[@Xiao.Tian.Chen.ea.2024]. We reproduce both the failure and the\n",
    "fix, evaluating our passage with attention restricted to a 256-token\n",
    "window plus a varying number of retained *sink tokens*:"
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "kv-cache-a-window-needs-a-sink-2"
   },
   "source": [
    "j = jnp.arange(x.shape[1])\n",
    "causal = j[None, :] <= j[:, None]\n",
    "window = causal & (j[:, None] - j[None, :] < 256)\n",
    "for nsink in (0, 1, 4):\n",
    "    mask = window | (causal & (j[None, :] < nsink))\n",
    "    loss = tail_loss(forward_blocks(\n",
    "        gpt2, x, lambda q, k, v, i: jax.nn.dot_product_attention(\n",
    "            q, k, v, mask=mask[None, None])))\n",
    "    print(f'window 256 + {nsink} sink tokens: loss {loss:.2f}, '\n",
    "          f'perplexity {jnp.exp(loss):.0f}')\n",
    "print(f'full attention:            loss {full:.2f}, '\n",
    "      f'perplexity {jnp.exp(full):.0f}')"
   ],
   "execution_count": 16,
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "window 256 + 0 sink tokens: loss 8.25, perplexity 3842\nwindow 256 + 1 sink tokens: loss 3.86, perplexity 47\n"
     ]
    },
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "window 256 + 4 sink tokens: loss 3.76, perplexity 43\nfull attention:            loss 3.58, perplexity 36\n"
     ]
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=kv-cache-md-21 fw=all -->\n",
    "\n",
    "The numbers are dramatic. Windowed attention alone destroys the model:\n",
    "perplexity explodes from the mid-thirties into the thousands, on text\n",
    "where every evaluated token has its entire 256-token window available —\n",
    "the damage is not lost context but the lost sink. Restoring a *single*\n",
    "initial token recovers almost everything, and four sink tokens land\n",
    "within a fraction of a nat of full attention. (Our mask-based experiment\n",
    "keeps original position indices; a real rolling buffer also has to\n",
    "handle positions carefully as entries are evicted, which is an\n",
    "exercise.) The lesson generalizes beyond eviction: the sink is a\n",
    "structural fact about softmax attention in trained transformers.\n",
    "Modern designs increasingly build it in on purpose: gpt-oss ships an\n",
    "explicit learned sink logit per head in its sliding-window layers\n",
    "[@OpenAI.2025], which frees the first token from double duty.\n",
    "\n",
    "### The Cache-Relief Map\n",
    "\n",
    "The techniques of this section slot into one map, organized by which\n",
    "factor of the equation they attack. GQA and MLA shrink the\n",
    "*width* of each cached token: fewer key-value heads, or a low-rank\n",
    "latent in place of the full vectors. Sliding windows (with their sinks)\n",
    "bound the *length*, at the price of genuinely forgetting the far past.\n",
    "The linear attention of that section removes the\n",
    "cache altogether, collapsing the entire past into a fixed-size recurrent\n",
    "state — that is its real selling point, constant-memory generation — and\n",
    "the hybrid stacks of that section interleave a few\n",
    "full-attention layers into a mostly-linear model so that most layers pay\n",
    "no cache at all while a few retain exact recall. Beyond the cache\n",
    "proper, the decode-side bandwidth arithmetic of this section is also\n",
    "what *speculative decoding* exploits, drafting several tokens cheaply\n",
    "and verifying them in one prefill-priced pass\n",
    "[@Leviathan.Kalman.Matias.2023]. The roofline economics behind that\n",
    "arithmetic are made precise in that section; the systems-level\n",
    "story of speculative decoding and the serving engines around it belongs\n",
    "to the Language Models part.\n",
    "\n",
    "## Summary\n",
    "\n",
    "Naive generation reruns the full forward pass per token, quadratic in\n",
    "the length of the text; since causality freezes every past token's keys\n",
    "and values, storing them makes the dominant dense-layer work linear\n",
    "(attention still reads the growing cache, a cumulative quadratic that\n",
    "stays subdominant at our sizes). The cached step is\n",
    "mostly plumbing — a per-layer K/V buffer and a position offset for RoPE\n",
    "(in JAX, a preallocated fixed-shape buffer with index writes, so one\n",
    "compiled function serves every step) — and it leaves the logits\n",
    "unchanged to floating-point rounding while decoding several times faster\n",
    "at long contexts. The price is memory: $2 \\cdot n_\\textrm{layers} \\cdot\n",
    "n_\\textrm{kv} \\cdot d_\\textrm{head} \\cdot n \\cdot b$ elements, verified\n",
    "against the allocator, and the cache moves on every step. Counting FLOPs\n",
    "against bytes shows prefill compute-bound and decode memory-bound, which\n",
    "is why cache bytes are the currency of generation speed. GQA spends that\n",
    "insight on head sharing: our sweep from 8 key-value heads to 1 shrank\n",
    "the cache eightfold with best validation loss flat to within seed noise,\n",
    "matching the large-scale ablations. MLA compresses width instead, and\n",
    "the oracle version of its premise checks out on GPT-2 (a rank-256\n",
    "truncation of the 1536-wide KV cache leaves the loss unchanged on our\n",
    "passage). Bounding length with a sliding window fails catastrophically\n",
    "if it evicts the *attention sink* (the first token, where trained\n",
    "softmax attention parks a third to a half of its weight), and\n",
    "keeping even one sink token restores the model; gpt-oss builds the sink\n",
    "in as a learned logit. Linear attention removes the cache entirely, and\n",
    "hybrid stacks interleave the two regimes.\n",
    "\n",
    "## Exercises\n",
    "\n",
    "1. Work out the KV cache of Llama-2-70B, which uses 80 layers, 64 query\n",
    "   heads of dimension 128, and GQA with 8 key-value heads, storing the\n",
    "   cache in 16-bit precision. How many bytes per token? At what context\n",
    "   length does a single sequence's cache reach the size of the weights\n",
    "   (140 GB in fp16)? Redo both numbers for the same model without GQA\n",
    "   (64 key-value heads) and for MQA (1 key-value head).\n",
    "2. Break the cache deliberately: remove the `offset` from the cached\n",
    "   RoPE path, so decoded tokens are rotated as if they sat at position\n",
    "   zero, and rerun the correctness check. How large is the logit\n",
    "   deviation, and why does it grow with the length of the prefix? What\n",
    "   is the corresponding bug for the `pos='learned'` scheme?\n",
    "3. Our decode measurement ran a batch of one. Extend `generate_cached`\n",
    "   to a batch of prompts of equal length and measure tokens per second\n",
    "   at batch sizes 1, 4, 16, and 64 at a fixed context. Explain the shape\n",
    "   of the curve with the arithmetic-intensity argument: which bytes are\n",
    "   read once per *step* and which once per *sequence*?\n",
    "4. The PyTorch implementation grows the cache by `torch.cat`, copying\n",
    "   the whole buffer every step; the JAX one preallocates and writes into\n",
    "   slots, but hands the jitted function fresh buffer copies unless the\n",
    "   arguments are donated. Fix either one: preallocate in PyTorch (write\n",
    "   into a slice of a `max_len` buffer), or pass `donate_argnums` for the\n",
    "   cache arguments in JAX. Measure the per-step latency at context 4096\n",
    "   before and after your fix.\n",
    "5. Give `GQAAttention` a `forward_step` in the style of this section, so\n",
    "   that the cache stores only the $H_{kv}$ key-value heads. Verify\n",
    "   correctness against the full forward pass, and confirm that measured\n",
    "   cache memory shrinks by $H / H_{kv}$.\n",
    "6. Implement a true rolling buffer: cap the per-layer cache at the 4\n",
    "   sink entries plus the most recent $w - 4$, evicting the rest as\n",
    "   generation proceeds past $w$ tokens. Decide what position index a\n",
    "   retained entry should keep (consider both the `'rope'` and\n",
    "   `'learned'` schemes), state your choice, and check the model's loss\n",
    "   on a long passage against the mask-based experiment of this section."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "name": "d2l-jax",
   "display_name": "d2l (JAX)",
   "language": "python"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
