% Compile with pdflatex. Replace the demonstration content before delivery.
\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}{%
  \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}}

\title[SpargeAttention]{SpargeAttention}
\subtitle{Accurate and Training-free Sparse Attention\\Accelerating Any Model Inference}
\author{Research paper reading\\\small Zhang, Xiang, Huang, Wei, Xi, Zhu and Chen}
\date{ICML 2025 \;|\; arXiv:2502.18137v8\\Reading: 18 September 2026}
\begin{document}
\begin{frame}\titlepage\end{frame}
\begin{frame}{Selective compression makes sparse prediction safer}
\begin{itemize}
\item Predict block importance from representative tokens only when within-block similarity is high.
\item Protect dissimilar blocks; then skip negligible PV updates inside online softmax.
\item Combine sparsity with SageAttention quantization. Mochi on L40: 1897 s to 1037 s (1.83$\times$).
\item Evidence spans language, image and video models; it is not a universal accuracy guarantee.
\end{itemize}
\papersource{Paper, Secs. 3--4; Table 2, PDF p.8.}
\end{frame}

\begin{frame}{The mask must cost less than the work it saves}
\[O=\operatorname{softmax}(QK^\top/\sqrt d)V,\qquad Q,K,V\in\mathbb R^{N\times d}.\]
\begin{itemize}
\item Dense attention performs two quadratic matrix products.
\item Fixed windows and attention sinks need not transfer to visual models.
\item Pooling every block can hide a rare but important token.
\item SpargeAttn asks whether a block is safe to summarize before trusting its mean.
\end{itemize}
\papersource{Paper, Secs. 1--3.2, PDF pp.1--5.}
\end{frame}

\begin{frame}{Two filters skip different pieces of work}
\centering
\includegraphics[width=.94\linewidth,height=.66\textheight,keepaspectratio]{figures/overview.pdf}

\papersource{Paper, Fig.3, PDF p.4. Original author figure; red blocks are protected.}
\end{frame}

\begin{frame}{Online softmax maintains a running normalization}
\begin{align*}
S_{ij}&=Q_iK_j^\top/\sqrt d,\\
m_{ij}&=\max(m_{i,j-1},\operatorname{rowmax}S_{ij}),\\
\widetilde P_{ij}&=\exp(S_{ij}-m_{ij}),\\
l_{ij}&=e^{m_{i,j-1}-m_{ij}}l_{i,j-1}+\operatorname{rowsum}\widetilde P_{ij},\\
O_{ij}&=\operatorname{diag}(e^{m_{i,j-1}-m_{ij}})O_{i,j-1}+\widetilde P_{ij}V_j.
\end{align*}
$Q_i$: query block; $K_j,V_j$: key/value blocks. $m,l$: row-wise states.\\
Final output: $O_i=\operatorname{diag}(l_{i,T_n})^{-1}O_{i,T_n}$.

\papersource{Paper, Sec.3.1, Eq.(1), PDF p.3.}
\end{frame}

\begin{frame}{Stage 1: protect blocks that are hard to summarize}
\[q_i=\operatorname{mean}(Q_i),\quad k_j=\operatorname{mean}(K_j),\quad \hat S=qk^\top.\]
\begin{itemize}
\item Compute within-block scores $s_{qi},s_{kj}$. Exclude low-similarity key columns from compressed softmax.
\item Apply TopCdf to each compressed probability row, controlled by $\tau$.
\item Force $M_g[i,:]=1$ if $s_{qi}<\theta$; force $M_g[:,j]=1$ if $s_{kj}<\theta$.
\item If $M_g[i,j]=0$, skip both $Q_iK_j^\top$ and $\widetilde P_{ij}V_j$.
\end{itemize}
\papersource{Paper, Secs.3.2--3.3, Eqs.(4)--(6), PDF pp.3--5.}
\end{frame}

\begin{frame}{Two definitions require care when reproducing the paper}
\begin{block}{TopCdf boundary}
Text says cumulative mass ``reaches'' $\tau$; pseudocode uses
$\mathrm{cumsum}\leq\tau\,\mathrm{sum}$.
For $(0.6,0.3,0.1)$ and $\tau=0.8$, the code keeps only $0.6$.
\end{block}
\begin{block}{Similarity definition}
The paper calls this cosine similarity but prints
$\mathrm{CosSim}(X)=\mathrm{mean}(XX^\top/|\max(XX^\top)|)$.
This differs from standard pairwise cosine normalization.
\end{block}
Check the implementation before resolving these ambiguities.

