\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{\arxivlink}{\href{https://arxiv.org/abs/2409.10516v3}{arXiv:2409.10516v3}}

\title[RetrievalAttention]{RetrievalAttention}
\subtitle{Accelerating Long-Context LLM Inference via Vector Retrieval}
\author{Paper by Di Liu, Meng Chen, Baotong Lu, et al.}
\date{\arxivlink\quad Paper discussion, 28 October 2026}

\begin{document}

\begin{frame}
  \titlepage
  \vspace{-3mm}
  \centering\small
  Published at \href{https://proceedings.neurips.cc/paper_files/paper/2025/hash/4e36d4049fb0fea195a8267c8dcd0824-Abstract-Conference.html}{NeurIPS 2025 Main Conference}
\end{frame}

\begin{frame}{One question: how can decoding read less KV?}
  \begin{block}{The setting}
    Long prompt already prefetched; decode one new token at a time with limited GPU memory.
  \end{block}
  \begin{itemize}
    \item Full KV cache grows with context length; each decode step must access history.
    \item Attention weights are sparse, but the important positions change with the query.
    \item RetrievalAttention stores most KV on CPU and searches a query-aware index for each step.
  \end{itemize}
  \medskip
  \small Code status (28 Oct 2026): the \href{https://github.com/microsoft/RetrievalAttention}{Microsoft repository}
  currently hosts RetroInfer; an implementation of the original method was not verified.
  \vfill
  \papersource{Paper, Sections 1--3, PDF pp. 1--7. All quantitative results here refer to arXiv v3.}
\end{frame}

\begin{frame}{The bottleneck is both storage and KV access}
  \begin{table}
    \centering
    \begin{tabular}{lrrrr}
      \toprule
      Prompt length & 128K & 256K & 512K & 1M\\
      \midrule
      Full KV capacity (GB) & 15.6 & 31.2 & 62.5 & 125\\
      No-cache token latency (s) & 32.8 & 111 & 465 & 1,765\\
      Attention share (s) & 25.2 & 96 & 434 & 1,695\\
      \bottomrule
    \end{tabular}
  \end{table}
  \begin{itemize}
    \item GPU-resident KV becomes infeasible on a 24 GB RTX 4090.
    \item Recomputing the prompt avoids the cache, but is prohibitively slow.
  \end{itemize}
  \vfill
  \papersource{Llama-3-8B; paper, Table 1, PDF p. 2. Capacity and no-cache latency describe different configurations.}
\end{frame}

\begin{frame}{The active tokens are sparse \emph{and} dynamic}
  \centering
  \includegraphics[width=0.98\linewidth,height=0.52\textheight,keepaspectratio]{figures/fig-02-dynamic.png}
  \begin{itemize}
    \item Dynamic top-1000 recovers 89\% of attention mass on average.
    \item Freezing the first token's top-1000 drops recovery to 71\%.
  \end{itemize}
  \papersource{100K-token KV retrieval, 20 generated tokens, Llama-3-8B; paper, Fig. 2, PDF p. 4.}
\end{frame}

\begin{frame}{Ordinary ANN indices miss Q-to-K neighbors}
  \centering
  \includegraphics[width=0.84\linewidth,height=0.67\textheight,keepaspectratio]{figures/fig-03a-ood-recall.pdf}
  \begin{itemize}
    \item Key-to-key search is easy; actual query-to-key search is out of distribution.
    \item IVF scans roughly 30--50\% of keys for Recall@100 above 0.95.
  \end{itemize}
  \papersource{Paper, Fig. 3a and Section 2.4, PDF pp. 4--5.}
\end{frame}

\begin{frame}{Query and key vectors occupy different regions}
  \centering
  \includegraphics[width=0.85\linewidth,height=0.68\textheight,keepaspectratio]{figures/fig-03b-mahalanobis.pdf}
  \begin{itemize}
    \item The Mahalanobis-distance probe puts Q-to-K far beyond K-to-K.
    \item A graph built only from K-to-K proximity follows the wrong geometry.
  \end{itemize}
  \papersource{Yi-9B and Llama-3-8B, 128K-token prompt; paper, Fig. 3b, PDF pp. 4--5.}
\end{frame}

\begin{frame}{RetrievalAttention splits the work across CPU and GPU}
  \centering
  \includegraphics[width=0.91\linewidth,height=0.62\textheight,keepaspectratio]{figures/fig-04a-architecture.pdf}
  \begin{itemize}
    \item GPU: a small predictable KV set.
    \item CPU: indexed historical KV, searched with the current query.
    \item Compute partial attention in parallel; merge with correct normalization.
  \end{itemize}
  \papersource{Paper, Fig. 4a and Section 3, PDF pp. 5--7.}
\end{frame}

\begin{frame}{Sparse attention renormalizes selected tokens}
  \[
    z_i=\frac{\mathbf q_t\mathbf k_i^\top}{\sqrt d},
    \qquad a_{t,i}=\frac{e^{z_i}}{\sum_{j\le t}e^{z_j}}
  \]
  \[
    \mathcal I_{t,\epsilon}=\{i:a_{t,i}>\epsilon\},
    \qquad
    \mathbf o_t\approx
    \sum_{i\in\mathcal I_{t,\epsilon}}
    \frac{e^{z_i}}{\sum_{j\in\mathcal I_{t,\epsilon}}e^{z_j}}\,\mathbf v_i
  \]
  \begin{itemize}
    \item Search aims to find the high-weight KV pairs.
    \item The implementation uses a retrieval budget (usually top-100), not an oracle threshold.
  \end{itemize}
  \vfill
  \papersource{Paper, Eqs. (1)--(2), PDF pp. 3 and 6; retrieval budgets in Table 2, PDF p. 8.}
\end{frame}

\begin{frame}{Prefill queries teach the key graph what matters}
  \begin{columns}[T]
    \begin{column}{0.53\linewidth}
      \begin{enumerate}
        \item Use prefill queries to find exact top-$k$ keys on GPU.
        \item Connect each query to those keys.
        \item Project shared-query links into a key-only graph.
        \item Search this graph with each new decode query.
      \end{enumerate}
      \medskip
      The projection follows the RoarGraph idea and avoids retaining query nodes.
    \end{column}
    \begin{column}{0.43\linewidth}
      \centering
      \includegraphics[width=\linewidth,height=0.67\textheight,keepaspectratio]{figures/fig-04b-index.pdf}
    \end{column}
  \end{columns}
  \vfill
  \papersource{Paper, Section 3.2 and Fig. 4b, PDF pp. 5--6. Figure shows the pre-projection Q--K links.}
\end{frame}

\begin{frame}{The GPU keeps 640 fixed positions}
  \begin{table}
    \centering
    \begin{tabular}{lll}
      \toprule
      Memory & KV set & Decode work\\
      \midrule
      GPU & First 128 + last 512 tokens & FlashAttention on $\mathcal W$\\
      CPU & Most other historical tokens & Index search + attention on $\Omega$\\
      \bottomrule
    \end{tabular}
  \end{table}
  \begin{itemize}
    \item $\mathcal W$ and $\Omega$ are disjoint; top-100 is the default dynamic budget.
    \item Only retrieved CPU KV participates in the CPU partial attention.
    \item Multiple query heads search in parallel; GQA heads get separate indices but share KV storage.
  \end{itemize}
  \vfill
  \papersource{Paper, Section 3.3, PDF pp. 6--7; Table 2, PDF p. 8; Appendix C, PDF p. 18.}
\end{frame}

\begin{frame}{Two local softmax outputs need global weights}
  \[
    Z_S=\sum_{i\in S}e^{z_i-m_S},\quad
    \mathbf o_S=\frac{\sum_{i\in S}e^{z_i-m_S}\mathbf v_i}{Z_S},
    \quad m_S=\max_{i\in S}z_i
  \]
  \[
    \gamma_S=
    \frac{e^{m_S-m}Z_S}
    {e^{m_{\mathcal W}-m}Z_{\mathcal W}
     +e^{m_\Omega-m}Z_\Omega},
    \quad
    \mathbf o=\gamma_{\mathcal W}\mathbf o_{\mathcal W}
    +\gamma_\Omega\mathbf o_\Omega
  \]
  \begin{block}{What this guarantees}
    The merge equals softmax over the \emph{selected union} $\mathcal W\cup\Omega$.
    Any approximation to full attention comes from omitted KV.
  \end{block}
  \papersource{Derived stable form of paper, Eqs. (3)--(5), Appendix B, PDF p. 17; $m=\max(m_{\mathcal W},m_\Omega)$.}
\end{frame}

\begin{frame}{The evaluation separates task quality from latency}
  \begin{itemize}
    \item \textbf{RTX 4090 testbed:} 24 GB GPU, 10-core i9-10900X, 128 GB DRAM; batch size 1.
    \item \textbf{Models:} Llama-3-8B-Instruct-262k, Yi-6B-200K, Yi-9B-200K.
    \item \textbf{Quality:} seven $\infty$-Bench tasks, RULER at 4K--128K, needle retrieval.
    \item \textbf{Search:} Recall@100 against exact top-100 and fraction of keys scanned.
    \item \textbf{Speed:} seconds per generated token, after long-context prefill.
  \end{itemize}
  \vfill
  \papersource{Paper, Section 4.1, PDF p. 7; Tables 2--5, PDF pp. 8--10.}
\end{frame}

\begin{frame}{Baselines test different ways to reduce KV cost}
  \begin{table}
    \centering
    \begin{tabular}{p{0.25\linewidth}p{0.63\linewidth}}
      \toprule
      Family & Representative methods and role\\
      \midrule
      Full attention & No-cache recomputation; vLLM with GPU KV cache\\
      KV reduction & StreamingLLM, SnapKV, InfLLM, Quest, InfiniGen\\
      Vector search & Flat: exact linear scan; IVF: key-cluster ANN\\
      \bottomrule
    \end{tabular}
  \end{table}
  \begin{itemize}
    \item Flat and IVF isolate the benefit of the query-aware index.
    \item Faster fixed-budget cache methods must be compared together with accuracy.
  \end{itemize}
  \vfill
  \papersource{Paper, Section 4.1, PDF p. 7.}
\end{frame}

\begin{frame}{InfiniteBench averages stay near full attention}
  \begin{table}
    \centering
    \begin{tabular}{lrrr}
      \toprule
      Model & Full & Retrieval top-100 & Retrieval top-2000\\
      \midrule
      Llama-3-8B & 50.4 & 48.9 & 49.6\\
      Yi-9B & 52.8 & 50.8 & 52.2\\
      Yi-6B & 45.5 & 45.0 & 45.0\\
      \bottomrule
    \end{tabular}
  \end{table}
  \begin{itemize}
    \item Seven-task average; higher is better.
    \item Top-2000 results are reported for the hard KV retrieval task; other task settings remain as in Table 2.
  \end{itemize}
  \vfill
  \papersource{Paper, Table 2, PDF p. 8. Scores are percentage points, not relative speedups.}
\end{frame}

\begin{frame}{The hard KV task exposes the retrieval budget}
  \begin{table}
    \centering
    \begin{tabular}{lrrr}
      \toprule
      $\infty$-Bench Retr.KV & Full & Top-100 & Top-2000\\
      \midrule
      Llama-3-8B & 17.5 & 9.0 & 14.0\\
      Yi-9B & 30.5 & 20.0 & 30.0\\
      Yi-6B & 3.5 & 3.0 & 3.0\\
      \bottomrule
    \end{tabular}
  \end{table}
  \begin{itemize}
    \item More retrieved KV can recover accuracy on difficult associative lookup.
    \item Near-full average accuracy does not mean every task matches full attention.
  \end{itemize}
  \vfill
  \papersource{Paper, Table 2, PDF p. 8. Higher is better.}
\end{frame}

\begin{frame}{RULER is close on average, with 128K gaps}
  \begin{table}
    \centering
    \begin{tabular}{lrrrr}
      \toprule
      & \multicolumn{2}{c}{Average, 4K--128K} & \multicolumn{2}{c}{128K only}\\
      Model & Full & Retrieval & Full & Retrieval\\
      \midrule
      Llama-3-8B & 86.54 & 84.70 & 78.74 & 74.70\\
      Yi-9B & 76.87 & 76.43 & 60.51 & 59.15\\
      Yi-6B & 67.86 & 65.86 & 55.77 & 51.44\\
      \bottomrule
    \end{tabular}
  \end{table}
  \begin{itemize}
    \item Scores are task percentages; higher is better.
    \item Table 3 also reports a shorter effective context than full attention for Llama-3-8B: 16K vs 32K.
  \end{itemize}
  \vfill
  \papersource{Paper, Table 3, PDF p. 9.}
\end{frame}

\begin{frame}{Needle retrieval works across tested positions}
  \centering
  \includegraphics[width=0.75\linewidth,height=0.67\textheight,keepaspectratio]{figures/fig-05-needle.png}
  \begin{itemize}
    \item All displayed 4K--128K depth/length cells pass on Llama-3-8B.
    \item Appendix A.3 also reports passing 250K--1M cells with Llama-3-8B-1048K.
  \end{itemize}
  \papersource{Paper, Figs. 5 and 8, PDF pp. 9 and 16. Synthetic needle retrieval.}
\end{frame}

\begin{frame}{At 128K, index search drives the speedup}
  \begin{table}
    \centering
    \begin{tabular}{lrrrr}
      \toprule
      Method & Retrieval & Attention & Other & Total (s/token)\\
      \midrule
      Flat & 0.798 & 0.083 & 0.041 & 0.922\\
      IVF & 0.250 & 0.084 & 0.039 & 0.373\\
      \textbf{RetrievalAttention} & \textbf{0.064} & 0.081 & 0.043 & \textbf{0.188}\\
      \bottomrule
    \end{tabular}
  \end{table}
  \begin{itemize}
    \item Total latency: 4.9$\times$ lower than Flat; 1.98$\times$ lower than IVF.
    \item The attention component barely changes; retrieval is the differentiator.
  \end{itemize}
  \vfill
  \papersource{Llama-3-8B, RTX 4090, 128K, batch size 1; paper, Tables 4--5, PDF pp. 9--10.}
\end{frame}

\begin{frame}{Low scan cost retains high top-100 recall}
  \centering
  \includegraphics[width=0.91\linewidth,height=0.68\textheight,keepaspectratio]{figures/fig-06-recall.pdf}
  \begin{itemize}
    \item RetrievalAttention reaches Recall@100 $>0.95$ after scanning about 1--3\% of keys.
    \item The advantage appears on Q-to-K; K-to-K is easy for several indices.
  \end{itemize}
  \papersource{Paper, Fig. 6 and Section 4.4, PDF pp. 9--10. Scanned fraction differs from top-100 output size.}
\end{frame}

\begin{frame}{Available GPU memory changes the comparison}
  \begin{table}
    \centering
    \begin{tabular}{lrrr}
      \toprule
      A100, 128K (s/token) & Llama-3-8B & Yi-6B & Yi-9B\\
      \midrule
      vLLM, full GPU KV & 0.033 & 0.030 & 0.044\\
      IVF & 0.345 & 0.309 & 0.468\\
      RetrievalAttention & 0.155 & 0.150 & 0.227\\
      \bottomrule
    \end{tabular}
  \end{table}
  \begin{itemize}
    \item With enough GPU memory, vLLM's full cache is faster.
    \item On the paper's RTX 4090 testbed, vLLM is reported OOM even at 4K.
  \end{itemize}
  \vfill
  \papersource{Paper, Appendix A.4, Table 7, PDF p. 16; RTX 4090 Table 4, PDF p. 9. Different machines.}
\end{frame}

\begin{frame}{Million-token latency uses a large-memory server}
  \begin{table}
    \centering
    \begin{tabular}{lrrrr}
      \toprule
      Llama-3-8B (s/token) & 100K & 200K & 500K & 1M\\
      \midrule
      Flat & 0.489 & 0.871 & 1.92 & 3.69\\
      IVF & 0.308 & 0.476 & 1.032 & 1.889\\
      RetrievalAttention & 0.159 & 0.167 & 0.170 & 0.172\\
      \bottomrule
    \end{tabular}
  \end{table}
  \begin{itemize}
    \item The 1M result uses an A100 80 GB and a machine with \textbf{1.72 TB DRAM}.
    \item It is a separate hardware regime from the 24 GB RTX 4090 result.
  \end{itemize}
  \vfill
  \papersource{Paper, Appendix A.4, Table 8, PDF p. 16.}
\end{frame}

\begin{frame}{Extra experiments show where budget matters}
  \begin{columns}[T]
    \begin{column}{0.48\linewidth}
      \begin{block}{Adaptive allocation at 128K}
        PyramidKV-style layer budget:
        \begin{itemize}
          \item Retr.KV: 14.5 $\rightarrow$ 16.0
          \item Seven-task mean: 49.9 $\rightarrow$ 50.1
          \item En.QA: 8.7 $\rightarrow$ 8.5
        \end{itemize}
      \end{block}
    \end{column}
    \begin{column}{0.48\linewidth}
      \begin{block}{70B stress test}
        Eight A100 40 GB GPUs, KV retrieval:
        \begin{itemize}
          \item Accuracy: 23.5 vs 24.0 Flat
          \item Full attention accuracy: 35.0
          \item Latency: 1.62 vs 5.68 s/token Flat
        \end{itemize}
      \end{block}
    \end{column}
  \end{columns}
  \vfill
  \papersource{Paper, Appendix F--G, Tables 10--11, PDF p. 19. Adaptive-budget run has its own setup.}
\end{frame}

\begin{frame}{The result is a specific accuracy--resource tradeoff}
  \begin{enumerate}
    \item Query-aware graph construction addresses the measured Q/K distribution gap.
    \item CPU retrieval reduces scanned KV; GPU retains the cheap predictable positions.
    \item The merge is exact on selected KV, while selection quality controls task accuracy.
  \end{enumerate}
  \begin{block}{Deployment conditions reflected in the paper}
    Prefill/index building is outside the primary decode latency; large contexts need CPU DRAM;
    hard retrieval tasks may need a larger top-$k$ budget.
  \end{block}
  \vfill
  \papersource{Paper, Sections 3--4 and Appendices A, B, G, PDF pp. 5--10, 16--19.}
\end{frame}

\begin{frame}{Paper identity and links}
  \begin{itemize}
    \item \textbf{Read version:} \arxivlink, revised 31 Dec 2024.
    \item \textbf{Publication:} \href{https://proceedings.neurips.cc/paper_files/paper/2025/hash/4e36d4049fb0fea195a8267c8dcd0824-Abstract-Conference.html}{NeurIPS 2025 Main Conference paper}.
    \item \textbf{Code check (28 Oct 2026):} original RetrievalAttention implementation not verified. The \href{https://github.com/microsoft/RetrievalAttention}{Microsoft repository} currently implements the later RetroInfer system.
    \item \textbf{Version caution:} proceedings abstract says 0.107 s/token; this presentation uses the arXiv v3 value of 0.188 s/token.
  \end{itemize}
  \vfill
  \papersource{Paper, arXiv v3 PDF p. 1 and Table 4, PDF p. 9; linked proceedings and repository.}
\end{frame}

\appendix
\begin{frame}{Backup: the normalization identity}
  \[
    N_S=\sum_{i\in S}e^{z_i-m_S}\mathbf v_i,\qquad
    Z_S=\sum_{i\in S}e^{z_i-m_S},\qquad
    \mathbf o_S=N_S/Z_S.
  \]
  \[
    \frac{\sum_{S\in\{\mathcal W,\Omega\}}e^{m_S-m}N_S}
         {\sum_{S\in\{\mathcal W,\Omega\}}e^{m_S-m}Z_S}
    =
    \sum_{S\in\{\mathcal W,\Omega\}}
    \underbrace{\frac{e^{m_S-m}Z_S}
      {\sum_T e^{m_T-m}Z_T}}_{\gamma_S}\mathbf o_S.
  \]
  \begin{itemize}
    \item $m=\max(m_{\mathcal W},m_\Omega)$ prevents overflow.
    \item Disjoint $\mathcal W,\Omega$ give the exact softmax on their union.
  \end{itemize}
  \vfill
  \papersource{Algebraic expansion of paper, Appendix B, Eqs. (3)--(5), PDF p. 17.}
\end{frame}

\end{document}