{
 "cells": [
  {
   "cell_type": "raw",
   "metadata": {},
   "source": [
    "---\n",
    "execute:\n",
    "  enabled: false\n",
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=encoders-decoders-md-1 fw=all -->\n",
    "\n",
    "# Encoders, Decoders, and Cross-Attention\n",
    "\n",
    "The GPT of that section made one architectural commitment beyond\n",
    "stacking blocks: the causal mask. That mask is what lets the model factor a\n",
    "joint distribution into next-token predictions, and it is also a\n",
    "restriction: every representation is built from the left half of its\n",
    "context only. This section treats the mask as the design variable it is.\n",
    "Removing it gives an *encoder*, a model that reads in both directions and\n",
    "excels at representing rather than generating; combining a masked stack\n",
    "with an unmasked one, joined by the cross-attention of\n",
    "that section, gives the *encoder--decoder* that\n",
    "transformers started as [@Vaswani.Shazeer.Parmar.ea.2017]. We build\n",
    "both from the same `d2l.TransformerBlock` as always, watch a\n",
    "cross-attention map reproduce an alignment we know in advance, and then\n",
    "push cross-attention past sequence-to-sequence entirely: its queries need\n",
    "not come from a sequence at all, and making them learned parameters turns\n",
    "attention into a general interface between fixed-size computation and\n",
    "variable-size data — the Perceiver idea, alive today inside most\n",
    "vision--language models."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "encoders-decoders-encoders-decoders-and-cross-attention"
   },
   "source": [
    "%matplotlib inline\n",
    "from d2l import torch as d2l\n",
    "import time\n",
    "import torch\n",
    "from torch import nn\n",
    "from torch.nn import functional as F"
   ],
   "execution_count": 1,
   "outputs": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=encoders-decoders-md-2 fw=all -->\n",
    "\n",
    "## Three Wirings of One Block\n",
    "\n",
    "A transformer block maps a sequence of $d$-dimensional vectors to a\n",
    "sequence of the same shape, and it leaves two questions open: which\n",
    "positions may attend to which, and where the keys and values come from.\n",
    "Three answers cover essentially every deployed transformer, and\n",
    "the figure draws them in the convention we will use for\n",
    "every attention map in this section — queries down the rows, keys along\n",
    "the columns.\n",
    "\n",
    "![The three wirings and their attention patterns (query position runs downward, key position rightward; a filled cell means the query may attend to that key). Encoder-only: every token attends to every token. Decoder-only: each token attends only to itself and its past. Encoder--decoder: the source attends to itself bidirectionally, while each target token attends to the full source through cross-attention and to its own past causally.](../img/mdl-transformers-three-wirings.svg)\n",
    "\n",
    "**Encoder-only.** Drop the mask. Every token attends to every other, so\n",
    "each output vector summarizes the *whole* input as seen from its position.\n",
    "Such a model does not directly implement the left-to-right autoregressive\n",
    "factorization (with the future visible, next-token prediction is a copying\n",
    "exercise — though masked models can still be decoded by iterative\n",
    "re-masking, the idea text diffusion models develop), but it is the\n",
    "strongest way to *represent* an input, and one\n",
    "representation per token is exactly what classification, retrieval, and\n",
    "tagging consume. BERT is this wiring pretrained on text\n",
    "[@Devlin.Chang.Lee.ea.2018]; the vision transformer of\n",
    "that section is the same wiring over image patches.\n",
    "\n",
    "**Decoder-only.** Keep the causal mask everywhere: the GPT of\n",
    "that section, in two sentences. Each token predicts its successor,\n",
    "generation is the training objective run forward, and one stack serves\n",
    "both understanding and production. We do not rebuild it here; it appears\n",
    "in the figure as the pattern the other two are measured\n",
    "against.\n",
    "\n",
    "**Encoder--decoder.** The original transformer\n",
    "[@Vaswani.Shazeer.Parmar.ea.2017] combines the two: a bidirectional\n",
    "encoder reads the source sequence, and a causal decoder generates the\n",
    "target while *cross-attending* into the encoder's output — queries from\n",
    "the target stream, keys and values from the source, the second wiring of\n",
    "that section. The pattern in\n",
    "the figure shows the division: a full square for the\n",
    "source, a full rectangle for target-to-source cross-attention, a triangle\n",
    "for the target's own past. Machine translation was the founding\n",
    "application; T5 pretrained the architecture on span reconstruction and\n",
    "recast a broad family of tasks as text-to-text [@raffel2020exploring],\n",
    "BART on denoising corrupted text [@lewis2019bart].\n",
    "\n",
    "The rest of this section builds the two wirings that that section did\n",
    "not, in order.\n",
    "\n",
    "## An Encoder: Predicting from Both Sides\n",
    "\n",
    "### A Bidirectional Encoder in a Dozen Lines\n",
    "\n",
    "The encoder differs from the `CharLM` of that section\n",
    "by a single argument: we pass no `valid_lens`, so nothing is masked.\n",
    "Positions are still the model's job, since attention is permutation\n",
    "equivariant (that section), so a learned position\n",
    "table stays."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "encoders-decoders-a-bidirectional-encoder-in-a-dozen-lines"
   },
   "source": [
    "class TransformerEncoder(nn.Module):\n",
    "    \"\"\"Bidirectional encoder: embeddings plus unmasked pre-norm blocks.\"\"\"\n",
    "    def __init__(self, vocab_size, num_hiddens=128, num_heads=4, num_blks=4,\n",
    "                 max_len=64):\n",
    "        super().__init__()\n",
    "        self.token_emb = nn.Embedding(vocab_size, num_hiddens)\n",
    "        self.pos_emb = nn.Embedding(max_len, num_hiddens)\n",
    "        for emb in (self.token_emb, self.pos_emb):\n",
    "            nn.init.normal_(emb.weight, std=0.02)\n",
    "        self.blks = nn.ModuleList([\n",
    "            d2l.TransformerBlock(num_hiddens, num_heads)\n",
    "            for _ in range(num_blks)])\n",
    "        self.norm = nn.RMSNorm(num_hiddens)\n",
    "\n",
    "    def forward(self, X):\n",
    "        H = self.token_emb(X) + self.pos_emb(\n",
    "            torch.arange(X.shape[1], device=X.device))\n",
    "        for blk in self.blks:\n",
    "            H = blk(H)  # no valid_lens: every token attends everywhere\n",
    "        return self.norm(H)"
   ],
   "execution_count": 2,
   "outputs": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=encoders-decoders-md-3 fw=all -->\n",
    "\n",
    "### The Masked-Token Objective\n",
    "\n",
    "What should this model train on? Not next-token prediction: with the\n",
    "future visible, position $t$ can read token $t+1$ directly, and the loss\n",
    "collapses without teaching anything. The objective must hide what it asks\n",
    "for. *Masked language modeling* [@Devlin.Chang.Lee.ea.2018] replaces\n",
    "a random subset of tokens with a special `<mask>` symbol and asks the\n",
    "model to reconstruct them from everything that remains:\n",
    "\n",
    "$$\n",
    "\\max \\; \\sum_{t \\in \\mathcal{M}} \\log p\\left(x_t \\mid \\mathbf{x}_{\\setminus \\mathcal{M}}\\right),\n",
    "$$\n",
    "\n",
    "where $\\mathcal{M}$ is the masked set. Prediction at a masked position\n",
    "draws on context from *both* sides, which is the point of dropping the\n",
    "mask in the first place. We train the recipe in miniature on the\n",
    "character-level Time Machine corpus of that section,\n",
    "masking 15% of characters per window and giving `<mask>` one extra\n",
    "embedding row; the tied output head is the same trick as in\n",
    "that section."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "encoders-decoders-the-masked-token-objective"
   },
   "source": [
    "data = d2l.TimeMachine(batch_size=64, num_steps=64, tokenization='char',\n",
    "                       num_train=100000, num_val=3000)\n",
    "MASK = len(data.vocab)  # id of the extra <mask> embedding row\n",
    "\n",
    "def mask_tokens(X, p=0.15):\n",
    "    mask = torch.rand(X.shape, device=X.device) < p\n",
    "    return torch.where(mask, torch.full_like(X, MASK), X), mask\n",
    "\n",
    "torch.manual_seed(0)\n",
    "device = d2l.try_gpu()\n",
    "model = TransformerEncoder(len(data.vocab) + 1).to(device)\n",
    "optimizer = torch.optim.AdamW(model.parameters(), lr=1e-3,\n",
    "                              weight_decay=0.0)\n",
    "losses, step = [], 0\n",
    "while step < 2000:\n",
    "    for X, _ in data.train_dataloader():\n",
    "        X = X.to(device)\n",
    "        Xm, mask = mask_tokens(X)\n",
    "        logits = F.linear(model(Xm), model.token_emb.weight)\n",
    "        loss = F.cross_entropy(logits[mask], X[mask])\n",
    "        optimizer.zero_grad()\n",
    "        loss.backward()\n",
    "        optimizer.step()\n",
    "        losses.append(loss.item())\n",
    "        step += 1\n",
    "        if step >= 2000:\n",
    "            break\n",
    "print('masked loss at step 500/1000/2000: ' + '/'.join(\n",
    "    f'{sum(losses[k-50:k]) / 50:.2f}' for k in (500, 1000, 2000)))"
   ],
   "execution_count": 3,
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "masked loss at step 500/1000/2000: 1.92/1.35/1.08\n"
     ]
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=encoders-decoders-md-4 fw=all -->\n",
    "\n",
    "A minute of training brings the masked loss to about one nat and the\n",
    "masked-character accuracy to roughly 65% — against a 28-way vocabulary\n",
    "whose unigram entropy alone is $2.83$ nats. More interesting than the\n",
    "average is *where* the model earns it.\n",
    "\n",
    "### What the Second Side Is Worth\n",
    "\n",
    "Our windows are 64 characters long, and that finiteness builds a\n",
    "comparison into every batch: a masked character in the interior has\n",
    "context on both sides, while one at position 0 or 63 sees only one side\n",
    "— the final position is exactly the situation a causal language model is\n",
    "in at every step. Same model, same objective, so binning the validation\n",
    "loss by position measures directly what the second side of the context is\n",
    "worth."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "encoders-decoders-what-the-second-side-is-worth-1"
   },
   "source": [
    "model.eval()\n",
    "pos_loss = torch.zeros(64, device=device)\n",
    "pos_cnt = torch.zeros(64, device=device)\n",
    "correct = total = 0\n",
    "torch.manual_seed(1)\n",
    "with torch.no_grad():\n",
    "    for rep in range(5):\n",
    "        for X, _ in data.val_dataloader():\n",
    "            X = X.to(device)\n",
    "            Xm, mask = mask_tokens(X)\n",
    "            logits = F.linear(model(Xm), model.token_emb.weight)\n",
    "            loss = F.cross_entropy(logits.transpose(1, 2), X,\n",
    "                                   reduction='none')\n",
    "            pos_loss += (loss * mask).sum(0)\n",
    "            pos_cnt += mask.sum(0)\n",
    "            correct += (logits.argmax(-1)[mask] == X[mask]).sum().item()\n",
    "            total += int(mask.sum())\n",
    "pos_loss = (pos_loss / pos_cnt).cpu()\n",
    "print(f'masked accuracy {correct / total:.2f}')\n",
    "print(f'loss at position 0: {pos_loss[0]:.2f}, at position 63: '\n",
    "      f'{pos_loss[63]:.2f}, interior mean: {pos_loss[16:48].mean():.2f}')\n",
    "d2l.plot(torch.arange(64), pos_loss, 'position in the window',\n",
    "         'masked loss')"
   ],
   "execution_count": 4,
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "masked accuracy 0.65\nloss at position 0: 2.06, at position 63: 2.08, interior mean: 1.10\n"
     ]
    },
    {
     "output_type": "display_data",
     "data": {
      "image/svg+xml": "<?xml version=\"1.0\" encoding=\"utf-8\" standalone=\"no\"?>\n<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n  \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n<svg xmlns:xlink=\"http://www.w3.org/1999/xlink\" width=\"246.28125pt\" height=\"183.35625pt\" viewBox=\"0 0 246.28125 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-19T14:04:24.787303</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 246.28125 183.35625 \nL 246.28125 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 43.78125 145.8 \nL 239.08125 145.8 \nL 239.08125 7.2 \nL 43.78125 7.2 \nz\n\" style=\"fill: #ffffff\"/>\n   </g>\n   <g id=\"matplotlib.axis_1\">\n    <g id=\"xtick_1\">\n     <g id=\"line2d_1\">\n      <path d=\"M 52.658523 145.8 \nL 52.658523 7.2 \n\" clip-path=\"url(#pe230d3eb36)\" style=\"fill: none; stroke: #b0b0b0; stroke-width: 0.8; stroke-linecap: square\"/>\n     </g>\n     <g id=\"line2d_2\">\n      <defs>\n       <path id=\"m2109cdd002\" d=\"M 0 0 \nL 0 3.5 \n\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </defs>\n      <g>\n       <use xlink:href=\"#m2109cdd002\" x=\"52.658523\" 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(49.477273 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_3\">\n      <path d=\"M 109.022159 145.8 \nL 109.022159 7.2 \n\" clip-path=\"url(#pe230d3eb36)\" style=\"fill: none; stroke: #b0b0b0; stroke-width: 0.8; stroke-linecap: square\"/>\n     </g>\n     <g id=\"line2d_4\">\n      <g>\n       <use xlink:href=\"#m2109cdd002\" x=\"109.022159\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_2\">\n      <!-- 20 -->\n      <g transform=\"translate(102.659659 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       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(63.623047 0)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_3\">\n     <g id=\"line2d_5\">\n      <path d=\"M 165.385795 145.8 \nL 165.385795 7.2 \n\" clip-path=\"url(#pe230d3eb36)\" style=\"fill: none; stroke: #b0b0b0; stroke-width: 0.8; stroke-linecap: square\"/>\n     </g>\n     <g id=\"line2d_6\">\n      <g>\n       <use xlink:href=\"#m2109cdd002\" x=\"165.385795\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_3\">\n      <!-- 40 -->\n      <g transform=\"translate(159.023295 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       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(63.623047 0)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_4\">\n     <g id=\"line2d_7\">\n      <path d=\"M 221.749432 145.8 \nL 221.749432 7.2 \n\" clip-path=\"url(#pe230d3eb36)\" style=\"fill: none; stroke: #b0b0b0; stroke-width: 0.8; stroke-linecap: square\"/>\n     </g>\n     <g id=\"line2d_8\">\n      <g>\n       <use xlink:href=\"#m2109cdd002\" x=\"221.749432\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_4\">\n      <!-- 60 -->\n      <g transform=\"translate(215.386932 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       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(63.623047 0)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"text_5\">\n     <!-- position in the window -->\n     <g transform=\"translate(85.126563 174.076563) 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-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-73\" d=\"M 2834 3397 \nL 2834 2853 \nQ 2591 2978 2328 3040 \nQ 2066 3103 1784 3103 \nQ 1356 3103 1142 2972 \nQ 928 2841 928 2578 \nQ 928 2378 1081 2264 \nQ 1234 2150 1697 2047 \nL 1894 2003 \nQ 2506 1872 2764 1633 \nQ 3022 1394 3022 966 \nQ 3022 478 2636 193 \nQ 2250 -91 1575 -91 \nQ 1294 -91 989 -36 \nQ 684 19 347 128 \nL 347 722 \nQ 666 556 975 473 \nQ 1284 391 1588 391 \nQ 1994 391 2212 530 \nQ 2431 669 2431 922 \nQ 2431 1156 2273 1281 \nQ 2116 1406 1581 1522 \nL 1381 1569 \nQ 847 1681 609 1914 \nQ 372 2147 372 2553 \nQ 372 3047 722 3315 \nQ 1072 3584 1716 3584 \nQ 2034 3584 2315 3537 \nQ 2597 3491 2834 3397 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-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-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-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-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       <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-77\" d=\"M 269 3500 \nL 844 3500 \nL 1563 769 \nL 2278 3500 \nL 2956 3500 \nL 3675 769 \nL 4391 3500 \nL 4966 3500 \nL 4050 0 \nL 3372 0 \nL 2619 2869 \nL 1863 0 \nL 1184 0 \nL 269 3500 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-64\" d=\"M 2906 2969 \nL 2906 4863 \nL 3481 4863 \nL 3481 0 \nL 2906 0 \nL 2906 525 \nQ 2725 213 2448 61 \nQ 2172 -91 1784 -91 \nQ 1150 -91 751 415 \nQ 353 922 353 1747 \nQ 353 2572 751 3078 \nQ 1150 3584 1784 3584 \nQ 2172 3584 2448 3432 \nQ 2725 3281 2906 2969 \nz\nM 947 1747 \nQ 947 1113 1208 752 \nQ 1469 391 1925 391 \nQ 2381 391 2643 752 \nQ 2906 1113 2906 1747 \nQ 2906 2381 2643 2742 \nQ 2381 3103 1925 3103 \nQ 1469 3103 1208 2742 \nQ 947 2381 947 1747 \nz\n\" transform=\"scale(0.015625)\"/>\n      </defs>\n      <use xlink:href=\"#DejaVuSans-70\"/>\n      <use xlink:href=\"#DejaVuSans-6f\" transform=\"translate(63.476562 0)\"/>\n      <use xlink:href=\"#DejaVuSans-73\" transform=\"translate(124.658203 0)\"/>\n      <use xlink:href=\"#DejaVuSans-69\" transform=\"translate(176.757812 0)\"/>\n      <use xlink:href=\"#DejaVuSans-74\" transform=\"translate(204.541016 0)\"/>\n      <use xlink:href=\"#DejaVuSans-69\" transform=\"translate(243.75 0)\"/>\n      <use xlink:href=\"#DejaVuSans-6f\" transform=\"translate(271.533203 0)\"/>\n      <use xlink:href=\"#DejaVuSans-6e\" transform=\"translate(332.714844 0)\"/>\n      <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(396.09375 0)\"/>\n      <use xlink:href=\"#DejaVuSans-69\" transform=\"translate(427.880859 0)\"/>\n      <use xlink:href=\"#DejaVuSans-6e\" transform=\"translate(455.664062 0)\"/>\n      <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(519.042969 0)\"/>\n      <use xlink:href=\"#DejaVuSans-74\" transform=\"translate(550.830078 0)\"/>\n      <use xlink:href=\"#DejaVuSans-68\" transform=\"translate(590.039062 0)\"/>\n      <use xlink:href=\"#DejaVuSans-65\" transform=\"translate(653.417969 0)\"/>\n      <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(714.941406 0)\"/>\n      <use xlink:href=\"#DejaVuSans-77\" transform=\"translate(746.728516 0)\"/>\n      <use xlink:href=\"#DejaVuSans-69\" transform=\"translate(828.515625 0)\"/>\n      <use xlink:href=\"#DejaVuSans-6e\" transform=\"translate(856.298828 0)\"/>\n      <use xlink:href=\"#DejaVuSans-64\" transform=\"translate(919.677734 0)\"/>\n      <use xlink:href=\"#DejaVuSans-6f\" transform=\"translate(983.154297 0)\"/>\n      <use xlink:href=\"#DejaVuSans-77\" transform=\"translate(1044.335938 0)\"/>\n     </g>\n    </g>\n   </g>\n   <g id=\"matplotlib.axis_2\">\n    <g id=\"ytick_1\">\n     <g id=\"line2d_9\">\n      <path d=\"M 43.78125 144.484984 \nL 239.08125 144.484984 \n\" clip-path=\"url(#pe230d3eb36)\" style=\"fill: none; stroke: #b0b0b0; stroke-width: 0.8; stroke-linecap: square\"/>\n     </g>\n     <g id=\"line2d_10\">\n      <defs>\n       <path id=\"mba2db8896a\" d=\"M 0 0 \nL -3.5 0 \n\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </defs>\n      <g>\n       <use xlink:href=\"#mba2db8896a\" x=\"43.78125\" y=\"144.484984\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_6\">\n      <!-- 1.0 -->\n      <g transform=\"translate(20.878125 148.284203) 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-2e\" d=\"M 684 794 \nL 1344 794 \nL 1344 0 \nL 684 0 \nL 684 794 \nz\n\" transform=\"scale(0.015625)\"/>\n       </defs>\n       <use xlink:href=\"#DejaVuSans-31\"/>\n       <use xlink:href=\"#DejaVuSans-2e\" transform=\"translate(63.623047 0)\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(95.410156 0)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_2\">\n     <g id=\"line2d_11\">\n      <path d=\"M 43.78125 120.238492 \nL 239.08125 120.238492 \n\" clip-path=\"url(#pe230d3eb36)\" style=\"fill: none; stroke: #b0b0b0; stroke-width: 0.8; stroke-linecap: square\"/>\n     </g>\n     <g id=\"line2d_12\">\n      <g>\n       <use xlink:href=\"#mba2db8896a\" x=\"43.78125\" y=\"120.238492\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_7\">\n      <!-- 1.2 -->\n      <g transform=\"translate(20.878125 124.03771) scale(0.1 -0.1)\">\n       <use xlink:href=\"#DejaVuSans-31\"/>\n       <use xlink:href=\"#DejaVuSans-2e\" transform=\"translate(63.623047 0)\"/>\n       <use xlink:href=\"#DejaVuSans-32\" transform=\"translate(95.410156 0)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_3\">\n     <g id=\"line2d_13\">\n      <path d=\"M 43.78125 95.991999 \nL 239.08125 95.991999 \n\" clip-path=\"url(#pe230d3eb36)\" style=\"fill: none; stroke: #b0b0b0; stroke-width: 0.8; stroke-linecap: square\"/>\n     </g>\n     <g id=\"line2d_14\">\n      <g>\n       <use xlink:href=\"#mba2db8896a\" x=\"43.78125\" y=\"95.991999\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_8\">\n      <!-- 1.4 -->\n      <g transform=\"translate(20.878125 99.791218) scale(0.1 -0.1)\">\n       <use xlink:href=\"#DejaVuSans-31\"/>\n       <use xlink:href=\"#DejaVuSans-2e\" transform=\"translate(63.623047 0)\"/>\n       <use xlink:href=\"#DejaVuSans-34\" transform=\"translate(95.410156 0)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_4\">\n     <g id=\"line2d_15\">\n      <path d=\"M 43.78125 71.745507 \nL 239.08125 71.745507 \n\" clip-path=\"url(#pe230d3eb36)\" style=\"fill: none; stroke: #b0b0b0; stroke-width: 0.8; stroke-linecap: square\"/>\n     </g>\n     <g id=\"line2d_16\">\n      <g>\n       <use xlink:href=\"#mba2db8896a\" x=\"43.78125\" y=\"71.745507\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_9\">\n      <!-- 1.6 -->\n      <g transform=\"translate(20.878125 75.544726) scale(0.1 -0.1)\">\n       <use xlink:href=\"#DejaVuSans-31\"/>\n       <use xlink:href=\"#DejaVuSans-2e\" transform=\"translate(63.623047 0)\"/>\n       <use xlink:href=\"#DejaVuSans-36\" transform=\"translate(95.410156 0)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_5\">\n     <g id=\"line2d_17\">\n      <path d=\"M 43.78125 47.499015 \nL 239.08125 47.499015 \n\" clip-path=\"url(#pe230d3eb36)\" style=\"fill: none; stroke: #b0b0b0; stroke-width: 0.8; stroke-linecap: square\"/>\n     </g>\n     <g id=\"line2d_18\">\n      <g>\n       <use xlink:href=\"#mba2db8896a\" x=\"43.78125\" y=\"47.499015\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_10\">\n      <!-- 1.8 -->\n      <g transform=\"translate(20.878125 51.298234) 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-31\"/>\n       <use xlink:href=\"#DejaVuSans-2e\" transform=\"translate(63.623047 0)\"/>\n       <use xlink:href=\"#DejaVuSans-38\" transform=\"translate(95.410156 0)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_6\">\n     <g id=\"line2d_19\">\n      <path d=\"M 43.78125 23.252523 \nL 239.08125 23.252523 \n\" clip-path=\"url(#pe230d3eb36)\" style=\"fill: none; stroke: #b0b0b0; stroke-width: 0.8; stroke-linecap: square\"/>\n     </g>\n     <g id=\"line2d_20\">\n      <g>\n       <use xlink:href=\"#mba2db8896a\" x=\"43.78125\" y=\"23.252523\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_11\">\n      <!-- 2.0 -->\n      <g transform=\"translate(20.878125 27.051741) scale(0.1 -0.1)\">\n       <use xlink:href=\"#DejaVuSans-32\"/>\n       <use xlink:href=\"#DejaVuSans-2e\" transform=\"translate(63.623047 0)\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(95.410156 0)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"text_12\">\n     <!-- masked loss -->\n     <g transform=\"translate(14.798438 107.250781) rotate(-90) scale(0.1 -0.1)\">\n      <defs>\n       <path id=\"DejaVuSans-6d\" d=\"M 3328 2828 \nQ 3544 3216 3844 3400 \nQ 4144 3584 4550 3584 \nQ 5097 3584 5394 3201 \nQ 5691 2819 5691 2113 \nL 5691 0 \nL 5113 0 \nL 5113 2094 \nQ 5113 2597 4934 2840 \nQ 4756 3084 4391 3084 \nQ 3944 3084 3684 2787 \nQ 3425 2491 3425 1978 \nL 3425 0 \nL 2847 0 \nL 2847 2094 \nQ 2847 2600 2669 2842 \nQ 2491 3084 2119 3084 \nQ 1678 3084 1418 2786 \nQ 1159 2488 1159 1978 \nL 1159 0 \nL 581 0 \nL 581 3500 \nL 1159 3500 \nL 1159 2956 \nQ 1356 3278 1631 3431 \nQ 1906 3584 2284 3584 \nQ 2666 3584 2933 3390 \nQ 3200 3197 3328 2828 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-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-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-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-6d\"/>\n      <use xlink:href=\"#DejaVuSans-61\" transform=\"translate(97.412109 0)\"/>\n      <use xlink:href=\"#DejaVuSans-73\" transform=\"translate(158.691406 0)\"/>\n      <use xlink:href=\"#DejaVuSans-6b\" transform=\"translate(210.791016 0)\"/>\n      <use xlink:href=\"#DejaVuSans-65\" transform=\"translate(265.076172 0)\"/>\n      <use xlink:href=\"#DejaVuSans-64\" transform=\"translate(326.599609 0)\"/>\n      <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(390.076172 0)\"/>\n      <use xlink:href=\"#DejaVuSans-6c\" transform=\"translate(421.863281 0)\"/>\n      <use xlink:href=\"#DejaVuSans-6f\" transform=\"translate(449.646484 0)\"/>\n      <use xlink:href=\"#DejaVuSans-73\" transform=\"translate(510.828125 0)\"/>\n      <use xlink:href=\"#DejaVuSans-73\" transform=\"translate(562.927734 0)\"/>\n     </g>\n    </g>\n   </g>\n   <g id=\"line2d_21\">\n    <path d=\"M 52.658523 16.151631 \nL 55.476705 92.77128 \nL 58.294886 128.94208 \nL 61.113068 138.417745 \nL 63.93125 137.126513 \nL 66.749432 135.471148 \nL 69.567614 137.100485 \nL 72.385795 131.571729 \nL 75.203977 129.14701 \nL 78.022159 135.669502 \nL 80.840341 129.412942 \nL 83.658523 129.414054 \nL 86.476705 131.168849 \nL 89.294886 133.44571 \nL 92.113068 129.150594 \nL 94.93125 134.2467 \nL 97.749432 133.899171 \nL 100.567614 129.303612 \nL 103.385795 129.283813 \nL 106.203977 132.928789 \nL 109.022159 136.635318 \nL 111.840341 131.670985 \nL 114.658523 131.831967 \nL 117.476705 125.64755 \nL 120.294886 130.516658 \nL 123.113068 130.560014 \nL 125.93125 129.493252 \nL 128.749432 128.233843 \nL 131.567614 133.586892 \nL 134.385795 125.142553 \nL 137.203977 132.495937 \nL 140.022159 131.695829 \nL 142.840341 133.971056 \nL 145.658523 139.5 \nL 148.476705 128.640524 \nL 151.294886 127.523959 \nL 154.113068 133.766979 \nL 156.93125 132.255744 \nL 159.749432 127.522803 \nL 162.567614 136.856029 \nL 165.385795 135.239627 \nL 168.203977 134.523774 \nL 171.022159 128.575374 \nL 173.840341 136.464755 \nL 176.658523 133.740098 \nL 179.476705 130.64122 \nL 182.294886 135.439701 \nL 185.113068 130.78113 \nL 187.93125 137.993057 \nL 190.749432 135.519172 \nL 193.567614 131.483282 \nL 196.385795 133.577874 \nL 199.203977 131.688212 \nL 202.022159 128.970146 \nL 204.840341 128.494341 \nL 207.658523 133.540819 \nL 210.476705 132.519754 \nL 213.294886 137.490979 \nL 216.113068 133.807618 \nL 218.93125 125.886862 \nL 221.749432 127.152513 \nL 224.567614 124.060168 \nL 227.385795 97.883933 \nL 230.203977 13.5 \n\" clip-path=\"url(#pe230d3eb36)\" style=\"fill: none; stroke: #1f77b4; stroke-width: 1.5; stroke-linecap: square\"/>\n   </g>\n   <g id=\"patch_3\">\n    <path d=\"M 43.78125 145.8 \nL 43.78125 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 239.08125 145.8 \nL 239.08125 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 43.78125 145.8 \nL 239.08125 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 43.78125 7.2 \nL 239.08125 7.2 \n\" style=\"fill: none; stroke: #000000; stroke-width: 0.8; stroke-linejoin: miter; stroke-linecap: square\"/>\n   </g>\n  </g>\n </g>\n <defs>\n  <clipPath id=\"pe230d3eb36\">\n   <rect x=\"43.78125\" 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=encoders-decoders-md-5 fw=all -->\n",
    "\n",
    "The profile is flat across the interior at about $1.1$ nats and roughly\n",
    "doubles at the two one-sided edges. That gap is the second side's value,\n",
    "measured: conditioning on both sides of a character cuts its loss by\n",
    "about half relative to one side, because for text, what follows a gap\n",
    "narrows it down about as sharply as what precedes it. The predictions are\n",
    "readable too — mask a character and the model fills it from its\n",
    "surroundings:"
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "encoders-decoders-what-the-second-side-is-worth-2"
   },
   "source": [
    "snippet = 'the time traveller for so it will be convenient to speak of him '\n",
    "ids = torch.tensor(data.vocab[list(snippet)], device=device)[None]\n",
    "for pos in (9, 14, 30):\n",
    "    Xm = ids.clone()\n",
    "    Xm[0, pos] = MASK\n",
    "    with torch.no_grad():\n",
    "        logits = F.linear(model(Xm), model.token_emb.weight)\n",
    "    probs = F.softmax(logits[0, pos], -1)\n",
    "    top = probs.topk(3)\n",
    "    shown = snippet[:pos] + '_' + snippet[pos + 1:]\n",
    "    print(f'{shown[:40]!r}... -> '\n",
    "          + ', '.join(f'{data.vocab.to_tokens(int(i))!r} {p:.2f}'\n",
    "                      for p, i in zip(top.values, top.indices)))"
   ],
   "execution_count": 5,
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "'the time _raveller for so it will be con'... -> 't' 0.94, 'g' 0.02, 'f' 0.01\n'the time trave_ler for so it will be con'... -> 'l' 0.99, ' ' 0.01, 'r' 0.00\n'the time traveller for so it w_ll be con'... -> 'i' 0.63, 'e' 0.29, 'a' 0.06\n"
     ]
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=encoders-decoders-md-6 fw=all -->\n",
    "\n",
    "The doubled consonant in \"trave_ler\" comes back with high confidence:\n",
    "only the right-hand context (\"ler\") pins it down, and a left-to-right\n",
    "model would never see it. This experiment, scaled up (subword tokens,\n",
    "sentence pairs, gigabytes of text, a fine-tuning recipe per downstream\n",
    "task), is BERT [@Devlin.Chang.Lee.ea.2018], whose pretraining and\n",
    "fine-tuning the Language Models part covers in full\n",
    "(that section). Nor did the wiring stop evolving in 2019:\n",
    "ModernBERT rebuilds the same encoder-only architecture with the modern\n",
    "block internals of this chapter, RoPE, gated FFN, alternating\n",
    "local--global attention, and an 8k context, and remains the backbone of\n",
    "choice for retrieval and classification at small model sizes\n",
    "[@Warner.Chaffin.Clavie.ea.2024].\n",
    "\n",
    "## An Encoder--Decoder: Cross-Attention at Work\n",
    "\n",
    "### A Task Whose Alignment We Know\n",
    "\n",
    "The encoder--decoder earns its keep when input and output are different\n",
    "sequences. Its signature component, cross-attention, is usually\n",
    "illustrated on machine translation, but a trained translation model gives\n",
    "us no ground truth to check its attention against. So we choose a task\n",
    "whose correct alignment is known by construction: *reverse a random\n",
    "string*. Target position $t$ must copy source position $n-1-t$, the\n",
    "letters are drawn independently at random, and the only path from source\n",
    "content to the decoder runs through cross-attention. If the mechanism\n",
    "works and the model solves the task directly, its attention map should be\n",
    "the anti-diagonal — a prediction we can check. Random strings also mean\n",
    "unlimited fresh data: unlike the memorizing GPT of that section,\n",
    "this model never sees the same example twice."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "encoders-decoders-a-task-whose-alignment-we-know"
   },
   "source": [
    "V, T = 16, 12   # 16 letters, strings of length 12\n",
    "BOS = V         # decoder start token\n",
    "\n",
    "def sample_batch(batch_size):\n",
    "    src = torch.randint(0, V, (batch_size, T), device=device)\n",
    "    tgt = src.flip(1)\n",
    "    dec_in = torch.cat([torch.full((batch_size, 1), BOS, device=device),\n",
    "                        tgt[:, :-1]], 1)\n",
    "    return src, dec_in, tgt\n",
    "\n",
    "def to_str(ids):\n",
    "    return ''.join(chr(97 + int(i)) for i in ids)\n",
    "\n",
    "src, dec_in, tgt = sample_batch(1)\n",
    "print(f'source {to_str(src[0])!r} -> target {to_str(tgt[0])!r}')"
   ],
   "execution_count": 6,
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "source 'ioaofaoebgaj' -> target 'jagbeoafoaoi'\n"
     ]
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=encoders-decoders-md-7 fw=all -->\n",
    "\n",
    "As in that section, training uses teacher forcing: the decoder input\n",
    "is the target shifted right behind a `<bos>` token, so every position\n",
    "learns to predict its successor in parallel.\n",
    "\n",
    "### The Decoder Block: One More Sublayer\n",
    "\n",
    "A decoder block is the transformer block plus one sublayer. Between the\n",
    "causal self-attention and the FFN sits cross-attention: queries from the\n",
    "target's residual stream, keys and values from the encoder output. It\n",
    "follows the same pre-norm discipline as everything in this chapter — each\n",
    "sublayer reads the stream through a normalization and adds its result\n",
    "back. Note the masking asymmetry: self-attention stays causal (the target\n",
    "is being generated), while cross-attention is unmasked (the source is\n",
    "fully known before generation starts)."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "encoders-decoders-the-decoder-block-one-more-sublayer-1"
   },
   "source": [
    "class DecoderBlock(nn.Module):\n",
    "    \"\"\"Pre-norm decoder block: causal self-attention, cross-attention,\n",
    "    FFN.\"\"\"\n",
    "    def __init__(self, num_hiddens, num_heads):\n",
    "        super().__init__()\n",
    "        self.norm1 = nn.RMSNorm(num_hiddens)\n",
    "        self.norm2 = nn.RMSNorm(num_hiddens)\n",
    "        self.norm3 = nn.RMSNorm(num_hiddens)\n",
    "        self.self_attention = d2l.MultiHeadAttention(num_hiddens, num_heads,\n",
    "                                                     dropout=0)\n",
    "        self.cross_attention = d2l.MultiHeadAttention(num_hiddens,\n",
    "                                                      num_heads, dropout=0)\n",
    "        self.ffn = d2l.FeedForward(num_hiddens)\n",
    "\n",
    "    def forward(self, X, enc):\n",
    "        B, T = X.shape[:2]\n",
    "        causal = torch.arange(1, T + 1, device=X.device).repeat(B, 1)\n",
    "        Y = self.norm1(X)\n",
    "        X = X + self.self_attention(Y, Y, Y, causal)\n",
    "        X = X + self.cross_attention(self.norm2(X), enc, enc, None)\n",
    "        return X + self.ffn(self.norm3(X))"
   ],
   "execution_count": 7,
   "outputs": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=encoders-decoders-md-8 fw=all -->\n",
    "\n",
    "The full model wires a `TransformerEncoder` (the class from the previous\n",
    "section, reused unchanged) to a stack of decoder blocks with its own\n",
    "embeddings and output head. Following the framework conventions of\n",
    "that section, the JAX model returns the\n",
    "cross-attention weights alongside the logits, while the PyTorch model\n",
    "stores them on the attention module."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "encoders-decoders-the-decoder-block-one-more-sublayer-2"
   },
   "source": [
    "class EncoderDecoder(nn.Module):\n",
    "    \"\"\"A causal decoder cross-attending into a bidirectional encoder.\"\"\"\n",
    "    def __init__(self, vocab_size, num_hiddens=128, num_heads=4,\n",
    "                 num_blks=1, max_len=64):\n",
    "        super().__init__()\n",
    "        self.encoder = TransformerEncoder(vocab_size, num_hiddens,\n",
    "                                          num_heads, num_blks, max_len)\n",
    "        self.tgt_emb = nn.Embedding(vocab_size, num_hiddens)\n",
    "        self.pos_emb = nn.Embedding(max_len, num_hiddens)\n",
    "        for emb in (self.tgt_emb, self.pos_emb):\n",
    "            nn.init.normal_(emb.weight, std=0.02)\n",
    "        self.blks = nn.ModuleList([DecoderBlock(num_hiddens, num_heads)\n",
    "                                   for _ in range(num_blks)])\n",
    "        self.norm = nn.RMSNorm(num_hiddens)\n",
    "        self.head = nn.Linear(num_hiddens, vocab_size, bias=False)\n",
    "\n",
    "    def forward(self, src, dec_in):\n",
    "        enc = self.encoder(src)\n",
    "        H = self.tgt_emb(dec_in) + self.pos_emb(\n",
    "            torch.arange(dec_in.shape[1], device=dec_in.device))\n",
    "        for blk in self.blks:\n",
    "            H = blk(H, enc)\n",
    "        return self.head(self.norm(H))"
   ],
   "execution_count": 8,
   "outputs": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=encoders-decoders-md-9 fw=all -->\n",
    "\n",
    "### Assembling the Masks\n",
    "\n",
    "Our reversal task ducks one bookkeeping question by construction: every\n",
    "string has the same length, so nothing is padding, and the only mask in\n",
    "sight is the decoder's causal one. A real batch — sequences of different\n",
    "lengths, padded to a rectangle — needs three masks, one per attention\n",
    "site, each composed from the two primitives of\n",
    "that section: a padding mask built from valid\n",
    "lengths, and the causal triangle, combined by logical AND under\n",
    "broadcasting. Encoder self-attention masks source padding. Decoder\n",
    "self-attention during teacher-forced training needs the causal triangle\n",
    "*and* target padding on the key side (padded query rows compute outputs\n",
    "the loss ignores). Cross-attention masks source padding again — the target may\n",
    "be mid-generation, but the source it reads is fully known. The cell below\n",
    "assembles all three for a toy ragged batch, as boolean arrays of shape\n",
    "(batch, queries, keys) — the form the fused kernels of\n",
    "that section accept; `d2l.MultiHeadAttention`'s\n",
    "`valid_lens` argument carries the same information in compressed form."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "encoders-decoders-assembling-the-masks"
   },
   "source": [
    "src_len, tgt_len = torch.tensor([3, 5]), torch.tensor([3, 4])\n",
    "S, T_dec = int(src_len.max()), int(tgt_len.max())\n",
    "src_valid = (torch.arange(S)[None, :] < src_len[:, None])[:, None, :]\n",
    "tgt_valid = (torch.arange(T_dec)[None, :] < tgt_len[:, None])[:, None, :]\n",
    "causal = (torch.arange(T_dec)[None, :]\n",
    "          <= torch.arange(T_dec)[:, None])[None]        # (1, T, T)\n",
    "enc_self = src_valid.expand(-1, S, -1)     # (B, S, S): source padding\n",
    "dec_self = causal & tgt_valid              # (B, T, T): causal AND padding\n",
    "cross = src_valid.expand(-1, T_dec, -1)    # (B, T, S): source padding\n",
    "for name, m in (('encoder self', enc_self), ('decoder self', dec_self),\n",
    "                ('cross', cross)):\n",
    "    print(f'{name}-attention mask, sequence 0 (1 = may attend):')\n",
    "    print(m[0].int().numpy())"
   ],
   "execution_count": 9,
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "encoder self-attention mask, sequence 0 (1 = may attend):\n[[1 1 1 0 0]\n [1 1 1 0 0]\n [1 1 1 0 0]\n [1 1 1 0 0]\n [1 1 1 0 0]]\ndecoder self-attention mask, sequence 0 (1 = may attend):\n[[1 0 0 0]\n [1 1 0 0]\n [1 1 1 0]\n [1 1 1 0]]\ncross-attention mask, sequence 0 (1 = may attend):\n[[1 1 1 0 0]\n [1 1 1 0 0]\n [1 1 1 0 0]\n [1 1 1 0 0]]\n"
     ]
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=encoders-decoders-md-10 fw=all -->\n",
    "\n",
    "Read sequence 0's three grids (source length 3 of 5, target length 3 of\n",
    "4): the encoder square and the cross rectangle both blank the same two\n",
    "padded source columns, and the decoder triangle loses its last column to\n",
    "target padding. In this section's model the composition never surfaces —\n",
    "`sample_batch` produces no padding, and the cross-attention call passes\n",
    "`valid_lens=None` — but these three grids are what a production\n",
    "encoder--decoder assembles for every batch it trains on.\n",
    "\n",
    "### Training and Decoding\n",
    "\n",
    "One encoder block, one decoder block, and a few hundred steps of on-line\n",
    "batches suffice — the model sees about ten million characters, none twice."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "encoders-decoders-training-and-decoding-1"
   },
   "source": [
    "torch.manual_seed(0)\n",
    "seq2seq = EncoderDecoder(V + 1).to(device)\n",
    "optimizer = torch.optim.AdamW(seq2seq.parameters(), lr=1e-3,\n",
    "                              weight_decay=0.0)\n",
    "losses = []\n",
    "for step in range(600):\n",
    "    src, dec_in, tgt = sample_batch(128)\n",
    "    logits = seq2seq(src, dec_in)\n",
    "    loss = F.cross_entropy(logits.reshape(-1, V + 1), tgt.reshape(-1))\n",
    "    optimizer.zero_grad()\n",
    "    loss.backward()\n",
    "    optimizer.step()\n",
    "    losses.append(loss.item())\n",
    "print('loss at step 100/200/400/600: ' + '/'.join(\n",
    "    f'{sum(losses[k-20:k]) / 20:.3f}' for k in (100, 200, 400, 600)))"
   ],
   "execution_count": 10,
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "loss at step 100/200/400/600: 0.005/0.001/0.001/0.000\n"
     ]
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=encoders-decoders-md-11 fw=all -->\n",
    "\n",
    "Decoding runs the encoder once and the decoder autoregressively: feed\n",
    "`<bos>`, take the argmax, append, repeat. On a thousand fresh strings the\n",
    "model reverses essentially every one exactly."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "encoders-decoders-training-and-decoding-2"
   },
   "source": [
    "seq2seq.eval()\n",
    "torch.manual_seed(1)\n",
    "with torch.no_grad():\n",
    "    src, _, tgt = sample_batch(1000)\n",
    "    enc = seq2seq.encoder(src)\n",
    "    out = torch.full((1000, T + 1), BOS, device=device)\n",
    "    for t in range(T):\n",
    "        H = seq2seq.tgt_emb(out[:, :t + 1]) + seq2seq.pos_emb(\n",
    "            torch.arange(t + 1, device=device))\n",
    "        for blk in seq2seq.blks:\n",
    "            H = blk(H, enc)\n",
    "        out[:, t + 1] = seq2seq.head(seq2seq.norm(H))[:, -1].argmax(-1)\n",
    "pred = out[:, 1:]\n",
    "print(f'exact match on 1000 fresh strings: '\n",
    "      f'{(pred == tgt).all(-1).float().mean():.3f}')\n",
    "print(f'source {to_str(src[0])!r} -> predicted {to_str(pred[0])!r}')"
   ],
   "execution_count": 11,
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "exact match on 1000 fresh strings: 1.000\nsource 'acppaolbfbak' -> predicted 'kabfbloappca'\n"
     ]
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=encoders-decoders-md-12 fw=all -->\n",
    "\n",
    "### Reading the Alignment\n",
    "\n",
    "Now the promised check. We run a batch through the model, pull the\n",
    "cross-attention weights out of the decoder block, and compare each target\n",
    "position's attention against the alignment the task dictates."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "encoders-decoders-reading-the-alignment"
   },
   "source": [
    "with torch.no_grad():\n",
    "    src, dec_in, tgt = sample_batch(64)\n",
    "    seq2seq(src, dec_in)\n",
    "w = seq2seq.blks[0].cross_attention.attention.attention_weights\n",
    "w = w.reshape(64, 4, T, T)\n",
    "want = torch.arange(T - 1, -1, -1, device=device)  # row t -> column T-1-t\n",
    "hit = (w.mean(1).argmax(-1) == want).float().mean()\n",
    "mass = w.mean(1).gather(-1, want.expand(64, T)[..., None]).mean()\n",
    "print(f'head-averaged argmax hits the true source position on '\n",
    "      f'{100 * hit:.0f}% of rows; mean weight there {mass:.2f}')\n",
    "d2l.show_heatmaps(w[0].cpu()[None], xlabel='source position',\n",
    "                  ylabel='target position',\n",
    "                  titles=[f'Head {i}' for i in range(1, 5)],\n",
    "                  figsize=(9, 2.5), cmap='Blues')"
   ],
   "execution_count": 12,
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "head-averaged argmax hits the true source position on 100% of rows; mean weight there 0.88\n"
     ]
    },
    {
     "output_type": "display_data",
     "data": {
      "image/svg+xml": "<?xml version=\"1.0\" encoding=\"utf-8\" standalone=\"no\"?>\n<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n  \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n<svg xmlns:xlink=\"http://www.w3.org/1999/xlink\" width=\"508.09675pt\" height=\"147.213505pt\" viewBox=\"0 0 508.09675 147.213505\" 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-19T14:04:32.525681</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 147.213505 \nL 508.09675 147.213505 \nL 508.09675 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 40.603125 109.657255 \nL 127.942255 109.657255 \nL 127.942255 22.318125 \nL 40.603125 22.318125 \nz\n\" style=\"fill: #ffffff\"/>\n   </g>\n   <g clip-path=\"url(#pb75e09566a)\">\n    <image xlink:href=\"data:image/png;base64,\niVBORw0KGgoAAAANSUhEUgAAAHoAAAB6CAYAAABwWUfkAAACnUlEQVR4nO3cvWpTcRyH8XPaxNYhlrbawUHBRR0cXApFkQrFQVy9Bwu+TDqIilocXfQKnERxFYcUCi5eQCdHR6EQaGlj2rx4B/LFHBPJ83zmH8nhPOe//DhJObu6MSgCreaTZKzY2etEcycbM9GcqjE17gvQaBgawtAQhoYwNIShIQwNYWgIQ0OUB4f9aDO2sHwv+sCf395Ec8dqPmOj5N2GMDSEoSEMDWFoCENDGBrC0BCGhij3fvWizVhtOnsm5q8/i+ZaWy+jOarBIMpS7Hd60ZwnGsLQEIaGMDSEoSEMDWFoCENDGBrC0BDlbjtbgdYrfpnv4sPP8ey79ZVobvncwt9ezsTzREMYGsLQEIaGMDSEoSEMDWFoCENDlO2j8C20irX2D+PZC+sforntt7ejuaW52fi7J4UnGsLQEIaGMDSEoSEMDWFoCENDGBpibJuxf2H+6qNo7kfzVTR34nh9mMv5r3iiIQwNYWgIQ0MYGsLQEIaGMDSEoSEmajPW7fWjuVM3NqK5nWb253gHnW401xjjps0TDWFoCENDGBrC0BCGhjA0hKEhDA0Rb8bSv/4vy3KoCxpGuhnbbWebrCsvmtHc16dr0dxMPT9XVb+v5omGMDSEoSEMDWFoCENDGBrC0BCGhpiod8ZS6QZtKtzynb3zMZrbfH4zmiuKojh/uhHPJjzREIaGMDSEoSEMDWFoCENDGBrC0BCGhkCuQKuW/mz28uMv8Wd+enAtmrt0Zi6a80RDGBrC0BCGhjA0hKEhDA1haAhDQ7gZG6F+P7/Vi7deR3Pf39+N5jzREIaGMDSEoSEMDWFoCENDGBrC0BCVb8bSn6TWpn3G/uSom93HpZX70Zx3G8LQEIaGMDSEoSEMDWFoCENDGBriN/rdeJad7aIbAAAAAElFTkSuQmCC\" id=\"image000c2824e1\" transform=\"scale(1 -1) translate(0 -87.84)\" x=\"40.603125\" y=\"-21.817255\" width=\"87.84\" height=\"87.84\"/>\n   </g>\n   <g id=\"matplotlib.axis_1\">\n    <g id=\"xtick_1\">\n     <g id=\"line2d_1\">\n      <defs>\n       <path id=\"mf5d0e5e922\" d=\"M 0 0 \nL 0 3.5 \n\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </defs>\n      <g>\n       <use xlink:href=\"#mf5d0e5e922\" x=\"44.242255\" y=\"109.657255\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_1\">\n      <!-- 0 -->\n      <g transform=\"translate(41.061005 124.255693) 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=\"#mf5d0e5e922\" x=\"117.024864\" y=\"109.657255\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_2\">\n      <!-- 10 -->\n      <g transform=\"translate(110.662364 124.255693) 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_3\">\n     <!-- source position -->\n     <g transform=\"translate(46.277378 137.933818) scale(0.1 -0.1)\">\n      <defs>\n       <path id=\"DejaVuSans-73\" d=\"M 2834 3397 \nL 2834 2853 \nQ 2591 2978 2328 3040 \nQ 2066 3103 1784 3103 \nQ 1356 3103 1142 2972 \nQ 928 2841 928 2578 \nQ 928 2378 1081 2264 \nQ 1234 2150 1697 2047 \nL 1894 2003 \nQ 2506 1872 2764 1633 \nQ 3022 1394 3022 966 \nQ 3022 478 2636 193 \nQ 2250 -91 1575 -91 \nQ 1294 -91 989 -36 \nQ 684 19 347 128 \nL 347 722 \nQ 666 556 975 473 \nQ 1284 391 1588 391 \nQ 1994 391 2212 530 \nQ 2431 669 2431 922 \nQ 2431 1156 2273 1281 \nQ 2116 1406 1581 1522 \nL 1381 1569 \nQ 847 1681 609 1914 \nQ 372 2147 372 2553 \nQ 372 3047 722 3315 \nQ 1072 3584 1716 3584 \nQ 2034 3584 2315 3537 \nQ 2597 3491 2834 3397 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-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-75\" d=\"M 544 1381 \nL 544 3500 \nL 1119 3500 \nL 1119 1403 \nQ 1119 906 1312 657 \nQ 1506 409 1894 409 \nQ 2359 409 2629 706 \nQ 2900 1003 2900 1516 \nL 2900 3500 \nL 3475 3500 \nL 3475 0 \nL 2900 0 \nL 2900 538 \nQ 2691 219 2414 64 \nQ 2138 -91 1772 -91 \nQ 1169 -91 856 284 \nQ 544 659 544 1381 \nz\nM 1991 3584 \nL 1991 3584 \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-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-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-20\" 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-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-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-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      </defs>\n      <use xlink:href=\"#DejaVuSans-73\"/>\n      <use xlink:href=\"#DejaVuSans-6f\" transform=\"translate(52.099609 0)\"/>\n      <use xlink:href=\"#DejaVuSans-75\" transform=\"translate(113.28125 0)\"/>\n      <use xlink:href=\"#DejaVuSans-72\" transform=\"translate(176.660156 0)\"/>\n      <use xlink:href=\"#DejaVuSans-63\" transform=\"translate(215.523438 0)\"/>\n      <use xlink:href=\"#DejaVuSans-65\" transform=\"translate(270.503906 0)\"/>\n      <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(332.027344 0)\"/>\n      <use xlink:href=\"#DejaVuSans-70\" transform=\"translate(363.814453 0)\"/>\n      <use xlink:href=\"#DejaVuSans-6f\" transform=\"translate(427.291016 0)\"/>\n      <use xlink:href=\"#DejaVuSans-73\" transform=\"translate(488.472656 0)\"/>\n      <use xlink:href=\"#DejaVuSans-69\" transform=\"translate(540.572266 0)\"/>\n      <use xlink:href=\"#DejaVuSans-74\" transform=\"translate(568.355469 0)\"/>\n      <use xlink:href=\"#DejaVuSans-69\" transform=\"translate(607.564453 0)\"/>\n      <use xlink:href=\"#DejaVuSans-6f\" transform=\"translate(635.347656 0)\"/>\n      <use xlink:href=\"#DejaVuSans-6e\" transform=\"translate(696.529297 0)\"/>\n     </g>\n    </g>\n   </g>\n   <g id=\"matplotlib.axis_2\">\n    <g id=\"ytick_1\">\n     <g id=\"line2d_3\">\n      <defs>\n       <path id=\"m5d66a6d893\" d=\"M 0 0 \nL -3.5 0 \n\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </defs>\n      <g>\n       <use xlink:href=\"#m5d66a6d893\" x=\"40.603125\" y=\"25.957255\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_4\">\n      <!-- 0 -->\n      <g transform=\"translate(27.240625 29.756474) scale(0.1 -0.1)\">\n       <use xlink:href=\"#DejaVuSans-30\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_2\">\n     <g id=\"line2d_4\">\n      <g>\n       <use xlink:href=\"#m5d66a6d893\" x=\"40.603125\" y=\"62.34856\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_5\">\n      <!-- 5 -->\n      <g transform=\"translate(27.240625 66.147779) 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-35\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_3\">\n     <g id=\"line2d_5\">\n      <g>\n       <use xlink:href=\"#m5d66a6d893\" x=\"40.603125\" y=\"98.739864\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_6\">\n      <!-- 10 -->\n      <g transform=\"translate(20.878125 102.539083) scale(0.1 -0.1)\">\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     <!-- target position -->\n     <g transform=\"translate(14.798438 102.584565) rotate(-90) scale(0.1 -0.1)\">\n      <defs>\n       <path id=\"DejaVuSans-61\" d=\"M 2194 1759 \nQ 1497 1759 1228 1600 \nQ 959 1441 959 1056 \nQ 959 750 1161 570 \nQ 1363 391 1709 391 \nQ 2188 391 2477 730 \nQ 2766 1069 2766 1631 \nL 2766 1759 \nL 2194 1759 \nz\nM 3341 1997 \nL 3341 0 \nL 2766 0 \nL 2766 531 \nQ 2569 213 2275 61 \nQ 1981 -91 1556 -91 \nQ 1019 -91 701 211 \nQ 384 513 384 1019 \nQ 384 1609 779 1909 \nQ 1175 2209 1959 2209 \nL 2766 2209 \nL 2766 2266 \nQ 2766 2663 2505 2880 \nQ 2244 3097 1772 3097 \nQ 1472 3097 1187 3025 \nQ 903 2953 641 2809 \nL 641 3341 \nQ 956 3463 1253 3523 \nQ 1550 3584 1831 3584 \nQ 2591 3584 2966 3190 \nQ 3341 2797 3341 1997 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-67\" d=\"M 2906 1791 \nQ 2906 2416 2648 2759 \nQ 2391 3103 1925 3103 \nQ 1463 3103 1205 2759 \nQ 947 2416 947 1791 \nQ 947 1169 1205 825 \nQ 1463 481 1925 481 \nQ 2391 481 2648 825 \nQ 2906 1169 2906 1791 \nz\nM 3481 434 \nQ 3481 -459 3084 -895 \nQ 2688 -1331 1869 -1331 \nQ 1566 -1331 1297 -1286 \nQ 1028 -1241 775 -1147 \nL 775 -588 \nQ 1028 -725 1275 -790 \nQ 1522 -856 1778 -856 \nQ 2344 -856 2625 -561 \nQ 2906 -266 2906 331 \nL 2906 616 \nQ 2728 306 2450 153 \nQ 2172 0 1784 0 \nQ 1141 0 747 490 \nQ 353 981 353 1791 \nQ 353 2603 747 3093 \nQ 1141 3584 1784 3584 \nQ 2172 3584 2450 3431 \nQ 2728 3278 2906 2969 \nL 2906 3500 \nL 3481 3500 \nL 3481 434 \nz\n\" transform=\"scale(0.015625)\"/>\n      </defs>\n      <use xlink:href=\"#DejaVuSans-74\"/>\n      <use xlink:href=\"#DejaVuSans-61\" transform=\"translate(39.208984 0)\"/>\n      <use xlink:href=\"#DejaVuSans-72\" transform=\"translate(100.488281 0)\"/>\n      <use xlink:href=\"#DejaVuSans-67\" transform=\"translate(139.851562 0)\"/>\n      <use xlink:href=\"#DejaVuSans-65\" transform=\"translate(203.328125 0)\"/>\n      <use xlink:href=\"#DejaVuSans-74\" transform=\"translate(264.851562 0)\"/>\n      <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(304.060547 0)\"/>\n      <use xlink:href=\"#DejaVuSans-70\" transform=\"translate(335.847656 0)\"/>\n      <use xlink:href=\"#DejaVuSans-6f\" transform=\"translate(399.324219 0)\"/>\n      <use xlink:href=\"#DejaVuSans-73\" transform=\"translate(460.505859 0)\"/>\n      <use xlink:href=\"#DejaVuSans-69\" transform=\"translate(512.605469 0)\"/>\n      <use xlink:href=\"#DejaVuSans-74\" transform=\"translate(540.388672 0)\"/>\n      <use xlink:href=\"#DejaVuSans-69\" transform=\"translate(579.597656 0)\"/>\n      <use xlink:href=\"#DejaVuSans-6f\" transform=\"translate(607.380859 0)\"/>\n      <use xlink:href=\"#DejaVuSans-6e\" transform=\"translate(668.5625 0)\"/>\n     </g>\n    </g>\n   </g>\n   <g id=\"patch_3\">\n    <path d=\"M 40.603125 109.657255 \nL 40.603125 22.318125 \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 127.942255 109.657255 \nL 127.942255 22.318125 \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 40.603125 109.657255 \nL 127.942255 109.657255 \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 40.603125 22.318125 \nL 127.942255 22.318125 \n\" style=\"fill: none; stroke: #000000; stroke-width: 0.8; stroke-linejoin: miter; stroke-linecap: square\"/>\n   </g>\n   <g id=\"text_8\">\n    <!-- Head 1 -->\n    <g transform=\"translate(62.858315 16.318125) scale(0.12 -0.12)\">\n     <defs>\n      <path id=\"DejaVuSans-48\" d=\"M 628 4666 \nL 1259 4666 \nL 1259 2753 \nL 3553 2753 \nL 3553 4666 \nL 4184 4666 \nL 4184 0 \nL 3553 0 \nL 3553 2222 \nL 1259 2222 \nL 1259 0 \nL 628 0 \nL 628 4666 \nz\n\" transform=\"scale(0.015625)\"/>\n      <path id=\"DejaVuSans-64\" d=\"M 2906 2969 \nL 2906 4863 \nL 3481 4863 \nL 3481 0 \nL 2906 0 \nL 2906 525 \nQ 2725 213 2448 61 \nQ 2172 -91 1784 -91 \nQ 1150 -91 751 415 \nQ 353 922 353 1747 \nQ 353 2572 751 3078 \nQ 1150 3584 1784 3584 \nQ 2172 3584 2448 3432 \nQ 2725 3281 2906 2969 \nz\nM 947 1747 \nQ 947 1113 1208 752 \nQ 1469 391 1925 391 \nQ 2381 391 2643 752 \nQ 2906 1113 2906 1747 \nQ 2906 2381 2643 2742 \nQ 2381 3103 1925 3103 \nQ 1469 3103 1208 2742 \nQ 947 2381 947 1747 \nz\n\" transform=\"scale(0.015625)\"/>\n     </defs>\n     <use xlink:href=\"#DejaVuSans-48\"/>\n     <use xlink:href=\"#DejaVuSans-65\" transform=\"translate(75.195312 0)\"/>\n     <use xlink:href=\"#DejaVuSans-61\" transform=\"translate(136.71875 0)\"/>\n     <use xlink:href=\"#DejaVuSans-64\" transform=\"translate(197.998047 0)\"/>\n     <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(261.474609 0)\"/>\n     <use xlink:href=\"#DejaVuSans-31\" transform=\"translate(293.261719 0)\"/>\n    </g>\n   </g>\n  </g>\n  <g id=\"axes_2\">\n   <g id=\"patch_7\">\n    <path d=\"M 145.410082 109.657255 \nL 232.749212 109.657255 \nL 232.749212 22.318125 \nL 145.410082 22.318125 \nz\n\" style=\"fill: #ffffff\"/>\n   </g>\n   <g clip-path=\"url(#p0877f60188)\">\n    <image xlink:href=\"data:image/png;base64,\niVBORw0KGgoAAAANSUhEUgAAAHoAAAB6CAYAAABwWUfkAAACnElEQVR4nO3dvWoUURiH8TPubowfYBJTKjYpBbFRwVIFIY1gLVililoJAQURLAQRES9A9AYsNCCInVh4FYKlJIHgusb9srEOf+SE4DzPr36Z2eTZ07xMMs3s2dVpCWx9eZGMldF4Es11OweiOdXhbxvC0BCGhjA0hKEhDA1haAhDQxgaovn5exJtxhbO3YouuBlu0JqmieZUhycawtAQhoYwNIShIQwNYWgIQ0MYGqLZHoyjzVivm30n5q88iua2PtyP5rS7/s4omvNEQxgawtAQhoYwNIShIQwNYWgIQ0MYGqLZ7I+iFeihmU7VG5+59z6efb1yIbvmqbl//DTt54mGMDSEoSEMDWFoCENDGBrC0BCGhmgGw2m0Gavtx6/sobZSSjl542U09/XVzWju2OFefO+28ERDGBrC0BCGhjA0hKEhDA1haAhDQ+zbZmwvzJ+/E819//wsmmvT6yDa85NoV4aGMDSEoSEMDWFoCENDGBrC0BCt2oxNsrdGlOPLT6K5jfW70dz2YBjNzR2Zieb2gicawtAQhoYwNIShIQwNYWgIQ0MYGiLejI3Gk+iC+/mcVfoZ0xegLl56EM1tfHwY3jca+ztb9yWtnmgIQ0MYGsLQEIaGMDSEoSEMDWFoiFY9M5aqveVLX7z67e1aNFdKKUdnu/FswhMNYWgIQ0MYGsLQEIaGMDSEoSEMDWFoCOQKtLZ++NqIq88/xdd8fP10NHdxaTGa80RDGBrC0BCGhjA0hKEhDA1haAhDQ1TfjE3Dy9X+s9D/QfoP70opZen2m2ju3drlaM4TDWFoCENDGBrC0BCGhjA0hKEhDA1RfTO2MxxHcwd7nZq3bZ30ObQT155Gc55oCENDGBrC0BCGhjA0hKEhDA1haIg/pgV1oZzqiPwAAAAASUVORK5CYII=\" id=\"image5a8bd7d68e\" transform=\"scale(1 -1) translate(0 -87.84)\" x=\"145.410082\" y=\"-21.817255\" width=\"87.84\" height=\"87.84\"/>\n   </g>\n   <g id=\"matplotlib.axis_3\">\n    <g id=\"xtick_3\">\n     <g id=\"line2d_6\">\n      <g>\n       <use xlink:href=\"#mf5d0e5e922\" x=\"149.049212\" y=\"109.657255\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_9\">\n      <!-- 0 -->\n      <g transform=\"translate(145.867962 124.255693) scale(0.1 -0.1)\">\n       <use xlink:href=\"#DejaVuSans-30\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_4\">\n     <g id=\"line2d_7\">\n      <g>\n       <use xlink:href=\"#mf5d0e5e922\" x=\"221.831821\" y=\"109.657255\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_10\">\n      <!-- 10 -->\n      <g transform=\"translate(215.469321 124.255693) scale(0.1 -0.1)\">\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_11\">\n     <!-- source position -->\n     <g transform=\"translate(151.084334 137.933818) scale(0.1 -0.1)\">\n      <use xlink:href=\"#DejaVuSans-73\"/>\n      <use xlink:href=\"#DejaVuSans-6f\" transform=\"translate(52.099609 0)\"/>\n      <use xlink:href=\"#DejaVuSans-75\" transform=\"translate(113.28125 0)\"/>\n      <use xlink:href=\"#DejaVuSans-72\" transform=\"translate(176.660156 0)\"/>\n      <use xlink:href=\"#DejaVuSans-63\" transform=\"translate(215.523438 0)\"/>\n      <use xlink:href=\"#DejaVuSans-65\" transform=\"translate(270.503906 0)\"/>\n      <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(332.027344 0)\"/>\n      <use xlink:href=\"#DejaVuSans-70\" transform=\"translate(363.814453 0)\"/>\n      <use xlink:href=\"#DejaVuSans-6f\" transform=\"translate(427.291016 0)\"/>\n      <use xlink:href=\"#DejaVuSans-73\" transform=\"translate(488.472656 0)\"/>\n      <use xlink:href=\"#DejaVuSans-69\" transform=\"translate(540.572266 0)\"/>\n      <use xlink:href=\"#DejaVuSans-74\" transform=\"translate(568.355469 0)\"/>\n      <use xlink:href=\"#DejaVuSans-69\" transform=\"translate(607.564453 0)\"/>\n      <use xlink:href=\"#DejaVuSans-6f\" transform=\"translate(635.347656 0)\"/>\n      <use xlink:href=\"#DejaVuSans-6e\" transform=\"translate(696.529297 0)\"/>\n     </g>\n    </g>\n   </g>\n   <g id=\"matplotlib.axis_4\">\n    <g id=\"ytick_4\">\n     <g id=\"line2d_8\">\n      <g>\n       <use xlink:href=\"#m5d66a6d893\" x=\"145.410082\" y=\"25.957255\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_5\">\n     <g id=\"line2d_9\">\n      <g>\n       <use xlink:href=\"#m5d66a6d893\" x=\"145.410082\" y=\"62.34856\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_6\">\n     <g id=\"line2d_10\">\n      <g>\n       <use xlink:href=\"#m5d66a6d893\" x=\"145.410082\" y=\"98.739864\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n    </g>\n   </g>\n   <g id=\"patch_8\">\n    <path d=\"M 145.410082 109.657255 \nL 145.410082 22.318125 \n\" style=\"fill: none; stroke: #000000; stroke-width: 0.8; stroke-linejoin: miter; stroke-linecap: square\"/>\n   </g>\n   <g id=\"patch_9\">\n    <path d=\"M 232.749212 109.657255 \nL 232.749212 22.318125 \n\" style=\"fill: none; stroke: #000000; stroke-width: 0.8; stroke-linejoin: miter; stroke-linecap: square\"/>\n   </g>\n   <g id=\"patch_10\">\n    <path d=\"M 145.410082 109.657255 \nL 232.749212 109.657255 \n\" style=\"fill: none; stroke: #000000; stroke-width: 0.8; stroke-linejoin: miter; stroke-linecap: square\"/>\n   </g>\n   <g id=\"patch_11\">\n    <path d=\"M 145.410082 22.318125 \nL 232.749212 22.318125 \n\" style=\"fill: none; stroke: #000000; stroke-width: 0.8; stroke-linejoin: miter; stroke-linecap: square\"/>\n   </g>\n   <g id=\"text_12\">\n    <!-- Head 2 -->\n    <g transform=\"translate(167.665272 16.318125) scale(0.12 -0.12)\">\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-48\"/>\n     <use xlink:href=\"#DejaVuSans-65\" transform=\"translate(75.195312 0)\"/>\n     <use xlink:href=\"#DejaVuSans-61\" transform=\"translate(136.71875 0)\"/>\n     <use xlink:href=\"#DejaVuSans-64\" transform=\"translate(197.998047 0)\"/>\n     <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(261.474609 0)\"/>\n     <use xlink:href=\"#DejaVuSans-32\" transform=\"translate(293.261719 0)\"/>\n    </g>\n   </g>\n  </g>\n  <g id=\"axes_3\">\n   <g id=\"patch_12\">\n    <path d=\"M 250.217038 109.657255 \nL 337.556168 109.657255 \nL 337.556168 22.318125 \nL 250.217038 22.318125 \nz\n\" style=\"fill: #ffffff\"/>\n   </g>\n   <g clip-path=\"url(#p3797306b8e)\">\n    <image xlink:href=\"data:image/png;base64,\niVBORw0KGgoAAAANSUhEUgAAAHoAAAB6CAYAAABwWUfkAAACj0lEQVR4nO3dO2uTYQCG4fdLWxsqCKFYRCriUtDFSceuIi0ewNFBhE7VwaHg5lpEF1twchNnC4K/wAPqLylKRAlNmkP9B/KgX4zkvq/5IU25+y4vX5qqubZ7VALt15vJrOz/6EW7pRPz0U71aEz6DejfMDSEoSEMDWFoCENDGBrC0BCGhqgO+kfRzVjr0r3oBdufd//qDWk8PNEQhoYwNIShIQwNYWgIQ0MYGsLQEFW7M4huxprHZqIXbF3fiXbtvfvRTr/386Af7TzREIaGMDSEoSEMDWFoCENDGBrC0BCGhqg6vVF0BdpoVLX+4Cs77+LtxurZaHfr4vKfvp2p54mGMDSEoSEMDWFoCENDGBrC0BCGhog/Nlu3TncQb5dvPI12+2+2ot3cLO/vm/cbQxkawtAQhoYwNIShIQwNYWgIQ0NM7GZsHFqXs4/ifvv4LNrV/ZzcJHmiIQwNYWgIQ0MYGsLQEIaGMDSEoSGm6mZslH0wtCxe3Y52X98+jHbdw2G0O96cjXbj4ImGMDSEoSEMDWFoCENDGBrC0BCGhohvxobhrdPMBJ+z6vazG6rUhQd70e7L9nq0Wwi/rqKU/KstUp5oCENDGBrC0BCGhjA0hKEhDA1haIipemYsNRiOol16y3f67qto9+nJzWhXSilnFhfibcITDWFoCENDGBrC0BCGhjA0hKEhDA1haAjkFWjd0q+NuPb8ffyaj9bOR7vVlZPRzhMNYWgIQ0MYGsLQEIaGMDSEoSEMDeHN2H/q1J2X0e7D4+yBQ080hKEhDA1haAhDQxgawtAQhoYwNETtN2O98J+6zc/V+w/Tps33zmG0O3f7RbTzREMYGsLQEIaGMDSEoSEMDWFoCEND/AIM72/FiZVWcwAAAABJRU5ErkJggg==\" id=\"image00c1e14e04\" transform=\"scale(1 -1) translate(0 -87.84)\" x=\"250.217038\" y=\"-21.817255\" width=\"87.84\" height=\"87.84\"/>\n   </g>\n   <g id=\"matplotlib.axis_5\">\n    <g id=\"xtick_5\">\n     <g id=\"line2d_11\">\n      <g>\n       <use xlink:href=\"#mf5d0e5e922\" x=\"253.856168\" y=\"109.657255\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_13\">\n      <!-- 0 -->\n      <g transform=\"translate(250.674918 124.255693) scale(0.1 -0.1)\">\n       <use xlink:href=\"#DejaVuSans-30\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_6\">\n     <g id=\"line2d_12\">\n      <g>\n       <use xlink:href=\"#mf5d0e5e922\" x=\"326.638777\" y=\"109.657255\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_14\">\n      <!-- 10 -->\n      <g transform=\"translate(320.276277 124.255693) scale(0.1 -0.1)\">\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_15\">\n     <!-- source position -->\n     <g transform=\"translate(255.891291 137.933818) scale(0.1 -0.1)\">\n      <use xlink:href=\"#DejaVuSans-73\"/>\n      <use xlink:href=\"#DejaVuSans-6f\" transform=\"translate(52.099609 0)\"/>\n      <use xlink:href=\"#DejaVuSans-75\" transform=\"translate(113.28125 0)\"/>\n      <use xlink:href=\"#DejaVuSans-72\" transform=\"translate(176.660156 0)\"/>\n      <use xlink:href=\"#DejaVuSans-63\" transform=\"translate(215.523438 0)\"/>\n      <use xlink:href=\"#DejaVuSans-65\" transform=\"translate(270.503906 0)\"/>\n      <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(332.027344 0)\"/>\n      <use xlink:href=\"#DejaVuSans-70\" transform=\"translate(363.814453 0)\"/>\n      <use xlink:href=\"#DejaVuSans-6f\" transform=\"translate(427.291016 0)\"/>\n      <use xlink:href=\"#DejaVuSans-73\" transform=\"translate(488.472656 0)\"/>\n      <use xlink:href=\"#DejaVuSans-69\" transform=\"translate(540.572266 0)\"/>\n      <use xlink:href=\"#DejaVuSans-74\" transform=\"translate(568.355469 0)\"/>\n      <use xlink:href=\"#DejaVuSans-69\" transform=\"translate(607.564453 0)\"/>\n      <use xlink:href=\"#DejaVuSans-6f\" transform=\"translate(635.347656 0)\"/>\n      <use xlink:href=\"#DejaVuSans-6e\" transform=\"translate(696.529297 0)\"/>\n     </g>\n    </g>\n   </g>\n   <g id=\"matplotlib.axis_6\">\n    <g id=\"ytick_7\">\n     <g id=\"line2d_13\">\n      <g>\n       <use xlink:href=\"#m5d66a6d893\" x=\"250.217038\" y=\"25.957255\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_8\">\n     <g id=\"line2d_14\">\n      <g>\n       <use xlink:href=\"#m5d66a6d893\" x=\"250.217038\" y=\"62.34856\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_9\">\n     <g id=\"line2d_15\">\n      <g>\n       <use xlink:href=\"#m5d66a6d893\" x=\"250.217038\" y=\"98.739864\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n    </g>\n   </g>\n   <g id=\"patch_13\">\n    <path d=\"M 250.217038 109.657255 \nL 250.217038 22.318125 \n\" style=\"fill: none; stroke: #000000; stroke-width: 0.8; stroke-linejoin: miter; stroke-linecap: square\"/>\n   </g>\n   <g id=\"patch_14\">\n    <path d=\"M 337.556168 109.657255 \nL 337.556168 22.318125 \n\" style=\"fill: none; stroke: #000000; stroke-width: 0.8; stroke-linejoin: miter; stroke-linecap: square\"/>\n   </g>\n   <g id=\"patch_15\">\n    <path d=\"M 250.217038 109.657255 \nL 337.556168 109.657255 \n\" style=\"fill: none; stroke: #000000; stroke-width: 0.8; stroke-linejoin: miter; stroke-linecap: square\"/>\n   </g>\n   <g id=\"patch_16\">\n    <path d=\"M 250.217038 22.318125 \nL 337.556168 22.318125 \n\" style=\"fill: none; stroke: #000000; stroke-width: 0.8; stroke-linejoin: miter; stroke-linecap: square\"/>\n   </g>\n   <g id=\"text_16\">\n    <!-- Head 3 -->\n    <g transform=\"translate(272.472228 16.318125) scale(0.12 -0.12)\">\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-48\"/>\n     <use xlink:href=\"#DejaVuSans-65\" transform=\"translate(75.195312 0)\"/>\n     <use xlink:href=\"#DejaVuSans-61\" transform=\"translate(136.71875 0)\"/>\n     <use xlink:href=\"#DejaVuSans-64\" transform=\"translate(197.998047 0)\"/>\n     <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(261.474609 0)\"/>\n     <use xlink:href=\"#DejaVuSans-33\" transform=\"translate(293.261719 0)\"/>\n    </g>\n   </g>\n  </g>\n  <g id=\"axes_4\">\n   <g id=\"patch_17\">\n    <path d=\"M 355.023995 109.657255 \nL 442.363125 109.657255 \nL 442.363125 22.318125 \nL 355.023995 22.318125 \nz\n\" style=\"fill: #ffffff\"/>\n   </g>\n   <g clip-path=\"url(#pd4668b2f0e)\">\n    <image xlink:href=\"data:image/png;base64,\niVBORw0KGgoAAAANSUhEUgAAAHoAAAB6CAYAAABwWUfkAAACjElEQVR4nO3dv2oUYRhG8W92Y9xGcIMRhBRiaRWRiAh2qSzEMp0QrESITQIp0sQinYjpgmCntU1AsRNBvAUvQEiCKWIwYXd2vYPwIGMW5pxf/TL75/A2H7M7Ve/2yrgEDr+9SsbKsB5Fc1PdTjSnZvhtQxgawtAQhoYwNIShIQwNYWgIQ0NUfwbj6GSsv/AsuuCv79vZC1dVNKdmuNEQhoYwNIShIQwNYWgIQ0MYGsLQENXRSR2djKX3ePUXX0Rzh583ojmd7fh0GM250RCGhjA0hKEhDA1haAhDQxgawtAQhoaofp+OoiPQbqfZm/luru3Gs++e3ovm5q9f/sd3035uNIShIQwNYWgIQ0MYGsLQEIaGMDRE/LPZpp0M6nj22oOtaO7n7no017vQjV+7LdxoCENDGBrC0BCGhjA0hKEhDA1haIiJnYz9D/27z6O5/a8vo7k2PQ6iPZ9EZzI0hKEhDA1haAhDQxgawtAQhoZo1cnYOPwoM4ub0dzex+xP79IvcHpqcnvlRkMYGsLQEIaGMDSEoSEMDWFoCENDxCdj6anTJB8uOqxHjV5v9tHraO7gw0o0Nxjm76833ewvPt1oCENDGBrC0BCGhjA0hKEhDA1haIhW3TOWqrOHDpT0oQO3Nj5FczvLC9kFSyl3bszEswk3GsLQEIaGMDSEoSEMDWFoCENDGBrC0BDII9CmpTf9XV16E1/zx9vH0dyVSxejOTcawtAQhoYwNIShIQwNYWgIQ0MYGsKTsXM0Cm9KLKWUuSfvo7kvWw+jOTcawtAQhoYwNIShIQwNYWgIQ0MYGqLxk7H09KeT/iYVKv1zvNn7q9GcGw1haAhDQxgawtAQhoYwNIShIQwN8RcEUHOLNQZkngAAAABJRU5ErkJggg==\" id=\"imageb3dc16d912\" transform=\"scale(1 -1) translate(0 -87.84)\" x=\"355.023995\" y=\"-21.817255\" width=\"87.84\" height=\"87.84\"/>\n   </g>\n   <g id=\"matplotlib.axis_7\">\n    <g id=\"xtick_7\">\n     <g id=\"line2d_16\">\n      <g>\n       <use xlink:href=\"#mf5d0e5e922\" x=\"358.663125\" y=\"109.657255\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_17\">\n      <!-- 0 -->\n      <g transform=\"translate(355.481875 124.255693) scale(0.1 -0.1)\">\n       <use xlink:href=\"#DejaVuSans-30\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_8\">\n     <g id=\"line2d_17\">\n      <g>\n       <use xlink:href=\"#mf5d0e5e922\" x=\"431.445734\" y=\"109.657255\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_18\">\n      <!-- 10 -->\n      <g transform=\"translate(425.083234 124.255693) scale(0.1 -0.1)\">\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_19\">\n     <!-- source position -->\n     <g transform=\"translate(360.698247 137.933818) scale(0.1 -0.1)\">\n      <use xlink:href=\"#DejaVuSans-73\"/>\n      <use xlink:href=\"#DejaVuSans-6f\" transform=\"translate(52.099609 0)\"/>\n      <use xlink:href=\"#DejaVuSans-75\" transform=\"translate(113.28125 0)\"/>\n      <use xlink:href=\"#DejaVuSans-72\" transform=\"translate(176.660156 0)\"/>\n      <use xlink:href=\"#DejaVuSans-63\" transform=\"translate(215.523438 0)\"/>\n      <use xlink:href=\"#DejaVuSans-65\" transform=\"translate(270.503906 0)\"/>\n      <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(332.027344 0)\"/>\n      <use xlink:href=\"#DejaVuSans-70\" transform=\"translate(363.814453 0)\"/>\n      <use xlink:href=\"#DejaVuSans-6f\" transform=\"translate(427.291016 0)\"/>\n      <use xlink:href=\"#DejaVuSans-73\" transform=\"translate(488.472656 0)\"/>\n      <use xlink:href=\"#DejaVuSans-69\" transform=\"translate(540.572266 0)\"/>\n      <use xlink:href=\"#DejaVuSans-74\" transform=\"translate(568.355469 0)\"/>\n      <use xlink:href=\"#DejaVuSans-69\" transform=\"translate(607.564453 0)\"/>\n      <use xlink:href=\"#DejaVuSans-6f\" transform=\"translate(635.347656 0)\"/>\n      <use xlink:href=\"#DejaVuSans-6e\" transform=\"translate(696.529297 0)\"/>\n     </g>\n    </g>\n   </g>\n   <g id=\"matplotlib.axis_8\">\n    <g id=\"ytick_10\">\n     <g id=\"line2d_18\">\n      <g>\n       <use xlink:href=\"#m5d66a6d893\" x=\"355.023995\" y=\"25.957255\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_11\">\n     <g id=\"line2d_19\">\n      <g>\n       <use xlink:href=\"#m5d66a6d893\" x=\"355.023995\" y=\"62.34856\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_12\">\n     <g id=\"line2d_20\">\n      <g>\n       <use xlink:href=\"#m5d66a6d893\" x=\"355.023995\" y=\"98.739864\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n    </g>\n   </g>\n   <g id=\"patch_18\">\n    <path d=\"M 355.023995 109.657255 \nL 355.023995 22.318125 \n\" style=\"fill: none; stroke: #000000; stroke-width: 0.8; stroke-linejoin: miter; stroke-linecap: square\"/>\n   </g>\n   <g id=\"patch_19\">\n    <path d=\"M 442.363125 109.657255 \nL 442.363125 22.318125 \n\" style=\"fill: none; stroke: #000000; stroke-width: 0.8; stroke-linejoin: miter; stroke-linecap: square\"/>\n   </g>\n   <g id=\"patch_20\">\n    <path d=\"M 355.023995 109.657255 \nL 442.363125 109.657255 \n\" style=\"fill: none; stroke: #000000; stroke-width: 0.8; stroke-linejoin: miter; stroke-linecap: square\"/>\n   </g>\n   <g id=\"patch_21\">\n    <path d=\"M 355.023995 22.318125 \nL 442.363125 22.318125 \n\" style=\"fill: none; stroke: #000000; stroke-width: 0.8; stroke-linejoin: miter; stroke-linecap: square\"/>\n   </g>\n   <g id=\"text_20\">\n    <!-- Head 4 -->\n    <g transform=\"translate(377.279185 16.318125) scale(0.12 -0.12)\">\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-48\"/>\n     <use xlink:href=\"#DejaVuSans-65\" transform=\"translate(75.195312 0)\"/>\n     <use xlink:href=\"#DejaVuSans-61\" transform=\"translate(136.71875 0)\"/>\n     <use xlink:href=\"#DejaVuSans-64\" transform=\"translate(197.998047 0)\"/>\n     <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(261.474609 0)\"/>\n     <use xlink:href=\"#DejaVuSans-34\" transform=\"translate(293.261719 0)\"/>\n    </g>\n   </g>\n  </g>\n  <g id=\"axes_5\">\n   <g id=\"patch_22\">\n    <path d=\"M 467.473125 107.56769 \nL 471.631125 107.56769 \nL 471.631125 24.40769 \nL 467.473125 24.40769 \nz\n\" style=\"fill: #ffffff\"/>\n   </g>\n   <image xlink:href=\"data:image/png;base64,\niVBORw0KGgoAAAANSUhEUgAAAAYAAAB0CAYAAACmJkOCAAAAsElEQVR4nOXTQQ7DIAxEUSpx/+t2AZhegIfkCJFFs7Q18zPG/nzbnGXx1YhlvVTUS51rp40irLgAvxCQiqEG6puRWPG3AQlnjo0CjT5Df3WMQUU/Z8UhkkGrwfdwY1kvtT2wUg4xuhVpOPdKigbJjpFV+GnTAX1qZvA+zsF5H5ruQbitsNUPrF5leH1wUg+spgOOpCK0cHlFeLrnGBfgU4oyGhqBsZ9s5OFahivwbOMHEnU9fz5mdEMAAAAASUVORK5CYII=\" id=\"image4bddcb5777\" transform=\"scale(1 -1) translate(0 -83.52)\" x=\"467.28\" y=\"-23.76\" width=\"4.32\" height=\"83.52\"/>\n   <g id=\"matplotlib.axis_9\"/>\n   <g id=\"matplotlib.axis_10\">\n    <g id=\"ytick_13\">\n     <g id=\"line2d_21\">\n      <defs>\n       <path id=\"m8505a67507\" d=\"M 0 0 \nL 3.5 0 \n\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </defs>\n      <g>\n       <use xlink:href=\"#m8505a67507\" x=\"471.631125\" y=\"107.56769\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_21\">\n      <!-- 0.00 -->\n      <g transform=\"translate(478.631125 111.366909) 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       </defs>\n       <use xlink:href=\"#DejaVuSans-30\"/>\n       <use xlink:href=\"#DejaVuSans-2e\" transform=\"translate(63.623047 0)\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(95.410156 0)\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(159.033203 0)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_14\">\n     <g id=\"line2d_22\">\n      <g>\n       <use xlink:href=\"#m8505a67507\" x=\"471.631125\" y=\"86.603357\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_22\">\n      <!-- 0.25 -->\n      <g transform=\"translate(478.631125 90.402576) scale(0.1 -0.1)\">\n       <use xlink:href=\"#DejaVuSans-30\"/>\n       <use xlink:href=\"#DejaVuSans-2e\" transform=\"translate(63.623047 0)\"/>\n       <use xlink:href=\"#DejaVuSans-32\" transform=\"translate(95.410156 0)\"/>\n       <use xlink:href=\"#DejaVuSans-35\" transform=\"translate(159.033203 0)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_15\">\n     <g id=\"line2d_23\">\n      <g>\n       <use xlink:href=\"#m8505a67507\" x=\"471.631125\" y=\"65.639025\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_23\">\n      <!-- 0.50 -->\n      <g transform=\"translate(478.631125 69.438244) scale(0.1 -0.1)\">\n       <use xlink:href=\"#DejaVuSans-30\"/>\n       <use xlink:href=\"#DejaVuSans-2e\" transform=\"translate(63.623047 0)\"/>\n       <use xlink:href=\"#DejaVuSans-35\" transform=\"translate(95.410156 0)\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(159.033203 0)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_16\">\n     <g id=\"line2d_24\">\n      <g>\n       <use xlink:href=\"#m8505a67507\" x=\"471.631125\" y=\"44.674692\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_24\">\n      <!-- 0.75 -->\n      <g transform=\"translate(478.631125 48.473911) 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-30\"/>\n       <use xlink:href=\"#DejaVuSans-2e\" transform=\"translate(63.623047 0)\"/>\n       <use xlink:href=\"#DejaVuSans-37\" transform=\"translate(95.410156 0)\"/>\n       <use xlink:href=\"#DejaVuSans-35\" transform=\"translate(159.033203 0)\"/>\n      </g>\n     </g>\n    </g>\n   </g>\n   <g id=\"LineCollection_1\"/>\n   <g id=\"patch_23\">\n    <path d=\"M 467.473125 107.56769 \nL 469.552125 107.56769 \nL 471.631125 107.56769 \nL 471.631125 24.40769 \nL 469.552125 24.40769 \nL 467.473125 24.40769 \nL 467.473125 107.56769 \nz\n\" style=\"fill: none; stroke: #000000; stroke-width: 0.8; stroke-linejoin: miter; stroke-linecap: square\"/>\n   </g>\n  </g>\n </g>\n <defs>\n  <clipPath id=\"pb75e09566a\">\n   <rect x=\"40.603125\" y=\"22.318125\" width=\"87.33913\" height=\"87.33913\"/>\n  </clipPath>\n  <clipPath id=\"p0877f60188\">\n   <rect x=\"145.410082\" y=\"22.318125\" width=\"87.33913\" height=\"87.33913\"/>\n  </clipPath>\n  <clipPath id=\"p3797306b8e\">\n   <rect x=\"250.217038\" y=\"22.318125\" width=\"87.33913\" height=\"87.33913\"/>\n  </clipPath>\n  <clipPath id=\"pd4668b2f0e\">\n   <rect x=\"355.023995\" y=\"22.318125\" width=\"87.33913\" height=\"87.33913\"/>\n  </clipPath>\n </defs>\n</svg>\n"
     },
     "metadata": {}
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=encoders-decoders-md-13 fw=all -->\n",
    "\n",
    "The maps show the anti-diagonal of the figure's third\n",
    "panel made real: averaged over heads, the argmax lands on the true source\n",
    "position for well over nine rows in ten, with most of the softmax mass\n",
    "concentrated there. The model has *learned* the alignment we built into\n",
    "the task, and cross-attention is where it lives — which is exactly the\n",
    "kind of readable evidence that section warned is the\n",
    "exception rather than the rule. It is readable here because we made the\n",
    "model small; give the encoder and decoder more depth and heads and the\n",
    "task stays solved while the maps delocalize, as one of the exercises\n",
    "demonstrates.\n",
    "\n",
    "## Cross-Attention as Interface\n",
    "\n",
    "### Queries Need Not Come from a Sequence\n",
    "\n",
    "In the decoder, the cross-attention queries came from the target stream.\n",
    "Nothing in the mechanism requires that. A query is just a vector, and a\n",
    "set of $M$ query vectors can simply be *learned parameters* — a fixed\n",
    "array that exists before any input arrives. Cross-attending it into an\n",
    "input of length $N$ costs $O(MN)$; the quadratic term of\n",
    "that section never appears, because the $M$ latents\n",
    "only ever self-attend among themselves at $O(M^2)$. This is the\n",
    "*Perceiver* [@Jaegle.Gimeno.Brock.ea.2021]: a fixed-size latent\n",
    "bottleneck that reads arbitrarily long, arbitrarily structured\n",
    "inputs through cross-attention, sketched in\n",
    "the figure.\n",
    "\n",
    "![The latent bottleneck. A learned array of M latents (M much smaller than the input length N) reads the input once through cross-attention at cost O(MN); all further processing is self-attention and FFN among the latents at cost O(M squared), independent of N.](../img/mdl-transformers-latent-bottleneck.svg)\n",
    "\n",
    "A minimal version needs a parameter array, one cross-attention, and a\n",
    "stack of ordinary transformer blocks over the latents:"
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "encoders-decoders-queries-need-not-come-from-a-sequence"
   },
   "source": [
    "class PerceiverEncoder(nn.Module):\n",
    "    \"\"\"M learned latents cross-attend into the input, then process among\n",
    "    themselves.\"\"\"\n",
    "    def __init__(self, num_latents, num_hiddens, num_heads=4, num_blks=2):\n",
    "        super().__init__()\n",
    "        self.latents = nn.Parameter(\n",
    "            0.02 * torch.randn(num_latents, num_hiddens))\n",
    "        self.norm_q = nn.RMSNorm(num_hiddens)\n",
    "        self.cross_attention = d2l.MultiHeadAttention(num_hiddens,\n",
    "                                                      num_heads, dropout=0)\n",
    "        self.blks = nn.ModuleList([\n",
    "            d2l.TransformerBlock(num_hiddens, num_heads)\n",
    "            for _ in range(num_blks)])\n",
    "        self.norm = nn.RMSNorm(num_hiddens)\n",
    "\n",
    "    def forward(self, X):\n",
    "        Z = self.latents.expand(X.shape[0], -1, -1)\n",
    "        Z = Z + self.cross_attention(self.norm_q(Z), X, X, None)  # O(MN)\n",
    "        for blk in self.blks:\n",
    "            Z = blk(Z)                                            # O(M^2)\n",
    "        return self.norm(Z)\n",
    "\n",
    "perceiver = PerceiverEncoder(num_latents=64, num_hiddens=256).to(device)\n",
    "X = torch.randn(1, 4096, 256, device=device)\n",
    "print('input', tuple(X.shape), '-> latent summary',\n",
    "      tuple(perceiver(X).shape))"
   ],
   "execution_count": 13,
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "input (1, 4096, 256) -> latent summary (1, 64, 256)\n"
     ]
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=encoders-decoders-md-14 fw=all -->\n",
    "\n",
    "Whatever the input length, the output is $M = 64$ vectors. The input here\n",
    "is a raw feature sequence rather than token embeddings, because the whole\n",
    "point is indifference to what the input is — text, audio frames, image\n",
    "pixels, or a concatenation of all three.\n",
    "\n",
    "### The Cost Curve\n",
    "\n",
    "The claim to verify is the shape of the cost. We time the Perceiver\n",
    "against the direct alternative (the same two transformer blocks applied\n",
    "to the full input sequence) as $N$ doubles at fixed $M = 64$."
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "id": "encoders-decoders-the-cost-curve"
   },
   "source": [
    "class SelfAttentionEncoder(nn.Module):\n",
    "    \"\"\"The comparison: the same blocks over the full input sequence.\"\"\"\n",
    "    def __init__(self, num_hiddens, num_heads=4, num_blks=2):\n",
    "        super().__init__()\n",
    "        self.blks = nn.ModuleList([\n",
    "            d2l.TransformerBlock(num_hiddens, num_heads)\n",
    "            for _ in range(num_blks)])\n",
    "\n",
    "    def forward(self, X):\n",
    "        for blk in self.blks:\n",
    "            X = blk(X)                                            # O(N^2)\n",
    "        return X\n",
    "\n",
    "full = SelfAttentionEncoder(256).to(device).eval()\n",
    "perceiver.eval()\n",
    "\n",
    "def timed(model, X, reps=20):\n",
    "    with torch.no_grad():\n",
    "        for _ in range(3):\n",
    "            model(X)\n",
    "        if device.type == 'cuda':\n",
    "            torch.cuda.synchronize()\n",
    "        t0 = time.time()\n",
    "        for _ in range(reps):\n",
    "            model(X)\n",
    "        if device.type == 'cuda':\n",
    "            torch.cuda.synchronize()\n",
    "    return (time.time() - t0) / reps * 1e3\n",
    "\n",
    "lengths, t_full, t_perc = (1024, 2048, 4096, 8192), [], []\n",
    "for N in lengths:\n",
    "    X = torch.randn(1, N, 256, device=device)\n",
    "    t_full.append(timed(full, X))\n",
    "    t_perc.append(timed(perceiver, X))\n",
    "    print(f'N={N:5d}: self-attention {t_full[-1]:6.2f} ms, '\n",
    "          f'perceiver {t_perc[-1]:5.2f} ms')\n",
    "d2l.plot(list(lengths), [t_full, t_perc], 'input length N',\n",
    "         'forward time (ms)', xscale='log', yscale='log',\n",
    "         legend=['self-attention encoder', 'perceiver encoder'])"
   ],
   "execution_count": 14,
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "N= 1024: self-attention   0.99 ms, perceiver  1.31 ms\nN= 2048: self-attention   2.80 ms, perceiver  1.40 ms\n"
     ]
    },
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "N= 4096: self-attention   9.46 ms, perceiver  1.35 ms\n"
     ]
    },
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "N= 8192: self-attention  34.79 ms, perceiver  1.72 ms\n"
     ]
    },
    {
     "output_type": "display_data",
     "data": {
      "image/svg+xml": "<?xml version=\"1.0\" encoding=\"utf-8\" standalone=\"no\"?>\n<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n  \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n<svg xmlns:xlink=\"http://www.w3.org/1999/xlink\" width=\"247.978125pt\" height=\"183.35625pt\" viewBox=\"0 0 247.978125 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-19T14:04:34.303919</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 247.978125 183.35625 \nL 247.978125 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 45.478125 145.8 \nL 240.778125 145.8 \nL 240.778125 7.2 \nL 45.478125 7.2 \nz\n\" style=\"fill: #ffffff\"/>\n   </g>\n   <g id=\"matplotlib.axis_1\">\n    <g id=\"xtick_1\">\n     <g id=\"line2d_1\">\n      <path d=\"M 52.330449 145.8 \nL 52.330449 7.2 \n\" clip-path=\"url(#pf96d8c46ba)\" style=\"fill: none; stroke: #b0b0b0; stroke-width: 0.8; stroke-linecap: square\"/>\n     </g>\n     <g id=\"line2d_2\">\n      <defs>\n       <path id=\"me3996ca9ab\" d=\"M 0 0 \nL 0 3.5 \n\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </defs>\n      <g>\n       <use xlink:href=\"#me3996ca9ab\" x=\"52.330449\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_1\">\n      <!-- $\\mathdefault{10^{3}}$ -->\n      <g transform=\"translate(43.530449 160.398438) scale(0.1 -0.1)\">\n       <defs>\n        <path id=\"DejaVuSans-31\" d=\"M 794 531 \nL 1825 531 \nL 1825 4091 \nL 703 3866 \nL 703 4441 \nL 1819 4666 \nL 2450 4666 \nL 2450 531 \nL 3481 531 \nL 3481 0 \nL 794 0 \nL 794 531 \nz\n\" transform=\"scale(0.015625)\"/>\n        <path id=\"DejaVuSans-30\" d=\"M 2034 4250 \nQ 1547 4250 1301 3770 \nQ 1056 3291 1056 2328 \nQ 1056 1369 1301 889 \nQ 1547 409 2034 409 \nQ 2525 409 2770 889 \nQ 3016 1369 3016 2328 \nQ 3016 3291 2770 3770 \nQ 2525 4250 2034 4250 \nz\nM 2034 4750 \nQ 2819 4750 3233 4129 \nQ 3647 3509 3647 2328 \nQ 3647 1150 3233 529 \nQ 2819 -91 2034 -91 \nQ 1250 -91 836 529 \nQ 422 1150 422 2328 \nQ 422 3509 836 4129 \nQ 1250 4750 2034 4750 \nz\n\" transform=\"scale(0.015625)\"/>\n        <path id=\"DejaVuSans-33\" d=\"M 2597 2516 \nQ 3050 2419 3304 2112 \nQ 3559 1806 3559 1356 \nQ 3559 666 3084 287 \nQ 2609 -91 1734 -91 \nQ 1441 -91 1130 -33 \nQ 819 25 488 141 \nL 488 750 \nQ 750 597 1062 519 \nQ 1375 441 1716 441 \nQ 2309 441 2620 675 \nQ 2931 909 2931 1356 \nQ 2931 1769 2642 2001 \nQ 2353 2234 1838 2234 \nL 1294 2234 \nL 1294 2753 \nL 1863 2753 \nQ 2328 2753 2575 2939 \nQ 2822 3125 2822 3475 \nQ 2822 3834 2567 4026 \nQ 2313 4219 1838 4219 \nQ 1578 4219 1281 4162 \nQ 984 4106 628 3988 \nL 628 4550 \nQ 988 4650 1302 4700 \nQ 1616 4750 1894 4750 \nQ 2613 4750 3031 4423 \nQ 3450 4097 3450 3541 \nQ 3450 3153 3228 2886 \nQ 3006 2619 2597 2516 \nz\n\" transform=\"scale(0.015625)\"/>\n       </defs>\n       <use xlink:href=\"#DejaVuSans-31\" transform=\"translate(0 0.765625)\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(63.623047 0.765625)\"/>\n       <use xlink:href=\"#DejaVuSans-33\" transform=\"translate(128.203125 39.046875) scale(0.7)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_2\">\n     <g id=\"line2d_3\">\n      <defs>\n       <path id=\"m7c964e20fa\" d=\"M 0 0 \nL 0 2 \n\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </defs>\n      <g>\n       <use xlink:href=\"#m7c964e20fa\" x=\"111.512268\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n     <g id=\"text_2\">\n      <!-- $\\mathdefault{2\\times10^{3}}$ -->\n      <g transform=\"translate(93.412268 158.798438) 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        <path id=\"DejaVuSans-d7\" d=\"M 4488 3438 \nL 3059 2003 \nL 4488 575 \nL 4116 197 \nL 2681 1631 \nL 1247 197 \nL 878 575 \nL 2303 2003 \nL 878 3438 \nL 1247 3816 \nL 2681 2381 \nL 4116 3816 \nL 4488 3438 \nz\n\" transform=\"scale(0.015625)\"/>\n       </defs>\n       <use xlink:href=\"#DejaVuSans-32\" transform=\"translate(0 0.765625)\"/>\n       <use xlink:href=\"#DejaVuSans-d7\" transform=\"translate(83.105469 0.765625)\"/>\n       <use xlink:href=\"#DejaVuSans-31\" transform=\"translate(186.376953 0.765625)\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(250 0.765625)\"/>\n       <use xlink:href=\"#DejaVuSans-33\" transform=\"translate(314.580078 39.046875) scale(0.7)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_3\">\n     <g id=\"line2d_4\">\n      <g>\n       <use xlink:href=\"#m7c964e20fa\" x=\"146.131412\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n     <g id=\"text_3\">\n      <!-- $\\mathdefault{3\\times10^{3}}$ -->\n      <g transform=\"translate(128.031412 158.798438) scale(0.1 -0.1)\">\n       <use xlink:href=\"#DejaVuSans-33\" transform=\"translate(0 0.765625)\"/>\n       <use xlink:href=\"#DejaVuSans-d7\" transform=\"translate(83.105469 0.765625)\"/>\n       <use xlink:href=\"#DejaVuSans-31\" transform=\"translate(186.376953 0.765625)\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(250 0.765625)\"/>\n       <use xlink:href=\"#DejaVuSans-33\" transform=\"translate(314.580078 39.046875) scale(0.7)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_4\">\n     <g id=\"line2d_5\">\n      <g>\n       <use xlink:href=\"#m7c964e20fa\" x=\"170.694086\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n     <g id=\"text_4\">\n      <!-- $\\mathdefault{4\\times10^{3}}$ -->\n      <g transform=\"translate(152.594086 158.798438) scale(0.1 -0.1)\">\n       <defs>\n        <path id=\"DejaVuSans-34\" d=\"M 2419 4116 \nL 825 1625 \nL 2419 1625 \nL 2419 4116 \nz\nM 2253 4666 \nL 3047 4666 \nL 3047 1625 \nL 3713 1625 \nL 3713 1100 \nL 3047 1100 \nL 3047 0 \nL 2419 0 \nL 2419 1100 \nL 313 1100 \nL 313 1709 \nL 2253 4666 \nz\n\" transform=\"scale(0.015625)\"/>\n       </defs>\n       <use xlink:href=\"#DejaVuSans-34\" transform=\"translate(0 0.765625)\"/>\n       <use xlink:href=\"#DejaVuSans-d7\" transform=\"translate(83.105469 0.765625)\"/>\n       <use xlink:href=\"#DejaVuSans-31\" transform=\"translate(186.376953 0.765625)\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(250 0.765625)\"/>\n       <use xlink:href=\"#DejaVuSans-33\" transform=\"translate(314.580078 39.046875) scale(0.7)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_5\">\n     <g id=\"line2d_6\">\n      <g>\n       <use xlink:href=\"#m7c964e20fa\" x=\"189.746376\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_6\">\n     <g id=\"line2d_7\">\n      <g>\n       <use xlink:href=\"#m7c964e20fa\" x=\"205.31323\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n     <g id=\"text_5\">\n      <!-- $\\mathdefault{6\\times10^{3}}$ -->\n      <g transform=\"translate(187.21323 158.798438) scale(0.1 -0.1)\">\n       <defs>\n        <path id=\"DejaVuSans-36\" d=\"M 2113 2584 \nQ 1688 2584 1439 2293 \nQ 1191 2003 1191 1497 \nQ 1191 994 1439 701 \nQ 1688 409 2113 409 \nQ 2538 409 2786 701 \nQ 3034 994 3034 1497 \nQ 3034 2003 2786 2293 \nQ 2538 2584 2113 2584 \nz\nM 3366 4563 \nL 3366 3988 \nQ 3128 4100 2886 4159 \nQ 2644 4219 2406 4219 \nQ 1781 4219 1451 3797 \nQ 1122 3375 1075 2522 \nQ 1259 2794 1537 2939 \nQ 1816 3084 2150 3084 \nQ 2853 3084 3261 2657 \nQ 3669 2231 3669 1497 \nQ 3669 778 3244 343 \nQ 2819 -91 2113 -91 \nQ 1303 -91 875 529 \nQ 447 1150 447 2328 \nQ 447 3434 972 4092 \nQ 1497 4750 2381 4750 \nQ 2619 4750 2861 4703 \nQ 3103 4656 3366 4563 \nz\n\" transform=\"scale(0.015625)\"/>\n       </defs>\n       <use xlink:href=\"#DejaVuSans-36\" transform=\"translate(0 0.765625)\"/>\n       <use xlink:href=\"#DejaVuSans-d7\" transform=\"translate(83.105469 0.765625)\"/>\n       <use xlink:href=\"#DejaVuSans-31\" transform=\"translate(186.376953 0.765625)\"/>\n       <use xlink:href=\"#DejaVuSans-30\" transform=\"translate(250 0.765625)\"/>\n       <use xlink:href=\"#DejaVuSans-33\" transform=\"translate(314.580078 39.046875) scale(0.7)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_7\">\n     <g id=\"line2d_8\">\n      <g>\n       <use xlink:href=\"#m7c964e20fa\" x=\"218.474818\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_8\">\n     <g id=\"line2d_9\">\n      <g>\n       <use xlink:href=\"#m7c964e20fa\" x=\"229.875904\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"xtick_9\">\n     <g id=\"line2d_10\">\n      <g>\n       <use xlink:href=\"#m7c964e20fa\" x=\"239.932375\" y=\"145.8\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"text_6\">\n     <!-- input length N -->\n     <g transform=\"translate(107.410938 174.076563) scale(0.1 -0.1)\">\n      <defs>\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-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-75\" d=\"M 544 1381 \nL 544 3500 \nL 1119 3500 \nL 1119 1403 \nQ 1119 906 1312 657 \nQ 1506 409 1894 409 \nQ 2359 409 2629 706 \nQ 2900 1003 2900 1516 \nL 2900 3500 \nL 3475 3500 \nL 3475 0 \nL 2900 0 \nL 2900 538 \nQ 2691 219 2414 64 \nQ 2138 -91 1772 -91 \nQ 1169 -91 856 284 \nQ 544 659 544 1381 \nz\nM 1991 3584 \nL 1991 3584 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-74\" d=\"M 1172 4494 \nL 1172 3500 \nL 2356 3500 \nL 2356 3053 \nL 1172 3053 \nL 1172 1153 \nQ 1172 725 1289 603 \nQ 1406 481 1766 481 \nL 2356 481 \nL 2356 0 \nL 1766 0 \nQ 1100 0 847 248 \nQ 594 497 594 1153 \nL 594 3053 \nL 172 3053 \nL 172 3500 \nL 594 3500 \nL 594 4494 \nL 1172 4494 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-20\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-6c\" d=\"M 603 4863 \nL 1178 4863 \nL 1178 0 \nL 603 0 \nL 603 4863 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-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-67\" d=\"M 2906 1791 \nQ 2906 2416 2648 2759 \nQ 2391 3103 1925 3103 \nQ 1463 3103 1205 2759 \nQ 947 2416 947 1791 \nQ 947 1169 1205 825 \nQ 1463 481 1925 481 \nQ 2391 481 2648 825 \nQ 2906 1169 2906 1791 \nz\nM 3481 434 \nQ 3481 -459 3084 -895 \nQ 2688 -1331 1869 -1331 \nQ 1566 -1331 1297 -1286 \nQ 1028 -1241 775 -1147 \nL 775 -588 \nQ 1028 -725 1275 -790 \nQ 1522 -856 1778 -856 \nQ 2344 -856 2625 -561 \nQ 2906 -266 2906 331 \nL 2906 616 \nQ 2728 306 2450 153 \nQ 2172 0 1784 0 \nQ 1141 0 747 490 \nQ 353 981 353 1791 \nQ 353 2603 747 3093 \nQ 1141 3584 1784 3584 \nQ 2172 3584 2450 3431 \nQ 2728 3278 2906 2969 \nL 2906 3500 \nL 3481 3500 \nL 3481 434 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-68\" d=\"M 3513 2113 \nL 3513 0 \nL 2938 0 \nL 2938 2094 \nQ 2938 2591 2744 2837 \nQ 2550 3084 2163 3084 \nQ 1697 3084 1428 2787 \nQ 1159 2491 1159 1978 \nL 1159 0 \nL 581 0 \nL 581 4863 \nL 1159 4863 \nL 1159 2956 \nQ 1366 3272 1645 3428 \nQ 1925 3584 2291 3584 \nQ 2894 3584 3203 3211 \nQ 3513 2838 3513 2113 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-4e\" d=\"M 628 4666 \nL 1478 4666 \nL 3547 763 \nL 3547 4666 \nL 4159 4666 \nL 4159 0 \nL 3309 0 \nL 1241 3903 \nL 1241 0 \nL 628 0 \nL 628 4666 \nz\n\" transform=\"scale(0.015625)\"/>\n      </defs>\n      <use xlink:href=\"#DejaVuSans-69\"/>\n      <use xlink:href=\"#DejaVuSans-6e\" transform=\"translate(27.783203 0)\"/>\n      <use xlink:href=\"#DejaVuSans-70\" transform=\"translate(91.162109 0)\"/>\n      <use xlink:href=\"#DejaVuSans-75\" transform=\"translate(154.638672 0)\"/>\n      <use xlink:href=\"#DejaVuSans-74\" transform=\"translate(218.017578 0)\"/>\n      <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(257.226562 0)\"/>\n      <use xlink:href=\"#DejaVuSans-6c\" transform=\"translate(289.013672 0)\"/>\n      <use xlink:href=\"#DejaVuSans-65\" transform=\"translate(316.796875 0)\"/>\n      <use xlink:href=\"#DejaVuSans-6e\" transform=\"translate(378.320312 0)\"/>\n      <use xlink:href=\"#DejaVuSans-67\" transform=\"translate(441.699219 0)\"/>\n      <use xlink:href=\"#DejaVuSans-74\" transform=\"translate(505.175781 0)\"/>\n      <use xlink:href=\"#DejaVuSans-68\" transform=\"translate(544.384766 0)\"/>\n      <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(607.763672 0)\"/>\n      <use xlink:href=\"#DejaVuSans-4e\" transform=\"translate(639.550781 0)\"/>\n     </g>\n    </g>\n   </g>\n   <g id=\"matplotlib.axis_2\">\n    <g id=\"ytick_1\">\n     <g id=\"line2d_11\">\n      <path d=\"M 45.478125 139.245663 \nL 240.778125 139.245663 \n\" clip-path=\"url(#pf96d8c46ba)\" style=\"fill: none; stroke: #b0b0b0; stroke-width: 0.8; stroke-linecap: square\"/>\n     </g>\n     <g id=\"line2d_12\">\n      <defs>\n       <path id=\"m1cb33679d8\" d=\"M 0 0 \nL -3.5 0 \n\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </defs>\n      <g>\n       <use xlink:href=\"#m1cb33679d8\" x=\"45.478125\" y=\"139.245663\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_7\">\n      <!-- $\\mathdefault{10^{0}}$ -->\n      <g transform=\"translate(20.878125 143.044882) 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-30\" transform=\"translate(128.203125 39.046875) scale(0.7)\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_2\">\n     <g id=\"line2d_13\">\n      <path d=\"M 45.478125 57.672468 \nL 240.778125 57.672468 \n\" clip-path=\"url(#pf96d8c46ba)\" style=\"fill: none; stroke: #b0b0b0; stroke-width: 0.8; stroke-linecap: square\"/>\n     </g>\n     <g id=\"line2d_14\">\n      <g>\n       <use xlink:href=\"#m1cb33679d8\" x=\"45.478125\" y=\"57.672468\" style=\"stroke: #000000; stroke-width: 0.8\"/>\n      </g>\n     </g>\n     <g id=\"text_8\">\n      <!-- $\\mathdefault{10^{1}}$ -->\n      <g transform=\"translate(20.878125 61.471687) 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=\"ytick_3\">\n     <g id=\"line2d_15\">\n      <defs>\n       <path id=\"m06428f981d\" d=\"M 0 0 \nL -2 0 \n\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </defs>\n      <g>\n       <use xlink:href=\"#m06428f981d\" x=\"45.478125\" y=\"142.978248\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_4\">\n     <g id=\"line2d_16\">\n      <g>\n       <use xlink:href=\"#m06428f981d\" x=\"45.478125\" y=\"114.689685\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_5\">\n     <g id=\"line2d_17\">\n      <g>\n       <use xlink:href=\"#m06428f981d\" x=\"45.478125\" y=\"100.325358\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_6\">\n     <g id=\"line2d_18\">\n      <g>\n       <use xlink:href=\"#m06428f981d\" x=\"45.478125\" y=\"90.133706\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_7\">\n     <g id=\"line2d_19\">\n      <g>\n       <use xlink:href=\"#m06428f981d\" x=\"45.478125\" y=\"82.228447\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_8\">\n     <g id=\"line2d_20\">\n      <g>\n       <use xlink:href=\"#m06428f981d\" x=\"45.478125\" y=\"75.769379\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_9\">\n     <g id=\"line2d_21\">\n      <g>\n       <use xlink:href=\"#m06428f981d\" x=\"45.478125\" y=\"70.308316\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_10\">\n     <g id=\"line2d_22\">\n      <g>\n       <use xlink:href=\"#m06428f981d\" x=\"45.478125\" y=\"65.577728\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_11\">\n     <g id=\"line2d_23\">\n      <g>\n       <use xlink:href=\"#m06428f981d\" x=\"45.478125\" y=\"61.405053\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_12\">\n     <g id=\"line2d_24\">\n      <g>\n       <use xlink:href=\"#m06428f981d\" x=\"45.478125\" y=\"33.11649\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_13\">\n     <g id=\"line2d_25\">\n      <g>\n       <use xlink:href=\"#m06428f981d\" x=\"45.478125\" y=\"18.752163\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"ytick_14\">\n     <g id=\"line2d_26\">\n      <g>\n       <use xlink:href=\"#m06428f981d\" x=\"45.478125\" y=\"8.560511\" style=\"stroke: #000000; stroke-width: 0.6\"/>\n      </g>\n     </g>\n    </g>\n    <g id=\"text_9\">\n     <!-- forward time (ms) -->\n     <g transform=\"translate(14.798438 121.521094) rotate(-90) scale(0.1 -0.1)\">\n      <defs>\n       <path id=\"DejaVuSans-66\" d=\"M 2375 4863 \nL 2375 4384 \nL 1825 4384 \nQ 1516 4384 1395 4259 \nQ 1275 4134 1275 3809 \nL 1275 3500 \nL 2222 3500 \nL 2222 3053 \nL 1275 3053 \nL 1275 0 \nL 697 0 \nL 697 3053 \nL 147 3053 \nL 147 3500 \nL 697 3500 \nL 697 3744 \nQ 697 4328 969 4595 \nQ 1241 4863 1831 4863 \nL 2375 4863 \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-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-77\" d=\"M 269 3500 \nL 844 3500 \nL 1563 769 \nL 2278 3500 \nL 2956 3500 \nL 3675 769 \nL 4391 3500 \nL 4966 3500 \nL 4050 0 \nL 3372 0 \nL 2619 2869 \nL 1863 0 \nL 1184 0 \nL 269 3500 \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-64\" d=\"M 2906 2969 \nL 2906 4863 \nL 3481 4863 \nL 3481 0 \nL 2906 0 \nL 2906 525 \nQ 2725 213 2448 61 \nQ 2172 -91 1784 -91 \nQ 1150 -91 751 415 \nQ 353 922 353 1747 \nQ 353 2572 751 3078 \nQ 1150 3584 1784 3584 \nQ 2172 3584 2448 3432 \nQ 2725 3281 2906 2969 \nz\nM 947 1747 \nQ 947 1113 1208 752 \nQ 1469 391 1925 391 \nQ 2381 391 2643 752 \nQ 2906 1113 2906 1747 \nQ 2906 2381 2643 2742 \nQ 2381 3103 1925 3103 \nQ 1469 3103 1208 2742 \nQ 947 2381 947 1747 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-6d\" d=\"M 3328 2828 \nQ 3544 3216 3844 3400 \nQ 4144 3584 4550 3584 \nQ 5097 3584 5394 3201 \nQ 5691 2819 5691 2113 \nL 5691 0 \nL 5113 0 \nL 5113 2094 \nQ 5113 2597 4934 2840 \nQ 4756 3084 4391 3084 \nQ 3944 3084 3684 2787 \nQ 3425 2491 3425 1978 \nL 3425 0 \nL 2847 0 \nL 2847 2094 \nQ 2847 2600 2669 2842 \nQ 2491 3084 2119 3084 \nQ 1678 3084 1418 2786 \nQ 1159 2488 1159 1978 \nL 1159 0 \nL 581 0 \nL 581 3500 \nL 1159 3500 \nL 1159 2956 \nQ 1356 3278 1631 3431 \nQ 1906 3584 2284 3584 \nQ 2666 3584 2933 3390 \nQ 3200 3197 3328 2828 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-28\" d=\"M 1984 4856 \nQ 1566 4138 1362 3434 \nQ 1159 2731 1159 2009 \nQ 1159 1288 1364 580 \nQ 1569 -128 1984 -844 \nL 1484 -844 \nQ 1016 -109 783 600 \nQ 550 1309 550 2009 \nQ 550 2706 781 3412 \nQ 1013 4119 1484 4856 \nL 1984 4856 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-73\" d=\"M 2834 3397 \nL 2834 2853 \nQ 2591 2978 2328 3040 \nQ 2066 3103 1784 3103 \nQ 1356 3103 1142 2972 \nQ 928 2841 928 2578 \nQ 928 2378 1081 2264 \nQ 1234 2150 1697 2047 \nL 1894 2003 \nQ 2506 1872 2764 1633 \nQ 3022 1394 3022 966 \nQ 3022 478 2636 193 \nQ 2250 -91 1575 -91 \nQ 1294 -91 989 -36 \nQ 684 19 347 128 \nL 347 722 \nQ 666 556 975 473 \nQ 1284 391 1588 391 \nQ 1994 391 2212 530 \nQ 2431 669 2431 922 \nQ 2431 1156 2273 1281 \nQ 2116 1406 1581 1522 \nL 1381 1569 \nQ 847 1681 609 1914 \nQ 372 2147 372 2553 \nQ 372 3047 722 3315 \nQ 1072 3584 1716 3584 \nQ 2034 3584 2315 3537 \nQ 2597 3491 2834 3397 \nz\n\" transform=\"scale(0.015625)\"/>\n       <path id=\"DejaVuSans-29\" d=\"M 513 4856 \nL 1013 4856 \nQ 1481 4119 1714 3412 \nQ 1947 2706 1947 2009 \nQ 1947 1309 1714 600 \nQ 1481 -109 1013 -844 \nL 513 -844 \nQ 928 -128 1133 580 \nQ 1338 1288 1338 2009 \nQ 1338 2731 1133 3434 \nQ 928 4138 513 4856 \nz\n\" transform=\"scale(0.015625)\"/>\n      </defs>\n      <use xlink:href=\"#DejaVuSans-66\"/>\n      <use xlink:href=\"#DejaVuSans-6f\" transform=\"translate(35.205078 0)\"/>\n      <use xlink:href=\"#DejaVuSans-72\" transform=\"translate(96.386719 0)\"/>\n      <use xlink:href=\"#DejaVuSans-77\" transform=\"translate(137.5 0)\"/>\n      <use xlink:href=\"#DejaVuSans-61\" transform=\"translate(219.287109 0)\"/>\n      <use xlink:href=\"#DejaVuSans-72\" transform=\"translate(280.566406 0)\"/>\n      <use xlink:href=\"#DejaVuSans-64\" transform=\"translate(319.929688 0)\"/>\n      <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(383.40625 0)\"/>\n      <use xlink:href=\"#DejaVuSans-74\" transform=\"translate(415.193359 0)\"/>\n      <use xlink:href=\"#DejaVuSans-69\" transform=\"translate(454.402344 0)\"/>\n      <use xlink:href=\"#DejaVuSans-6d\" transform=\"translate(482.185547 0)\"/>\n      <use xlink:href=\"#DejaVuSans-65\" transform=\"translate(579.597656 0)\"/>\n      <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(641.121094 0)\"/>\n      <use xlink:href=\"#DejaVuSans-28\" transform=\"translate(672.908203 0)\"/>\n      <use xlink:href=\"#DejaVuSans-6d\" transform=\"translate(711.921875 0)\"/>\n      <use xlink:href=\"#DejaVuSans-73\" transform=\"translate(809.333984 0)\"/>\n      <use xlink:href=\"#DejaVuSans-29\" transform=\"translate(861.433594 0)\"/>\n     </g>\n    </g>\n   </g>\n   <g id=\"line2d_27\">\n    <path d=\"M 54.355398 139.5 \nL 113.537216 102.814684 \nL 172.719034 59.625908 \nL 231.900852 13.5 \n\" clip-path=\"url(#pf96d8c46ba)\" style=\"fill: none; stroke: #1f77b4; stroke-width: 1.5; stroke-linecap: square\"/>\n   </g>\n   <g id=\"line2d_28\">\n    <path d=\"M 54.355398 129.58892 \nL 113.537216 127.238916 \nL 172.719034 128.591157 \nL 231.900852 120.034834 \n\" clip-path=\"url(#pf96d8c46ba)\" style=\"fill: none; stroke-dasharray: 5.55,2.4; stroke-dashoffset: 0; stroke: #bf00bf; stroke-width: 1.5\"/>\n   </g>\n   <g id=\"patch_3\">\n    <path d=\"M 45.478125 145.8 \nL 45.478125 7.2 \n\" style=\"fill: none; stroke: #000000; stroke-width: 0.8; stroke-linejoin: miter; stroke-linecap: square\"/>\n   </g>\n   <g id=\"patch_4\">\n    <path d=\"M 240.778125 145.8 \nL 240.778125 7.2 \n\" style=\"fill: none; stroke: #000000; stroke-width: 0.8; stroke-linejoin: miter; stroke-linecap: square\"/>\n   </g>\n   <g id=\"patch_5\">\n    <path d=\"M 45.478125 145.8 \nL 240.778125 145.8 \n\" style=\"fill: none; stroke: #000000; stroke-width: 0.8; stroke-linejoin: miter; stroke-linecap: square\"/>\n   </g>\n   <g id=\"patch_6\">\n    <path d=\"M 45.478125 7.2 \nL 240.778125 7.2 \n\" style=\"fill: none; stroke: #000000; stroke-width: 0.8; stroke-linejoin: miter; stroke-linecap: square\"/>\n   </g>\n   <g id=\"legend_1\">\n    <g id=\"patch_7\">\n     <path d=\"M 52.478125 44.55625 \nL 194.709375 44.55625 \nQ 196.709375 44.55625 196.709375 42.55625 \nL 196.709375 14.2 \nQ 196.709375 12.2 194.709375 12.2 \nL 52.478125 12.2 \nQ 50.478125 12.2 50.478125 14.2 \nL 50.478125 42.55625 \nQ 50.478125 44.55625 52.478125 44.55625 \nz\n\" style=\"fill: #ffffff; opacity: 0.8; stroke: #cccccc; stroke-linejoin: miter\"/>\n    </g>\n    <g id=\"line2d_29\">\n     <path d=\"M 54.478125 20.298438 \nL 64.478125 20.298438 \nL 74.478125 20.298438 \n\" style=\"fill: none; stroke: #1f77b4; stroke-width: 1.5; stroke-linecap: square\"/>\n    </g>\n    <g id=\"text_10\">\n     <!-- self-attention encoder -->\n     <g transform=\"translate(82.478125 23.798438) 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-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      </defs>\n      <use xlink:href=\"#DejaVuSans-73\"/>\n      <use xlink:href=\"#DejaVuSans-65\" transform=\"translate(52.099609 0)\"/>\n      <use xlink:href=\"#DejaVuSans-6c\" transform=\"translate(113.623047 0)\"/>\n      <use xlink:href=\"#DejaVuSans-66\" transform=\"translate(141.40625 0)\"/>\n      <use xlink:href=\"#DejaVuSans-2d\" transform=\"translate(171.111328 0)\"/>\n      <use xlink:href=\"#DejaVuSans-61\" transform=\"translate(207.195312 0)\"/>\n      <use xlink:href=\"#DejaVuSans-74\" transform=\"translate(268.474609 0)\"/>\n      <use xlink:href=\"#DejaVuSans-74\" transform=\"translate(307.683594 0)\"/>\n      <use xlink:href=\"#DejaVuSans-65\" transform=\"translate(346.892578 0)\"/>\n      <use xlink:href=\"#DejaVuSans-6e\" transform=\"translate(408.416016 0)\"/>\n      <use xlink:href=\"#DejaVuSans-74\" transform=\"translate(471.794922 0)\"/>\n      <use xlink:href=\"#DejaVuSans-69\" transform=\"translate(511.003906 0)\"/>\n      <use xlink:href=\"#DejaVuSans-6f\" transform=\"translate(538.787109 0)\"/>\n      <use xlink:href=\"#DejaVuSans-6e\" transform=\"translate(599.96875 0)\"/>\n      <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(663.347656 0)\"/>\n      <use xlink:href=\"#DejaVuSans-65\" transform=\"translate(695.134766 0)\"/>\n      <use xlink:href=\"#DejaVuSans-6e\" transform=\"translate(756.658203 0)\"/>\n      <use xlink:href=\"#DejaVuSans-63\" transform=\"translate(820.037109 0)\"/>\n      <use xlink:href=\"#DejaVuSans-6f\" transform=\"translate(875.017578 0)\"/>\n      <use xlink:href=\"#DejaVuSans-64\" transform=\"translate(936.199219 0)\"/>\n      <use xlink:href=\"#DejaVuSans-65\" transform=\"translate(999.675781 0)\"/>\n      <use xlink:href=\"#DejaVuSans-72\" transform=\"translate(1061.199219 0)\"/>\n     </g>\n    </g>\n    <g id=\"line2d_30\">\n     <path d=\"M 54.478125 34.976562 \nL 64.478125 34.976562 \nL 74.478125 34.976562 \n\" style=\"fill: none; stroke-dasharray: 5.55,2.4; stroke-dashoffset: 0; stroke: #bf00bf; stroke-width: 1.5\"/>\n    </g>\n    <g id=\"text_11\">\n     <!-- perceiver encoder -->\n     <g transform=\"translate(82.478125 38.476562) 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-70\"/>\n      <use xlink:href=\"#DejaVuSans-65\" transform=\"translate(63.476562 0)\"/>\n      <use xlink:href=\"#DejaVuSans-72\" transform=\"translate(125 0)\"/>\n      <use xlink:href=\"#DejaVuSans-63\" transform=\"translate(163.863281 0)\"/>\n      <use xlink:href=\"#DejaVuSans-65\" transform=\"translate(218.84375 0)\"/>\n      <use xlink:href=\"#DejaVuSans-69\" transform=\"translate(280.367188 0)\"/>\n      <use xlink:href=\"#DejaVuSans-76\" transform=\"translate(308.150391 0)\"/>\n      <use xlink:href=\"#DejaVuSans-65\" transform=\"translate(367.330078 0)\"/>\n      <use xlink:href=\"#DejaVuSans-72\" transform=\"translate(428.853516 0)\"/>\n      <use xlink:href=\"#DejaVuSans-20\" transform=\"translate(469.966797 0)\"/>\n      <use xlink:href=\"#DejaVuSans-65\" transform=\"translate(501.753906 0)\"/>\n      <use xlink:href=\"#DejaVuSans-6e\" transform=\"translate(563.277344 0)\"/>\n      <use xlink:href=\"#DejaVuSans-63\" transform=\"translate(626.65625 0)\"/>\n      <use xlink:href=\"#DejaVuSans-6f\" transform=\"translate(681.636719 0)\"/>\n      <use xlink:href=\"#DejaVuSans-64\" transform=\"translate(742.818359 0)\"/>\n      <use xlink:href=\"#DejaVuSans-65\" transform=\"translate(806.294922 0)\"/>\n      <use xlink:href=\"#DejaVuSans-72\" transform=\"translate(867.818359 0)\"/>\n     </g>\n    </g>\n   </g>\n  </g>\n </g>\n <defs>\n  <clipPath id=\"pf96d8c46ba\">\n   <rect x=\"45.478125\" y=\"7.2\" width=\"195.3\" height=\"138.6\"/>\n  </clipPath>\n </defs>\n</svg>\n"
     },
     "metadata": {}
    }
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- d2l:prose id=encoders-decoders-md-15 fw=all -->\n",
    "\n",
    "Each doubling of $N$ eventually multiplies the self-attention encoder's\n",
    "time by about four, the signature of an $N^2$ term taking over. The\n",
    "Perceiver's time barely moves (its $O(MN)$ cross-attention grows\n",
    "linearly but stays dominated by the fixed $O(M^2)$ latent processing),\n",
    "and by $N = 8192$ the gap exceeds an order of magnitude. The left end of\n",
    "the plot belongs in the reading too: at short inputs the bottleneck\n",
    "buys nothing, and full self-attention is as fast or faster. A latent\n",
    "bottleneck is worth having when the input is long and a fixed-size\n",
    "summary of it suffices.\n",
    "\n",
    "### Perceiver IO and the Idea's Descendants\n",
    "\n",
    "Reading through learned queries has a mirror image: *writing* through\n",
    "them. Perceiver IO [@Jaegle.Borgeaud.Alayrac.ea.2022] adds an output\n",
    "query array that cross-attends *out of* the latent summary, so the output\n",
    "size and shape are set by the queries rather than by the input — one\n",
    "query for a classification label, one per pixel for optical flow, one per\n",
    "audio sample for a waveform. Input length, latent width, and output shape\n",
    "become three independent dials, with everything in between a fixed-cost\n",
    "transformer.\n",
    "\n",
    "The pattern's descendants run through today's multimodal systems.\n",
    "Flamingo's Perceiver resampler compresses a variable number of image and\n",
    "video features into a fixed handful of visual tokens before a frozen\n",
    "language model ever sees them [@alayrac2022flamingo]; BLIP-2's\n",
    "Q-Former is a small stack of learned query tokens that bridges a frozen\n",
    "vision encoder and a frozen LLM [@Li.Li.Savarese.ea.2023]; learned\n",
    "query tokens remain one of the two standard interfaces in current\n",
    "vision--language models — the other is a plain learned projection applied\n",
    "patch by patch. DETR had already used the query-token device for detection — a\n",
    "hundred learned object queries cross-attend into image features, each\n",
    "producing one detection [@Carion.Massa.Synnaeve.ea.2020]. The Image\n",
    "Models part (that section) takes up DETR and its successors in\n",
    "depth.\n",
    "\n",
    "## Which Wiring When\n",
    "\n",
    "The taxonomy of the figure maps cleanly onto current\n",
    "practice:\n",
    "\n",
    "| Wiring | Exemplars today | Typical use |\n",
    "|---|---|---|\n",
    "| encoder-only | BERT descendants, ModernBERT | embeddings, retrieval, classification |\n",
    "| encoder--decoder | T5 family, Whisper | translation, speech recognition |\n",
    "| decoder-only | essentially everything else | generation, chat, in-context everything |\n",
    "\n",
    "Encoder-only survives where the product *is* the representation: an\n",
    "embedding model is run once per document, at bidirectional quality, with\n",
    "no generation loop to pay for — which is why retrieval and reranking\n",
    "stacks still train BERT-shaped models\n",
    "[@Warner.Chaffin.Clavie.ea.2024]. The encoder--decoder survives\n",
    "where the input is fully known before generation starts and deserves its\n",
    "own tower: T5-style text-to-text [@raffel2020exploring], and Whisper,\n",
    "whose encoder reads an entire audio clip bidirectionally while a text\n",
    "decoder cross-attends into it [@radford2023whisper].\n",
    "\n",
    "Everything else went decoder-only, and the reasons compound. One stack\n",
    "means one pretraining objective: next-token prediction on raw text, with\n",
    "no masking scheme or span-corruption design to engineer. Every parameter\n",
    "serves both understanding and generation instead of splitting the budget\n",
    "between towers. Generation needs no separate machinery, and in-context\n",
    "learning falls out of it [@brown2020language]: a task description in\n",
    "the prompt does what a fine-tuned head used to. When one architecture,\n",
    "trained one way, covers everything from chat to code with the same\n",
    "serving stack, the coordination costs of maintaining three wirings stop\n",
    "being worth paying — except in the niches above, where the other two are\n",
    "simply better tools.\n",
    "\n",
    "## Summary\n",
    "\n",
    "One transformer block supports three wirings. Removing the causal mask\n",
    "gives an encoder-only model: not a left-to-right generator, but the\n",
    "strongest way to compute one representation per token, trained by masking\n",
    "tokens and\n",
    "predicting them from both sides; in our character-level demo, positions\n",
    "with context on both sides had roughly half the loss of one-sided\n",
    "positions, which is the bidirectional advantage in one number.\n",
    "The encoder--decoder joins an unmasked encoder to a causal decoder\n",
    "through cross-attention; on a reversal task whose true alignment is known\n",
    "by construction, the learned cross-attention map reproduces the\n",
    "anti-diagonal almost exactly. Cross-attention also works with queries\n",
    "that come from no sequence at all: a learned latent array reading a\n",
    "length-$N$ input costs $O(MN)$ instead of $O(N^2)$, stays nearly constant\n",
    "in measured time as $N$ grows, and under the names Perceiver, resampler,\n",
    "and Q-Former is how today's multimodal models feed long perceptual\n",
    "streams into fixed-size computation. In current practice encoders own\n",
    "representation (retrieval, classification), encoder--decoders own tasks\n",
    "with a fully-known input in another modality or length regime\n",
    "(translation, speech), and decoder-only owns the rest — one model, one\n",
    "objective, generation for free.\n",
    "\n",
    "## Exercises\n",
    "\n",
    "1. Our masking always writes `<mask>`. BERT instead replaces the chosen\n",
    "   position with `<mask>` 80% of the time, a random token 10%, and the\n",
    "   original token 10% [@Devlin.Chang.Lee.ea.2018] — partly because\n",
    "   `<mask>` never appears when the pretrained encoder is used on real\n",
    "   text. Implement the 80/10/10 rule and compare masked accuracy and the\n",
    "   loss on inputs containing no `<mask>` at all.\n",
    "2. Mask two *adjacent* characters instead of one and evaluate the loss at\n",
    "   both positions. Explain the change using the per-position analysis of\n",
    "   this section: what context did each masked character lose?\n",
    "3. Widen the encoder--decoder to `num_blks=2` and rerun the alignment\n",
    "   check and the heatmaps. The task remains solved; what happens to the\n",
    "   argmax hit rate and the attention mass on the true source position?\n",
    "   Reconcile this with the warnings about reading attention maps in\n",
    "   that section.\n",
    "4. Change one line of `sample_batch` to make the task *copy* instead of\n",
    "   reverse, and predict the heatmap before rerunning. Then try\n",
    "   reverse-then-copy with `T` even: target = reversed source for the\n",
    "   first half's length, then the source itself. What alignment do you\n",
    "   expect in each half of the map?\n",
    "5. Sweep the number of latents $M \\in \\{16, 64, 256\\}$ in the cost-curve\n",
    "   experiment. Where does the crossover with full self-attention move,\n",
    "   and why? Derive the FLOP count of `PerceiverEncoder.forward` as a\n",
    "   function of $M$, $N$, and $d$, and check which term dominates at each\n",
    "   $M$.\n",
    "6. Build a minimal Perceiver IO head: a second learned query array of\n",
    "   length $K$ that cross-attends into the latent summary and produces\n",
    "   output shape $(B, K, d)$. Verify the shape, then argue the total cost\n",
    "   is $O(MN + M^2 + KM)$ and state when this beats attaching the output\n",
    "   queries to the input directly."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "name": "d2l-pytorch",
   "display_name": "d2l (PyTorch)",
   "language": "python"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
