\documentclass[aspectratio=169,11pt]{beamer}
\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage{lmodern}
\usepackage{amsmath,amssymb,graphicx,booktabs}

\definecolor{AcademicBlue}{RGB}{26,57,86}
\definecolor{AcademicTeal}{RGB}{0,105,112}
\setbeamercolor{structure}{fg=AcademicBlue}
\setbeamercolor{frametitle}{fg=AcademicBlue,bg=white}
\setbeamercolor{title}{fg=AcademicBlue}
\setbeamercolor{alerted text}{fg=AcademicTeal}
\setbeamercolor{block title}{fg=white,bg=AcademicBlue}
\setbeamercolor{block body}{fg=black,bg=AcademicBlue!5}
\setbeamertemplate{navigation symbols}{}
\setbeamertemplate{itemize items}[circle]
\setbeamertemplate{footline}{\hfill\usebeamerfont{page number in head/foot}\insertframenumber\,/\,\inserttotalframenumber\hspace{4mm}\vspace{3mm}}
\setbeamersize{text margin left=8mm,text margin right=8mm}
\setbeamerfont{frametitle}{size=\Large,series=\bfseries}
\setbeamerfont{title}{size=\LARGE,series=\bfseries}
\newcommand{\papersource}[1]{\par\smallskip{\scriptsize\color{gray}#1\par}}
\newcommand{\good}[1]{{\color{AcademicTeal}\bfseries #1}}

\title[ParisKV]{ParisKV: Fast and Drift-Robust\\KV-Cache Retrieval}
\subtitle{Long-context LLM inference: a research paper discussion}
\author{Paper by Yanlin Qi, Xinhang Chen, Huiqiang Jiang,\\Qitong Wang, Botao Peng, and Themis Palpanas}
\date{ICML 2026 \quad \href{https://arxiv.org/abs/2602.07721v3}{arXiv:2602.07721v3}\\Reading: 26 October 2026}

\begin{document}
\begin{frame}
  \titlepage
\end{frame}

\begin{frame}{ParisKV combines stable routing with selective KV transfer}
  \begin{block}{Core idea}
  Keep compact key summaries on GPU; use fixed spherical direction codes to shortlist keys, then estimate raw attention scores from 4-bit summaries.
  \end{block}
  \begin{itemize}
    \item Full-precision KV resides in CPU memory; UVA fetches only final Top-$100$ pairs.
    \item On long-generation reasoning, accuracy meets or exceeds full attention in 7 of 9 model--task settings.
    \item At 1024K context, Llama3.1-8B decode latency is 49 ms/step versus 830 and 2179 ms/step for MagicPIG and PQCache.
  \end{itemize}
  \papersource{Paper, Secs. 4--5, PDF pp. 3--8; Appendix D, PDF p. 20. Different methods use their recommended retrieval budgets.}
\end{frame}

\begin{frame}{Long decoding makes prefill-trained centroids stale}
  \centering
  \includegraphics[width=0.96\linewidth,height=0.68\textheight,keepaspectratio]{figures/fig-01.pdf}
  \par\smallskip
  \small Recall@100 on AIME: ParisKV 81.9\%; MagicPIG 2.6\%; PQCache 10.0\% in this example.
  \papersource{Paper, Fig. 1, PDF p. 1. Left: recall vs. decode step; right: prefill-only vs. prefill+decode reference centroids.}
\end{frame}

\begin{frame}{The target is high-score KV indices at each decode step}
  \begin{block}{Full attention over $n_t$ historical keys}
    \[s_i=\langle\mathbf{k}_i,\mathbf{q}\rangle,\qquad
      \mathbf{o}=\sum_{i=1}^{n_t}\operatorname{softmax}(s)_i\mathbf{v}_i.\]
  \end{block}
  \begin{itemize}
    \item Retrieve a small candidate set $\mathcal{C}(\mathbf{q})$ that covers the true Top-$k$ scores.
    \item Recompute softmax and value aggregation using the selected full-precision KV.
    \item The retrieval path must be cheaper than reading the entire cache every step.
  \end{itemize}
  \papersource{Paper, Sec. 3, Eqs. (1)--(3), PDF p. 3.}
\end{frame}

\begin{frame}{The pipeline separates GPU search from CPU storage}
  \centering
  \includegraphics[width=0.98\linewidth,height=0.76\textheight,keepaspectratio]{figures/fig-02.pdf}
  \papersource{Paper, Fig. 2, PDF p. 4. Blue: prefill summaries. Red: decode-time shortlist, rerank, and UVA fetch.}
\end{frame}

\begin{frame}{Normalization and rotation enable a fixed codebook}
  \[\hat{\mathbf{k}}=\frac{\mathbf{k}}{\|\mathbf{k}\|_2},\quad
    \hat{\mathbf{q}}=\frac{\mathbf{q}}{\|\mathbf{q}\|_2},\quad
    \tilde{\mathbf{k}}=R\hat{\mathbf{k}},\quad
    \tilde{\mathbf{q}}=R\hat{\mathbf{q}}.\]
  \begin{itemize}
    \item $R$ is a shared orthogonal transform (implemented with SRHT); it preserves normalized inner products.
    \item Split $D$ dimensions into $B$ blocks of size $m=D/B$.
    \item Each block uses fixed sign-pattern centers:
  \end{itemize}
  \[\Omega=\{\pm 1/\sqrt{m}\}^{m},\quad |\Omega|=2^m,\quad
    c_{i,b}=\arg\max_{\omega\in\Omega}\mathbf{u}_{i,b}^{\top}\omega.\]
  \papersource{Paper, Sec. 4.1.1--4.1.2, Eqs. (5)--(6), PDF pp. 3--5. $\mathbf{u}_{i,b}$ is the rotated block's unit direction.}
\end{frame}

\begin{frame}{The codebook is data-independent; the quantizer uses a prior}
  \begin{itemize}
    \item Fixed centers cover all sign patterns, so new decode keys can be indexed without retraining centroids.
    \item Under Haar-random rotation, block energy and squared direction coordinates obey Beta distributions:
  \end{itemize}
  \[r_b^2\sim\operatorname{Beta}\!\left(\frac m2,\frac{D-m}{2}\right),\qquad
    (u_b)_j^2\sim\operatorname{Beta}\!\left(\frac12,\frac{m-1}{2}\right).\]
  \begin{itemize}
    \item Offline Lloyd--Max quantization gives shared 3-bit magnitude levels; a fourth bit stores the sign.
    \item The final reranker retains exact block radii inside stored weights.
  \end{itemize}
  \papersource{Paper, Proposition 4.1, PDF p. 6; Appendix B.1, PDF p. 14. SRHT uses the Haar prior as an approximation.}
\end{frame}

\begin{frame}{Stage I uses multi-tier collision votes to prune keys}
  \begin{itemize}
    \item In each block, score a key using its assigned center and keep the top-$\rho$ fraction.
    \item Divide that fraction into six percentile tiers with bonuses $6,5,4,3,2,1$.
  \end{itemize}
  \[S_i=\sum_{b=1}^{B}\mathbf{1}\{i\in T_b(\rho)\}\,w_{\ell(i,b)}.\]
  \begin{itemize}
    \item Choose the top-$\beta$ keys by $S_i$; typically $\beta=5$--$10\%$ and $\rho\geq\beta$.
    \item Small integer scores allow histogram and prefix-scan selection instead of a full sort.
  \end{itemize}
  \papersource{Paper, Sec. 4.2.2, PDF p. 5; Appendix B.2.1, Eq. (15), PDF p. 15.}
\end{frame}

\begin{frame}{Stage II estimates the raw attention score from 4-bit codes}
  \small
  \[r_{i,b}=\|\tilde{\mathbf{k}}_{i,b}\|_2,\quad
    \mathbf{u}_{i,b}=\tilde{\mathbf{k}}_{i,b}/r_{i,b},\quad
    \alpha_{i,b}=\langle\mathbf{v}_{i,b},\mathbf{u}_{i,b}\rangle.\]
  \[w_{i,b}=\|\mathbf{k}_i\|_2\frac{r_{i,b}}{\alpha_{i,b}},\qquad
    \widehat{\langle\mathbf{k}_i,\mathbf{q}\rangle}
    =\|\mathbf{q}\|_2\sum_{b=1}^{B}w_{i,b}
      \langle\mathbf{v}_{i,b},\tilde{\mathbf{q}}_b\rangle.\]
  \begin{itemize}
    \item $\mathbf{v}_{i,b}$ reconstructs the key block from one sign bit and three magnitude bits per coordinate.
    \item $\alpha$ corrects alignment loss; the division is an approximation, not an identity for every query.
    \item Key-only factors are precomputed, so GPU ranking needs no full-precision keys.
  \end{itemize}
  \papersource{Paper, Eqs. (7)--(10), PDF p. 5; Appendix B.2.2, PDF pp. 15--16.}
\end{frame}

\begin{frame}{The memory layout amortizes updates and fetches Top-$k$}
  \centering
  \includegraphics[width=0.94\linewidth,height=0.31\textheight,keepaspectratio]{figures/fig-05.pdf}
  \begin{itemize}
    \item Sink and recent Local tokens stay on GPU for dense attention.
    \item New tokens enter the GPU Update Buffer; a full buffer triggers encoding and offload of old Local tokens.
    \item GPU reranking returns Top-$100$ indices; UVA reads only those full KV pairs from the CPU Retrieval region.
  \end{itemize}
  \papersource{Paper, Fig. 5, Sec. 4.2.1--4.2.3, PDF pp. 5--6. Update interval is task-dependent (Table 1).}
\end{frame}

\begin{frame}{Fewer transferred bytes are the main systems lever}
  \begin{center}
  \begin{tabular}{@{}ll@{}}
    \toprule
    Full attention & dense scores over $(|S|+n)$ keys, full dimension $D$ \\
    ParisKV & dense local $|S|$; compressed search over history $n$ \\
     & rerank $C=\lceil\beta n\rceil$; fetch only final $k\ll C$ KV \\
    \bottomrule
  \end{tabular}
  \end{center}
  \begin{itemize}
    \item Custom CUDA kernels: collision accumulation, integer bucket Top-$k$, fused rerank, UVA gather.
    \item Candidate work still grows with context length; compression and kernel fusion reduce the cost per key.
  \end{itemize}
  \papersource{Paper, Sec. 4.3, PDF p. 6.}
\end{frame}

\begin{frame}{Evaluation spans long generation and long input}
  \begin{center}
  \small
  \begin{tabular}{@{}lll@{}}
    \toprule
    Workload & Metric & Models \\
    \midrule
    GPQA-Diamond, MATH500 & pass@1 & Qwen3-4B, DS-R1-Llama-8B, Qwen3-8B \\
    AIME25, up to 38.9K output & pass@8 & same three model families \\
    LongBench-V2 & accuracy & same three model families \\
    RULER 128K & accuracy & Llama3.1-8B \\
    \bottomrule
  \end{tabular}
  \end{center}
  \begin{itemize}
    \item ParisKV always retrieves Top-$100$; PQCache uses a 20\% compression budget and MagicPIG a dynamic policy.
    \item Efficiency tests use Llama3.1-8B and Qwen3-8B, 64K--1024K contexts, with batch and single-request analyses.
  \end{itemize}
  \papersource{Paper, Sec. 5, Table 1, PDF p. 6; Appendix D.1, PDF pp. 16--18. Baselines use recommended budgets.}
\end{frame}

\begin{frame}{On AIME25, ParisKV retains long-generation accuracy}
  \begin{center}
  \begin{tabular}{@{}lrrr@{}}
    \toprule
    AIME25 pass@8 (\%) & Qwen3-4B & DS-R1-Llama-8B & Qwen3-8B \\
    \midrule
    Full attention & 86.67 & 50.00 & 83.33 \\
    PQCache & 3.33 & 13.30 & 16.67 \\
    MagicPIG & 6.67 & 13.30 & 10.00 \\
    \good{ParisKV} & \good{80.00} & \good{53.30} & \good{73.33} \\
    \bottomrule
  \end{tabular}
  \end{center}
  \begin{itemize}
    \item Gains over PQCache: +76.67, +40.00, +56.66 percentage points.
    \item ParisKV is below full attention on two Qwen AIME25 settings, above it on the DS setting.
  \end{itemize}
  \papersource{Paper, Table 2, PDF p. 7. AIME25 reports pass@8; larger is better.}
\end{frame}

\begin{frame}{Seven of nine reasoning results meet or exceed dense attention}
  \begin{center}
  \begin{tabular}{@{}lrrr@{}}
    \toprule
    Qwen3-4B & Full & PQCache & ParisKV \\
    \midrule
    GPQA-Diamond pass@1 & 64.14 & 38.38 & \good{72.22} \\
    MATH500 pass@1 & 88.60 & 58.80 & \good{92.80} \\
    AIME25 pass@8 & \good{86.67} & 3.33 & 80.00 \\
    \bottomrule
  \end{tabular}
  \end{center}
  \begin{itemize}
    \item Across three models and three tasks, ParisKV meets or exceeds full attention in 7/9 cells.
    \item The task scores show generated-answer quality; they do not directly measure retrieval recall.
  \end{itemize}
  \papersource{Paper, Table 2, Sec. 5.1, PDF p. 7. Scores are percentages; differences are percentage points.}
\end{frame}

\begin{frame}{LongBench-V2 gains vary by model}
  \begin{center}
  \begin{tabular}{@{}lrrrr@{}}
    \toprule
    Overall accuracy (\%) & Full & PQCache & MagicPIG & ParisKV \\
    \midrule
    Qwen3-4B & \good{25.84} & 17.91 & 16.70 & 24.60 \\
    Qwen3-8B & \good{33.59} & 25.50 & 10.34 & 33.07 \\
    DS-R1-Llama-8B & 13.12 & 19.90 & 13.92 & \good{28.43} \\
    \bottomrule
  \end{tabular}
  \end{center}
  \begin{itemize}
    \item ParisKV exceeds PQCache and MagicPIG in all three model settings.
    \item It trails full attention by 1.24 and 0.52 points on the two Qwen models.
    \item The DS model's gain over full attention is observed, but its mechanism is not isolated by this table.
  \end{itemize}
  \papersource{Paper, Table 3, PDF p. 8. LongBench-V2 with chain-of-thought; higher is better.}
\end{frame}

\begin{frame}{RULER shows a strong average with task-specific gaps}
  \begin{center}
  \begin{tabular}{@{}lrr@{}}
    \toprule
    128K RULER, Llama3.1-8B & Avg. (\%) & fwe (\%) \\
    \midrule
    Full attention & 84.12 & 71.18 \\
    ShadowKV & 80.29 & 61.11 \\
    Quest & 79.34 & 62.85 \\
    \good{ParisKV} & \good{83.49} & 56.25 \\
    \bottomrule
  \end{tabular}
  \end{center}
  \begin{itemize}
    \item Best average among the listed sparse/retrieval systems; 0.63 points below full attention.
    \item The 14.93-point fwe gap shows that average accuracy does not imply uniform preservation.
  \end{itemize}
  \papersource{Paper, Appendix Table 6, PDF p. 19. Higher accuracy is better.}
\end{frame}

\begin{frame}{The routing design improves recall over long decoding}
  \begin{columns}[T,onlytextwidth]
    \begin{column}{0.49\textwidth}
      \centering
      \includegraphics[width=0.98\linewidth,height=0.46\textheight,keepaspectratio]{figures/fig-10-coarse.pdf}
    \end{column}
    \begin{column}{0.49\textwidth}
      \centering
      \includegraphics[width=0.98\linewidth,height=0.46\textheight,keepaspectratio]{figures/fig-10-final.pdf}
    \end{column}
  \end{columns}
  \begin{itemize}
    \item Coarse Recall@100 average: K-means 6.0\%, ParisKV 16.1\%.
    \item Final two-stage Recall@100: 36.5\% to 64.3\% over 10K decode steps.
  \end{itemize}
  \papersource{Paper, Sec. 5.3 and Fig. 10 panels (a) and (b), PDF pp. 7--8. The panels are cropped from the original figure.}
\end{frame}

\begin{frame}{Batch throughput rises while dense attention runs out of memory}
  \centering
  \includegraphics[width=0.98\linewidth,height=0.57\textheight,keepaspectratio]{figures/fig-07-qwen.pdf}
  \par\smallskip
  \small Horizontal axis: batch size; vertical axis: decode throughput (tokens/s).\\
  Qwen3-8B peak throughput is 2.3$\times$, 2.2$\times$, and 2.8$\times$ dense attention at 64K, 128K, and 256K.
  \papersource{Paper, Fig. 7 top row, PDF p. 8; Appendix D.2, PDF p. 19. Peak values compare each method's runnable batch range.}
\end{frame}

\begin{frame}{At 1024K, on-demand KV access cuts decode latency}
  \centering
  \includegraphics[width=0.92\linewidth,height=0.62\textheight,keepaspectratio]{figures/fig-08.pdf}
  \par\smallskip
  \small Llama3.1-8B, batch 1: ParisKV 49 ms/step; MagicPIG 830; PQCache 2179 (16.9$\times$ and 44.4$\times$ ratios).
  \papersource{Paper, Fig. 8, PDF p. 8; Sec. 5.2, PDF p. 7. Left axis is log-scale decode ms/step; right is prefill seconds.}
\end{frame}

\begin{frame}{One-time prefill cost and small-context latency matter}
  \begin{center}
  \begin{tabular}{@{}llrr@{}}
    \toprule
    Context & Metric & Full attention & ParisKV \\
    \midrule
    128K & Prefill / TTFT (s) & 33.30 & 43.00 \\
    128K & Decode (ms/token) & 23.13 & 24.42 \\
    256K & Prefill / TTFT (s) & 116.20 & 139.50 \\
    256K & Decode (ms/token) & 33.29 & 32.16 \\
    \bottomrule
  \end{tabular}
  \end{center}
  \begin{itemize}
    \item These batch-1 measurements show the crossover depends on context and workload.
    \item Decode savings accumulate with output length; prefill cost is paid once per request.
  \end{itemize}
  \papersource{Paper, Appendix Table 7, PDF p. 20. Separate efficiency setting from the batch throughput figure.}
\end{frame}

\begin{frame}{Interpret the gains under their exact conditions}
  \begin{itemize}
    \item \textbf{Model and task:} two Qwen LongBench-V2 settings and individual RULER tasks remain below full attention.
    \item \textbf{Budget:} ParisKV uses fixed Top-$100$; baselines follow different recommended policies, including PQCache at 20\%.
    \item \textbf{Theory:} Beta priors are exact for Haar rotation; practical SRHT uses them approximately.
    \item \textbf{System:} CPU offload needs host memory and adds prefill work; the paper reports a 167 GB free-memory limit in one scaling setup.
  \end{itemize}
  \papersource{Paper, Tables 2--3, 6--7; Appendix B.1 and D.2, PDF pp. 14, 19--20.}
\end{frame}

\begin{frame}{Take-home messages}
  \begin{enumerate}
    \item Fixed, data-independent routing keeps a usable index as decode keys accumulate.
    \item Collision pruning plus calibrated 4-bit reranking selects KV without CPU-side search.
    \item GPU-resident summaries and on-demand UVA fetch make long-context, large-batch decode practical in the reported tests.
  \end{enumerate}
  \vspace{0.5cm}
  \small Paper: Qi et al., \emph{ParisKV: Fast and Drift-Robust KV-Cache Retrieval for Long-Context LLMs}, ICML 2026, \href{https://arxiv.org/abs/2602.07721v3}{arXiv:2602.07721v3}.\\
  \small Code: \href{https://github.com/amy-77/ParisKV/tree/main}{github.com/amy-77/ParisKV}.
\end{frame}

\appendix
\begin{frame}{Backup: why the rotation prior is Beta}
  \begin{itemize}
    \item If $R$ is Haar-random, $R\hat{\mathbf{k}}$ is uniform on the unit sphere and has the same distribution as $\mathbf g/\|\mathbf g\|_2$ for $\mathbf g\sim N(0,I_D)$.
    \item A block energy is a ratio of independent chi-squared sums:
  \end{itemize}
  \[r_b^2=\frac{\|\mathbf g_b\|_2^2}{\|\mathbf g\|_2^2}
    \sim\operatorname{Beta}\!\left(\frac m2,\frac{D-m}{2}\right).\]
  \begin{itemize}
    \item Within a block, the squared coordinate of $\mathbf u_b=\mathbf g_b/\|\mathbf g_b\|_2$ is $\operatorname{Beta}(1/2,(m-1)/2)$.
    \item The magnitude prior sets offline 3-bit Lloyd--Max thresholds.
  \end{itemize}
  \papersource{Paper, Appendix B.1.1--B.1.2, PDF p. 14.}
\end{frame}

\begin{frame}{Backup: candidate ratio must track KV length}
  \centering
  \includegraphics[width=0.96\linewidth,height=0.72\textheight,keepaspectratio]{figures/fig-09.pdf}
  \papersource{Paper, Fig. 9, PDF p. 8. Left: recall rises with candidate ratio; right: ratio needed for a given target recall falls as KV length grows.}
\end{frame}

\begin{frame}{Backup: source notation needs care during implementation}
  \begin{itemize}
    \item Appendix Table 4 lists $D=256$, $B=16$, and $m=D/B=8$ simultaneously; those numbers are arithmetically inconsistent.
    \item Appendix B's setup calls a center ``learned on prefill'', whereas Sec. 4.1.2 defines a fixed analytic codebook.
    \item Sec. 4.2.1 reuses $m$ for Update Buffer length, while Table 1 sets Update to 256 or 512 tokens by task.
  \end{itemize}
  \papersource{Paper, PDF pp. 5--6, 14, 17. Equations should use $D=Bm$; window sizes come from Table 1.}
\end{frame}

\end{document}