SPB Git

Repository Public

kv-cache.tsx 7.8 KB 122 lines tsx

1import type { Locale } from "@/schema";2import { param, type SimDef } from "../types";3import { Chart, chartSpec } from "../ui/Chart";4import { fmt, fmtInt, px } from "../ui/format";5import { Readouts } from "../ui/Readouts";67export interface KvStep {8  /** Tokens in the context when this token is generated (prompt + tokens generated so far). */9  n: number;10  /** Without cache: key/value pairs computed and query–key scores evaluated at this step. */11  plainKv: number; plainScores: number;12  /** With cache: key/value pairs computed, reused from the cache, and scores evaluated. */13  cacheKv: number; cacheReused: number; cacheScores: number;14}15export interface KvModel {16  prompt: number; newTokens: number; layers: number;17  steps: KvStep[];18  cumPlainScores: number[]; cumCacheScores: number[]; cumPlainKv: number[]; cumCacheKv: number[];19}2021/**22 * Exact counts for causal self-attention, per attention head.23 * Step s (1 … G) sees n = P + s − 1 tokens. Without cache the whole prefix is re-encoded: n keys/values per layer and24 * n(n+1)/2 query–key scores per layer. With a cache, step 1 encodes the prompt (same cost), then each step encodes25 * one new token: 1 key/value per layer and n scores per layer (its query against the n cached keys, itself included).26 */27export function computeKv(p: Readonly<Record<string, number>>): KvModel {28  const prompt = Math.round(p.prompt), newTokens = Math.round(p.newTokens), layers = Math.round(p.layers);29  const steps: KvStep[] = [];30  const cumPlainScores: number[] = [], cumCacheScores: number[] = [], cumPlainKv: number[] = [], cumCacheKv: number[] = [];31  let a = 0, b = 0, c = 0, d = 0;32  for (let s = 1; s <= newTokens; s++) {33    const n = prompt + s - 1;34    const tri = (n * (n + 1)) / 2;35    const st: KvStep = {36      n, plainKv: layers * n, plainScores: layers * tri,37      cacheKv: layers * (s === 1 ? n : 1), cacheReused: layers * (s === 1 ? 0 : n - 1), cacheScores: layers * (s === 1 ? tri : n),38    };39    steps.push(st);40    a += st.plainScores; b += st.cacheScores; c += st.plainKv; d += st.cacheKv;41    cumPlainScores.push(a); cumCacheScores.push(b); cumPlainKv.push(c); cumCacheKv.push(d);42  }43  return { prompt, newTokens, layers, steps, cumPlainScores, cumCacheScores, cumPlainKv, cumCacheKv };44}4546const TXT = {47  fr: { aria: "Clés et valeurs recalculées ou réutilisées à chaque jeton généré", plain: "Sans cache", cache: "Avec cache KV", computed: "K, V calculés à cette étape", reused: "K, V lus dans le cache", future: "pas encore dans le contexte", pos: "Position dans la séquence", promptEnd: "fin de l'invite", step: "Jeton généré", ctx: "Jetons dans le contexte", kv: "K/V calculés à cette étape (sans / avec)", sc: "Scores d'attention à cette étape (sans / avec)", cum: "Scores cumulés (sans / avec)", ratio: "Rapport cumulé", chart: "Scores d'attention cumulés", x: "Jeton généré", y: "Scores requête–clé cumulés", here: "étape courante" },48  en: { aria: "Keys and values recomputed or reused at each generated token", plain: "No cache", cache: "With KV cache", computed: "K, V computed at this step", reused: "K, V read from the cache", future: "not in the context yet", pos: "Position in the sequence", promptEnd: "end of prompt", step: "Generated token", ctx: "Tokens in context", kv: "K/V computed at this step (without / with)", sc: "Attention scores at this step (without / with)", cum: "Cumulative scores (without / with)", ratio: "Cumulative ratio", chart: "Cumulative attention scores", x: "Generated token", y: "Cumulative query–key scores", here: "current step" },49} as const;5051function KvView({ model: m, locale, step, idPrefix }: { model: KvModel; locale: Locale; step: number; idPrefix: string }) {52  const L = TXT[locale];53  const s = Math.min(Math.max(0, step), m.steps.length - 1);54  const st = m.steps[s];55  const total = m.prompt + m.newTokens - 1;56  const W = 560, left = 118, cell = Math.min(28, (W - left - 10) / total), H = 128;57  const rowsY = [34, 76];58  const state = (row: 0 | 1, i: number): "computed" | "reused" | "future" => {59    if (i >= st.n) return "future";60    if (row === 0 || s === 0) return "computed";61    return i === st.n - 1 ? "computed" : "reused";62  };63  const pair = (a: number, b: number) => `${fmtInt(locale, a)} / ${fmtInt(locale, b)}`;64  const chart = chartSpec({65    kind: "line", dataKind: "illustrative", title: L.chart, xLabel: L.x, yLabel: L.y,66    series: [67      { name: L.plain, tone: "amber", points: m.cumPlainScores.map((y, i) => ({ x: i + 1, y })) },68      { name: L.cache, tone: "teal", points: m.cumCacheScores.map((y, i) => ({ x: i + 1, y })) },69    ],70    annotations: [{ x: s + 1, label: L.here }],71  });72  return (73    <>74      <svg viewBox={`0 0 ${W} ${H}`} role="img" aria-label={L.aria} className="sim-svg sim-kv">75        <text x={left} y={16} className="sim-label">{L.pos}</text>76        {([0, 1] as const).map((row) => (77          <g key={row}>78            <text x={left - 10} y={rowsY[row] + 19} textAnchor="end" className="sim-label">{row === 0 ? L.plain : L.cache}</text>79            {Array.from({ length: total }, (_, i) => (80              <rect key={i} x={px(left + i * cell + 1.5)} y={rowsY[row]} width={px(cell - 3)} height={28} rx={5} className="sim-kv-cell" data-state={state(row, i)} />81            ))}82          </g>83        ))}84        <line x1={px(left + m.prompt * cell)} x2={px(left + m.prompt * cell)} y1={26} y2={110} className="sim-kv-sep" />85        <text x={px(left + m.prompt * cell + 4)} y={122} className="sim-tick">{L.promptEnd}</text>86      </svg>87      <ul className="sim-legend">88        <li><span className="sim-swatch" style={{ background: "var(--sh-t-amber)" }} />{L.computed}</li>89        <li><span className="sim-swatch" style={{ background: "var(--sh-t-teal-soft)", borderColor: "var(--sh-t-teal)" }} />{L.reused}</li>90        <li><span className="sim-swatch" style={{ background: "none", borderColor: "var(--sh-line)", borderStyle: "dashed" }} />{L.future}</li>91      </ul>92      <Readouts items={[93        { label: L.step, value: `${fmtInt(locale, s + 1)} / ${fmtInt(locale, m.newTokens)}` },94        { label: L.ctx, value: fmtInt(locale, st.n) },95        { label: L.kv, value: pair(st.plainKv, st.cacheKv) },96        { label: L.sc, value: pair(st.plainScores, st.cacheScores) },97        { label: L.cum, value: pair(m.cumPlainScores[s], m.cumCacheScores[s]) },98        { label: L.ratio, value: `${fmt(locale, m.cumPlainScores[s] / m.cumCacheScores[s], 1)} ×`, tone: "teal" },99      ]} />100      <Chart chart={chart} locale={locale} idPrefix={`${idPrefix}-c`} height={280} />101    </>102  );103}104105export const kvCache: SimDef<KvModel> = {106  kind: "kv-cache",107  title: { fr: "Génération autorégressive avec et sans cache KV", en: "Autoregressive generation with and without a KV cache" },108  description: {109    fr: "Sans cache, chaque nouveau jeton oblige à réencoder tout le préfixe : $n$ clés/valeurs et $n(n+1)/2$ scores requête–clé par couche. Avec le cache, seules la clé et la valeur du dernier jeton sont calculées, et sa requête est comparée aux $n$ clés : $n$ scores par couche. Décompte exact par tête d'attention, attention causale ; le coût des couches denses (MLP) n'est pas compté.",110    en: "Without a cache, each new token re-encodes the whole prefix: $n$ keys/values and $n(n+1)/2$ query–key scores per layer. With the cache, only the last token's key and value are computed and its query is compared with the $n$ keys: $n$ scores per layer. Exact count per attention head, causal attention; the cost of the dense (MLP) layers is not counted.",111  },112  params: [113    param("prompt", "Longueur de l'invite", "Prompt length", 1, 8, 1, 4),114    param("newTokens", "Jetons générés", "Generated tokens", 2, 16, 1, 8),115    param("layers", "Couches", "Layers", 1, 12, 1, 4),116  ],117  stochastic: false,118  compute: (p) => computeKv(p),119  steps: (m) => m.steps.length,120  View: KvView,121};122
Files main
Menu

Theme