\papersource{Paper, Sec.3.2, PDF pp.4--5. Example and caution: reading analysis.}
\end{frame}

\begin{frame}{Stage 2: skip PV when the local maximum is far below}
For query rows $I_w$ handled by one GPU warp:
\[
\max\big(m_{\mathrm{local}}[I_w]-m_{ij}[I_w]\big)<\lambda,\qquad\lambda<0.
\]
\begin{itemize}
\item Then every unnormalized weight in this warp is below $e^\lambda$.
\item The running maximum stays unchanged; the previous output needs no rescaling.
\item Skip $\widetilde P_{ij}[I_w]V_j$. QK and denominator updates have already happened.
\item Small weights alone do not bound total output error for arbitrary $V$.
\end{itemize}
\papersource{Paper, Sec.3.4 and Algorithm 1, PDF pp.4--5; last point: reading analysis.}
\end{frame}

\begin{frame}{Training-free still involves calibration}
\[L1=\frac{\sum|O-O'|}{\sum|O|}.\]
\begin{itemize}
\item Use five model inputs; search $(\tau,\theta)$ under $L1<l_1$, then $\lambda$ under $L1<l_2$.
\item $(l_1,l_2)$: Llama $(.08,.09)$; CogVideoX/Mochi $(.05,.06)$.
\item Flux/SD3.5 $(.07,.08)$; Open-Sora-Plan $(.03,.035)$.
\item These constrain attention output error on calibration inputs, not downstream quality on all inputs.
\end{itemize}
\papersource{Paper, Secs.3.6 and 4.1, PDF pp.5--6.}
\end{frame}

\begin{frame}{Quantization contributes to the reported speedup}
\begin{itemize}
\item The main experiments build on SageAttention with block quantization in the QK path.
\item CUDA implementation and kernel fusion reduce prediction overhead.
\item A speedup over dense attention combines sparsity, quantization and implementation effects.
\item The p.1 footnote describes a newer SageAttention2 implementation; it does not replace every table with new measurements.
\end{itemize}
\papersource{Paper, Sec.3.5, Algorithm 1 and p.1 footnote, PDF pp.1,4--5.}
\end{frame}

\begin{frame}{Hilbert ordering exposes visual locality}
\begin{itemize}
\item Flatten visual tokens in $T\times H\times W$ along a Hilbert curve to improve within-block similarity.
\item Permute Q/K/V after positional embedding; apply the inverse permutation to the output.
\item For joint visual-language attention, permute visual tokens only.
\item Appendix ablation: query blocks 128, key blocks 64; FlashAttention2 is the accuracy reference.
\item Masks and position-dependent biases must remain consistent under permutation (reading analysis).
\end{itemize}
\papersource{Paper, Sec.3.7 and Appendix A.1, PDF pp.6,14.}
\end{frame}

\begin{frame}{Evaluation tests transfer across three model families}
\begin{tabular}{lll}\toprule
Task & Models & Evaluation\\\midrule
Language & Llama3.1-8B & WikiText, LongBench,\\
& & InfiniteBench En.MC, NIAH\\
Image & Flux.1-dev, SD3.5 large & COCO annotations\\
Video & CogVideoX-2B, Mochi, & open-sora prompts\\
& Open-Sora-Plan &\\\bottomrule\end{tabular}
\medskip
\begin{itemize}
\item Quality reference: full attention. Sparse baselines: block-sparse MInference and FlexPrefill.
\item Table 1 uses different achieved sparsities: compare quality and speed together.
\end{itemize}
\papersource{Paper, Sec.4.1 and Table 1, PDF pp.6--7.}
\end{frame}

\begin{frame}{Speed, sparsity and quality have different denominators}
\begin{itemize}
\item Speed is defined as dense operation count divided by attention latency, including mask prediction. It is not tokens/s.
\item Sparsity counts skipped QK and PV block products together; it is not the fraction of zero entries in $P$.
\item PPL and FID: lower is better. Task scores, CLIP/IR and reported video scores: higher is better.
\item Table 1 speed uses the real task tensors; Llama speed/sparsity specifically use 128K NIAH.
\end{itemize}
\papersource{Paper, Sec.4.1 and Table 1 caption, PDF pp.6--7.}
\end{frame}

\begin{frame}{Language quality is close while attention gets faster}
\centering
\begin{tabular}{lrr}\toprule
Llama3.1 & Full & SpargeAttn\\\midrule
Attention speed (paper units) &156.9&708.1\\
WikiText PPL $\downarrow$ &6.013&6.020\\
LongBench $\uparrow$ &38.682&39.058\\
InfiniteBench $\uparrow$ &0.6594&0.6638\\
NIAH $\uparrow$ &0.907&0.909\\\bottomrule\end{tabular}
\medskip
\par Attention speed: $4.51\times$ at 128K; sparsity: 0.54.
\par Small score improvements have no reported confidence intervals.

\papersource{Paper, Table 1, PDF p.7. Speed ratio calculated from table values.}
\end{frame}

\begin{frame}{Visual metrics are largely retained, but not identical}
\centering
\begin{tabular}{llrr}\toprule
Model & Metric & Full & SpargeAttn\\\midrule
CogVideoX & VQA-a $\uparrow$ &80.384&78.276\\
Mochi & VQA-a $\uparrow$ &56.472&54.179\\
Mochi & FScore $\uparrow$ &1.681&1.807\\
Open-Sora-Plan & VQA-t $\uparrow$ &80.60&76.91\\
Flux & FID $\downarrow$ &166.103&163.982\\
SD3.5 & FID $\downarrow$ &166.101&166.193\\\bottomrule\end{tabular}
\medskip
\par ``No quality loss'' is the authors' summary, not literal equality.
\par Reported sparse baselines often degrade much more.

\papersource{Paper, Table 1, PDF p.7. Selected metrics, original scales.}
\end{frame}

\begin{frame}{Kernel curves separate sparse and quantized variants}
\centering
\includegraphics[width=.84\linewidth,height=.66\textheight,keepaspectratio]{figures/speed_comparison.pdf}

\papersource{Paper, Fig.10, PDF p.9. Sequence 22K; head dimension 128. Not end-to-end speed.}
\end{frame}

\begin{frame}{End-to-end gains are smaller than attention gains}
\centering
\begin{tabular}{llrrr}\toprule
Model & GPU & Original & Sage & Sparge\\\midrule
CogVideoX & RTX4090 &87 s&68 s&53 s\\
Mochi & L40 &1897 s&1544 s&1037 s\\
Llama 24K & RTX4090 &4.01 s&3.53 s&2.60 s\\
Llama 128K & L40 &52 s&42 s&29.98 s\\\bottomrule\end{tabular}
\medskip
\par Mochi: $1.83\times$ vs. original, $1.49\times$ vs. SageAttention.
\par Non-attention work limits whole-model acceleration.

\papersource{Paper, Table 2, PDF p.8. Ratios calculated from reported latency.}
\end{frame}

\begin{frame}{Prediction overhead shrinks relative to full attention}
\centering
\begin{tabular}{rrrr}\toprule
Length & Prediction (ms) & Full attention (ms) & Ratio\\\midrule
8K&0.251&6.649&3.78\%\\
32K&0.972&106.68&0.911\%\\
128K&8.764&1696.2&0.516\%\\\bottomrule\end{tabular}
\medskip
\begin{itemize}
\item The absolute prediction time still grows.
\item These ratios use full-attention time, not accelerated total time.
\item Compressed attention remains quadratic in the number of blocks.
\end{itemize}
\papersource{Paper, Table 3, PDF p.8; complexity interpretation: reading analysis.}
\end{frame}

\begin{frame}{The similarity guard prevents damaging outliers}
\centering
\begin{tabular}{lrr}\toprule
Mochi & Without guard & With guard\\\midrule
VQA-a $\uparrow$ &34.664&54.179\\
VQA-t $\uparrow$ &44.722&67.219\\
FScore $\uparrow$ &1.138&1.807\\\bottomrule\end{tabular}
\medskip
\par Appendix: on a selected $\sim$2\% high-difference subset,
CogVideoX L1 is 0.214 without vs. 0.0843 with the guard.
\par This selected subset is not the population average.

\papersource{Paper, Tables 5 and 10; Appendix A.2, PDF pp.9,14--15.}
\end{frame}

\begin{frame}{Hilbert ordering trades a little accuracy for sparsity}
\centering
\begin{tabular}{lrrrr}\toprule
Mochi & Sim-q & Sim-k & L1 $\downarrow$ & Sparsity\\\midrule
Random&.321&.019&.0414&.048\\
Row-major&.551&.390&.0307&.363\\
Hilbert&.572&.479&.0389&.392\\\bottomrule\end{tabular}
\medskip
\par Row-major to Hilbert: sparsity increases by 2.9 percentage points.
\par Random ordering retains accuracy by falling back to more computation.

\papersource{Paper, Tables 4 and 9, PDF pp.9,14. Ablation settings differ from Table 1.}
\end{frame}

\begin{frame}{The two stages overlap; longer contexts expose more sparsity}
\begin{block}{Llama3.1, 128K NIAH}
Only $M_g$: 51.2\%; only $M_{pv}$: 27.7\%; together: 54\%.
The incremental gain over stage 1 is 2.8 percentage points.
\end{block}
\begin{center}\begin{tabular}{lrrrrr}\toprule
Length&8K&16K&24K&48K&128K\\\midrule
Sparsity&6.8\%&26.4\%&35.7\%&49.8\%&54\%\\\bottomrule\end{tabular}\end{center}
These are measured trends under the paper's accuracy constraint,\par
not a guarantee for every longer input.

\papersource{Paper, Tables 6--7, PDF p.9.}
\end{frame}

\begin{frame}{Diffusion sparsity varies over sampling steps}
\centering
\includegraphics[width=.8\linewidth,height=.61\textheight,keepaspectratio]{figures/timestep-wise.pdf}
\par Layer and head variation is also substantial; prompt averages vary less.

\papersource{Paper, Appendix A.4, Figs.14--17, PDF pp.17--18. Shown: original Fig.15.}
\end{frame}

\begin{frame}{What the evidence supports, and what remains open}
\begin{itemize}
\item Supported: selective protection plus two-stage skipping is practical across the tested model families.
\item Calibration, quantization and CUDA implementation are part of the result.
\item No arbitrary-input error theorem; some quality metrics decline; repeated-run uncertainty is not reported.
\item Reproduction needs exact threshold semantics, kernel versions, baseline settings and hardware details.
\item Discussion: can omitted mass and value norms provide a stronger error control?
\end{itemize}
\papersource{Paper, Secs.3--4 and Appendix; limitations and question: reading analysis.}
\end{frame}

\begin{frame}{Reference and scope of this reading}
\textbf{Jintao Zhang, Chendong Xiang, Haofeng Huang, Jia Wei, Haocheng Xi, Jun Zhu, Jianfei Chen.}
\medskip
\par SpargeAttention: Accurate and Training-free Sparse Attention Accelerating Any Model Inference.
\par ICML 2025; arXiv:2502.18137v8, revised 19 November 2025.
\medskip
\par \url{https://arxiv.org/abs/2502.18137v8}
\par \url{https://github.com/thu-ml/SpargeAttn}
\medskip
\par Read from the version-matched PDF, author TeX and figures.
\par Experiments are reported by the paper, not independently reproduced.

\papersource{Reading prepared 18 September 2026. Main talk: about 25--30 minutes.}
\end{frame}

\begin{frame}{Backup: medium-length retrieval and calibration gaps}
\begin{itemize}
\item Appendix Table 11 evaluates NIAH across 16--28K; the speed row is labeled 24K.
\item Full to Sparge: 156.9 to 443.6 TOPS; NIAH 0.838 to 0.863; sparsity 0.36.
\item Section 4.1 says MInference 30\%/70\%, while main table labels are mostly 0.3/0.5; the discrepancy is unresolved.
\item The full calibration grid, cost, sample sensitivity and head-wise configuration are not specified.
\end{itemize}
\papersource{Paper, Table 11, PDF p.15; Secs.3.6,4.1,4.3, PDF pp.5--9.}
\end{frame}
\end{document}