{
 "cells": [
  {
   "cell_type": "raw",
   "metadata": {},
   "source": [
    "---\n",
    "execute:\n",
    "  enabled: false\n",
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=decoding-md-1 fw=all -->\n",
    "\n",
    "# Decoding and Generation\n",
    "\n",
    "The language model of that section ended with a cliffhanger. We\n",
    "trained a network that assigns a probability to every possible next token,\n",
    "and the moment we asked it to write, two crude recipes presented themselves:\n",
    "always take the most probable token, or draw one at random from the model's\n",
    "distribution. Both produced text, and both produced problems, from\n",
    "continuations that circle through the same phrase to continuations that\n",
    "wander into gibberish. This section treats the step we improvised there as\n",
    "a subject of its own. *Decoding*, turning a model over next tokens into\n",
    "actual sequences, is a design space with its own algorithms, failure modes,\n",
    "and a modern toolkit [@Graves.2013; @Holtzman.Buys.Du.ea.2020], and it is\n",
    "largely independent of the network that feeds it: everything we build here\n",
    "applies unchanged to the gated architectures of the next chapter and to the\n",
    "largest of large language models."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "decoding-decoding-and-generation"
   },
   "source": [
    "%matplotlib inline\n",
    "from d2l import mxnet as d2l\n",
    "import math\n",
    "import numpy as np\n",
    "import random\n",
    "from mxnet import npx\n",
    "npx.set_np()"
   ],
   "execution_count": 1,
   "outputs": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=decoding-md-2 fw=all -->\n",
    "\n",
    "## The Decoding Problem\n",
    "\n",
    "A trained language model supplies conditionals: writing $x_{<t}$ for the\n",
    "prefix $x_1, \\ldots, x_{t-1}$, it turns any prefix into a distribution\n",
    "$P(x_t \\mid x_{<t})$ over the next token. The chain rule of probability\n",
    "assembles these local judgments into the probability of an entire sequence,\n",
    "\n",
    "$$P(x_1, \\ldots, x_T) = \\prod_{t=1}^{T} P(x_t \\mid x_{<t}).$$\n",
    "\n",
    "Decoding asks the inverse question: given the conditionals, which sequence\n",
    "should we output? One natural answer is the *most probable* sequence, the\n",
    "argmax of the equation over all candidates. But the number of\n",
    "candidates is staggering. With vocabulary $\\mathcal{V}$ and $T$ tokens to\n",
    "generate there are $|\\mathcal{V}|^T$ sequences to compare; for our modest\n",
    "1,024-token vocabulary and a 50-token continuation that is $1024^{50} =\n",
    "2^{500} \\approx 10^{150}$ sequences, vastly more than there are atoms in\n",
    "the observable universe. Evaluating them all, *exhaustive search*, costs\n",
    "$\\mathcal{O}(|\\mathcal{V}|^T)$ model evaluations and is out of the\n",
    "question; every practical decoder explores a vanishing fraction of this\n",
    "space and must decide, step by step, which fraction.\n",
    "\n",
    "Intractability is only half of the problem, though. The other half is that\n",
    "for many uses the most probable sequence is not even what we want. When a\n",
    "task has essentially one right answer conditioned on the input, a French\n",
    "sentence to translate, an utterance to transcribe, a function signature to\n",
    "complete, probability mass concentrates on that answer and hunting for the\n",
    "argmax is exactly right. But when we ask a model to *write*, there are\n",
    "astronomically many acceptable continuations, each individually improbable.\n",
    "A model that has learned this diversity spreads its mass accordingly, and\n",
    "insisting on the single most probable output discards the diversity we\n",
    "asked for; we will see shortly that it collapses into dull repetition.\n",
    "Matching the output's diversity to the model's is what *sampling* does.\n",
    "\n",
    "These two regimes organize the whole section (the figure).\n",
    "*Maximization* methods, greedy decoding and beam search, chase the most\n",
    "probable output and rule tasks with a right answer, such as machine\n",
    "translation and speech recognition. *Sampling* methods draw from the\n",
    "model's distribution, reshaped by a small set of dials named temperature,\n",
    "top-$k$, top-$p$, and min-$p$, and rule open-ended generation: chat,\n",
    "stories, and everything one now associates with a large language model.\n",
    "\n",
    "![One trained language model, two families of decoding strategies: maximization for tasks with one right answer, sampling for tasks with many.](../img/mdl-rnn-decoding-taskmap.svg)\n",
    "\n",
    "### A Model to Decode From\n",
    "\n",
    "We need a trained model to experiment on, and the concise RNN language\n",
    "model of that section is ideal: small enough to train here in\n",
    "about a minute, good enough (recall, about 2.4 bits per byte) that its\n",
    "continuations respond visibly to decoding choices. We retrain it with\n",
    "exactly the recipe used there."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "decoding-a-model-to-decode-from-1"
   },
   "source": [
    "data = d2l.TimeMachine(batch_size=1024, num_steps=32,\n",
    "                       num_train=50000, num_val=5000)"
   ],
   "execution_count": 2,
   "outputs": []
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "decoding-a-model-to-decode-from-2"
   },
   "source": [
    "rnn = d2l.RNN(num_inputs=64, num_hiddens=128)\n",
    "model = d2l.RNNLM(rnn, vocab_size=len(data.vocab), lr=4)"
   ],
   "execution_count": 3,
   "outputs": []
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "decoding-a-model-to-decode-from-3"
   },
   "source": [
    "trainer = d2l.Trainer(max_epochs=10, gradient_clip_val=1, num_gpus=1)\n",
    "model.board.yscale = 'log'\n",
    "trainer.fit(model, data)"
   ],
   "execution_count": 4,
   "outputs": [
    {
     "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=\"240.6625pt\" height=\"183.35625pt\" viewBox=\"0 0 240.6625 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:59:09.719216</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 240.6625 183.35625 \nL 240.6625 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 31.8 145.8 \nL 227.1 145.8 \nL 227.1 7.2 \nL 31.8 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      <defs>\n       <path id=\"m61f07daa11\" d=\"M 0 0 \nL 0 3.5 \n\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </defs>\n      <g>\n       <use xlink:href=\"#m61f07daa11\" x=\"31.8\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_1\">\n      <!-- 0 -->\n      <g transform=\"translate(28.61875 160.398438) scale(0.1 -0.1)\">\n       <defs>\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       </defs>\n       <use xlink:href=\"#DejaVuSans-30\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_2\">\n     <g id=\"line2d_2\">\n      <g>\n       <use xlink:href=\"#m61f07daa11\" x=\"70.86\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_2\">\n      <!-- 2 -->\n      <g transform=\"translate(67.67875 160.398438) scale(0.1 -0.1)\">\n       <defs>\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-32\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_3\">\n     <g id=\"line2d_3\">\n      <g>\n       <use xlink:href=\"#m61f07daa11\" x=\"109.92\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_3\">\n      <!-- 4 -->\n      <g transform=\"translate(106.73875 160.398438) 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\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_4\">\n     <g id=\"line2d_4\">\n      <g>\n       <use xlink:href=\"#m61f07daa11\" x=\"148.98\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_4\">\n      <!-- 6 -->\n      <g transform=\"translate(145.79875 160.398438) 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       </defs>\n       <use xlink:href=\"#DejaVuSans-36\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_5\">\n     <g id=\"line2d_5\">\n      <g>\n       <use xlink:href=\"#m61f07daa11\" x=\"188.04\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_5\">\n      <!-- 8 -->\n      <g transform=\"translate(184.85875 160.398438) scale(0.1 -0.1)\">\n       <defs>\n        <path id=\"DejaVuSans-38\" d=\"M 2034 2216 \nQ 1584 2216 1326 1975 \nQ 1069 1734 1069 1313 \nQ 1069 891 1326 650 \nQ 1584 409 2034 409 \nQ 2484 409 2743 651 \nQ 3003 894 3003 1313 \nQ 3003 1734 2745 1975 \nQ 2488 2216 2034 2216 \nz\nM 1403 2484 \nQ 997 2584 770 2862 \nQ 544 3141 544 3541 \nQ 544 4100 942 4425 \nQ 1341 4750 2034 4750 \nQ 2731 4750 3128 4425 \nQ 3525 4100 3525 3541 \nQ 3525 3141 3298 2862 \nQ 3072 2584 2669 2484 \nQ 3125 2378 3379 2068 \nQ 3634 1759 3634 1313 \nQ 3634 634 3220 271 \nQ 2806 -91 2034 -91 \nQ 1263 -91 848 271 \nQ 434 634 434 1313 \nQ 434 1759 690 2068 \nQ 947 2378 1403 2484 \nz\nM 1172 3481 \nQ 1172 3119 1398 2916 \nQ 1625 2713 2034 2713 \nQ 2441 2713 2670 2916 \nQ 2900 3119 2900 3481 \nQ 2900 3844 2670 4047 \nQ 2441 4250 2034 4250 \nQ 1625 4250 1398 4047 \nQ 1172 3844 1172 3481 \nz\n\" transform=\"scale(0.015625)\"/>\n       </defs>\n       <use xlink:href=\"#DejaVuSans-38\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_6\">\n     <g id=\"line2d_6\">\n      <g>\n       <use xlink:href=\"#m61f07daa11\" x=\"227.1\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_6\">\n      <!-- 10 -->\n      <g transform=\"translate(220.7375 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       </defs>\n       <use xlink:href=\"#DejaVuSans-31\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(63.623047 0)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"text_7\">\n     <!-- epoch -->\n     <g transform=\"translate(114.221875 174.076563) scale(0.1 -0.1)\">\n      <defs>\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-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-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-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-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-65\"/>\n      <use xlink:href=\"#DejaVuSans-70\" transform=\"translate(61.523438 0)\"/>\n      <use xlink:href=\"#DejaVuSans-6f\" transform=\"translate(125 0)\"/>\n      <use xlink:href=\"#DejaVuSans-63\" transform=\"translate(186.181641 0)\"/>\n      <use xlink:href=\"#DejaVuSans-68\" transform=\"translate(241.162109 0)\"/>\n     </g>\n    </g>\n   </g>\n   <g id=\"matplotlib.axis_2\">\n    <g id=\"ytick_1\">\n     <g id=\"line2d_7\">\n      <defs>\n       <path id=\"m3065b24a27\" d=\"M 0 0 \nL -3.5 0 \n\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </defs>\n      <g>\n       <use xlink:href=\"#m3065b24a27\" x=\"31.8\" y=\"72.689464\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_8\">\n      <!-- $\\mathdefault{10^{2}}$ -->\n      <g transform=\"translate(7.2 76.488683) scale(0.1 -0.1)\">\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-32\" transform=\"translate(128.203125 39.046875) scale(0.7)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_2\">\n     <g id=\"line2d_8\">\n      <defs>\n       <path id=\"m4af1659456\" d=\"M 0 0 \nL -2 0 \n\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </defs>\n      <g>\n       <use xlink:href=\"#m4af1659456\" x=\"31.8\" y=\"139.034387\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_3\">\n     <g id=\"line2d_9\">\n      <g>\n       <use xlink:href=\"#m4af1659456\" x=\"31.8\" y=\"123.181666\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_4\">\n     <g id=\"line2d_10\">\n      <g>\n       <use xlink:href=\"#m4af1659456\" x=\"31.8\" y=\"110.885341\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_5\">\n     <g id=\"line2d_11\">\n      <g>\n       <use xlink:href=\"#m4af1659456\" x=\"31.8\" y=\"100.838511\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_6\">\n     <g id=\"line2d_12\">\n      <g>\n       <use xlink:href=\"#m4af1659456\" x=\"31.8\" y=\"92.344038\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_7\">\n     <g id=\"line2d_13\">\n      <g>\n       <use xlink:href=\"#m4af1659456\" x=\"31.8\" y=\"84.98579\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_8\">\n     <g id=\"line2d_14\">\n      <g>\n       <use xlink:href=\"#m4af1659456\" x=\"31.8\" y=\"78.495356\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_9\">\n     <g id=\"line2d_15\">\n      <g>\n       <use xlink:href=\"#m4af1659456\" x=\"31.8\" y=\"34.493588\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_10\">\n     <g id=\"line2d_16\">\n      <g>\n       <use xlink:href=\"#m4af1659456\" x=\"31.8\" y=\"12.150433\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n   </g>\n   <g id=\"line2d_17\">\n    <path d=\"M 45.949286 13.5 \nL 55.515 33.919371 \nL 65.080714 48.894943 \nL 74.646429 59.563828 \nL 84.212143 71.271109 \nL 93.777857 82.504614 \nL 103.343571 89.677862 \nL 112.909286 96.996535 \nL 122.475 101.378115 \nL 132.040714 109.802909 \nL 141.606429 115.784662 \nL 151.172143 115.68992 \nL 160.737857 121.838617 \nL 170.303571 126.898778 \nL 179.869286 128.574609 \nL 189.435 131.78948 \nL 199.000714 135.287361 \nL 208.566429 138.53684 \nL 218.132143 139.5 \n\" clip-path=\"url(#p0bbcaf9418)\" style=\"fill: none; stroke: #1f77b4; stroke-width: 1.5; stroke-linecap: square\"/>\n   </g>\n   <g id=\"line2d_18\">\n    <path d=\"M 51.33 30.69336 \nL 70.86 43.047419 \nL 90.39 45.63543 \nL 109.92 67.962972 \nL 129.45 67.534353 \nL 148.98 76.425944 \nL 168.51 63.792953 \nL 188.04 71.088564 \nL 207.57 60.494108 \nL 227.1 65.90642 \n\" clip-path=\"url(#p0bbcaf9418)\" style=\"fill: none; stroke-dasharray: 5.55,2.4; stroke-dashoffset: 0; stroke: #ff7f0e; stroke-width: 1.5\"/>\n   </g>\n   <g id=\"patch_3\">\n    <path d=\"M 31.8 145.8 \nL 31.8 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 227.1 145.8 \nL 227.1 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 31.8 145.8 \nL 227.1 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 31.8 7.2 \nL 227.1 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 144.35 45.1125 \nL 220.1 45.1125 \nQ 222.1 45.1125 222.1 43.1125 \nL 222.1 14.2 \nQ 222.1 12.2 220.1 12.2 \nL 144.35 12.2 \nQ 142.35 12.2 142.35 14.2 \nL 142.35 43.1125 \nQ 142.35 45.1125 144.35 45.1125 \nz\n\" style=\"fill: #ffffff; opacity: 0.8; stroke: #cccccc; stroke-linejoin: miter\"/>\n    </g>\n    <g id=\"line2d_19\">\n     <path d=\"M 146.35 20.298438 \nL 156.35 20.298438 \nL 166.35 20.298438 \n\" style=\"fill: none; stroke: #1f77b4; stroke-width: 1.5; stroke-linecap: square\"/>\n    </g>\n    <g id=\"text_9\">\n     <!-- train_ppl -->\n     <g transform=\"translate(174.35 23.798438) scale(0.1 -0.1)\">\n      <defs>\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-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-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-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-5f\" d=\"M 3263 -1063 \nL 3263 -1509 \nL -63 -1509 \nL -63 -1063 \nL 3263 -1063 \nz\n\" 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      </defs>\n      <use xlink:href=\"#DejaVuSans-74\"/>\n      <use xlink:href=\"#DejaVuSans-72\" transform=\"translate(39.208984 0)\"/>\n      <use xlink:href=\"#DejaVuSans-61\" transform=\"translate(80.322266 0)\"/>\n      <use xlink:href=\"#DejaVuSans-69\" transform=\"translate(141.601562 0)\"/>\n      <use xlink:href=\"#DejaVuSans-6e\" transform=\"translate(169.384766 0)\"/>\n      <use xlink:href=\"#DejaVuSans-5f\" transform=\"translate(232.763672 0)\"/>\n      <use xlink:href=\"#DejaVuSans-70\" transform=\"translate(282.763672 0)\"/>\n      <use xlink:href=\"#DejaVuSans-70\" transform=\"translate(346.240234 0)\"/>\n      <use xlink:href=\"#DejaVuSans-6c\" transform=\"translate(409.716797 0)\"/>\n     </g>\n    </g>\n    <g id=\"line2d_20\">\n     <path d=\"M 146.35 35.254688 \nL 156.35 35.254688 \nL 166.35 35.254688 \n\" style=\"fill: none; stroke-dasharray: 5.55,2.4; stroke-dashoffset: 0; stroke: #ff7f0e; stroke-width: 1.5\"/>\n    </g>\n    <g id=\"text_10\">\n     <!-- val_ppl -->\n     <g transform=\"translate(174.35 38.754688) scale(0.1 -0.1)\">\n      <defs>\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-76\"/>\n      <use xlink:href=\"#DejaVuSans-61\" transform=\"translate(59.179688 0)\"/>\n      <use xlink:href=\"#DejaVuSans-6c\" transform=\"translate(120.458984 0)\"/>\n      <use xlink:href=\"#DejaVuSans-5f\" transform=\"translate(148.242188 0)\"/>\n      <use xlink:href=\"#DejaVuSans-70\" transform=\"translate(198.242188 0)\"/>\n      <use xlink:href=\"#DejaVuSans-70\" transform=\"translate(261.71875 0)\"/>\n      <use xlink:href=\"#DejaVuSans-6c\" transform=\"translate(325.195312 0)\"/>\n     </g>\n    </g>\n   </g>\n  </g>\n </g>\n <defs>\n  <clipPath id=\"p0bbcaf9418\">\n   <rect x=\"31.8\" 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=decoding-md-3 fw=all -->\n",
    "\n",
    "Every decoding strategy in this section interacts with the model through\n",
    "one narrow interface: hand me the token ids so far, and I will hand you the\n",
    "logits for the next token. We wrap the trained network in a `step_fn`\n",
    "implementing that interface, converting the result to a plain NumPy vector\n",
    "so that the strategies themselves can be written once, in ordinary Python,\n",
    "with no framework in sight. Any model that can fill this interface, today's\n",
    "RNN, next chapter's LSTM, a transformer, can be decoded by every algorithm\n",
    "below."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "decoding-a-model-to-decode-from-4"
   },
   "source": [
    "def step_fn(ids):  # Token ids in, numpy logits for the next token out\n",
    "    logits = model(d2l.tensor([ids], ctx=d2l.try_gpu()))\n",
    "    return d2l.numpy(logits)[0, -1]"
   ],
   "execution_count": 5,
   "outputs": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=decoding-md-4 fw=all -->\n",
    "\n",
    "Note the deliberate extravagance: each call re-runs the network over the\n",
    "*entire* prefix just to produce one vector of logits. We will tally the\n",
    "cost of this convenience at the end of the section.\n",
    "\n",
    "## Greedy Decoding\n",
    "\n",
    "The simplest decoder commits, at every step, to the single most likely\n",
    "token:\n",
    "\n",
    "$$x_t = \\operatorname*{argmax}_{x \\in \\mathcal{V}} P(x \\mid x_{<t}).$$\n",
    "\n",
    "The algorithm is a one-line loop: score, take the argmax, append, repeat.\n",
    "It costs one model evaluation per token, $\\mathcal{O}(|\\mathcal{V}| T)$\n",
    "work in total, and it is deterministic: the same prefix always yields the\n",
    "same continuation."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "decoding-greedy-decoding"
   },
   "source": [
    "def decode_greedy(text, num_tokens=50):\n",
    "    ids = data.tokenizer.encode(text)\n",
    "    for _ in range(num_tokens):\n",
    "        ids.append(int(step_fn(ids).argmax()))\n",
    "    return data.tokenizer.decode(ids)\n",
    "\n",
    "for text in ('the time traveller', 'it seemed to me that'):\n",
    "    print(repr(decode_greedy(text)))"
   ],
   "execution_count": 6,
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "'the time traveller I had come into the future. I was a vast array of a vast array of a vast array of a vast array of a vast array of a vast arr'\n'it seemed to me that the sun willutes of a tramblance of the Time Traveller. The Time Traveller. The Time Traveller. The Time Traveller. The Time Traveller. The Time Traveller. The Time Traveller. The Time Traveller. The Time Traveller.'\n"
     ]
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=decoding-md-5 fw=all -->\n",
    "\n",
    "The output is locally plausible Wells, but it drifts toward the generic,\n",
    "and it drifts *predictably*: the two different prefixes soon funnel into\n",
    "the same stock phrases, and, depending on the training run, the\n",
    "continuation may lock into a verbatim repeating cycle outright. Two\n",
    "distinct flaws are on display. The first is *myopia*: a sequence of\n",
    "locally best tokens need not be the best sequence. Suppose the vocabulary\n",
    "holds four tokens $A$, $B$, $C$, and $D$, and at the first step the model\n",
    "assigns them probabilities 0.5, 0.2, 0.2, and 0.1. Greedy picks $A$.\n",
    "Conditioned on $A$, suppose the best continuation runs through $B$ with\n",
    "probability 0.4, then 0.4, then 0.6: the greedy sequence has probability\n",
    "$0.5 \\times 0.4 \\times 0.4 \\times 0.6 = 0.048$. Had we accepted the\n",
    "*second*-best token $C$ (probability 0.3) at the second step, the changed\n",
    "conditioning might offer 0.6 and 0.6 next, for a total of $0.5 \\times 0.3\n",
    "\\times 0.6 \\times 0.6 = 0.054$. Taking one locally suboptimal step bought a\n",
    "globally better sequence; greedy can never make that trade.\n",
    "\n",
    "The second flaw runs deeper than myopia. Greedy decoding feeds its own\n",
    "argmax back in as context, and repetition is self-reinforcing: once a\n",
    "phrase has appeared twice, its third occurrence is *more* probable still,\n",
    "since the model has learned that text which repeats tends to keep\n",
    "repeating. The argmax feedback loop rides this gradient toward repetition\n",
    "and, given enough maximization pressure, into a literal fixed cycle.\n",
    "@Holtzman.Buys.Du.ea.2020 documented the phenomenon, aptly named\n",
    "*neural text degeneration*, in models a thousand times larger than ours:\n",
    "maximization-based decoding of open-ended text produces output that is\n",
    "repetitive, low-diversity, and measurably unlike human text, no matter how\n",
    "good the underlying model is. Keep that in mind as we now fix the first\n",
    "flaw, myopia, and watch the second one get worse.\n",
    "\n",
    "## Beam Search\n",
    "\n",
    "Decoding strategies live on a spectrum between the two extremes we have\n",
    "met: greedy search commits instantly and exhaustive search never commits at\n",
    "all. *Beam search* interpolates with a single knob, the *beam size* $k$:\n",
    "keep the $k$ most probable prefixes alive at every step. At the first step\n",
    "it selects the $k$ highest-probability tokens; thereafter, each of the $k$\n",
    "surviving prefixes is extended by every token in the vocabulary, the\n",
    "resulting $k \\cdot |\\mathcal{V}|$ candidates are scored by their cumulative\n",
    "log-probability, and only the best $k$ survive. Greedy search is the\n",
    "special case $k = 1$; exhaustive search is the limit where $k$ outgrows the\n",
    "candidate count and pruning never happens.\n",
    "\n",
    "![Beam search with beam size 2 over a five-token vocabulary. At every step each surviving prefix is expanded over the whole vocabulary and only the two highest-scoring prefixes are kept; the candidates here are $A$, $C$, then $AB$, $CE$, then $ABD$, $CED$.](../img/mdl-rnn-beam-tree.svg)\n",
    "\n",
    "the figure traces a worked example with $k = 2$ over the toy\n",
    "vocabulary $\\mathcal{V} = \\{A, B, C, D, E\\}$ and three generation steps.\n",
    "Suppose the two most probable first tokens are $A$ and $C$; they form the\n",
    "initial beam. At the second step we compute, for every $x_2 \\in\n",
    "\\mathcal{V}$, the extension scores\n",
    "\n",
    "$$\\begin{aligned}P(A, x_2 \\mid x_{\\leq m}) &= P(A \\mid x_{\\leq m}) P(x_2 \\mid A, x_{\\leq m}),\\\\ P(C, x_2 \\mid x_{\\leq m}) &= P(C \\mid x_{\\leq m}) P(x_2 \\mid C, x_{\\leq m}),\\end{aligned}$$\n",
    "\n",
    "ten numbers in all (here $x_{\\leq m}$ denotes the given prefix), and keep\n",
    "the two largest, say $P(A, B \\mid x_{\\leq m})$ and $P(C, E \\mid x_{\\leq\n",
    "m})$. The third step repeats the recipe from the survivors $AB$ and $CE$,\n",
    "yielding say $ABD$ and $CED$. Note what pruning bought us: instead of\n",
    "$5^3 = 125$ sequences we scored $5 + 10 + 10 = 25$, and in general beam\n",
    "search costs $\\mathcal{O}(k |\\mathcal{V}| T)$, a factor $k$ more than\n",
    "greedy and exponentially less than exhaustive search.\n",
    "\n",
    "One correction is needed before we can rank the finished candidates.\n",
    "Log-probabilities of tokens are non-positive, so the cumulative score of a\n",
    "sequence only falls as it grows, and comparing raw scores systematically\n",
    "favors short candidates (an acute issue once an end-of-sequence token can\n",
    "terminate some beams early). The standard remedy is *length normalization*\n",
    "[@Wu.Schuster.Chen.ea.2016]: rank each candidate of generated length\n",
    "$L$ by\n",
    "\n",
    "$$\\frac{1}{L^\\alpha} \\sum_{t=m+1}^{m+L} \\log P(x_t \\mid x_{<t}),$$\n",
    "\n",
    "where $\\alpha$ (typically around 0.75) interpolates between no correction\n",
    "($\\alpha = 0$) and the per-token average log-probability ($\\alpha = 1$).\n",
    "The implementation below follows the recipe directly. Finished candidates\n",
    "(those that produced `eos_id`) pass through unchanged from round to round;\n",
    "live ones are expanded and rescored. Since the global top $k$ can contain\n",
    "at most $k$ continuations of any single prefix, it suffices to consider\n",
    "each beam's $k$ best tokens rather than all $|\\mathcal{V}|$ of them. Like\n",
    "the rest of this section's toolkit, everything is plain Python against\n",
    "plain arrays, so this same function will decode next chapter's translation\n",
    "model without modification."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "decoding-beam-search-1"
   },
   "source": [
    "def beam_search(step_fn, prefix, num_tokens, beam_size=4,\n",
    "                alpha=0.75, eos_id=None):\n",
    "    \"\"\"Length-normalized beam search (score = log P / len^alpha).\n",
    "    Returns candidates sorted best-first; [0][1] is the argmax sequence.\"\"\"\n",
    "    def log_softmax(logits):\n",
    "        logits = [float(l) for l in logits]\n",
    "        m = max(logits)\n",
    "        lse = m + math.log(sum(math.exp(l - m) for l in logits))\n",
    "        return [l - lse for l in logits]\n",
    "    score = lambda logp, ids: logp / max(1, len(ids) - len(prefix))**alpha\n",
    "    beams = [(0.0, list(prefix), False)]  # (log-prob, sequence, finished)\n",
    "    for _ in range(num_tokens):\n",
    "        if all(done for _, _, done in beams):\n",
    "            break\n",
    "        candidates = [b for b in beams if b[2]]  # Finished pass through\n",
    "        for logp, ids, _ in (b for b in beams if not b[2]):\n",
    "            logprobs = log_softmax(step_fn(ids))\n",
    "            best = sorted(range(len(logprobs)),\n",
    "                          key=lambda i: -logprobs[i])[:beam_size]\n",
    "            candidates += [(logp + logprobs[i], ids + [i], i == eos_id)\n",
    "                           for i in best]\n",
    "        beams = sorted(candidates, key=lambda b: score(b[0], b[1]),\n",
    "                       reverse=True)[:beam_size]\n",
    "    return sorted([(score(logp, ids), ids) for logp, ids, _ in beams],\n",
    "                  reverse=True)"
   ],
   "execution_count": 7,
   "outputs": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=decoding-md-6 fw=all -->\n",
    "\n",
    "Let's decode the same two prefixes as before, with $k = 1$ (which\n",
    "reproduces greedy decoding) and $k = 4$. To make the repetition failure\n",
    "measurable rather than anecdotal we also report *distinct-3*, the fraction\n",
    "of distinct 3-grams among all 3-grams of the continuation: a value of 1\n",
    "means no 3-gram ever recurs, and a continuation stuck in a loop scores\n",
    "close to 0."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "decoding-beam-search-2"
   },
   "source": [
    "def distinct(ids, n=3):\n",
    "    grams = [tuple(ids[i:i + n]) for i in range(len(ids) - n + 1)]\n",
    "    return len(set(grams)) / max(1, len(grams))\n",
    "\n",
    "for text in ('the time traveller', 'it seemed to me that'):\n",
    "    pre = data.tokenizer.encode(text)\n",
    "    for k in (1, 4):\n",
    "        score, ids = beam_search(step_fn, pre, 40, beam_size=k)[0]\n",
    "        print(f'k={k}, score {score:.2f}, distinct-3 '\n",
    "              f'{distinct(ids[len(pre):]):.2f}: '\n",
    "              f'{data.tokenizer.decode(ids)!r}')"
   ],
   "execution_count": 8,
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "k=1, score -4.23, distinct-3 0.45: 'the time traveller I had come into the future. I was a vast array of a vast array of a vast array of a vast array of a v'\n"
     ]
    },
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "k=4, score -2.40, distinct-3 0.29: \"the time traveller-side windows. 'II\\n\\n\\n\\n\\n\\n\\n\\n\\n\\n\\n\\n\\n\\n\\n\\n\\n\\n\\n\\n\\n\\n\\n\\n\\n\\n\\n\\n\\n\\n\\n\\n\\n\\n\\n\\n\\n\\n\\n\\n\\n\\n\\n\\n\\n\\n\\n\\n\\n\\n\\n\\n\\n\\n\\n\\n\\n\\n\\n\\n\"\n"
     ]
    },
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "k=1, score -4.62, distinct-3 0.50: 'it seemed to me that the sun willutes of a tramblance of the Time Traveller. The Time Traveller. The Time Traveller. The Time Traveller. The Time Traveller. The Time Traveller. The Time'\n"
     ]
    },
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "k=4, score -3.42, distinct-3 0.76: \"it seemed to me that they were no doubt. I thought I heard a signs of the Time Traveller. The Time Traveller. 'II\\n\\n\\n\\n\\n\\n\\n\\n\\n\\n\\n\\n\\n\\n\\n\\n\\n\\n\\n\\n\\n\\n\"\n"
     ]
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=decoding-md-7 fw=all -->\n",
    "\n",
    "Beam search mostly does what it promises: at $k = 4$ it usually finds\n",
    "continuations that the model scores better than the greedy ones, curing the\n",
    "myopia of the four-token example above. It remains an approximate search,\n",
    "though, so on a given prefix a wider beam can occasionally come back\n",
    "*worse*. And yet look at the text. The continuations it returns lock into a\n",
    "literal loop, repeating one phrase verbatim, and the distinct-3 numbers\n",
    "collapse far below the values sampling will achieve; where greedy decoding\n",
    "already loops, beam search simply finds a higher-probability loop to be\n",
    "stuck in. This is the\n",
    "degeneration mechanism at work: the better a maximizer gets, the deeper\n",
    "it digs into the repetitive mode of the distribution. The lesson\n",
    "generalizes far beyond RNNs. For open-ended text\n",
    "the argmax itself is a bad target, and no improvement in search can fix a\n",
    "correctly solved wrong problem [@Holtzman.Buys.Du.ea.2020].\n",
    "\n",
    "It is tempting to conclude that more search at least helps the tasks where\n",
    "maximization *is* the right target. Curiously, it does not: in machine\n",
    "translation, pushing the beam from a handful to hundreds reliably *lowers*\n",
    "translation quality. Ever-larger beams find ever-higher-probability\n",
    "outputs, and those outputs are systematically shorter and blander, until\n",
    "the search starts uncovering pathologies of the model itself, such as an\n",
    "empty translation that outscores every real one. Length normalization\n",
    "softens this large-beam curse without eliminating it, so practitioners\n",
    "stop at small beams, typically $k$ between 4 and 10, where the search\n",
    "fixes local myopia but is not yet strong enough to exploit the model's\n",
    "blind spots.\n",
    "\n",
    "Where does beam search live today? Exactly where its assumptions hold:\n",
    "speech recognition and machine translation systems\n",
    "[@Sutskever.Vinyals.Le.2014; @Wu.Schuster.Chen.ea.2016] still\n",
    "beam-decode, and *constrained* decoding, which forces the output to obey a\n",
    "grammar, a JSON schema, or an API signature, is beam search over the valid\n",
    "continuations. Your chat assistant, however, does not use it: open-ended\n",
    "dialogue sits firmly in the second family, to which we now turn.\n",
    "\n",
    "## Sampling and Its Dials\n",
    "\n",
    "If the model's distribution is worth trusting, the principled way to\n",
    "generate is to *sample* from it: draw $x_t \\sim P(x_t \\mid x_{<t})$,\n",
    "append, repeat. Text produced this way is distributed exactly as the model\n",
    "believes text should be, with all the diversity that maximization threw\n",
    "away and none of its repetition traps. The catch appears in the tail. Our\n",
    "model spreads small probability over a thousand tokens, a large one over\n",
    "hundreds of thousands, and although each unlikely token is individually\n",
    "negligible, their combined mass at every step is not. Sampling therefore\n",
    "regularly hits tokens the model itself considers near-nonsense, and one\n",
    "absurd token, fed back as context, can derail everything after it.\n",
    "@Holtzman.Buys.Du.ea.2020 call this the *unreliable tail*: the\n",
    "model's estimates are relatively trustworthy at the head of the\n",
    "distribution and mostly noise far down the ranking, so the fix is to\n",
    "sample from a reshaped, truncated distribution. Each of the dials below is\n",
    "one way of doing that.\n",
    "\n",
    "**Temperature** rescales before sampling. Dividing every logit $o_x$ by a\n",
    "temperature $T > 0$ gives\n",
    "\n",
    "$$P_T(x \\mid x_{<t}) = \\frac{\\exp(o_x / T)}{\\sum_{x' \\in \\mathcal{V}} \\exp(o_{x'} / T)} \\propto P(x \\mid x_{<t})^{1/T}.$$\n",
    "\n",
    "At $T = 1$ we sample the model as-is; as $T \\to 0$ the distribution\n",
    "sharpens toward its mode and sampling becomes greedy decoding; as $T$\n",
    "grows it flattens toward uniform. Temperature trades diversity against\n",
    "safety smoothly, but it reshapes head and tail together: cooling the\n",
    "distribution enough to suppress the tail also crushes legitimate variety\n",
    "at the head.\n",
    "\n",
    "**Top-$k$** truncates by *count*: keep the $k$ most probable tokens,\n",
    "renormalize, and sample [@Radford.Wu.Child.ea.2019]. **Top-$p$** (or\n",
    "*nucleus*) sampling truncates by *mass*: keep the smallest set of\n",
    "most-probable tokens whose cumulative probability reaches $p$, for example\n",
    "$p = 0.9$ [@Holtzman.Buys.Du.ea.2020]. The difference matters because\n",
    "the model's confidence varies wildly from step to step. Where our model is\n",
    "nearly certain of the next token, a fixed $k = 20$ needlessly admits\n",
    "nineteen bad options; mid-sentence, where dozens of words are genuinely\n",
    "plausible, the same $k$ may cut off real diversity. Top-$p$ adapts better,\n",
    "keeping few tokens when the head is heavy and many when it is flat, but it\n",
    "too misbehaves on peaked distributions: if the top token already holds\n",
    "0.95 of the mass, top-$p$ with $p = 0.9$ keeps exactly one token and acts\n",
    "greedily even where the runner-up was perfectly acceptable.\n",
    "\n",
    "**Min-$p$** scales the cutoff by the model's own confidence\n",
    "[@Nguyen.Baker.Neo.ea.2025]: keep every token whose probability is at\n",
    "least $p_{\\min}$ times that of the most probable token, e.g. $p_{\\min} =\n",
    "0.05$. When the model is sure, the bar is high and few tokens pass; when\n",
    "the model is uncertain, the bar drops and the genuine variety survives.\n",
    "This relative rule holds up notably better at high temperatures, where\n",
    "creative sampling wants to operate and where absolute-threshold rules\n",
    "admit the noise floor wholesale.\n",
    "\n",
    "### A Unified Sampler\n",
    "\n",
    "All four dials act on the same object, the next-token distribution, so a\n",
    "single function can host them. `sample_next` turns one vector of logits\n",
    "into one token id: greedy if asked, otherwise temperature-scaled sampling\n",
    "after optional top-$k$, top-$p$, and min-$p$ truncation. Note how each\n",
    "truncation rule is just a different cut of the same sorted-by-probability\n",
    "order, a pure function of the distribution; we exploit that shortly to\n",
    "visualize all three at once. Like `beam_search` it is written in plain\n",
    "Python, and it draws through an explicit `rng` (anything with a\n",
    "`random()` method, such as `numpy.random.default_rng(seed)`) so that\n",
    "generation is reproducible."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "decoding-a-unified-sampler-1"
   },
   "source": [
    "def sample_next(logits, strategy='greedy', temperature=1.0,\n",
    "                k=None, p=None, min_p=None, rng=None):\n",
    "    \"\"\"Choose the next token id from a 1-D numpy logits array.\n",
    "    strategy: 'greedy' | 'sample' (with optional top-k / top-p / min-p\n",
    "    truncation applied to the temperature-scaled distribution).\"\"\"\n",
    "    logits = [float(l) for l in logits]\n",
    "    if strategy == 'greedy' or temperature == 0:\n",
    "        return max(range(len(logits)), key=lambda i: logits[i])\n",
    "    m = max(logits)\n",
    "    probs = [math.exp((l - m) / temperature) for l in logits]\n",
    "    total = sum(probs)\n",
    "    probs = [q / total for q in probs]\n",
    "    order = sorted(range(len(probs)), key=lambda i: -probs[i])\n",
    "    keep = len(order)\n",
    "    if k is not None:  # Top-k: the k most probable tokens\n",
    "        keep = min(keep, k)\n",
    "    if p is not None:  # Top-p: smallest head with cumulative mass >= p\n",
    "        mass, n = 0.0, 0\n",
    "        while mass < p and n < len(order):\n",
    "            mass, n = mass + probs[order[n]], n + 1\n",
    "        keep = min(keep, n)\n",
    "    if min_p is not None:  # Min-p: within a factor of the top token\n",
    "        bar = min_p * probs[order[0]]\n",
    "        keep = min(keep, sum(q >= bar for q in probs))\n",
    "    kept = order[:keep]\n",
    "    rng = random if rng is None else rng\n",
    "    r = rng.random() * sum(probs[i] for i in kept)\n",
    "    for i in kept:\n",
    "        r -= probs[i]\n",
    "        if r <= 0:\n",
    "            return i\n",
    "    return kept[-1]"
   ],
   "execution_count": 9,
   "outputs": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=decoding-md-8 fw=all -->\n",
    "\n",
    "`generate` is the loop we have been writing by hand all along: query\n",
    "`step_fn`, choose via `sample_next` (extra keyword arguments pass straight\n",
    "through to it), append, and stop early if an end-of-sequence token\n",
    "appears. Open-ended generation has no such token, so our demonstrations\n",
    "simply run for a fixed length; the translation models of the next chapter\n",
    "set `eos_id` and let the model decide when it is done."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "decoding-a-unified-sampler-2"
   },
   "source": [
    "def generate(step_fn, prefix, num_tokens, eos_id=None, **strategy):\n",
    "    \"\"\"Autoregressive generation. step_fn(ids: list[int]) -> numpy logits\n",
    "    for the next token. Returns prefix + continuation (stops on eos_id).\"\"\"\n",
    "    ids = list(prefix)\n",
    "    for _ in range(num_tokens):\n",
    "        ids.append(sample_next(step_fn(ids), **strategy))\n",
    "        if eos_id is not None and ids[-1] == eos_id:\n",
    "            break\n",
    "    return ids"
   ],
   "execution_count": 10,
   "outputs": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=decoding-md-9 fw=all -->\n",
    "\n",
    "A toy distribution makes the truncation rules concrete. Five tokens carry\n",
    "probabilities 0.45, 0.25, 0.15, 0.10, and 0.05. Top-$k$ with $k = 2$ may\n",
    "only ever emit tokens 0 and 1; top-$p$ with $p = 0.85$ keeps three tokens,\n",
    "since the cumulative mass first reaches 0.85 at the third; min-$p$ with\n",
    "$p_{\\min} = 0.5$ keeps the tokens with probability at least $0.5 \\times\n",
    "0.45 = 0.225$, which is again tokens 0 and 1."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "decoding-a-unified-sampler-3"
   },
   "source": [
    "logits, rng = np.log([0.45, 0.25, 0.15, 0.1, 0.05]), np.random.default_rng(0)\n",
    "print('greedy:', sample_next(logits))\n",
    "for dial in (dict(k=2), dict(p=0.85), dict(min_p=0.5)):\n",
    "    draws = [sample_next(logits, strategy='sample', rng=rng, **dial)\n",
    "             for _ in range(15)]\n",
    "    print(dial, draws)"
   ],
   "execution_count": 11,
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "greedy: 0\n{'k': 2} [0, 0, 0, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1]\n{'p': 0.85} [0, 2, 1, 0, 0, 0, 0, 1, 1, 1, 0, 2, 2, 1, 1]\n{'min_p': 0.5} [1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0]\n"
     ]
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=decoding-md-10 fw=all -->\n",
    "\n",
    "### One Distribution, Three Cutoffs\n",
    "\n",
    "Toy numbers are one thing; here is the real object every dial acts on. We\n",
    "query the trained model once and plot its entire next-token distribution,\n",
    "sorted by decreasing probability, on logarithmic axes (the shape is\n",
    "Zipf-like, as that section would lead us to expect). On\n",
    "this plot each truncation rule is a single line. Top-$k$ is a vertical cut\n",
    "at rank $k$, wherever the probabilities happen to lie. Top-$p$ is a\n",
    "vertical cut at the rank where the cumulative mass reaches $p$, so its\n",
    "position slides with the shape of the head. Min-$p$ is a *horizontal* cut\n",
    "at $p_{\\min}$ times the top probability: every token above the line\n",
    "survives, and the line itself rides up and down with the model's\n",
    "confidence. Everything below and to the right of the cuts is the\n",
    "unreliable tail that truncation exists to remove."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "decoding-one-distribution-three-cutoffs-1"
   },
   "source": [
    "def next_probs(text):  # Sorted next-token distribution after a prefix\n",
    "    logits = step_fn(data.tokenizer.encode(text))\n",
    "    probs = np.exp(logits - logits.max())\n",
    "    return np.sort(probs / probs.sum())[::-1]\n",
    "\n",
    "probs = next_probs('the time traveller')\n",
    "n_p = int((np.cumsum(probs) < 0.9).sum()) + 1\n",
    "n_m = int((probs >= 0.05 * probs[0]).sum())\n",
    "d2l.set_figsize((5.5, 3))\n",
    "d2l.plt.loglog(np.arange(1, len(probs) + 1), probs, color='C0')\n",
    "d2l.plt.axvline(20, color='C1', ls='--', label='top-k, k=20')\n",
    "d2l.plt.axvline(n_p, color='C2', ls='-.', label=f'top-p=0.9: keep {n_p}')\n",
    "d2l.plt.axhline(0.05 * probs[0], color='C3', ls=':',\n",
    "                label=f'min-p=0.05: keep {n_m}')\n",
    "d2l.plt.xlabel('token rank')\n",
    "d2l.plt.ylabel('probability')\n",
    "d2l.plt.legend()"
   ],
   "execution_count": 12,
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "<matplotlib.legend.Legend at 0x76b93a316000>"
     },
     "metadata": {},
     "execution_count": 12
    },
    {
     "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=\"365.478125pt\" height=\"211.07625pt\" viewBox=\"0 0 365.478125 211.07625\" 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:59:12.852034</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 211.07625 \nL 365.478125 211.07625 \nL 365.478125 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 51.378125 173.52 \nL 358.278125 173.52 \nL 358.278125 7.2 \nL 51.378125 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      <defs>\n       <path id=\"me4a79f335c\" d=\"M 0 0 \nL 0 3.5 \n\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </defs>\n      <g>\n       <use xlink:href=\"#me4a79f335c\" x=\"65.328125\" y=\"173.52\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_1\">\n      <!-- $\\mathdefault{10^{0}}$ -->\n      <g transform=\"translate(56.528125 188.118438) 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       </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-30\" transform=\"translate(128.203125 39.046875) scale(0.7)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_2\">\n     <g id=\"line2d_2\">\n      <g>\n       <use xlink:href=\"#me4a79f335c\" x=\"157.970819\" y=\"173.52\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_2\">\n      <!-- $\\mathdefault{10^{1}}$ -->\n      <g transform=\"translate(149.170819 188.118438) scale(0.1 -0.1)\">\n       <use xlink:href=\"#DejaVuSans-31\" transform=\"translate(0 0.684375)\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(63.623047 0.684375)\"/>\n       <use xlink:href=\"#DejaVuSans-31\" transform=\"translate(128.203125 38.965625) scale(0.7)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_3\">\n     <g id=\"line2d_3\">\n      <g>\n       <use xlink:href=\"#me4a79f335c\" x=\"250.613514\" y=\"173.52\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_3\">\n      <!-- $\\mathdefault{10^{2}}$ -->\n      <g transform=\"translate(241.813514 188.118438) scale(0.1 -0.1)\">\n       <defs>\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-31\" transform=\"translate(0 0.765625)\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(63.623047 0.765625)\"/>\n       <use xlink:href=\"#DejaVuSans-32\" transform=\"translate(128.203125 39.046875) scale(0.7)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_4\">\n     <g id=\"line2d_4\">\n      <g>\n       <use xlink:href=\"#me4a79f335c\" x=\"343.256208\" y=\"173.52\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_4\">\n      <!-- $\\mathdefault{10^{3}}$ -->\n      <g transform=\"translate(334.456208 188.118438) scale(0.1 -0.1)\">\n       <defs>\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_5\">\n     <g id=\"line2d_5\">\n      <defs>\n       <path id=\"m3e50b419e5\" d=\"M 0 0 \nL 0 2 \n\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </defs>\n      <g>\n       <use xlink:href=\"#m3e50b419e5\" x=\"56.35012\" y=\"173.52\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_6\">\n     <g id=\"line2d_6\">\n      <g>\n       <use xlink:href=\"#m3e50b419e5\" x=\"61.089028\" y=\"173.52\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_7\">\n     <g id=\"line2d_7\">\n      <g>\n       <use xlink:href=\"#m3e50b419e5\" x=\"93.216355\" y=\"173.52\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_8\">\n     <g id=\"line2d_8\">\n      <g>\n       <use xlink:href=\"#m3e50b419e5\" x=\"109.529924\" y=\"173.52\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_9\">\n     <g id=\"line2d_9\">\n      <g>\n       <use xlink:href=\"#m3e50b419e5\" x=\"121.104585\" y=\"173.52\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_10\">\n     <g id=\"line2d_10\">\n      <g>\n       <use xlink:href=\"#m3e50b419e5\" x=\"130.082589\" y=\"173.52\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_11\">\n     <g id=\"line2d_11\">\n      <g>\n       <use xlink:href=\"#m3e50b419e5\" x=\"137.418153\" y=\"173.52\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_12\">\n     <g id=\"line2d_12\">\n      <g>\n       <use xlink:href=\"#m3e50b419e5\" x=\"143.620284\" y=\"173.52\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_13\">\n     <g id=\"line2d_13\">\n      <g>\n       <use xlink:href=\"#m3e50b419e5\" x=\"148.992815\" y=\"173.52\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_14\">\n     <g id=\"line2d_14\">\n      <g>\n       <use xlink:href=\"#m3e50b419e5\" x=\"153.731722\" y=\"173.52\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_15\">\n     <g id=\"line2d_15\">\n      <g>\n       <use xlink:href=\"#m3e50b419e5\" x=\"185.859049\" y=\"173.52\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_16\">\n     <g id=\"line2d_16\">\n      <g>\n       <use xlink:href=\"#m3e50b419e5\" x=\"202.172618\" y=\"173.52\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_17\">\n     <g id=\"line2d_17\">\n      <g>\n       <use xlink:href=\"#m3e50b419e5\" x=\"213.747279\" y=\"173.52\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_18\">\n     <g id=\"line2d_18\">\n      <g>\n       <use xlink:href=\"#m3e50b419e5\" x=\"222.725284\" y=\"173.52\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_19\">\n     <g id=\"line2d_19\">\n      <g>\n       <use xlink:href=\"#m3e50b419e5\" x=\"230.060848\" y=\"173.52\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_20\">\n     <g id=\"line2d_20\">\n      <g>\n       <use xlink:href=\"#m3e50b419e5\" x=\"236.262979\" y=\"173.52\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_21\">\n     <g id=\"line2d_21\">\n      <g>\n       <use xlink:href=\"#m3e50b419e5\" x=\"241.635509\" y=\"173.52\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_22\">\n     <g id=\"line2d_22\">\n      <g>\n       <use xlink:href=\"#m3e50b419e5\" x=\"246.374416\" y=\"173.52\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_23\">\n     <g id=\"line2d_23\">\n      <g>\n       <use xlink:href=\"#m3e50b419e5\" x=\"278.501743\" y=\"173.52\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_24\">\n     <g id=\"line2d_24\">\n      <g>\n       <use xlink:href=\"#m3e50b419e5\" x=\"294.815312\" y=\"173.52\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_25\">\n     <g id=\"line2d_25\">\n      <g>\n       <use xlink:href=\"#m3e50b419e5\" x=\"306.389973\" y=\"173.52\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_26\">\n     <g id=\"line2d_26\">\n      <g>\n       <use xlink:href=\"#m3e50b419e5\" x=\"315.367978\" y=\"173.52\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_27\">\n     <g id=\"line2d_27\">\n      <g>\n       <use xlink:href=\"#m3e50b419e5\" x=\"322.703542\" y=\"173.52\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_28\">\n     <g id=\"line2d_28\">\n      <g>\n       <use xlink:href=\"#m3e50b419e5\" x=\"328.905673\" y=\"173.52\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_29\">\n     <g id=\"line2d_29\">\n      <g>\n       <use xlink:href=\"#m3e50b419e5\" x=\"334.278203\" y=\"173.52\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_30\">\n     <g id=\"line2d_30\">\n      <g>\n       <use xlink:href=\"#m3e50b419e5\" x=\"339.017111\" y=\"173.52\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"text_5\">\n     <!-- token rank -->\n     <g transform=\"translate(178.076563 201.796563) scale(0.1 -0.1)\">\n      <defs>\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-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-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       <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-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-20\" 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-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      </defs>\n      <use xlink:href=\"#DejaVuSans-74\"/>\n      <use xlink:href=\"#DejaVuSans-6f\" transform=\"translate(39.208984 0)\"/>\n      <use xlink:href=\"#DejaVuSans-6b\" transform=\"translate(100.390625 0)\"/>\n      <use xlink:href=\"#DejaVuSans-65\" transform=\"translate(154.675781 0)\"/>\n      <use xlink:href=\"#DejaVuSans-6e\" transform=\"translate(216.199219 0)\"/>\n      <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(279.578125 0)\"/>\n      <use xlink:href=\"#DejaVuSans-72\" transform=\"translate(311.365234 0)\"/>\n      <use xlink:href=\"#DejaVuSans-61\" transform=\"translate(352.478516 0)\"/>\n      <use xlink:href=\"#DejaVuSans-6e\" transform=\"translate(413.757812 0)\"/>\n      <use xlink:href=\"#DejaVuSans-6b\" transform=\"translate(477.136719 0)\"/>\n     </g>\n    </g>\n   </g>\n   <g id=\"matplotlib.axis_2\">\n    <g id=\"ytick_1\">\n     <g id=\"line2d_31\">\n      <defs>\n       <path id=\"m3decea8783\" d=\"M 0 0 \nL -3.5 0 \n\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </defs>\n      <g>\n       <use xlink:href=\"#m3decea8783\" x=\"51.378125\" y=\"152.510064\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_6\">\n      <!-- $\\mathdefault{10^{-9}}$ -->\n      <g transform=\"translate(20.878125 156.309283) scale(0.1 -0.1)\">\n       <defs>\n        <path id=\"DejaVuSans-2212\" d=\"M 678 2272 \nL 4684 2272 \nL 4684 1741 \nL 678 1741 \nL 678 2272 \nz\n\" transform=\"scale(0.015625)\"/>\n        <path id=\"DejaVuSans-39\" d=\"M 703 97 \nL 703 672 \nQ 941 559 1184 500 \nQ 1428 441 1663 441 \nQ 2288 441 2617 861 \nQ 2947 1281 2994 2138 \nQ 2813 1869 2534 1725 \nQ 2256 1581 1919 1581 \nQ 1219 1581 811 2004 \nQ 403 2428 403 3163 \nQ 403 3881 828 4315 \nQ 1253 4750 1959 4750 \nQ 2769 4750 3195 4129 \nQ 3622 3509 3622 2328 \nQ 3622 1225 3098 567 \nQ 2575 -91 1691 -91 \nQ 1453 -91 1209 -44 \nQ 966 3 703 97 \nz\nM 1959 2075 \nQ 2384 2075 2632 2365 \nQ 2881 2656 2881 3163 \nQ 2881 3666 2632 3958 \nQ 2384 4250 1959 4250 \nQ 1534 4250 1286 3958 \nQ 1038 3666 1038 3163 \nQ 1038 2656 1286 2365 \nQ 1534 2075 1959 2075 \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-2212\" transform=\"translate(128.203125 39.046875) scale(0.7)\"/>\n       <use xlink:href=\"#DejaVuSans-39\" transform=\"translate(186.855469 39.046875) scale(0.7)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_2\">\n     <g id=\"line2d_32\">\n      <g>\n       <use xlink:href=\"#m3decea8783\" x=\"51.378125\" y=\"119.876777\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_7\">\n      <!-- $\\mathdefault{10^{-7}}$ -->\n      <g transform=\"translate(20.878125 123.675996) scale(0.1 -0.1)\">\n       <defs>\n        <path id=\"DejaVuSans-37\" d=\"M 525 4666 \nL 3525 4666 \nL 3525 4397 \nL 1831 0 \nL 1172 0 \nL 2766 4134 \nL 525 4134 \nL 525 4666 \nz\n\" transform=\"scale(0.015625)\"/>\n       </defs>\n       <use xlink:href=\"#DejaVuSans-31\" transform=\"translate(0 0.684375)\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(63.623047 0.684375)\"/>\n       <use xlink:href=\"#DejaVuSans-2212\" transform=\"translate(128.203125 38.965625) scale(0.7)\"/>\n       <use xlink:href=\"#DejaVuSans-37\" transform=\"translate(186.855469 38.965625) scale(0.7)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_3\">\n     <g id=\"line2d_33\">\n      <g>\n       <use xlink:href=\"#m3decea8783\" x=\"51.378125\" y=\"87.24349\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_8\">\n      <!-- $\\mathdefault{10^{-5}}$ -->\n      <g transform=\"translate(20.878125 91.042709) scale(0.1 -0.1)\">\n       <defs>\n        <path id=\"DejaVuSans-35\" d=\"M 691 4666 \nL 3169 4666 \nL 3169 4134 \nL 1269 4134 \nL 1269 2991 \nQ 1406 3038 1543 3061 \nQ 1681 3084 1819 3084 \nQ 2600 3084 3056 2656 \nQ 3513 2228 3513 1497 \nQ 3513 744 3044 326 \nQ 2575 -91 1722 -91 \nQ 1428 -91 1123 -41 \nQ 819 9 494 109 \nL 494 744 \nQ 775 591 1075 516 \nQ 1375 441 1709 441 \nQ 2250 441 2565 725 \nQ 2881 1009 2881 1497 \nQ 2881 1984 2565 2268 \nQ 2250 2553 1709 2553 \nQ 1456 2553 1204 2497 \nQ 953 2441 691 2322 \nL 691 4666 \nz\n\" transform=\"scale(0.015625)\"/>\n       </defs>\n       <use xlink:href=\"#DejaVuSans-31\" transform=\"translate(0 0.684375)\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(63.623047 0.684375)\"/>\n       <use xlink:href=\"#DejaVuSans-2212\" transform=\"translate(128.203125 38.965625) scale(0.7)\"/>\n       <use xlink:href=\"#DejaVuSans-35\" transform=\"translate(186.855469 38.965625) scale(0.7)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_4\">\n     <g id=\"line2d_34\">\n      <g>\n       <use xlink:href=\"#m3decea8783\" x=\"51.378125\" y=\"54.610203\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_9\">\n      <!-- $\\mathdefault{10^{-3}}$ -->\n      <g transform=\"translate(20.878125 58.409422) scale(0.1 -0.1)\">\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-2212\" transform=\"translate(128.203125 39.046875) scale(0.7)\"/>\n       <use xlink:href=\"#DejaVuSans-33\" transform=\"translate(186.855469 39.046875) scale(0.7)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_5\">\n     <g id=\"line2d_35\">\n      <g>\n       <use xlink:href=\"#m3decea8783\" x=\"51.378125\" y=\"21.976916\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_10\">\n      <!-- $\\mathdefault{10^{-1}}$ -->\n      <g transform=\"translate(20.878125 25.776135) scale(0.1 -0.1)\">\n       <use xlink:href=\"#DejaVuSans-31\" transform=\"translate(0 0.684375)\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(63.623047 0.684375)\"/>\n       <use xlink:href=\"#DejaVuSans-2212\" transform=\"translate(128.203125 38.965625) scale(0.7)\"/>\n       <use xlink:href=\"#DejaVuSans-31\" transform=\"translate(186.855469 38.965625) scale(0.7)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"text_11\">\n     <!-- probability -->\n     <g transform=\"translate(14.798438 117.035781) rotate(-90) scale(0.1 -0.1)\">\n      <defs>\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-62\" d=\"M 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\nM 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 \nL 1159 0 \nL 581 0 \nL 581 4863 \nL 1159 4863 \nL 1159 2969 \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-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-79\" d=\"M 2059 -325 \nQ 1816 -950 1584 -1140 \nQ 1353 -1331 966 -1331 \nL 506 -1331 \nL 506 -850 \nL 844 -850 \nQ 1081 -850 1212 -737 \nQ 1344 -625 1503 -206 \nL 1606 56 \nL 191 3500 \nL 800 3500 \nL 1894 763 \nL 2988 3500 \nL 3597 3500 \nL 2059 -325 \nz\n\" transform=\"scale(0.015625)\"/>\n      </defs>\n      <use xlink:href=\"#DejaVuSans-70\"/>\n      <use xlink:href=\"#DejaVuSans-72\" transform=\"translate(63.476562 0)\"/>\n      <use xlink:href=\"#DejaVuSans-6f\" transform=\"translate(102.339844 0)\"/>\n      <use xlink:href=\"#DejaVuSans-62\" transform=\"translate(163.521484 0)\"/>\n      <use xlink:href=\"#DejaVuSans-61\" transform=\"translate(226.998047 0)\"/>\n      <use xlink:href=\"#DejaVuSans-62\" transform=\"translate(288.277344 0)\"/>\n      <use xlink:href=\"#DejaVuSans-69\" transform=\"translate(351.753906 0)\"/>\n      <use xlink:href=\"#DejaVuSans-6c\" transform=\"translate(379.537109 0)\"/>\n      <use xlink:href=\"#DejaVuSans-69\" transform=\"translate(407.320312 0)\"/>\n      <use xlink:href=\"#DejaVuSans-74\" transform=\"translate(435.103516 0)\"/>\n      <use xlink:href=\"#DejaVuSans-79\" transform=\"translate(474.3125 0)\"/>\n     </g>\n    </g>\n   </g>\n   <g id=\"line2d_36\">\n    <path d=\"M 65.328125 14.76 \nL 93.216355 20.622004 \nL 109.529924 25.732977 \nL 121.104585 26.936116 \nL 130.082589 29.73843 \nL 137.418153 29.778254 \nL 143.620284 30.313485 \nL 148.992815 30.419166 \nL 153.731722 31.501067 \nL 157.970819 31.690621 \nL 161.805549 33.833797 \nL 165.306383 35.074058 \nL 168.526838 36.443665 \nL 171.508514 37.911909 \nL 176.881044 38.252435 \nL 181.619952 38.447699 \nL 183.795304 39.088616 \nL 185.859049 39.286179 \nL 187.822083 40.194593 \nL 189.693779 40.687224 \nL 196.415068 41.502497 \nL 197.933521 41.569608 \nL 200.808616 42.149335 \nL 202.172618 43.712213 \nL 204.769274 43.938121 \nL 207.208458 44.529283 \nL 208.374749 46.519795 \nL 212.728637 47.073629 \nL 213.747279 47.767482 \nL 214.740767 47.814686 \nL 215.710313 48.723837 \nL 216.657044 48.812195 \nL 220.235776 49.918586 \nL 221.082843 49.924833 \nL 221.912444 50.917878 \nL 222.725284 51.333431 \nL 231.38012 52.721637 \nL 232.023881 53.468789 \nL 233.281303 53.632643 \nL 233.895578 53.98873 \nL 234.500615 54.124615 \nL 235.096688 54.391071 \nL 236.262979 54.508757 \nL 236.833686 54.538239 \nL 238.498788 54.960023 \nL 239.038852 55.43784 \nL 242.135319 55.871016 \nL 242.628997 56.128487 \nL 243.11669 56.152353 \nL 243.598543 56.402704 \nL 244.074693 56.439313 \nL 244.545274 56.779518 \nL 245.010414 56.795784 \nL 245.470239 57.275815 \nL 246.374416 57.375478 \nL 246.818998 57.379914 \nL 247.693689 57.88389 \nL 248.124006 57.975966 \nL 249.388011 58.572602 \nL 250.209146 58.623007 \nL 250.613514 58.776183 \nL 251.013857 59.140456 \nL 251.410257 59.211283 \nL 251.802789 59.793777 \nL 252.576547 59.918588 \nL 252.957917 60.152622 \nL 255.173204 60.670788 \nL 255.530844 61.287982 \nL 256.236725 61.334653 \nL 256.585075 61.772679 \nL 257.272856 61.899529 \nL 258.614121 62.593851 \nL 258.942565 62.643678 \nL 259.591518 62.867501 \nL 259.912111 62.900943 \nL 260.23017 63.3933 \nL 260.545734 63.407898 \nL 263.279675 64.53333 \nL 263.572289 64.536641 \nL 264.721916 65.236715 \nL 265.004263 65.606168 \nL 265.56308 65.683095 \nL 265.839605 65.903601 \nL 266.114242 65.948446 \nL 266.387018 66.288932 \nL 267.19442 66.496276 \nL 267.459994 66.860405 \nL 268.246355 67.320851 \nL 268.505097 67.367866 \nL 268.762185 67.547347 \nL 269.017641 67.585701 \nL 269.271486 68.011729 \nL 269.523739 68.033524 \nL 270.023549 68.301558 \nL 270.761812 68.393804 \nL 272.198901 68.852953 \nL 272.433504 69.167982 \nL 272.666746 69.182492 \nL 273.129213 69.422886 \nL 274.262646 69.551523 \nL 275.14695 70.025364 \nL 275.365022 70.040846 \nL 275.581919 70.60397 \nL 276.859303 70.774557 \nL 277.068312 70.805377 \nL 277.276241 70.988731 \nL 277.483101 70.998936 \nL 277.688903 71.607401 \nL 277.893658 71.634892 \nL 278.097376 71.801516 \nL 278.702413 71.942285 \nL 279.885858 72.542824 \nL 280.464777 72.685126 \nL 280.846147 72.783326 \nL 281.411508 73.07062 \nL 282.153174 73.173969 \nL 282.518942 73.284799 \nL 283.596708 73.614358 \nL 283.773562 73.925143 \nL 284.124955 74.010125 \nL 284.818665 74.45056 \nL 285.500618 74.610102 \nL 286.337118 74.95002 \nL 287.15658 75.815153 \nL 287.318489 75.819566 \nL 287.479748 76.228429 \nL 287.800341 76.276235 \nL 287.959685 76.538639 \nL 288.1184 76.562543 \nL 288.590823 76.859108 \nL 288.747072 76.907644 \nL 290.576215 78.837526 \nL 290.724955 78.850833 \nL 291.020796 79.1993 \nL 291.314478 79.534143 \nL 291.606032 79.699537 \nL 291.895488 79.714209 \nL 292.039438 79.915704 \nL 292.325804 80.005098 \nL 293.032926 80.332386 \nL 293.172871 80.333771 \nL 293.727835 80.737228 \nL 294.139091 80.905143 \nL 294.410945 81.128399 \nL 294.680974 81.169777 \nL 294.949203 81.36886 \nL 295.348223 81.436777 \nL 295.612055 81.617445 \nL 296.134585 81.744994 \nL 296.650415 82.102139 \nL 296.905871 82.179767 \nL 297.28604 82.382161 \nL 298.89315 83.00467 \nL 299.014155 83.102741 \nL 299.134797 83.481221 \nL 299.494569 83.516084 \nL 299.732642 83.659516 \nL 299.969315 83.732043 \nL 300.438524 84.098965 \nL 301.017443 84.334156 \nL 301.701327 84.619752 \nL 301.92673 84.880658 \nL 302.150876 84.927963 \nL 302.373781 85.08735 \nL 302.595458 85.206364 \nL 302.81592 85.444319 \nL 303.03518 85.590406 \nL 304.642619 86.668251 \nL 305.164471 87.512232 \nL 306.389973 88.011476 \nL 306.690604 88.208584 \nL 306.889784 88.592106 \nL 307.579248 89.219541 \nL 308.064589 89.459571 \nL 308.257097 89.740714 \nL 308.448689 89.845787 \nL 309.764879 90.348539 \nL 310.041404 90.680861 \nL 310.407172 90.964228 \nL 310.588816 91.337038 \nL 311.396219 91.720126 \nL 311.837872 92.047697 \nL 312.448154 92.293761 \nL 312.620833 92.432096 \nL 312.792774 92.49921 \nL 312.963984 92.689966 \nL 313.049316 92.692365 \nL 313.304233 92.917837 \nL 314.225348 93.459069 \nL 315.448366 94.449906 \nL 315.768322 94.953341 \nL 317.177446 95.844985 \nL 317.407576 95.939887 \nL 317.712382 96.146984 \nL 317.93948 96.261619 \nL 318.09017 96.394021 \nL 318.315153 96.639943 \nL 318.83527 96.773116 \nL 319.056135 97.202827 \nL 319.494261 97.279684 \nL 319.855757 97.597302 \nL 320.071106 97.65638 \nL 320.214034 97.8794 \nL 320.498376 98.126997 \nL 320.639797 98.31057 \nL 320.710321 98.336136 \nL 320.851001 98.507666 \nL 320.99119 98.526683 \nL 321.130892 98.79223 \nL 322.501866 100.137273 \nL 322.703542 100.357771 \nL 323.037438 100.526693 \nL 323.368585 100.657703 \nL 324.857713 101.868856 \nL 325.047946 102.011577 \nL 325.17427 102.180093 \nL 325.55088 102.756088 \nL 325.737871 103.251379 \nL 326.109266 103.749865 \nL 326.232307 103.860892 \nL 326.660009 104.866738 \nL 327.203315 105.268479 \nL 327.263232 105.268709 \nL 327.620872 106.044757 \nL 327.739382 106.178559 \nL 328.03414 106.690325 \nL 328.268401 106.990878 \nL 328.559322 107.145054 \nL 328.790554 107.350672 \nL 329.020464 107.618888 \nL 329.192039 107.958388 \nL 329.533009 108.657538 \nL 329.814959 109.309776 \nL 331.087075 111.219803 \nL 331.250077 111.583733 \nL 331.520287 111.861958 \nL 331.842163 112.686204 \nL 331.948885 112.820844 \nL 332.530849 113.418564 \nL 332.688117 113.826177 \nL 333.465363 114.987396 \nL 333.670118 115.359192 \nL 333.823003 115.37704 \nL 333.975309 115.602411 \nL 334.227879 115.791613 \nL 334.428799 115.998731 \nL 334.678547 116.350989 \nL 335.074946 116.639121 \nL 335.418621 117.563426 \nL 335.565016 117.618693 \nL 335.71088 117.84837 \nL 337.094291 119.410808 \nL 337.187968 119.474548 \nL 337.42121 119.70463 \nL 337.745495 119.850338 \nL 337.883678 120.051786 \nL 338.067186 120.447424 \nL 338.386326 120.657083 \nL 338.522329 120.829383 \nL 338.702955 121.115427 \nL 338.882773 121.246356 \nL 339.106421 121.614252 \nL 339.328833 122.008187 \nL 339.505881 122.203465 \nL 339.770002 122.510749 \nL 340.0324 122.711393 \nL 340.422816 122.968378 \nL 340.595125 123.232093 \nL 340.852214 123.800708 \nL 340.894902 123.806559 \nL 341.065206 124.089056 \nL 341.613767 125.075906 \nL 341.947663 125.387313 \nL 342.113577 125.658604 \nL 342.237566 125.769611 \nL 342.648123 126.234064 \nL 342.688949 126.262352 \nL 342.851841 126.639169 \nL 342.93304 126.719616 \nL 342.973578 126.800401 \nL 343.135324 127.363311 \nL 343.175659 127.396425 \nL 343.496892 128.576932 \nL 343.736145 129.323347 \nL 343.934441 130.286545 \nL 344.210424 134.718115 \nL 344.328125 165.96 \nL 344.328125 165.96 \n\" clip-path=\"url(#p5b871016b4)\" style=\"fill: none; stroke: #1f77b4; stroke-width: 1.5; stroke-linecap: square\"/>\n   </g>\n   <g id=\"line2d_37\">\n    <path d=\"M 185.859049 173.52 \nL 185.859049 7.2 \n\" clip-path=\"url(#p5b871016b4)\" style=\"fill: none; stroke-dasharray: 5.55,2.4; stroke-dashoffset: 0; stroke: #ff7f0e; stroke-width: 1.5\"/>\n   </g>\n   <g id=\"line2d_38\">\n    <path d=\"M 213.747279 173.52 \nL 213.747279 7.2 \n\" clip-path=\"url(#p5b871016b4)\" style=\"fill: none; stroke-dasharray: 9.6,2.4,1.5,2.4; stroke-dashoffset: 0; stroke: #2ca02c; stroke-width: 1.5\"/>\n   </g>\n   <g id=\"line2d_39\">\n    <path d=\"M 51.378125 35.988443 \nL 358.278125 35.988443 \n\" clip-path=\"url(#p5b871016b4)\" style=\"fill: none; stroke-dasharray: 1.5,2.475; stroke-dashoffset: 0; stroke: #d62728; stroke-width: 1.5\"/>\n   </g>\n   <g id=\"patch_3\">\n    <path d=\"M 51.378125 173.52 \nL 51.378125 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 358.278125 173.52 \nL 358.278125 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 51.378125 173.52 \nL 358.278125 173.52 \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 51.378125 7.2 \nL 358.278125 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 58.378125 168.52 \nL 196.36875 168.52 \nQ 198.36875 168.52 198.36875 166.52 \nL 198.36875 123.485625 \nQ 198.36875 121.485625 196.36875 121.485625 \nL 58.378125 121.485625 \nQ 56.378125 121.485625 56.378125 123.485625 \nL 56.378125 166.52 \nQ 56.378125 168.52 58.378125 168.52 \nz\n\" style=\"fill: #ffffff; opacity: 0.8; stroke: #cccccc; stroke-linejoin: miter\"/>\n    </g>\n    <g id=\"line2d_40\">\n     <path d=\"M 60.378125 129.584063 \nL 70.378125 129.584063 \nL 80.378125 129.584063 \n\" style=\"fill: none; stroke-dasharray: 5.55,2.4; stroke-dashoffset: 0; stroke: #ff7f0e; stroke-width: 1.5\"/>\n    </g>\n    <g id=\"text_12\">\n     <!-- top-k, k=20 -->\n     <g transform=\"translate(88.378125 133.084063) scale(0.1 -0.1)\">\n      <defs>\n       <path id=\"DejaVuSans-2d\" d=\"M 313 2009 \nL 1997 2009 \nL 1997 1497 \nL 313 1497 \nL 313 2009 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-2c\" d=\"M 750 794 \nL 1409 794 \nL 1409 256 \nL 897 -744 \nL 494 -744 \nL 750 256 \nL 750 794 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-3d\" d=\"M 678 2906 \nL 4684 2906 \nL 4684 2381 \nL 678 2381 \nL 678 2906 \nz\nM 678 1631 \nL 4684 1631 \nL 4684 1100 \nL 678 1100 \nL 678 1631 \nz\n\" transform=\"scale(0.015625)\"/>\n      </defs>\n      <use xlink:href=\"#DejaVuSans-74\"/>\n      <use xlink:href=\"#DejaVuSans-6f\" transform=\"translate(39.208984 0)\"/>\n      <use xlink:href=\"#DejaVuSans-70\" transform=\"translate(100.390625 0)\"/>\n      <use xlink:href=\"#DejaVuSans-2d\" transform=\"translate(163.867188 0)\"/>\n      <use xlink:href=\"#DejaVuSans-6b\" transform=\"translate(199.951172 0)\"/>\n      <use xlink:href=\"#DejaVuSans-2c\" transform=\"translate(257.861328 0)\"/>\n      <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(289.648438 0)\"/>\n      <use xlink:href=\"#DejaVuSans-6b\" transform=\"translate(321.435547 0)\"/>\n      <use xlink:href=\"#DejaVuSans-3d\" transform=\"translate(379.345703 0)\"/>\n      <use xlink:href=\"#DejaVuSans-32\" transform=\"translate(463.134766 0)\"/>\n      <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(526.757812 0)\"/>\n     </g>\n    </g>\n    <g id=\"line2d_41\">\n     <path d=\"M 60.378125 144.262188 \nL 70.378125 144.262188 \nL 80.378125 144.262188 \n\" style=\"fill: none; stroke-dasharray: 9.6,2.4,1.5,2.4; stroke-dashoffset: 0; stroke: #2ca02c; stroke-width: 1.5\"/>\n    </g>\n    <g id=\"text_13\">\n     <!-- top-p=0.9: keep 40 -->\n     <g transform=\"translate(88.378125 147.762188) scale(0.1 -0.1)\">\n      <defs>\n       <path id=\"DejaVuSans-2e\" d=\"M 684 794 \nL 1344 794 \nL 1344 0 \nL 684 0 \nL 684 794 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-3a\" d=\"M 750 794 \nL 1409 794 \nL 1409 0 \nL 750 0 \nL 750 794 \nz\nM 750 3309 \nL 1409 3309 \nL 1409 2516 \nL 750 2516 \nL 750 3309 \nz\n\" transform=\"scale(0.015625)\"/>\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-74\"/>\n      <use xlink:href=\"#DejaVuSans-6f\" transform=\"translate(39.208984 0)\"/>\n      <use xlink:href=\"#DejaVuSans-70\" transform=\"translate(100.390625 0)\"/>\n      <use xlink:href=\"#DejaVuSans-2d\" transform=\"translate(163.867188 0)\"/>\n      <use xlink:href=\"#DejaVuSans-70\" transform=\"translate(199.951172 0)\"/>\n      <use xlink:href=\"#DejaVuSans-3d\" transform=\"translate(263.427734 0)\"/>\n      <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(347.216797 0)\"/>\n      <use xlink:href=\"#DejaVuSans-2e\" transform=\"translate(410.839844 0)\"/>\n      <use xlink:href=\"#DejaVuSans-39\" transform=\"translate(442.626953 0)\"/>\n      <use xlink:href=\"#DejaVuSans-3a\" transform=\"translate(506.25 0)\"/>\n      <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(539.941406 0)\"/>\n      <use xlink:href=\"#DejaVuSans-6b\" transform=\"translate(571.728516 0)\"/>\n      <use xlink:href=\"#DejaVuSans-65\" transform=\"translate(626.013672 0)\"/>\n      <use xlink:href=\"#DejaVuSans-65\" transform=\"translate(687.537109 0)\"/>\n      <use xlink:href=\"#DejaVuSans-70\" transform=\"translate(749.060547 0)\"/>\n      <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(812.537109 0)\"/>\n      <use xlink:href=\"#DejaVuSans-34\" transform=\"translate(844.324219 0)\"/>\n      <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(907.947266 0)\"/>\n     </g>\n    </g>\n    <g id=\"line2d_42\">\n     <path d=\"M 60.378125 158.940313 \nL 70.378125 158.940313 \nL 80.378125 158.940313 \n\" style=\"fill: none; stroke-dasharray: 1.5,2.475; stroke-dashoffset: 0; stroke: #d62728; stroke-width: 1.5\"/>\n    </g>\n    <g id=\"text_14\">\n     <!-- min-p=0.05: keep 12 -->\n     <g transform=\"translate(88.378125 162.440313) 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      </defs>\n      <use xlink:href=\"#DejaVuSans-6d\"/>\n      <use xlink:href=\"#DejaVuSans-69\" transform=\"translate(97.412109 0)\"/>\n      <use xlink:href=\"#DejaVuSans-6e\" transform=\"translate(125.195312 0)\"/>\n      <use xlink:href=\"#DejaVuSans-2d\" transform=\"translate(188.574219 0)\"/>\n      <use xlink:href=\"#DejaVuSans-70\" transform=\"translate(224.658203 0)\"/>\n      <use xlink:href=\"#DejaVuSans-3d\" transform=\"translate(288.134766 0)\"/>\n      <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(371.923828 0)\"/>\n      <use xlink:href=\"#DejaVuSans-2e\" transform=\"translate(435.546875 0)\"/>\n      <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(467.333984 0)\"/>\n      <use xlink:href=\"#DejaVuSans-35\" transform=\"translate(530.957031 0)\"/>\n      <use xlink:href=\"#DejaVuSans-3a\" transform=\"translate(594.580078 0)\"/>\n      <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(628.271484 0)\"/>\n      <use xlink:href=\"#DejaVuSans-6b\" transform=\"translate(660.058594 0)\"/>\n      <use xlink:href=\"#DejaVuSans-65\" transform=\"translate(714.34375 0)\"/>\n      <use xlink:href=\"#DejaVuSans-65\" transform=\"translate(775.867188 0)\"/>\n      <use xlink:href=\"#DejaVuSans-70\" transform=\"translate(837.390625 0)\"/>\n      <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(900.867188 0)\"/>\n      <use xlink:href=\"#DejaVuSans-31\" transform=\"translate(932.654297 0)\"/>\n      <use xlink:href=\"#DejaVuSans-32\" transform=\"translate(996.277344 0)\"/>\n     </g>\n    </g>\n   </g>\n  </g>\n </g>\n <defs>\n  <clipPath id=\"p5b871016b4\">\n   <rect x=\"51.378125\" y=\"7.2\" width=\"306.9\" height=\"166.32\"/>\n  </clipPath>\n </defs>\n</svg>\n"
     },
     "metadata": {}
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=decoding-md-11 fw=all -->\n",
    "\n",
    "The adaptivity argument is now checkable: apply the same dials after two\n",
    "different prefixes and compare the kept sets. Top-$k$ keeps twenty tokens\n",
    "regardless. The other two rules track the model's confidence (how\n",
    "confident it is after a given prefix varies from training run to training\n",
    "run; the printed top probability tells you what this one thinks): the\n",
    "more certain the model, the smaller the top-$p$ and min-$p$ sets tend to\n",
    "be. That is the behavior we wanted: strict where the model is sure,\n",
    "permissive where it is genuinely uncertain."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "decoding-one-distribution-three-cutoffs-2"
   },
   "source": [
    "for text in ('the time traveller', 'it seemed to me that'):\n",
    "    probs = next_probs(text)\n",
    "    n_p = int((np.cumsum(probs) < 0.9).sum()) + 1\n",
    "    n_m = int((probs >= 0.05 * probs[0]).sum())\n",
    "    print(f'{text!r}: top prob {probs[0]:.2f}, top-k keeps 20, '\n",
    "          f'top-p keeps {n_p}, min-p keeps {n_m}')"
   ],
   "execution_count": 13,
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "'the time traveller': top prob 0.28, top-k keeps 20, top-p keeps 40, min-p keeps 12\n'it seemed to me that': top prob 0.14, top-k keeps 20, top-p keeps 56, min-p keeps 20\n"
     ]
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=decoding-md-12 fw=all -->\n",
    "\n",
    "### The Same Prefix Under Every Strategy\n",
    "\n",
    "Time to hear the dials rather than plot them. First, temperature alone: at\n",
    "$T = 0.5$ the text hugs the model's mode and inherits some of greedy's\n",
    "repetitiveness, at $T = 1$ it is diverse but occasionally derails into\n",
    "tail nonsense, already reaching for tokens whose bytes no longer decode to\n",
    "valid text (the replacement characters below), and at $T = 2$ the flattened\n",
    "distribution produces gibberish outright."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "decoding-the-same-prefix-under-every-strategy-1"
   },
   "source": [
    "prefix = data.tokenizer.encode('the time traveller')\n",
    "for T in (0.5, 1.0, 2.0):\n",
    "    out = generate(step_fn, prefix, 50, strategy='sample', temperature=T,\n",
    "                   rng=np.random.default_rng(0))\n",
    "    print(f'T={T}: {data.tokenizer.decode(out)!r}')"
   ],
   "execution_count": 14,
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "T=0.5: 'the time traveller I had come into my hand. I thought, for a small shadows. I was a vast array I that my tanger. I felt a valthyoins. Indeed, and sat'\n"
     ]
    },
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "T=1.0: 'the time travelleriveley. (ason b another queuge and ta-haoces I scattered� lirial swific earlyt. Oittly comfort. I should a shome'\n"
     ]
    },
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "T=2.0: \"the time traveller from lesseres� pl her long At perhaps a ruin necileking my to myself, incenseace from<pad>\\x14ren neous,'edolog surtingideitt incingsence had part lastplacx toac\"\n"
     ]
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=decoding-md-13 fw=all -->\n",
    "\n",
    "Finally, the whole menu on one prefix, with the distinct-3 diversity score\n",
    "alongside. Greedy is deterministic and generic, when not stuck in a loop\n",
    "outright; pure sampling is diverse but erratic; the truncated samplers\n",
    "occupy the useful middle, keeping the\n",
    "diversity that maximization destroyed (their distinct-3 stays near 1)\n",
    "while cutting the tail that pure sampling trips over. This is why some\n",
    "combination of temperature with top-$p$ or min-$p$ is the default in\n",
    "essentially every deployed text generator today."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "decoding-the-same-prefix-under-every-strategy-2"
   },
   "source": [
    "strategies = {'greedy': dict(strategy='greedy'),\n",
    "              'T=1.0': dict(strategy='sample'),\n",
    "              'top-k': dict(strategy='sample', k=20),\n",
    "              'top-p': dict(strategy='sample', p=0.9),\n",
    "              'min-p': dict(strategy='sample', min_p=0.05)}\n",
    "for name, s in strategies.items():\n",
    "    out = generate(step_fn, prefix, 50, rng=np.random.default_rng(0), **s)\n",
    "    print(f'{name:>7} (distinct-3 {distinct(out[len(prefix):]):.2f}): '\n",
    "          f'{data.tokenizer.decode(out)!r}')"
   ],
   "execution_count": 15,
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      " greedy (distinct-3 0.35): 'the time traveller I had come into the future. I was a vast array of a vast array of a vast array of a vast array of a vast array of a vast arr'\n"
     ]
    },
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "  T=1.0 (distinct-3 1.00): 'the time travelleriveley. (ason b another queuge and ta-haoces I scattered� lirial swific earlyt. Oittly comfort. I should a shome'\n  top-k (distinct-3 1.00): \"the time traveller by moderonke at it for any more. 'I supposit and course. It is this lit a civiliz. I felt asked in avolution. Instance of n\"\n"
     ]
    },
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "  top-p (distinct-3 1.00): \"the time traveller of a cigarened intoansites on ekingic were direain of the Time Traveller, however, catodous feet. 'Halloations togethering at elects of any kind r\"\n"
     ]
    },
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "  min-p (distinct-3 1.00): 'the time traveller-sidered that, was the chinased me. And there are of our own time. What it was this yet railway to the shaday very. One nothing had flowers. I do'\n"
     ]
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=decoding-md-14 fw=all -->\n",
    "\n",
    "Our small model cannot make any of these continuations *good*; what it\n",
    "makes visible is that they are *different*, in exactly the directions the\n",
    "theory predicts, and the differences only grow with model quality. The\n",
    "same dials, at the same typical settings, ship in every large language\n",
    "model API you will ever call.\n",
    "\n",
    "## Evaluation and Efficiency\n",
    "\n",
    "### Evaluating Generated Text\n",
    "\n",
    "How would we decide, beyond eyeballing, which strategy wrote better text?\n",
    "Perplexity, our faithful metric so far, is of surprisingly little help. It\n",
    "evaluates the *model*: how well the predicted conditionals compress text\n",
    "that humans actually wrote. It says nothing about any particular sample,\n",
    "and scoring a sample by its own model probability would just reinvent\n",
    "maximization, crowning the repetitive beam-search output we have already\n",
    "rejected. A generation strategy is not better because its output is more\n",
    "probable; the whole point of the sampling family is to deviate from the\n",
    "mode on purpose.\n",
    "\n",
    "The honest target is human judgment: can readers distinguish the model's\n",
    "text from text people wrote, and which do they prefer? Alongside such\n",
    "judgments, automated proxies catch specific failure modes: diversity\n",
    "statistics such as our distinct-3 flag degeneration, and repetition and\n",
    "length statistics serve as cheap regression tests for a decoding stack.\n",
    "Tasks with a reference answer are easier to score; the next chapter\n",
    "evaluates translations by their overlap with reference translations, the\n",
    "setting where maximization and automatic metrics agree best.\n",
    "\n",
    "At the frontier, evaluation has become a discipline of its own. Modern\n",
    "practice ranks systems by collecting human preferences between paired\n",
    "responses, and increasingly by asking a strong language model to play the\n",
    "judge, with well-documented blind spots of its own. We return to\n",
    "generation-quality evaluation in the context of large language models\n",
    "later in the book; for now, the operational summary is that perplexity\n",
    "selects the model, while humans, or proxies for them, select the decoding\n",
    "strategy.\n",
    "\n",
    "### The Cost of Generation\n",
    "\n",
    "One last practical concern, and a preview. Our `step_fn` re-runs the\n",
    "network over the whole prefix for every token generated, so a $T$-token\n",
    "continuation costs $\\mathcal{O}(T^2)$ cell updates, and generation is\n",
    "inherently *sequential*: unlike training, where all time steps of a known\n",
    "sequence are processed together, token $t + 1$ cannot be scored before\n",
    "token $t$ exists. For a recurrent network the quadratic part is pure\n",
    "waste: the hidden state already summarizes the prefix, so carrying it\n",
    "forward (as `predict` in that section did) makes each new\n",
    "token cost $\\mathcal{O}(1)$, independent of everything that came before.\n",
    "That constant-memory, constant-time-per-token property is a defining\n",
    "virtue of recurrence, and that section builds architectures\n",
    "that keep it at much higher quality. The sequential bottleneck, meanwhile,\n",
    "has spawned a toolbox of its own, most prominently *speculative decoding*,\n",
    "where a small draft model proposes several tokens and the large model\n",
    "verifies them in one parallel pass; we return to serving-time efficiency\n",
    "when we meet large language models.\n",
    "\n",
    "## Summary\n",
    "\n",
    "Decoding turns a language model's conditionals into sequences, and the\n",
    "choice of strategy is a modeling decision in its own right. Maximization\n",
    "targets the most probable output: greedy decoding takes the local argmax\n",
    "and is myopic; beam search keeps the $k$ best prefixes under the\n",
    "length-normalized score the equation and fixes myopia at\n",
    "$k$ times the cost. Maximization suits tasks with an essentially unique\n",
    "answer, but for open-ended text its target is wrong: the argmax of a good\n",
    "model is repetitive and dull, and a stronger search only finds it faster.\n",
    "Sampling draws from the model's distribution, reshaped by temperature\n",
    "the equation and truncated by top-$k$ (fixed count), top-$p$\n",
    "(fixed mass), or min-$p$ (fixed fraction of the top probability, hence\n",
    "adaptive to the model's confidence). Perplexity evaluates the model rather\n",
    "than its samples; judging generated text requires humans or proxies for\n",
    "them. Finally, generating naively re-runs the model over a growing prefix\n",
    "for every new token; a recurrent state cuts this to constant work per\n",
    "token, a property the next chapter's architectures inherit.\n",
    "\n",
    "## Exercises\n",
    "\n",
    "1. Implement a *repetition penalty*: in `sample_next`, divide the\n",
    "   probability of every token already present in the generated sequence by\n",
    "   a constant $\\theta > 1$ before truncation (you will need to thread the\n",
    "   generated ids through). Decode greedily with $\\theta = 1.2$. Does it\n",
    "   cure the loops? What legitimate text does it punish?\n",
    "1. In the figure, could the best candidate after three\n",
    "   steps (by cumulative probability) fail to contain the best candidate\n",
    "   after two steps as its prefix? Construct explicit probabilities or\n",
    "   prove it impossible. What does your answer imply about how beam search\n",
    "   can miss the true argmax sequence?\n",
    "1. Can exhaustive search be seen as a special case of beam search? For\n",
    "   which beam size do the two coincide?\n",
    "1. Add an `eos_id` to the beam-search demonstration (for instance the\n",
    "   token id of a newline) and vary $\\alpha \\in \\{0, 0.75, 1.5\\}$ at\n",
    "   $k = 4$. Compare the lengths and scores of the winning candidates and\n",
    "   explain the trend using the equation.\n",
    "1. At temperature $T = 1.5$, tune $p$ for top-$p$ and $p_{\\min}$ for\n",
    "   min-$p$ until each just keeps continuations coherent. Which setting\n",
    "   preserves more diversity (distinct-3) at matched coherence? Compare\n",
    "   your finding with those of @Nguyen.Baker.Neo.ea.2025 .\n",
    "1. Once you have trained the sequence-to-sequence translation model of the\n",
    "   next chapter, decode it with `beam_search` for\n",
    "   $k \\in \\{1, 2, 4, 8, 16\\}$. Measure translation quality and decoding\n",
    "   time as functions of $k$. Where does quality peak, and why does it not\n",
    "   keep improving?\n",
    "1. Constrained sampling: ban a set of tokens (say, every token whose text\n",
    "   contains the letter \"e\") by masking their logits to $-\\infty$ before\n",
    "   calling `sample_next`. Why is banning a *word* harder than banning a\n",
    "   token under a subword tokenizer? What can go wrong at the boundary\n",
    "   between two tokens?\n",
    "\n",
    "[Discussions](https://d2l.discourse.group/t/338)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "name": "d2l-mxnet",
   "display_name": "d2l (MXNet)",
   "language": "python"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
