% Compile with pdflatex via build_slides.py.
\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[Associative memory]{Understanding Transformer from the Perspective of Associative Memory}
\subtitle{Capacity, memory updates, and DeltaFormer}
\author{Paper authors: Shu Zhong, Mingyu Xu, Tenglong Ao, Guang Shi}
\date{arXiv:2505.19488v1 \quad | \quad Paper reading, 6 Nov 2026}

\begin{document}

\begin{frame}
  \titlepage
  \vspace{-0.4cm}
  \centering\small\href{https://arxiv.org/abs/2505.19488v1}{Versioned arXiv paper}
\end{frame}

\begin{frame}{The paper connects retrieval capacity to write rules}
  \begin{block}{One-sentence takeaway}
    Attention and FFNs can be read as associative memories; kernel choice controls retrieval interference, while the delta rule controls how old values are revised.
  \end{block}
  \begin{itemize}
    \item \textbf{Capacity:} inverse retrieval SNR compares target signal with cross-key interference.
    \item \textbf{Update:} DeltaFormer combines kernel matching with residual writing.
    \item \textbf{Evidence:} a constructive swap argument and finite synthetic learning curves.
  \end{itemize}
  \papersource{Paper, Secs. 1--3, PDF pp. 1--21.}
\end{frame}

\begin{frame}{Paper identity and code status}
  \begin{itemize}
    \item \textbf{Paper read:} \href{https://arxiv.org/abs/2505.19488v1}{arXiv:2505.19488v1}, submitted 26 May 2025.
    \item \textbf{Publication:} no formal publication record found for \emph{this article} as of 6 Nov 2026.
    \item A \href{https://proceedings.nips.cc/paper_files/paper/2025/hash/f9f2c4cb372afceb26394e78619367b1-Abstract-Conference.html}{distinct expanded DeltaFormer paper} by overlapping authors appeared at NeurIPS 2025.
    \item \textbf{Code:} author toy code in Appendix E.4; \href{https://github.com/fla-org/flash-linear-attention/blob/main/fla/layers/deltaformer.py}{third-party FLA implementation}. No separate author repository located.
  \end{itemize}
  \papersource{Paper, arXiv abstract and Appendix E.4; NeurIPS proceedings; FLA repository.}
\end{frame}

\begin{frame}{A memory has a write operation and a read operation}
  \begin{align*}
    S_t &= \sum_{i\leq t} v_i\phi(k_i)^\top, &
    o(q) &= S_t\phi(q)=\sum_{i\leq t}\kappa(k_i,q)v_i,\\
    \kappa(x,y)&=\phi(x)^\top\phi(y), &
    S_t&\in\mathbb{R}^{d_v\times d_\phi}.
  \end{align*}
  \begin{itemize}
    \item $k_i$ indexes a value $v_i$; $q$ retrieves by similarity.
    \item Context attention writes transient token associations.
    \item FFN weights hold persistent associations learned during training.
  \end{itemize}
  \papersource{Paper, Sec. 2, PDF pp. 3--4. Softmax normalization is omitted in this algebraic form.}
\end{frame}

\begin{frame}{Inverse SNR measures cross-key interference}
  \begin{align*}
    o(k_i)&=\underbrace{v_i\kappa(k_i,k_i)}_{\text{signal }c v_i}
       +\underbrace{\sum_{j\neq i}v_j\kappa(k_j,k_i)}_{\text{noise }r},\\
    \mathrm{SNR}^{-1}&=\mathbb E\!\left[\frac{\|r\|^2}{c^2\|v_i\|^2}\right]
      \approx N\frac{\mathbb E_{k_j}[\kappa(k_j,k_i)^2]}{\kappa(k_i,k_i)^2}.
  \end{align*}
  \begin{block}{Interpretation}
    Lower inverse SNR means cleaner recall for a stored key.
  \end{block}
  \papersource{Paper, Sec. 2.1, Eqs. (5)--(10), PDF pp. 4--5; Appendix A, pp. 26--27. Independent Gaussian keys/values and comparable value norms.}
\end{frame}

\begin{frame}{The exponential kernel suppresses random-key noise}
  \centering
  \begin{tabular}{lcc}
    \toprule
    Kernel $\kappa(x,y)$ & Approx. inverse SNR & Condition \\
    \midrule
    $x^\top y$ & $N/d_k$ & linear \\
    $\max(0,x^\top y)$ & $N/(2d_k)$ & ReLU \\
    $\exp(x^\top y/\tau)$ & $N e^{-2(\tau-1)d_k/\tau^2}$ & $\tau>1$ \\
    \bottomrule
  \end{tabular}
  \vspace{0.35cm}
  \begin{itemize}
    \item At $\tau=\sqrt{d_k}$, constant inverse SNR needs $d_k$ on the order of $\log^2 N$, versus order $N$ for a linear kernel.
    \item This is a Gaussian-key retrieval calculation, not a universal LLM capacity law.
  \end{itemize}
  \papersource{Paper, Sec. 2.1, PDF pp. 5--7; Appendix A, pp. 27--28. $N$ is the number of stored pairs.}
\end{frame}

\begin{frame}{An FFN is also a key--value lookup}
  \[
    \mathrm{FFN}(x)=W_V^\top\mathrm{ReLU}(W_Kx)
       =\sum_{a=1}^{m}v_a\,\mathrm{ReLU}(k_a^\top x).
  \]
  \begin{itemize}
    \item Rows of $W_K$ act as keys; rows of $W_V$ provide values.
    \item The paper hypothesizes that a less selective FFN kernel helps compress many associations into fixed weights.
    \item Multihead, sparsity and gating are design axes discussed by the authors, not ablated for FFNs here.
  \end{itemize}
  \papersource{Paper, Sec. 2.1.1, Eq. (14) and Table 1, PDF pp. 7--10.}
\end{frame}

\begin{frame}{The delta rule writes what the memory still misses}
  \begin{align*}
    \text{Linear:}\quad &S_t=S_{t-1}+v_tk_t^\top,\\
    \text{DeltaNet:}\quad &S_t=S_{t-1}+
       \underbrace{(v_t-S_{t-1}k_t)}_{\text{residual value}}k_t^\top.
  \end{align*}
  \begin{itemize}
    \item Linear attention keeps adding; related writes can accumulate.
    \item DeltaNet reads the existing value at $k_t$, then corrects it.
    \item Its update is one gradient step on $\tfrac12\|S_{t-1}k_t-v_t\|^2$ (unit step size).
  \end{itemize}
  \papersource{Paper, Sec. 2.2, Table 2, PDF pp. 10--12; Appendix B, pp. 29--30.}
\end{frame}

\begin{frame}{DeltaFormer performs residual writing with kernel matches}
  \begin{block}{General recurrence}
    \begin{align*}
      u_t &= \alpha_t v_t-\beta_t\sum_{i<t}\kappa_1(k_i,w_t)u_i,\\
      o_t &= \sum_{i\leq t}\kappa_2(k_i,q_t)u_i.
    \end{align*}
  \end{block}
  \begin{itemize}
    \item $\kappa_1$ decides which previous writes to subtract; $\kappa_2$ reads the corrected values.
    \item $\alpha_t,\beta_t$ gate new information and the subtraction.
    \item $\beta_t=0$ gives ordinary attention after output normalization; linear kernels with $w_t=k_t$ recover DeltaNet.
  \end{itemize}
  \papersource{Paper, Sec. 2.2.1, PDF pp. 12--14.}
\end{frame}

\begin{frame}{The residual recurrence follows from a kernel delta update}
  \begin{align*}
    S_t&=S_{t-1}+[v_t-S_{t-1}\phi(k_t)]\phi(k_t)^\top,\\
    S_{t-1}&=\sum_{i<t}u_i\phi(k_i)^\top,\\
    \Rightarrow\quad u_t&=v_t-\sum_{i<t}\kappa(k_i,k_t)u_i.
  \end{align*}
  \begin{itemize}
    \item Exact algebra requires the same feature map for writing and reading.
    \item Independent $\kappa_1$ and $\kappa_2$ in the general model are a further design choice.
    \item Softmax normalization is restored in practical variants.
  \end{itemize}
  \papersource{Paper, Sec. 2.2.1, PDF p. 13; Appendix C, PDF pp. 31--32.}
\end{frame}

\begin{frame}{The write dependency costs parallel depth}
  \[
    U=V-AU\quad\Longrightarrow\quad U=(I+A)^{-1}V,
    \qquad A_{t,i}=\kappa_1(k_i,w_t)\; (i<t).
  \]
  \begin{itemize}
    \item Naive sequence computation: $O(T^2d)$ work, $O(T)$ serial steps.
    \item Invert a strictly lower triangular block of length $C$ in parallel; advance across $T/C$ blocks.
    \item The appendix gives $O(T^2d+TCd+TC^2)$ work for this trade-off. No measured speedup is reported in this paper.
  \end{itemize}
  \papersource{Paper, Sec. 2.2.1, PDF pp. 15--16; Appendix D.3, PDF pp. 33--35.}
\end{frame}

\begin{frame}{State exchange is a constructive, conditional result}
  \begin{itemize}
    \item Initial unit keys are almost orthogonal: $|k_i^\top k_j|\leq\epsilon<1/8$ for $i\ne j$.
    \item A function $f$ maps neighborhoods of $-1,0,1,2$ \emph{exactly} to those integers.
    \item For a swap of positions $a,b$, write $k_t=k_a-k_b$ and $v_t=0$.
    \item Then queries $k_a,k_b$ exchange their stored values; other queries stay unchanged.
  \end{itemize}
  \begin{block}{Scope}
    The paper relates this construction to $NC^1$ state tracking; an ``above $TC^0$'' interpretation depends on the complexity separation assumption.
  \end{block}
  \papersource{Paper, Appendix E, Theorem 1, PDF pp. 35--40.}
\end{frame}

\begin{frame}{Infinite context is a model-based extrapolation}
  \begin{align*}
    S^*&=(W_v\Sigma W_k^\top)(W_k\Sigma W_k^\top)^{-1},\\
    W_k\text{ square/invertible}\quad&\Rightarrow\quad S^*=W_vW_k^{-1}.
  \end{align*}
  \begin{itemize}
    \item For a stationary, single-head DeltaNet model, the fixed optimum suggests weakening context-specific updates.
    \item For Softmax, the paper approximates the normalized state update with a $1/t$ step at large $t$.
    \item These arguments do not establish degradation for a trained multilayer Transformer; a vanishing step alone does not prove vanishing cumulative adaptation.
  \end{itemize}
  \papersource{Paper, Sec. 2.2.2, PDF pp. 16--17; Appendices B.2 and F, PDF pp. 30--31, 46.}
\end{frame}

\begin{frame}{Evaluation separates retrieval and state tracking}
  \begin{tabular}{p{0.25\linewidth}p{0.62\linewidth}}
    \toprule
    Question & Setup and metric \\
    \midrule
    Head allocation & GPT-2 small: 12 layers, width 768; 12 vs. 1 head; validation loss $\downarrow$. Both kernels use per-head RMS normalization. \\
    Swap tracking & Five objects, context length 16; compare 1--8-layer Transformer with DeltaFormer kernels; accuracy $\uparrow$. \\
    Scaling/curriculum & Fixed $d=128$, $n=128,256,512$; direct length 256 versus curriculum 32 to 256; accuracy $\uparrow$. \\
    Graph reachability & 32-node constructed DAG task; Transformer versus DeltaFormer; accuracy $\uparrow$. \\
    \bottomrule
  \end{tabular}
  \papersource{Paper, Sec. 3, Figs. 2--7, PDF pp. 17--21.}
\end{frame}

\begin{frame}{One head helps linear attention but hurts the exp kernel}
  \centering
  \includegraphics[width=0.91\linewidth,height=0.63\textheight,keepaspectratio]{figures/fig-heads.png}
  \par\smallskip
  \small At fixed width 768, linear attention's one-head curve improves; the exp-kernel curve slightly worsens. Both use per-head RMS normalization.
  \papersource{Paper, Fig. 2, PDF pp. 17--18. Y-axis: validation loss, lower is better.}
\end{frame}

\begin{frame}{The swap task asks for the current value at position 1}
  \centering
  \includegraphics[width=0.85\linewidth,height=0.56\textheight,keepaspectratio]{figures/fig-swap-task.png}
  \par\smallskip
  \small Each input swaps two of five positions; at each step the model predicts the token now at position 1. Default context length is 16.
  \papersource{Paper, Sec. 3.2, Fig. 3, PDF p. 18.}
\end{frame}

\begin{frame}{Residual writing learns the five-object swap task}
  \begin{columns}[T,onlytextwidth]
    \begin{column}{0.49\textwidth}
      \centering\small Transformer, 1--8 layers\par
      \includegraphics[width=\linewidth,height=0.46\textheight,keepaspectratio]{figures/fig-swap-transformer.png}
    \end{column}
    \begin{column}{0.49\textwidth}
      \centering\small DeltaFormer, rounded $\kappa_1$\par
      \includegraphics[width=\linewidth,height=0.46\textheight,keepaspectratio]{figures/fig-swap-round.png}
    \end{column}
  \end{columns}
  \smallskip
  \small Transformer plateaus around 0.4--0.45; rounded and linear write kernels approach 1.0 within roughly 300 steps. Read each panel's y-axis separately.
  \papersource{Paper, Fig. 4, PDF pp. 18--19. Training accuracy vs. training step; $\kappa_2$ is Softmax.}
\end{frame}

\begin{frame}{At $d=128$, a nonlinear write kernel scales better}
  \centering
  \includegraphics[width=0.91\linewidth,height=0.61\textheight,keepaspectratio]{figures/fig-stress-512.png}
  \par\smallskip
  \small For $n=512$, the rounded-kernel curve exceeds 0.9, while the linear curve remains near 0.25. Keys and values were preset near orthogonality; the model learns mainly to read.
  \papersource{Paper, Sec. 3.2, Fig. 5c, PDF p. 19. Accuracy vs. training step; swap length 1024.}
\end{frame}

\begin{frame}{Curriculum resolves a hard optimization regime}
  \centering
  \includegraphics[width=0.90\linewidth,height=0.61\textheight,keepaspectratio]{figures/fig-curriculum-nope.png}
  \par\smallskip
  \small Without position embeddings, direct training at length 256 stays near chance (0.2); increasing length from 32 to 256 approaches full accuracy.
  \papersource{Paper, Sec. 3.2, Fig. 6b, PDF p. 20. Y-axis: accuracy at the current training length; colored bands mark curriculum stages.}
\end{frame}

\begin{frame}{DeltaFormer improves the constructed DAG task}
  \begin{columns}[T,onlytextwidth]
    \begin{column}{0.49\textwidth}
      \centering\small Transformer, 1--8 layers\par
      \includegraphics[width=\linewidth,height=0.45\textheight,keepaspectratio]{figures/fig-dag-transformer.png}
    \end{column}
    \begin{column}{0.49\textwidth}
      \centering\small DeltaFormer, 1 layer\par
      \includegraphics[width=\linewidth,height=0.45\textheight,keepaspectratio]{figures/fig-dag-deltaformer.png}
    \end{column}
  \end{columns}
  \smallskip
  \small On a 32-node reachability task, Transformer curves remain around 0.8; several DeltaFormer write kernels approach 1.0.
  \papersource{Paper, Sec. 3.3, Fig. 7, PDF pp. 20--21. Accuracy vs. training step; $\kappa_2$ is Softmax.}
\end{frame}

\begin{frame}{What the evidence supports}
  \begin{enumerate}
    \item \textbf{Mechanism:} kernels control interference; residual writing changes what is stored.
    \item \textbf{Theory:} an exact-kernel, near-orthogonal construction tracks swaps with logarithmic key dimension.
    \item \textbf{Experiments:} selected kernels and curricula learn finite swap and reachability tasks more readily than the reported Transformer baselines.
  \end{enumerate}
  \begin{block}{Next question}
    Does residual writing retain its benefit in end-to-end language modeling under equal compute and realistic context extrapolation?
  \end{block}
  \papersource{Paper, Secs. 2--4, PDF pp. 4--22; Appendix E, PDF pp. 35--40.}
\end{frame}

\begin{frame}{References and links}
  \begin{itemize}
    \item Zhong, Xu, Ao, Shi. \emph{Understanding Transformer from the Perspective of Associative Memory}. \href{https://arxiv.org/abs/2505.19488v1}{arXiv:2505.19488v1}, 2025.
    \item Distinct follow-up: Xu et al. \emph{DeltaFormer: Unlock the State Space of Transformer}. \href{https://proceedings.nips.cc/paper_files/paper/2025/hash/f9f2c4cb372afceb26394e78619367b1-Abstract-Conference.html}{NeurIPS 2025 proceedings}.
    \item \href{https://github.com/fla-org/flash-linear-attention/blob/main/fla/layers/deltaformer.py}{Flash Linear Attention: third-party DeltaFormer implementation}; author toy code is in the original paper's Appendix E.4.
  \end{itemize}
  \papersource{Publication/code links checked 6 Nov 2026. Original arXiv version is the source for every result slide.}
\end{frame}

\appendix

\begin{frame}{Backup: multiple write queries improve a tiny-key setting}
  \begin{columns}[T,onlytextwidth]
    \begin{column}{0.49\textwidth}
      \centering\small One write query\par
      \includegraphics[width=\linewidth,height=0.47\textheight,keepaspectratio]{figures/fig-gqa-1.png}
    \end{column}
    \begin{column}{0.49\textwidth}
      \centering\small Four write queries\par
      \includegraphics[width=\linewidth,height=0.47\textheight,keepaspectratio]{figures/fig-gqa-4.png}
    \end{column}
  \end{columns}
  \smallskip
  \small With head dimension 3, the nonlinear configuration rises from about 0.2 to near 1.0 as write-query count increases; the linear configuration remains near 0.6.
  \papersource{Paper, Appendix E.2, Fig. 8, PDF p. 40. Five-object, 16-swap training task.}
\end{frame}

\begin{frame}{Backup: the triangular solve exposes the compute trade-off}
  \[
    u_t=v_t-\sum_{i<t}A_{t,i}u_i,
    \qquad U=(I+A)^{-1}V.
  \]
  \begin{itemize}
    \item $A$ is strictly lower triangular; $(I+A)^{-1}$ exists.
    \item A chunk can be solved with matrix operations; chunks remain sequential.
    \item Parallel inversion adds work and does not by itself establish practical speed.
  \end{itemize}
  \papersource{Paper, Appendix D.3, Eqs. (96)--(100), PDF pp. 33--35.}
\end{frame}

\end{document}