\documentclass[aspectratio=169,11pt]{beamer} \usepackage[T1]{fontenc} \usepackage[utf8]{inputenc} \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}{\hspace{4mm}{\scriptsize\color{gray}HashAttention\enspace|\enspace Paper discussion}\hfill\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{\ha}{HashAttention} \newcommand{\norm}[1]{\left\lVert #1\right\rVert_2} \pdfstringdefDisableCommands{\def\newline{ }\def\translate#1{#1}} \title[HashAttention]{HashAttention: Semantic Sparsity\newline for Faster Inference} \subtitle{Learning a compact selector for long-context attention} \author{Paper by Aditya Desai, Shuo Yang, Alejandro Cuadron,\newline Matei Zaharia, Joseph E. Gonzalez, and Ion Stoica} \date{ICML 2025\enspace|\enspace arXiv:2412.14468v2\newline Research discussion\enspace|\enspace 12 October 2026} \begin{document} \begin{frame} \titlepage \vspace{-6mm} \begin{center}\color{AcademicTeal}Learn 32-bit query/key codes; retrieve tokens; attend to their original KV.\end{center} \end{frame} \begin{frame}{The target is KV traffic during long-context decoding} \begin{block}{Research question} How can we identify a small useful set of tokens without first computing every full-dimensional query--key dot product? \end{block} \begin{itemize} \item Dense decoding reads a growing KV cache for each new query. \item Important tokens change with the query, even for the same document. \item \ha{} retains the full cache and selects what to read each step. \end{itemize} \medskip \alert{The 32-bit code is an auxiliary index per token per head.}\newline The reported sparsity factors describe token budgets, not resident KV compression. \papersource{Paper, Secs. 1, 4.1, and 6; PDF pp. 1--2, 4--5, 9.} \end{frame} \begin{frame}{Existing selectors spend their budgets differently} \renewcommand{\arraystretch}{1.22} \begin{tabular}{@{}p{2.7cm}p{4.2cm}p{6.4cm}@{}} \toprule Method & Selection signal & Main tradeoff in this setting \\ \midrule StreamingLLM & Initial and recent tokens & Middle tokens are never retrieved \\ H2O & Historical attention & Evicted tokens cannot be retrieved later \\ InfLLM / Quest & Block representatives & A useful token can require an entire block \\ Double Sparsity & Selected key channels & Channel budget and quantization affect recall \\ \ha{} & Learned binary codes & Requires model-specific adapter training \\ \bottomrule \end{tabular} \medskip Better recall can reduce the expensive attention budget downstream. \papersource{Paper, Sec. 2.2 and Appendix A; PDF pp. 3, 12--13.} \end{frame} \begin{frame}{Learn a retrieval space, then return to the original KV} \centering \includegraphics[width=0.94\linewidth,height=4.5cm,keepaspectratio]{figures/fig-02-method.png} \par\medskip \begin{itemize} \item Separate networks encode queries and cached keys. \item Nearest signatures provide token indices for sparse attention. \item The general notation includes values; experiments encode \alert{keys only}. \end{itemize} \papersource{Paper, Fig. 2 and Sec. 4.1; PDF pp. 4--5. Original author figure.} \end{frame} \begin{frame}{Only selection is approximate; selected KV stay in full form} Let $z_i=\langle q,k_i\rangle/\sqrt d$, with $n$ cached tokens. \[ o=\frac{\sum_{i=1}^n e^{z_i}v_i}{\sum_{j=1}^n e^{z_j}} \qquad\longrightarrow\qquad \widehat o=\frac{\sum_{i\in\mathcal I}e^{z_i}v_i}{\sum_{j\in\mathcal I}e^{z_j}} \] \begin{block}{Three stages} \textbf{SCORE}: compare compact signatures.\newline \textbf{TOPK}: select $m$ positions and include fixed windows.\newline \textbf{GATHER-ATT}: compute and normalize attention on selected KV. \end{block} \begin{itemize} \item $m$ is the retrieval budget; $\mathcal I$ is the final selected set. \item Normalization changes after selection. \end{itemize} \papersource{Paper, Sec. 4; PDF p. 4. Denominator index corrected; SDPA scaling made explicit.} \end{frame} \begin{frame}{A 32-bit signature makes scoring cheap} \[ \phi(x)=\operatorname{ReLU}(\operatorname{sign}(\mathcal F(x)))\in\{0,1\}^{b} \] \[ \operatorname{SCORE}(k_i,q)=-\operatorname{popcount}(h_i\operatorname{XOR}h_q) \] \begin{columns}[T,onlytextwidth] \begin{column}{0.46\textwidth} \begin{block}{Illustrative 4-bit example} Query: \texttt{1011}\newline Key \texttt{1011}: distance 0\newline Key \texttt{1001}: distance 1\newline Key \texttt{0110}: distance 3 \end{block} \end{column} \begin{column}{0.49\textwidth} \begin{itemize} \item 32 bits = 4 bytes per token per head. \item A 128-D FP16 key uses 256 bytes. \item All signatures are still scanned; this is not a sublinear hash-table lookup. \end{itemize} \end{column} \end{columns} \papersource{Paper, Eqs. (1)--(2), Sec. 4.1; PDF pp. 4--5. Example and byte comparison are explanatory.} \end{frame} \begin{frame}{Train the selector locally while freezing the LLM} \begin{enumerate} \item Run the LLM on text chunks; cache keys and collect queries. \item Label important tokens, for example the true top-64. \item Train each attention module with weighted binary cross-entropy and Adam. \end{enumerate} \begin{columns}[T,onlytextwidth] \begin{column}{0.47\textwidth} \begin{block}{Make learning feasible} Train with $\tanh$; infer with sign.\newline At 64K tokens, 64 positives = 0.1\%.\newline $w_+(n)=\alpha+\beta n$ balances labels. \end{block} \end{column} \begin{column}{0.49\textwidth} \begin{block}{Match the deployment distribution} Generic: concatenated OpenWebText.\newline Task-specific: \ha$^*$.\newline Training at $\leq$64K did not naturally transfer to 128K. \end{block} \end{column} \end{columns} \papersource{Paper, Sec. 4.2 and Eq. (4); PDF p. 5.} \end{frame} \begin{frame}{An isolated-contribution score leads to MIPS} For full-attention weights $a_i$, consider $s_i=a_i\norm{v_i}$. \[ \log s_i=\left\langle\frac{q}{\sqrt d},k_i\right\rangle+ \log\norm{v_i}-\log Z \] \[ \operatorname{rank}(s_i)=\operatorname{rank} \left\langle\left[q/\sqrt d,1\right],\left[k_i,\log\norm{v_i}\right]\right\rangle \] \begin{itemize} \item For nonzero values, the ranking reduction is exact. \item The residual argument drops cross-value correlations and preserves the original weights. \item Actual sparse attention renormalizes; the score is a useful proxy rather than a general optimality guarantee. \end{itemize} \papersource{Paper, Lemmas 4.1--4.2, Appendix B; PDF pp. 5, 13--14. Corrected cosine lift in backup.} \end{frame} \begin{frame}{Token-level sparsity still needs a careful kernel} \begin{itemize} \item Use paged attention with \alert{page size = 1}. \item Pass selected indices directly; avoid a separate KV gather buffer. \item A token vector can contain enough contiguous bytes for useful memory transactions. \end{itemize} \[ T\approx T_{\rm map}+T_{\rm scan}+T_{\rm TOPK}+T_{\rm selected\ attention} \] \begin{block}{Budget accounting} The experiments keep the first 128 and most recent 128 tokens.\newline Example: at 16,384 tokens, $m=1,024$ plus up to 256 fixed positions\newline means up to 1,280 reads, or 7.81\% of the context. \end{block} \papersource{Paper, Sec. 4.4 and evaluation protocol; PDF pp. 5--7. Budget calculation is illustrative.} \end{frame} \begin{frame}{The protocol models a prepared document plus a short query} \renewcommand{\arraystretch}{1.18} \begin{tabular}{@{}p{3.4cm}p{10cm}@{}} \toprule Models & Llama-3.1-8B-Instruct; Mistral-7B-Instruct-v0.3 \\ Quality suites & LongBench and RULER \\ Sparse region & Last 128 prompt tokens for LongBench; last 32 for RULER; all subsequent generation \\ Dense region & Earlier prompt tokens use full attention \\ Auxiliary budget & Usually 32 bits per token per attention head \\ Efficiency & A100; GPT-FAST and FlashDecode; throughput at batch 1 \\ \bottomrule \end{tabular} \medskip \alert{This protocol does not establish sparse prefill quality over the whole document.} \papersource{Paper, Sec. 5; PDF pp. 6--8.} \end{frame} \begin{frame}{At 512 retrieved tokens, learned codes compete well} \begin{columns}[T,onlytextwidth] \begin{column}{0.57\textwidth} \renewcommand{\arraystretch}{1.12} \begin{tabular}{@{}lrr@{}} \toprule Method & Aux. bits & Score $\uparrow$ \\ \midrule Full model & -- & 63.55 \\ Exact top-k oracle & -- & 63.43 \\ H2O & -- & 43.47 \\ StreamingLLM & -- & 33.28 \\ DS & 32 & 61.88 \\ Quest & 32 & 62.36 \\ Quest & 64 & 63.33 \\ \textbf{HashAttention} & \textbf{32} & \textbf{64.15} \\ \bottomrule \end{tabular} \end{column} \begin{column}{0.39\textwidth} Six LongBench categories; Llama-3.1-8B-Instruct. \par\medskip \alert{Table 1 uses task-related training}, despite no star in the row name. \par\medskip 25 examples per dataset enter training; MFQA is excluded. \par\medskip An exact top-k oracle is not an upper bound on task quality. \end{column} \end{columns} \papersource{Paper, Table 1 and its caption; PDF p. 6. Scores are averages over six tasks.} \end{frame} \begin{frame}{Generic training preserves most average quality at 16$\times$} \centering \renewcommand{\arraystretch}{1.35} \begin{tabular}{@{}lrrr@{}} \toprule Evaluation set & Full & HA-16$\times$ & Change \\ \midrule LongBench: 16 non-Chinese tasks & 48.78 & 48.00 & $-0.78$ \\ Without passage-count & 51.48 & 51.08 & $-0.40$ \\ RULER@16K: 13 tasks & 90.66 & 89.53 & $-1.13$ \\ LongBench: 5 Chinese tasks & 50.888 & 48.228 & $-2.660$ \\ \bottomrule \end{tabular} \par\medskip \begin{itemize} \item Scores increase with quality; changes are absolute score points. \item English-only adapter training also transfers to Chinese, with a larger loss. \item Aggregate averages hide important task-specific differences. \end{itemize} \papersource{Paper, Tables 2--3 and 5; PDF pp. 6, 14. Table 5 row order inferred from Sec. 5.1 and Table 4.} \end{frame} \begin{frame}{Retrieval can survive while aggregation degrades} \centering \renewcommand{\arraystretch}{1.25} \begin{tabular}{@{}llrrr@{}} \toprule Suite & Task & Full & HA-16$\times$ & Change \\ \midrule LongBench & Passage retrieval (en) & 100.00 & 100.00 & 0.00 \\ LongBench & Passage count & 8.29 & 1.85 & $-6.44$ \\ LongBench & HotpotQA & 55.40 & 51.92 & $-3.48$ \\ LongBench & RepoBench-P & 55.31 & 60.49 & $+5.18$ \\ RULER & Multi-key needle 2 & 100.00 & 90.00 & $-10.00$ \\ RULER & Common-word extraction & 50.50 & 62.40 & $+11.90$ \\ \bottomrule \end{tabular} \par\medskip The authors suggest distractor removal as an explanation for gains.\newline The experiments show the gains; they do not isolate that mechanism. \papersource{Paper, Tables 2--3 and Sec. 5.1; PDF pp. 6, 8.} \end{frame} \begin{frame}{At equal auxiliary memory, fewer tokens can suffice} \begin{columns}[T,onlytextwidth] \begin{column}{0.49\textwidth} \centering\textbf{Llama-3.1-8B-Instruct}\par\smallskip \includegraphics[width=\linewidth,height=4cm,keepaspectratio]{figures/fig-03a-llama-pareto.png} \end{column} \begin{column}{0.49\textwidth} \centering\textbf{Mistral-7B-Instruct-v0.3}\par\smallskip \includegraphics[width=\linewidth,height=4cm,keepaspectratio]{figures/fig-03b-mistral-pareto.png} \end{column} \end{columns} \medskip 32 bits per token per head; averages over \alert{four LongBench tasks}.\newline Llama: generic training approaches full quality at 16$\times$;\newline task tuning approaches it at 32$\times$. Mistral reaches this region earlier. \papersource{Paper, Fig. 3; PDF p. 7. Original figures; vertical-axis digits wrap in the source images.} \end{frame} \begin{frame}{Higher recall supports the selector-quality explanation} \begin{columns}[T,onlytextwidth] \begin{column}{0.49\textwidth} \centering\includegraphics[width=\linewidth,height=4.6cm,keepaspectratio]{figures/fig-05a-recall-layer17.png} \end{column} \begin{column}{0.49\textwidth} \centering\includegraphics[width=\linewidth,height=4.6cm,keepaspectratio]{figures/fig-05b-recall-layer5.png} \end{column} \end{columns} \medskip Recall of true top-32 tokens, using a 16$\times$ sparse retrieval budget.\newline Orange: HashAttention. Blue: Double Sparsity.\newline The two displayed layers favor learned signatures across most lengths. \papersource{Paper, Fig. 5; PDF p. 14. Original author panels.} \end{frame} \begin{frame}{Latency gains emerge after mapping costs are amortized} \centering \renewcommand{\arraystretch}{1.23} \begin{tabular}{@{}lrrrr@{}} \toprule Framework & Context & Dense (ms) & HA (ms) & Ratio \\ \midrule GPT-FAST & 32K & 2.03 & 0.47 & 4.32$\times$ \\ GPT-FAST & 131K & 8.09 & 2.53 & 3.20$\times$ \\ FlashDecode & 32K & 0.41 & 0.37 & 1.11$\times$ \\ FlashDecode & 65K & 0.79 & 0.55 & 1.44$\times$ \\ FlashDecode & 524K & 6.24 & 2.43 & 2.57$\times$ \\ \bottomrule \end{tabular} \par\medskip \begin{itemize} \item A100; 32$\times$ sparsity; MLP: $128\to128\to128\to32$. \item Short contexts can lose to the fixed mapping overhead. \item Sequence parallelism makes the FlashDecode baseline stronger. \end{itemize} \papersource{Values transcribed from Fig. 4(a), PDF p. 8; ratios use rounded labels. Text reports maxima of 4.3$\times$ and 2.54$\times$. The figure calls GPT-FAST ``GPT-FLASH.''} \end{frame} \begin{frame}{The plotted 3.12$\times$ throughput gain occurs near 65K} \centering \renewcommand{\arraystretch}{1.5} \begin{tabular}{@{}lrrr@{}} \toprule Context & GPT-FAST (tok/s) & HA-32$\times$ (tok/s) & Ratio \\ \midrule 32K & 7.27 & 18.28 & 2.51$\times$ \\ \textbf{65K} & \textbf{4.00} & \textbf{12.48} & \textbf{3.12$\times$} \\ 131K & 1.76 & 4.78 & 2.72$\times$ \\ \bottomrule \end{tabular} \par\medskip \begin{itemize} \item Llama-3.1-8B; A100; batch 1; model generation throughput. \item The paper's prose places the maximum at 32K; the plotted values place it at 65K. \item The authors attribute the later decline in the ratio to TOPK cost. \end{itemize} \papersource{Paper, Fig. 4(b) and Sec. 5.2; PDF p. 8. Ratios calculated from the figure labels.} \end{frame} \begin{frame}{Choose speed at a matched quality budget} RULER@32K, Llama-3.1-8B-Instruct, GPT-FAST, A100, batch 1. \medskip \centering \renewcommand{\arraystretch}{1.5} \begin{tabular}{@{}lrrr@{}} \toprule Working point & Quality $\uparrow$ & Change & Throughput ratio \\ \midrule Full model & 84.28 & -- & 1.0$\times$ \\ HashAttention, 4$\times$ sparse & 83.41 & $-0.87$ & $\sim$1.3$\times$ \\ HashAttention, 8$\times$ sparse & 82.56 & $-1.72$ & $\sim$1.7$\times$ \\ \bottomrule \end{tabular} \par\medskip \raggedright These joint quality/speed points are more informative for deployment\newline than combining a 16$\times$ quality result with a 32$\times$ speed result. \papersource{Paper, Fig. 1 and Sec. 1; PDF pp. 1--2. Fig. 1 omits DS quantization/dequantization time and the throughput impact of auxiliary-memory size.} \end{frame} \begin{frame}{Learning the codes matters more than merely hashing} \centering \renewcommand{\arraystretch}{1.3} \begin{tabular}{@{}lrrl@{}} \toprule Selector & Bits & Sparsity & Four-task mean $\uparrow$ \\ \midrule \textbf{HashAttention} & \textbf{32} & \textbf{16$\times$} & \textbf{75.0675} \\ Random-projection LSH & 32 & 16$\times$ & 48.8975 \\ Random-projection LSH & 256 & 16$\times$ & 69.7875 \\ Random-projection LSH & 512 & 16$\times$ & 68.6350 \\ Random-projection LSH & 1024 & 16$\times$ & Incomplete: TriviaQA OOM \\ \bottomrule \end{tabular} \par\medskip \begin{itemize} \item At 32 bits, the average gap is 26.17 score points. \item More random bits do not guarantee a monotonic improvement. \item This compares signatures, not the complete MagicPig algorithm. \end{itemize} \papersource{Paper, Sec. 5.3 and Table 8; PDF pp. 9, 16.} \end{frame} \begin{frame}{The useful operating region has concrete conditions} \begin{enumerate} \item \textbf{Model and context adaptation}\newline Each LLM needs learned mappings; training length and task distribution matter. \medskip \item \textbf{Access savings with retained storage}\newline Full KV remains on GPU in the reported experiments; CPU offload was not evaluated. \medskip \item \textbf{Task-dependent information loss}\newline Counting and multi-key retrieval can degrade despite a small average loss. \medskip \item \textbf{A remaining selection bottleneck}\newline Cheaper scores do not remove the cost of TOPK or attention over selected KV. \end{enumerate} \papersource{Paper, Secs. 4.2, 5.1--5.2, and 6; PDF pp. 5, 6--9.} \end{frame} \begin{frame}{Better retrieval is a systems resource} \begin{block}{Central contribution} Independent learned query/key maps produce compact binary codes\newline that help preserve attention quality at smaller retrieval budgets. \end{block} \begin{itemize} \item Optimize the whole chain: selector quality, auxiliary traffic, and selected attention. \item Read the 16$\times$ quality and 32$\times$ efficiency results with their own protocols. \item Promising next steps: adaptive budgets, faster discrete-score selection, and offloaded KV. \end{itemize} \medskip \href{https://arxiv.org/abs/2412.14468v2}{\textbf{Desai et al., HashAttention: Semantic Sparsity for Faster Inference.}}\newline ICML 2025; arXiv:2412.14468v2, revised 3 June 2025. \papersource{Main presentation ends here. Following slides provide derivations and additional results.} \end{frame} \appendix \begin{frame}{Backup: the cosine lift needs a zero query coordinate} Define $x_i=[k_i,\log\norm{v_i}]$, $u=[q/\sqrt d,1]$,\newline and choose $M>0$ with $M\geq\max_i\norm{x_i}$. \[ P(x_i)=\left[x_i,\sqrt{M^2-\norm{x_i}^2}\right],\qquad Q(u)=[u,0]. \] Then $\norm{P(x_i)}=M$ and \[ \cos(P(x_i),Q(u))=\frac{\langle x_i,u\rangle}{M\norm{u}}, \] so cosine similarity preserves the inner-product ranking. \medskip \begin{block}{Correction to the displayed formula in Sec. 4.3} The paper writes $[q,1,1]$. The final 1 adds a key-dependent square-root term and can reverse the ranking. It must be 0 for this lift. \end{block} \papersource{Paper, Sec. 4.3, PDF p. 5. Corrected derivation by the reader; the learned MLP does not implement this explicit lift.} \end{frame} \begin{frame}{Backup: isolated contribution is not general optimality} Without renormalization, the residual contains cross terms: \[ \left\lVert\sum_{i\notin\mathcal I}a_i v_i\right\rVert_2^2 =\sum_{i\notin\mathcal I}a_i^2\norm{v_i}^2 +2\!\sum_{\substack{i