% Research discussion prepared from arXiv:2505.16381v2.
% Main talk: frames 1--22, about 25 minutes. References: 23. Backup: 24--30.
% Build with: python3 build_slides.py slides.en.tex
\documentclass[aspectratio=169,11pt]{beamer}
\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage{lmodern}
\usepackage{amsmath,amssymb,graphicx,booktabs,array}

\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{\m}[1]{\mathbf{#1}}
\newcommand{\lo}{\operatorname{lower}}
\newcommand{\slo}{\operatorname{strictLower}}
\newcommand{\sig}{\operatorname{sigmoid}}

\title[PaTH Attention]{PaTH Attention}
\subtitle{Position Encoding via Accumulating\newline Householder Transformations}
\author{\small Paper authors: Songlin Yang, Yikang Shen, Kaiyue Wen, Shawn Tan,\newline
Mayank Mishra, Liliang Ren, Rameswar Panda, Yoon Kim}
\date{\small NeurIPS 2025 \quad | \quad arXiv:2505.16381v2 (3 Feb 2026)\newline
Independent paper discussion \quad | \quad 13 Oct 2026}

\begin{document}

\begin{frame}
  \titlepage
  \vspace{-3mm}
  \begin{center}
  \color{AcademicTeal}Let the events between two tokens transform how they match.
  \end{center}
\end{frame}

\begin{frame}{The path between tokens can carry state}
  \begin{block}{A concrete question}
  After writes, distractors, and swaps, which earlier record is still relevant?
  \end{block}
  \[
  \text{RoPE logit}=\m q_i^\top\m R^{i-j}\m k_j
  \]
  \begin{itemize}
    \item Queries and keys depend on content; the positional transform depends on distance.
    \item State tracking requires composing \alert{ordered events} between the endpoints.
    \item PaTH makes each step of that transformation depend on the input.
  \end{itemize}
  \papersource{Paper, Secs. 1--2, PDF pp. 1--3.}
\end{frame}

\begin{frame}{PaTH inserts a learned transformation along every path}
  \[
  \m H_t=\m I-\beta_t\m w_t\m w_t^\top,
  \qquad \beta_t=2\sig(\m u^\top\m x_t+b),\quad \|\m w_t\|_2=1
  \]
  \begin{block}{Causal attention, with product order explicit}
  \[
  \widetilde A_{ij}=\m k_j^\top
  \underbrace{\m H_{j+1}\m H_{j+2}\cdots\m H_i}_{\text{content-dependent path}}
  \m q_i,\qquad j\le i
  \]
  \[
  A_{ij}=\operatorname{softmax}_{j\le i}(\widetilde A_{ij}),
  \qquad \m o_i=\sum_{j\le i} A_{ij}\m v_j
  \]
  \end{block}
  $\m w_t$: low-rank projection $\rightarrow$ width-3 convolution $\rightarrow$ $L_2$ normalization.
  \papersource{Paper, Sec. 2.2 and footnote 2, PDF pp. 2--3. Attention scale omitted as in the paper.}
\end{frame}

\begin{frame}{One direction can shrink, disappear, or change sign}
  For $\m z=\m z_\perp+\alpha\m w_t$,
  \[
  \m H_t\m z=\m z_\perp+(1-\beta_t)\alpha\m w_t.
  \]
  \begin{center}
  \begin{tabular}{lll}
  \toprule
  $\beta_t$ & Along $\m w_t$ & Interpretation \\
  \midrule
  $(0,1)$ & Positive contraction & Attenuate \\
  $1$ & Zero & Erase \\
  $(1,2)$ & Negative contraction & Flip and attenuate \\
  $2$ & Exact reflection & Idealized proof endpoint \\
  \bottomrule
  \end{tabular}
  \end{center}
  \medskip
  Different directions generally \alert{do not commute}: event order matters.
  \papersource{Parameterization: Sec. 2.2, PDF p. 2. Eigenvalue interpretation derived here. Exact $\beta=2$: Appendix A, p. 17.}
\end{frame}

\begin{frame}{PaTH keeps a recurrent path and a softmax readout}
  A related linear RNN maintains a matrix state:
  \[
  \m S_t=\m S_{t-1}\m H_t+\m v_t\m k_t^\top,
  \qquad \m o_t=\m S_t\m q_t.
  \]
  Define $c_{tj}=\m k_j^\top(\m H_{j+1}\cdots\m H_t)\m q_t$.
  \begin{columns}[T]
  \begin{column}{0.47\textwidth}
    \begin{block}{Linear recurrence, unrolled}
    \[\m o_t=\sum_{j\le t}\m v_j c_{tj}\]
    History is compressed into $\m S_t$.
    \end{block}
  \end{column}
  \begin{column}{0.49\textwidth}
    \begin{block}{PaTH attention}
    \[\m o_t=\sum_{j\le t}\m v_j\frac{e^{c_{tj}}}{\sum_{r\le t}e^{c_{tr}}}\]
    Explicit historical values remain available.
    \end{block}
  \end{column}
  \end{columns}
  \papersource{Paper, Sec. 2.2, PDF p. 3. This connection does not give PaTH a fixed-size recurrent cache.}
\end{frame}

\begin{frame}{A reflection can implement a symbolic swap}
  \[
  \m w=\frac{\m e_a-\m e_b}{\sqrt2},\quad \beta=2
  \quad\Longrightarrow\quad
  (\m I-2\m w\m w^\top)\text{ swaps coordinates }a,b.
  \]
  \begin{block}{Theorem 2.1}
  A one-layer, two-head PaTH Transformer with $\log n$ precision can solve an
  $\mathsf{NC}^1$-complete problem under $\mathsf{AC}^0$ reductions.
  \end{block}
  \begin{itemize}
    \item Compose swaps of five elements; test whether the final permutation is identity.
    \item The separation from $\mathsf{TC}^0$ assumes $\mathsf{TC}^0\ne\mathsf{NC}^1$.
    \item The construction uses the ideal reflection endpoint; learned performance is tested separately.
  \end{itemize}
  \papersource{Paper, Theorem 2.1, PDF p. 3; construction in Appendix A, pp. 17--18.}
\end{frame}

\begin{frame}{FoX adds a separate mechanism for forgetting}
  \[
  f_t=\sig(\m u_f^\top\m x_t+b_f)\in(0,1)
  \]
  \begin{block}{PaTH-FoX attention}
  \[
  A_{ij}\propto
  \underbrace{\left(\prod_{s=j+1}^{i}f_s\right)}_{\text{forgetting}}
  \exp\!\left(
  \underbrace{\m k_j^\top\m H_{j+1}\cdots\m H_i\m q_i}_{\text{path-dependent matching}}
  \right)
  \]
  \end{block}
  \begin{itemize}
    \item PaTH changes the geometry of matching.
    \item FoX attenuates older unnormalized attention weights.
    \item The scalar product of gates is \alert{outside} the exponential.
  \end{itemize}
  \papersource{Paper, Sec. 2.2, PDF p. 3.}
\end{frame}

\begin{frame}{A triangular representation makes paths computable}
  Stack $\m w_t^\top$ into $\m W$ and define $\m D=\operatorname{diag}(\beta_t)$.
  \[
  \m U=(\m I+\slo(\m D\m W\m W^\top))^{-1}\m D
  \]
  \[
  \m H_L\cdots\m H_1=\m I-\m W^\top\m U\m W
  \]
  \begin{block}{All causal logits from shared matrix operations}
  \[
  \widetilde{\m A}=\lo(\m Q\m K^\top)
   -\lo(\m Q\m W^\top)\m U\slo(\m W\m K^\top)
  \]
  \end{block}
  Use \alert{local} triangular solves inside blocks; avoid a global $L\times L$ solve.
  \papersource{Paper, Secs. 3.1--3.3, PDF pp. 4--5. $\m U$ denotes the paper's $\m T^{-1}$; product orientation made explicit here.}
\end{frame}

\begin{frame}{A right-to-left scan accumulates cross-block paths}
  Precompute boundary-adjusted $\overleftarrow{\m Q}_b$,
  $\overrightarrow{\m K}_b$, and forward block product $\m F_b$.
  \begin{enumerate}
    \item Compute the causal diagonal block with the local formula.
    \item Set $\m Q_{\rm work}=\overleftarrow{\m Q}_b$.
    \item For earlier blocks $c=b-1,\ldots,0$:
  \end{enumerate}
  \[
    \widetilde{\m A}_{b,c}=\m Q_{\rm work}\overrightarrow{\m K}_c^\top
    \quad\longrightarrow\quad \text{online softmax and value accumulation}
  \]
  \[
    \m Q_{\rm work}\leftarrow\m Q_{\rm work}\m F_c^\top
  \]
  \alert{Read this block first, then cross its transition.}
  Query blocks can execute in parallel; the full attention matrix stays out of HBM.
  \papersource{Paper, Sec. 3.3, PDF p. 5. $\m F_c=\m H_{\rm first}\cdots\m H_{\rm last}$ fixes orientation and the missing identity term.}
\end{frame}

\begin{frame}{Decoding updates historical keys in place}
  \[
  \m k_j^{(t)}=\m k_j^{(t-1)}
   -\beta_t\m w_t\bigl(\m w_t^\top\m k_j^{(t-1)}\bigr),\quad j<t
  \]
  \[
  (\m k_j^{(t)})^\top\m q_t
   =\m k_j^\top\m H_{j+1}\cdots\m H_t\m q_t
  \]
  \begin{itemize}
    \item The transformed keys feed a standard softmax decoding readout.
    \item No separate cache of all past transition vectors is needed.
    \item Prefill must align keys to the prompt endpoint before decoding begins.
    \item Historical-key updates add $O(td)$ work per head and rewrite the cache.
  \end{itemize}
  \papersource{Paper, Sec. 3.4, PDF p. 6, Eq. (1). Complexity observation follows from the rank-one update.}
\end{frame}

\begin{frame}{The experiments ask three distinct questions}
  \begin{center}
  \small
  \renewcommand{\arraystretch}{1.35}
  \begin{tabular}{>{\raggedright\arraybackslash}p{0.21\textwidth}>{\raggedright\arraybackslash}p{0.31\textwidth}>{\raggedright\arraybackslash}p{0.35\textwidth}}
  \toprule
  Question & Evidence & Setting \\
  \midrule
  State tracking & FFLM; $A_5$; MQRAR-$N$ & Small Transformers \\
  Language modeling & Perplexity; commonsense; long context & 760M; 50B tokens; 4K context \\
  Model conversion & Math; code; general tasks & SmolLM2-1.7B; Qwen2.5-7B-Instruct \\
  \bottomrule
  \end{tabular}
  \end{center}
  \medskip
  RoPE: static position transform. FoX: learned forgetting.\newline
  SBA: ordered stick-breaking weights, evaluated on synthetic tasks.
  \papersource{Paper, Sec. 4, PDF pp. 7--10; training details in Appendix B, p. 20.}
\end{frame}

\begin{frame}{PaTH tracks sparse writes through heavy distraction}
  FFLM: return the bit from the most recent \texttt{write} operation.
  \begin{center}
  \texttt{w 1 r 1 w 0 i 1 i 0 i 1 r} $\quad\longrightarrow\quad$ \texttt{0}
  \par\medskip
  \begin{tabular}{lrrr}
  \toprule
  Error rate (\%) $\downarrow$ & ID & OOD sparse & OOD dense \\
  \midrule
  RoPE & 6.9 & 40.3 & 0.01 \\
  SBA & 9.6 & 38.9 & 0 \\
  FoX & 8.3 & 36.3 & 0 \\
  \alert{PaTH} & \alert{0} & \alert{0.0001} & \alert{0} \\
  \bottomrule
  \end{tabular}
  \end{center}
  All models: 1 layer, 2 heads, 64 dimensions.\newline
  Sparse: 98\% ignore operations. Dense: 10\% ignore operations.
  \papersource{Paper, Table 1 and Sec. 4.1, PDF p. 7. 0.0001\% is an error fraction of $10^{-6}$.}
\end{frame}

\begin{frame}{Ordered recall improves, and fewer layers solve swaps}
  \begin{columns}[c]
  \begin{column}{0.43\textwidth}
    \centering
    \includegraphics[width=\linewidth,height=0.72\textheight,keepaspectratio]{figures/fig-02-synthetic.pdf}
  \end{column}
  \begin{column}{0.54\textwidth}
    \textbf{Top: MQRAR-$N$}\par
    Recall the $N$-th previous assignment.\par
    PaTH stays strong through $N=3$ and degrades at $N=4$.
    \medskip\par
    \textbf{Bottom: $A_5$ word problem}\par
    Minimum depth for $>90\%$ accuracy.\par
    At length 20, PaTH uses about 2 layers; baselines use about 4.
    \medskip\par
    \small MQRAR: 2 layers, width 256, 2 heads; 32 KV pairs, length 768.
  \end{column}
  \end{columns}
  \papersource{Paper, Fig. 2 and Sec. 4.1, PDF pp. 7--8. Original figure; approximate layer counts read from plot.}
\end{frame}

\begin{frame}{Language modeling improves at a fixed token budget}
  760M parameters; 50B FineWeb-Edu tokens; context length 4096.
  \begin{center}
  \begin{tabular}{lrrrr}
  \toprule
  Model & Wiki. ppl$\downarrow$ & LMB. ppl$\downarrow$ & LMB. acc$\uparrow$ & Avg.$\uparrow$ \\
  \midrule
  RoPE & 19.01 & 19.77 & 40.4 & 52.7 \\
  FoX & 18.33 & 18.28 & 41.7 & 53.1 \\
  PaTH & 18.03 & 16.79 & 44.0 & \textbf{54.2} \\
  PaTH-FoX & \textbf{17.35} & \textbf{16.23} & \textbf{44.1} & \textbf{54.2} \\
  \bottomrule
  \end{tabular}
  \end{center}
  \begin{itemize}
    \item PaTH: \alert{+1.5 percentage points} in the six-task average over RoPE.
    \item PaTH-FoX lowers perplexity further, with the same rounded average.
    \item FoX remains better than PaTH on PIQA and WinoGrande.
  \end{itemize}
  \papersource{Paper, Table 2, PDF p. 8. Average: six accuracy metrics, excluding perplexity; HellaSwag and ARC-c use acc\_n.}
\end{frame}

\begin{frame}{Forgetting stabilizes extrapolation beyond 4K}
  \centering
  \includegraphics[width=0.98\linewidth,height=0.49\textheight,keepaspectratio]{figures/fig-03-length.pdf}
  \begin{itemize}
    \item Horizontal axis: token position, up to 64K. Lower perplexity is better.
    \item FoX and PaTH-FoX remain usable to 64K; the combination has lower perplexity.
    \item PaTH alone deteriorates beyond roughly 32K, most visibly in code.
  \end{itemize}
  \papersource{Paper, Fig. 3 and Sec. 4.2, PDF p. 8. Original figure; models trained at 4096 context length.}
\end{frame}

\begin{frame}{Dense retrieval benefits strongly from the combination}
  \begin{center}
  \begin{tabular}{lrrrr}
  \toprule
   & \multicolumn{2}{c}{RULER $\uparrow$} & \multicolumn{2}{c}{PhoneBook $\uparrow$} \\
  \cmidrule(lr){2-3}\cmidrule(lr){4-5}
  Model & 8K & 16K & 4K & 8K \\
  \midrule
  RoPE & 1.3 & 0.0 & 15.6 & 0.0 \\
  FoX & 29.5 & 4.9 & 38.5 & 17.7 \\
  PaTH & \textbf{34.8} & 18.7 & 20.8 & 0.0 \\
  PaTH-FoX & 34.0 & \textbf{22.6} & \textbf{93.8} & \textbf{66.6} \\
  \bottomrule
  \end{tabular}
  \end{center}
  \begin{block}{A useful distinction}
  PaTH's state-tracking gains do not automatically yield dense exact retrieval.\newline
  At 8K PhoneBook, PaTH scores 0.0; PaTH-FoX scores 66.6.
  \end{block}
  \papersource{Paper, Table 3, PDF p. 9. RULER averages 13 zero-shot tasks; training context is 4K.}
\end{frame}

\begin{frame}{The advantage differs across RULER task categories}
  \centering
  \includegraphics[width=0.98\linewidth,height=0.48\textheight,keepaspectratio]{figures/fig-04-ruler.pdf}
  \begin{itemize}
    \item FoX leads at some lengths on Single-NIAH.
    \item PaTH variants clearly improve Variable Tracking over FoX and RoPE.
    \item Variable Tracking remains difficult: the best curve reaches only about 0.25.
  \end{itemize}
  \papersource{Paper, Fig. 4, PDF p. 9. Original figure. Panel vertical scales differ; all report accuracy.}
\end{frame}

\begin{frame}{Narrative reasoning and mixed tasks show a tradeoff}
  \begin{center}
  \begin{tabular}{lrrrr}
  \toprule
  & \multicolumn{2}{c}{BABILONG $\uparrow$} & \multicolumn{2}{c}{LongBench-E $\uparrow$} \\
  \cmidrule(lr){2-3}\cmidrule(lr){4-5}
  Model & 8K & 16K & 4--8K & 8--16K \\
  \midrule
  RoPE & 0.0 & 0.0 & 3.7 & 2.0 \\
  FoX & 8.2 & 4.4 & 16.9 & 11.7 \\
  PaTH & 16.8 & \textbf{11.6} & \textbf{22.5} & 14.4 \\
  PaTH-FoX & \textbf{19.2} & 10.0 & 21.8 & \textbf{16.1} \\
  \bottomrule
  \end{tabular}
  \end{center}
  \begin{itemize}
    \item PaTH leads on BABILONG at 16K; the combination leads at 8K.
    \item LongBench-E columns are length \alert{buckets}, with mixed task scores.
    \item Which distant facts should be forgotten depends on the task.
  \end{itemize}
  \papersource{Paper, Table 3, PDF p. 9. Table 7 gives PaTH-FoX 21.9 rather than 21.8 for 4--8K; this slide uses Table 3.}
\end{frame}

\begin{frame}{SmolLM2 conversion improves code after further training}
  \small
  100M tokens: attention-output MSE $\rightarrow$ 3B tokens: output KL\newline
  $\rightarrow$ 21B tokens: DCLM / Python-Edu / MegaMathWeb (1:1:1).
  \normalsize
  \begin{center}
  \begin{tabular}{lrrr}
  \toprule
  SmolLM2-1.7B & GSM8K & HumanEval & MBPP+ \\
  \midrule
  Base, before further training & 8.6 & 16.4 & 38.6 \\
  RoPE, after further training & 19.9 & 23.1 & 47.1 \\
  FoX, converted and trained & 15.5 & 21.3 & 48.2 \\
  PaTH, converted and trained & \textbf{20.1} & \textbf{25.6} & \textbf{51.3} \\
  \bottomrule
  \end{tabular}
  \end{center}
  PaTH over continued RoPE: \alert{+0.2 / +2.5 / +4.2 points}.\newline
  The starting checkpoint precedes WSD decay and high-quality math/code training.
  \papersource{Paper, Sec. 4.3 and Table 4, PDF p. 9. Base-to-final gains also include the additional training data.}
\end{frame}

\begin{frame}{A mature Qwen model gives mixed conversion results}
  Qwen2.5-7B-Instruct: distillation only, without math/code continued pretraining.
  \begin{center}
  \begin{tabular}{lrrr}
  \toprule
  Task & RoPE teacher & PaTH student & Change (points) \\
  \midrule
  MMLU & 74.21 & 73.28 & $-0.93$ \\
  WinoGrande & 71.51 & 68.90 & $-2.61$ \\
  TheoremQA & 18.12 & 21.88 & $+3.76$ \\
  GSM8K & 80.29 & 80.67 & $+0.38$ \\
  MATH & 69.10 & 65.38 & $-3.72$ \\
  HumanEval & 82.32 & 77.44 & $-4.88$ \\
  \bottomrule
  \end{tabular}
  \end{center}
  Earlier conversion is an author hypothesis; model history and training protocols also differ.
  \papersource{Paper, selected rows of Table 5 and Sec. 4.3, PDF pp. 9--10.}
\end{frame}

\begin{frame}{The kernel remains quadratic and adds practical cost}
  \begin{columns}[c]
  \begin{column}{0.48\textwidth}
  \includegraphics[width=\linewidth,height=0.66\textheight,keepaspectratio]{figures/fig-01-speed.pdf}
  \end{column}
  \begin{column}{0.49\textwidth}
  Single H100; batch 32;\newline
  32 heads; head dimension 64.
  \medskip
  \begin{itemize}
    \item PaTH is slower than FlashAttention-triton.
    \item It is faster than FoX-triton at longer lengths.
    \item With $B\approx d$, attention stays $O(L^2d)$.
  \end{itemize}
  \medskip
  Larger heads and full decoding services require separate evaluation.
  \end{column}
  \end{columns}
  \papersource{Paper, Fig. 1, Sec. 3.3 and Sec. 6, PDF pp. 5--6, 10. Original figure; block-count correction in backup.}
\end{frame}

\begin{frame}{PaTH connects state transitions with explicit retrieval}
  \begin{block}{What to retain}
  Content-dependent, noncommuting path products improve state tracking.\newline
  FoX adds complementary forgetting for several long-context tasks.
  \end{block}
  \begin{itemize}
    \item \textbf{Compute:} quadratic attention, extra block transforms, and historical-key writes.
    \item \textbf{Numerics:} BF16 products can become unstable; clip $\beta$ below 2.
    \item \textbf{Geometry:} a single rank-one reflection-like step does not span arbitrary RoPE rotations.
    \item \textbf{Transfer:} gains depend on the task and conversion protocol.
  \end{itemize}
  \papersource{Paper, Secs. 4, 6--7, PDF pp. 7--10.}
\end{frame}

\begin{frame}{References and materials}
  \textbf{Songlin Yang et al.}\par
  \emph{PaTH Attention: Position Encoding via Accumulating Householder Transformations.}\par
  NeurIPS 2025; arXiv:2505.16381v2, revised 3 February 2026.
  \medskip\par
  \url{https://arxiv.org/abs/2505.16381v2}
  \medskip\par
  Original figures and numerical results are from this version.\newline
  All page locators refer to the PDF, counted from page 1.
  \medskip\par
  The paper links its implementation in Flash Linear Attention:\newline
  \url{https://github.com/fla-org/flash-linear-attention}
  \medskip\par
  \small Backup: exact block equations, complexity, proof ideas,\newline
  BABILONG details, LongBench-E examples, and training settings.
\end{frame}

\appendix

\begin{frame}{Backup: fix orientation before implementing UT products}
  Let $\m U_b=(\m I+\slo(\m D_b\m W_b\m W_b^\top))^{-1}\m D_b$.
  \[
  \overleftarrow{\m Q}_b
  =\m Q_b-\lo(\m Q_b\m W_b^\top)\m U_b\m W_b
  \]
  \[
  \overrightarrow{\m K}_b
  =\m K_b-(\m U_b\slo(\m W_b\m K_b^\top))^\top\m W_b
  \]
  \[
  \m F_b=\m H_{\rm first}\cdots\m H_{\rm last}
  =\m I-\m W_b^\top\m U_b^\top\m W_b
  \]
  \begin{itemize}
    \item A lower-triangular UT factor without the transpose gives the \emph{reverse} product.
    \item The paper's block product on p. 5 omits $\m I-$; its orientation also needs care.
    \item Apply a causal $-\infty$ mask before softmax, not a zero mask.
  \end{itemize}
  \papersource{Derived with explicit forward order from Secs. 3.1--3.3, PDF pp. 4--5; notation corrected for consistency.}
\end{frame}

\begin{frame}{Backup: count the cross-block transitions explicitly}
  Cost per query/key block pair:
  \[
  O(B^2d+Bd^2).
  \]
  Across $O((L/B)^2)$ causal pairs:
  \[
  \boxed{O\!\left(L^2d+\frac{L^2d^2}{B}\right)}.
  \]
  \begin{itemize}
    \item Local solves and boundary transforms: $O(LB^2+LBd)$.
    \item Explicit dense block products add $O(Ld^2)$ preprocessing.
    \item $B\approx d$ retains the $O(L^2d)$ dominant scaling.
  \end{itemize}
  The paper prints $Ld^2/B$ in the second term; multiplication by the number of block pairs gives $L^2d^2/B$.
  \papersource{Derivation from the per-block cost in Sec. 3.3, PDF pp. 5--6.}
\end{frame}

\begin{frame}{Backup: two heads distinguish the identity permutation}
  Compose five-element swaps using exact Householder reflections.
  \[
  s_0=n\left(\sum_{r=1}^{5}r\pi(r)-54.5\right)
  \]
  \[
  s_0=n/2\ \text{for identity},\qquad s_0\le -n/2\ \text{otherwise}.
  \]
  \begin{columns}[T]
  \begin{column}{0.47\textwidth}
    \begin{block}{Head 1: path-dependent}
    \[a_0=\frac{e^{s_0}}{e^{s_0}+n}\]
    Only the start token has a nonzero value.
    \end{block}
  \end{column}
  \begin{column}{0.47\textwidth}
    \begin{block}{Head 2: uniform reference}
    \[a_{\rm ref}=\frac{1}{n+1}\]
    All logits are zero.
    \end{block}
  \end{column}
  \end{columns}
  \smallskip
  Output the sign of $a_0-a_{\rm ref}$.
  \papersource{Paper, Appendix A, PDF pp. 17--18. Equality/inequality signs above follow directly from the displayed score.}
\end{frame}

\begin{frame}{Backup: the flip-flop construction erases older writes}
  \begin{block}{Theorem A.1, as stated in the paper}
  For inputs up to length $n$, a two-layer PaTH Transformer with $O(\log n)$ precision achieves FFLM accuracy above $1-1/n^{100}$.
  \end{block}
  \begin{enumerate}
    \item Layer 1 associates each bit with its preceding instruction.
    \item Layer 2 inserts a projection at a new write, blocking older write paths.
    \item The read position selects the latest surviving write value.
  \end{enumerate}
  \small
  The coordinate formulas on p. 19 contain mismatched indices: write bits are in
  $h_{10},h_{11}$, while later value/gate equations use $h_8,h_9$.
  The two final output tests are also identical. This slide explains the intended construction.
  \papersource{Paper, Appendix A, PDF pp. 18--19. The empirical one-layer results are separate (Table 1, p. 7).}
\end{frame}

\begin{frame}{Backup: BABILONG gains vary by reasoning skill}
  \centering
  \includegraphics[width=0.96\linewidth,height=0.64\textheight,keepaspectratio]{figures/fig-05-babilong.png}
  \small\par
  QA1--QA5 cover facts, multi-fact chains, and argument relations.\newline
  QA3 stays difficult; PaTH is particularly strong on several QA5 settings.
  \papersource{Paper, Fig. 5 and Table 6, PDF p. 20. Original figure. Main text says QA0--QA5; appendix shows QA1--QA5.}
\end{frame}

\begin{frame}{Backup: LongBench-E averages hide task-specific effects}
  \begin{center}
  \begin{tabular}{llrr}
  \toprule
  Dataset & Length bucket & PaTH & PaTH-FoX \\
  \midrule
  \texttt{gov\_report} & 0--4K & 22.3 & 10.2 \\
  \texttt{triviaqa} & 8--16K & 18.4 & 31.6 \\
  \texttt{hotpotqa} & 8--16K & 8.8 & 7.7 \\
  \texttt{repobench-p} & 8--16K & 19.2 & 19.3 \\
  \bottomrule
  \end{tabular}
  \end{center}
  \begin{itemize}
    \item PaTH can retain useful details for short-bucket summarization.
    \item Forgetting helps some longer-bucket tasks substantially.
    \item The long-bucket average does not imply a win on every task.
  \end{itemize}
  \small
  Reporting difference: Table 3 gives PaTH-FoX averages 23.4 / 21.8 / 16.1;
  Table 7 gives 23.5 / 21.9 / 16.1.
  \papersource{Paper, Tables 3 and 7, PDF pp. 9, 21. Selected task-specific scores; higher is better.}
\end{frame}

\begin{frame}{Backup: pretraining and extrapolation conditions}
  \begin{center}
  \begin{tabular}{ll}
  \toprule
  760M training & Reported setting \\
  \midrule
  Data / tokenizer & FineWeb-Edu / Mistral \\
  Tokens / context / batch & 50B / 4096 / 2M tokens \\
  Optimizer & AdamW; weight decay 0.01 \\
  Learning rate & Peak $10^{-3}$; start/end $3\times10^{-5}$ \\
  Schedule & Cosine; 1B-token warmup \\
  Gradient clipping / init std. & 1.0 / 0.02 \\
  Hardware / reported duration & 8 H100 GPUs / 2--3 days per model \\
  \bottomrule
  \end{tabular}
  \end{center}
  Extrapolation corpora: CodeParrot, PG-19, NarrativeQA.\newline
  Long-context tasks: RULER, BABILONG, PhoneBook, LongBench-E.
  \papersource{Paper, Sec. 4.2, PDF pp. 8--9; Appendix B, PDF p. 20.}
\end{frame}

\end{document}
