% Derived from the arxiv-paper-reader Beamer template.
% Build: python3 build_slides.py slides.en.tex
\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}}
\newcommand{\takeaway}[1]{\begin{block}{Key point}#1\end{block}}
\newcommand{\figasset}[3]{\includegraphics[width=#2\linewidth,height=#3\textheight,keepaspectratio]{figures/#1}}
\newcommand{\pp}{\,pp}

\title[Diffuser]{Diffuser}
\subtitle{Efficient Transformers with Multi-hop\\Attention Diffusion for Long Sequences}
\author{Paper authors: Aosong Feng, Irene Li, Yuang Jiang, Rex Ying\\[2mm]
{\small Yale University}}
\date{Research group discussion\\
\href{https://arxiv.org/abs/2210.11794v2}{arXiv:2210.11794v2 --- 31 January 2023}\\
Reading prepared: 9 October 2026}

\begin{document}

\begin{frame}
\titlepage
\vspace{-3mm}
\begin{center}
\color{AcademicTeal}Compute sparse attention once; propagate values several times.
\end{center}
\end{frame}

\begin{frame}{Sparse edges can delay important information}
\begin{columns}[T,onlytextwidth]
\begin{column}{0.49\textwidth}
\begin{itemize}
  \item A sparse attention layer directly reads only its allowed neighbors.
  \item Distant cues may require several network layers to arrive.
  \item Fixed block boundaries also change the routing after a small input shift.
\end{itemize}
\takeaway{Can one layer reach farther while retaining sparse computation?}
\end{column}
\begin{column}{0.48\textwidth}
\centering
\figasset{fig-s1-motivation.pdf}{1.0}{0.67}
\end{column}
\end{columns}
\papersource{Introduction; Fig. S.1, PDF pp. 1--2.}
\end{frame}

\begin{frame}{One set of edge weights supports repeated propagation}
\begin{columns}[T,onlytextwidth]
\begin{column}{0.50\textwidth}
\begin{enumerate}
  \item Project the input into $Q,K,V$.
  \item Compute attention scores on sparse edges.
  \item Reuse those scores for $K$ propagation steps.
  \item Apply output projection, residuals and the feed-forward module.
\end{enumerate}
\medskip
\alert{No new query--key scores are computed between diffusion steps.}
\end{column}
\begin{column}{0.46\textwidth}
\centering
\figasset{fig-s3-architecture.pdf}{0.90}{0.69}
\end{column}
\end{columns}
\papersource{Model Architecture; Fig. S.3, PDF p. 4.}
\end{frame}

\begin{frame}{Local, global and random edges serve different roles}
\centering
\figasset{fig-s2-patterns.pdf}{0.84}{0.43}
\medskip
\begin{columns}[T,onlytextwidth]
\begin{column}{0.31\textwidth}
\textbf{Local windows}\\
Preserve nearby structure; overlap adjacent windows.
\end{column}
\begin{column}{0.31\textwidth}
\textbf{Global tokens}\\
Provide short routes across the entire sequence.
\end{column}
\begin{column}{0.31\textwidth}
\textbf{Random edges}\\
Distribute long-range routes across individual tokens.
\end{column}
\end{columns}
\medskip
\raggedright
Global and random selections use individual tokens, unlike BigBird's blocks.
\papersource{Sparse Pattern Design; Fig. S.2, PDF pp. 3--4.}
\end{frame}

\begin{frame}{Multi-hop weights are products along attention paths}
\[
A_{ij}=
\frac{\exp(Q_iK_j^\top/\sqrt d)}
{\sum_{u\in Ne(i)}\exp(Q_iK_u^\top/\sqrt d)}
\quad (j\in Ne(i));\qquad A_{ij}=0\ \text{otherwise}.
\]
\begin{itemize}
  \item $Ne(i)$ is the allowed key set; every row of $A$ sums to one.
  \item $Q,K$ have $n$ rows; $V\in\mathbb R^{n\times d_v}$.
\end{itemize}
\[
  (A^2)_{ij}=\sum_u A_{iu}A_{uj},
  \qquad
  \mathcal A=\sum_{k=0}^{\infty}\theta_kA^k.
\]
\takeaway{An indirect relationship is composed from existing edges.
It need not equal the missing direct query--key score.}
\papersource{Eqs. S.5--S.6, PDF p. 3. $\theta_k\ge0$ and $\sum_k\theta_k=1$.}
\end{frame}

\begin{frame}{PPR computes diffusion through sparse matrix--value products}
\[
\boxed{Z_{(0)}=V,\qquad
Z_{(k+1)}=(1-\alpha)AZ_{(k)}+\alpha V}
\]
\begin{itemize}
  \item $K$ steps per layer; the original $V$ is injected at every step.
  \item $\alpha$ controls how much the output retains the source values.
  \item Compute $AZ$ directly with sparse kernels.
\end{itemize}
\medskip
For $0<\alpha\le1$, the limiting operator is
\[
\mathcal A=\sum_{k=0}^{\infty}\alpha(1-\alpha)^kA^k
=\alpha[I-(1-\alpha)A]^{-1}.
\]
\alert{The implementation forms neither the inverse nor the dense diffusion matrix.}
\papersource{Eq. S.7, PDF p. 3; Appendix A, Proposition 4, PDF p. 11.}
\end{frame}

\begin{frame}{Five steps give a finite polynomial in the sparse attention}
\[
Z_{(K)}=
\left[(1-\alpha)^KA^K+
\alpha\sum_{i=0}^{K-1}(1-\alpha)^iA^i\right]V.
\]
At $K=5$ and $\alpha=0.1$:
\[
\begin{aligned}
Z_{(5)}=\bigl(&0.1I+0.09A+0.081A^2+0.0729A^3\\
             &+0.06561A^4+\alert{0.59049}A^5\bigr)V.
\end{aligned}
\]
\begin{itemize}
  \item Reach is limited to paths of at most $K$ edges.
  \item Bidirectional global tokens make every pair reachable within two hops.
  \item Task saturation at five steps does not measure PPR approximation error.
\end{itemize}
\papersource{Appendix A, PDF p. 11; coefficient expansion is a teaching derivation.}
\end{frame}

\begin{frame}{The cost depends on both edge count and propagation steps}
For one head, with $|\mathcal E|$ retained edges:
\[
\underbrace{O(|\mathcal E|d)}_{\text{sparse scores}}
\quad+\quad
\underbrace{O(K|\mathcal E|d_v)}_{\text{value propagation}}.
\]
\begin{itemize}
  \item Fixed local/global/random budgets give $|\mathcal E|=O(n)$.
  \item Linear attention-module cost also requires fixed $K$.
  \item Edge weights use $O(|\mathcal E|)$ storage; one state uses $O(nd_v)$.
\end{itemize}
\medskip
\centering
\begin{tabular}{lrrr}
\toprule
Nonzero entries / $n^2$ & Longformer & BigBird & Diffuser\\
\midrule
$n=4{,}096$ & 18.0\% & 16.9\% & 11.2\%\\
$n=8{,}192$ & 9.2\% & 8.7\% & 5.7\%\\
\bottomrule
\end{tabular}\par
\papersource{Tables S.1/S.8, PDF pp. 4/12. Cost accounting excludes projections and FFNs; training may retain multiple states.}
\end{frame}

\begin{frame}{The theoretical claims concern different objects}
\begin{block}{Universal approximation}
Construct sequence identifiers, then map them to outputs.\\
The appendix uses $K>n$ and a designated global token.
\end{block}
\begin{block}{Expander graphs}
A sparse regular graph approximates a \emph{scaled} complete graph
in Laplacian quadratic forms.
\end{block}
\begin{block}{Fast mixing}
A small nontrivial eigenvalue magnitude gives rapid random-walk mixing.
\end{block}
\alert{These results do not give an arbitrary learned full-attention error bound
for the practical $K=5$ model.}
\papersource{Theorems 1--3, PDF p. 5; Appendices C--D, PDF pp. 12--17.}
\end{frame}

\begin{frame}{Evaluation asks about quality, long-range structure and cost}
\centering
\begin{tabular}{p{3.1cm}p{6.8cm}l}
\toprule
Experiment & Setting & Metric\\
\midrule
MLM & RoBERTa initialization; continue training at 4K & BPC $\downarrow$\\[2mm]
Classification / QA & Five classification sets; WikiHop, TriviaQA & F1/Acc/EM $\uparrow$\\[2mm]
Image density & CIFAR-10 and ImageNet-64 sequences & BPD $\downarrow$\\[2mm]
LRA & Five text, reasoning and vision tasks & Acc $\uparrow$\\[2mm]
Resource use & Sequence lengths 1K--4K & GB, sec $\downarrow$\\
\bottomrule
\end{tabular}\par
\medskip
\raggedright
Language configuration: 12 layers, width 768, 12 heads; $K=5$, $\alpha=0.1$.
\papersource{Experiments, PDF pp. 6--7; Appendix E, Tables S.9--S.12, PDF pp. 17--18.}
\end{frame}

\begin{frame}{Changing the operator requires continued pretraining}
\begin{columns}[T,onlytextwidth]
\begin{column}{0.49\textwidth}
\centering
\begin{tabular}{lr}
\toprule
Model / stage & MLM BPC $\downarrow$\\
\midrule
RoBERTa & 2.02\\
Longformer & 1.86\\
BigBird & 1.82\\
\midrule
Diffuser, initialization & 3.52\\
Diffuser, 10K steps & 1.96\\
Diffuser, 50K steps & \textbf{1.68}\\
\bottomrule
\end{tabular}\par
\end{column}
\begin{column}{0.47\textwidth}
\begin{itemize}
  \item Books, CC-News and Wikipedia.
  \item 15\% masked tokens; maximum length 4,096.
  \item Initialization degrades before adaptation improves the result.
  \item At 50K steps: 0.14 lower BPC than BigBird.
\end{itemize}
\end{column}
\end{columns}
\papersource{Table S.2, PDF p. 6; Appendix E, PDF p. 17. BPC is the paper's MLM evaluation measure.}
\end{frame}

\begin{frame}{Text classification improves on average}
\centering
\begin{tabular}{lrr}
\toprule
Model & Five-task mean F1 $\uparrow$ & A-2048 F1 $\uparrow$\\
\midrule
BigBird & 80.14 & 63.6\\
BigBird + diffusion & 80.84 & 63.4\\
Longformer & 80.86 & 61.2\\
Longformer + diffusion & 81.24 & 62.5\\
Diffuser & \textbf{81.80} & \textbf{64.8}\\
\bottomrule
\end{tabular}\par
\medskip
\begin{itemize}
  \item \textbf{+0.94 percentage points} over the original Longformer.
  \item +0.56 points over Longformer with diffusion.
  \item Individual winners differ: IMDB favors Longformer; 20NG favors its diffusion variant.
\end{itemize}
\papersource{Table S.3, PDF p. 6. Mean over HYP, 20NG, IMDB, A-512 and A-2048; selected columns.}
\end{frame}

\begin{frame}{Question answering improves across the reported metrics}
\centering
\begin{tabular}{lrrr}
\toprule
Model & WikiHop Acc & TriviaQA F1 & TriviaQA EM\\
\midrule
RoBERTa & 71.82 & 74.02 & 66.87\\
Longformer & 75.30 & 74.82 & 67.24\\
BigBird & 74.54 & 73.16 & 68.26\\
Diffuser & \textbf{75.80} & \textbf{75.84} & \textbf{70.20}\\
\bottomrule
\end{tabular}\par
\medskip
\begin{itemize}
  \item WikiHop selects an answer using evidence across documents.
  \item TriviaQA predicts an answer span.
  \item Gains over the best baseline in each column:\\
        \textbf{+0.50 / +1.02 / +1.94 percentage points}.
\end{itemize}
\papersource{Table S.4, PDF p. 7; Appendix E, PDF p. 18. Higher is better for all three metrics.}
\end{frame}

\begin{frame}{Image density gains are small and dataset-dependent}
\centering
\begin{tabular}{lrrr}
\toprule
Dataset & Sequence length & Sparse Trans. & Diffuser\\
\midrule
CIFAR-10 & 3,072 & 2.80 & \textbf{2.78}\\
ImageNet-64 & 12,288 & \textbf{3.44} & \textbf{3.44}\\
\bottomrule
\end{tabular}\par
\medskip
Bits per dimension (BPD): lower is better.
\begin{itemize}
  \item CIFAR-10: 0.02 BPD improvement.
  \item ImageNet-64: a tie at the reported precision.
\end{itemize}
\begin{block}{Use the dataset-specific appendix configuration}
CIFAR-10: 8 layers, width 512.\\
ImageNet-64: 20 layers, width 768.
\end{block}
\papersource{Table S.5, PDF p. 7; Appendix E, PDF p. 18. The main text broadly describes an 8-layer/512 model.}
\end{frame}

\begin{frame}{LRA has three task wins and an inconsistent reported mean}
\centering
\setlength{\tabcolsep}{8pt}
\begin{tabular}{lrrrrr}
\toprule
Model & ListOps & Text & Retrieval & Image & Pathfinder\\
\midrule
Transformer & 36.37 & 64.27 & 57.46 & 42.44 & 71.40\\
BigBird & 36.05 & 64.02 & 59.29 & 40.83 & 74.87\\
Diffuser & \textbf{37.52} & 65.20 & \textbf{61.28} & \textbf{45.20} & 76.58\\
\bottomrule
\end{tabular}\par
\medskip
\begin{block}{Recompute from the five listed scores}
Diffuser: $57.156\approx57.16$;\quad BigBird: $55.012\approx55.01$.\\
Improvement: \textbf{2.144 percentage points}.
\end{block}
\begin{itemize}
  \item Paper reports 57.31 and +2.30 points; the arithmetic differs.
  \item Best Text: Linear Transformer (65.90).\\
        Best Pathfinder: Performer (77.05).
\end{itemize}
\papersource{Table S.6, PDF p. 7. Bold marks Diffuser's wins over all listed baselines. The overall mean ranking is unchanged.}
\end{frame}

\begin{frame}{Removing diffusion or local edges hurts most}
\centering
\begin{tabular}{lrr}
\toprule
Variant & Recomputed LRA mean & Drop from full model\\
\midrule
Full Diffuser & 57.16 & ---\\
No local edges & 52.65 & 4.51 points\\
No random edges & 55.74 & 1.41 points\\
No global edges & 55.19 & 1.97 points\\
No diffusion & 52.36 & \textbf{4.79 points}\\
Uniformly spaced edges & 57.07 & 0.09 points\\
\bottomrule
\end{tabular}\par
\medskip
\begin{itemize}
  \item \emph{Uniform} changes edge placement, not attention weights.
  \item Distributed routes remain useful even without random placement.
  \item Removing edge types also changes the total edge budget.
\end{itemize}
\papersource{Table S.7, PDF p. 7; Appendix B, PDF p. 12. Means and drops recomputed from the five task scores.}
\end{frame}

\begin{frame}{A small number of diffusion steps captures most task gains}
\centering
\figasset{fig-s5-diffusion.pdf}{0.94}{0.57}
\begin{itemize}
  \item A-2048 performance plateaus around $K=5$.
  \item Too much restart weakens propagation; the authors choose $\alpha=0.1$.
\end{itemize}
\papersource{Fig. S.5, PDF p. 7. Original y-axis: Accuracy (\%); classification Table S.3 reports F1.}
\end{frame}

\begin{frame}{The mix of edge types matters as much as their presence}
\centering
\figasset{fig-s6-attention-budget.pdf}{1.0}{0.54}
\begin{itemize}
  \item More connections eventually saturate or reduce performance.
  \item A mixture of global and random routes beats either endpoint.
  \item The edge budget trades locality, coverage and compute.
\end{itemize}
\papersource{Fig. S.6, PDF p. 7. Left to right: local, random, global budgets; random share of random + global edges.}
\end{frame}

\begin{frame}{Low memory comes with a propagation-time cost}
\centering
\figasset{fig-s4-efficiency.pdf}{0.94}{0.55}
\begin{itemize}
  \item At 4K: $\sim$7.2 GB vs.\ Performer's $\sim$12 GB; Linformer is close.
  \item Diffuser $\sim$0.75 sec/iteration vs.\ Performer $\sim$0.25.
\end{itemize}
\papersource{Fig. S.4, PDF p. 6. Approximate plot readings. The claimed 1.67$\times$ memory ratio corresponds to about 40\% less memory.}
\end{frame}

\begin{frame}{Diffuser is less sensitive to the tested input shifts}
\centering
\figasset{fig-s11-rolling.pdf}{0.94}{0.54}
\begin{itemize}
  \item Input tokens and masks are rolled together at length 4,096.
  \item The test changes both sparse routing and content--position alignment.
\end{itemize}
\papersource{Appendix F; Fig. S.11, PDF pp. 18--19. HYP (left), A-2048 (right); y-axis is F1.}
\end{frame}

\begin{frame}{The useful idea is to separate scoring from propagation}
\begin{block}{Mechanism}
Reuse sparse attention weights to aggregate values along multiple paths
within one layer.
\end{block}
\begin{block}{Evidence}
Classification, QA and LRA improve overall; removing diffusion causes a large loss.
Image-density gains are modest.
\end{block}
\begin{block}{Tradeoff}
Fewer stored edges help memory, while repeated aggregation costs time.
Practical performance depends on the graph and sparse kernels.
\end{block}
\papersource{Synthesis of Eqs. S.5--S.7, Tables S.2--S.7 and Fig. S.4, PDF pp. 3--7.}
\end{frame}

\begin{frame}{Paper and discussion prompts}
\textbf{Aosong Feng, Irene Li, Yuang Jiang, Rex Ying}\\[1mm]
\emph{Diffuser: Efficient Transformers with Multi-hop Attention Diffusion
for Long Sequences}\\[2mm]
\href{https://arxiv.org/abs/2210.11794v2}{arXiv:2210.11794v2}
\quad (31 January 2023)\\
Author-linked implementation:
\href{https://github.com/asFeng/Diffuser}{github.com/asFeng/Diffuser}
\medskip
\begin{itemize}
  \item At equal edge-access cost, when is diffusion better than adding edges?
  \item Which tasks need direct query--key scores that paths cannot preserve?
  \item How does the tradeoff change with optimized sparse kernels?
\end{itemize}
\papersource{Figures reproduced from the paper's TeX assets. Source page numbers refer to the 19-page v2 PDF.\\
Main talk: approximately 20--30 minutes. Backup slides follow.}
\end{frame}

\appendix

\begin{frame}{Backup: a three-token example exposes the mechanism}
\[
A=\begin{bmatrix}
\tfrac12&\tfrac12&0\\
0&\tfrac12&\tfrac12\\
0&0&1
\end{bmatrix},
\qquad \alpha=0.1.
\]
\[
Z_{(2)}=(0.1I+0.09A+0.81A^2)V.
\]
For token 1:
\[
\boxed{Z_{(2),1}=0.3475V_1+0.45V_2+0.2025V_3.}
\]
\begin{itemize}
  \item Direct weight $A_{13}=0$.
  \item The path through token 2 contributes $0.9^2 A_{12}A_{23}=0.2025$.
\end{itemize}
\papersource{Teaching example derived from Eq. S.7; not an experiment from the paper.}
\end{frame}

\begin{frame}{Backup: convergence is geometric, but five steps need not suffice}
Let $Z_\star=\mathcal AV$ and $E_k=Z_{(k)}-Z_\star$. Then
\[
E_{k+1}=(1-\alpha)AE_k,\qquad
E_K=(1-\alpha)^K A^K(V-Z_\star).
\]
Because $A$ is row-stochastic, with
$\|X\|_{\max}=\max_{i,j}|X_{ij}|$:
\[
\|E_K\|_{\max}\le(1-\alpha)^K\|V-Z_\star\|_{\max}.
\]
\begin{itemize}
  \item At $\alpha=0.1$, $K=5$, the worst-case factor is $0.59049$.
  \item The actual error depends on $A$ and $V$.
  \item Accuracy saturation and operator convergence are different measurements.
\end{itemize}
\papersource{Appendix A, Proposition 4, PDF p. 11; explicit finite-step error bound derived for this reading.}
\end{frame}

\begin{frame}{Backup: what the universal-approximation construction uses}
\begin{enumerate}
  \item Approximate a continuous function on a compact domain by gridwise constants.
  \item Quantize inputs, add positional identifiers and use hardmax heads
        to encode context.
  \item Approximate the modified construction with ordinary softmax/FFN layers.
\end{enumerate}
\begin{block}{Conditions that matter}
The main statement assumes self-loops and a Hamiltonian path.\\
The appendix additionally uses $K>n$ and a chosen global token.
\end{block}
Reducing the count of network layers does not eliminate the cost of propagation.
\papersource{Theorem 1, PDF p. 5; Appendix C, especially PDF p. 15. The guarantee uses integrated $L^q$ error.}
\end{frame}

\begin{frame}{Backup: spectral approximation needs a scaled complete graph}
For an undirected, unweighted, $d$-regular expander:
\[
|\mu_i|\le\epsilon d\quad(i\ge2),
\qquad
H=\frac dnK_n.
\]
\[
(1-\epsilon)L_H\preceq L_G\preceq(1+\epsilon)L_H.
\]
For the random-walk matrix $\widehat A=A/d$:
\[
\|\widehat A^tv-u\|_1\le\sqrt n\,\beta^t,\qquad
\beta=\frac{\max(|\mu_2|,|\mu_n|)}d<1.
\]
\alert{The object here is graph topology under regularity assumptions,
not an arbitrary content-weighted attention matrix.}
\papersource{Theorems 2--3, PDF p. 5; Appendix D, PDF pp. 16--17. Here $d$ means degree, not hidden width.}
\end{frame}

\begin{frame}{Backup: the PPR operator preferentially preserves low frequencies}
For $L=I-A$ with a real spectral decomposition:
\[
\mathcal A:\quad
h(\lambda)=\frac{\alpha}{\alpha+(1-\alpha)\lambda},
\qquad
\mathcal L=I-\mathcal A:\quad
\widetilde\lambda=1-h(\lambda).
\]
\begin{itemize}
  \item $h(0)=1$: the constant mode is retained.
  \item $h(\lambda)$ decreases as frequency $\lambda$ increases.
  \item This low-pass interpretation assumes a symmetric or reversible
        normalized graph.
  \item The feature response $h(\lambda)$ and the new Laplacian eigenvalue
        $\widetilde\lambda$ are different quantities.
\end{itemize}
\papersource{Appendix A, Proposition 5 and Eq. S.10, PDF p. 11; response-form explanation derived for this reading.}
\end{frame}

\begin{frame}{Backup: dispersed random edges change the topology spectrum}
\centering
\figasset{fig-s8-pattern-spectra.pdf}{0.91}{0.70}
\papersource{Fig. S.8, PDF p. 13. Normalized Laplacian eigenvalue vs.\ index; marked extreme eigenvalues are joined by lines.}
\end{frame}

\end{document}