\documentclass[aspectratio=169,11pt]{beamer}
\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage{lmodern}
\usepackage{amsmath,amssymb,graphicx,booktabs}

\definecolor{AcademicBlue}{RGB}{26,57,86}
\definecolor{AcademicTeal}{RGB}{0,105,112}
\definecolor{StageBlue}{RGB}{32,95,160}
\definecolor{StageRed}{RGB}{183,55,52}
\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{\onestage}{\textcolor{StageRed}{single-stage}}
\newcommand{\twostage}{\textcolor{StageBlue}{two-stage}}

\title[Competing sorting algorithms]{Transformers Learn Two Competing Sorting Algorithms,\\and Only One Length-Generalizes}
\subtitle{Mechanisms, initialization, and the limits of the one-head result}
\author{\small Khashayar Gatmiry, Nathan W. Henry, Chloe H. Su, Emmanuel Abbe,\\
Samy Bengio, Melanie Weber, Jonathan A. Kelner, Peter L. Bartlett}
\date{\href{https://arxiv.org/abs/2610.26974v1}{arXiv:2610.26974v1} \quad Research group discussion, 26 October 2026}

\begin{document}

\begin{frame}
  \titlepage
\end{frame}

\begin{frame}{Extra capacity creates a choice of learned algorithms}
  \begin{block}{Question}
    If one attention layer can sort, what does training do when a second layer is available?
  \end{block}
  \begin{itemize}
    \item The same two-layer architecture reaches near-zero training loss through two distinct attention circuits.
    \item In the paper's \emph{one-head-per-layer} setting, the circuit that uses both layers extrapolates much better to longer lists.
    \item The paper traces this split to rare small gaps, cross-layer specialization, and a query-side hint.
  \end{itemize}
  \papersource{Paper, Secs. 1, 3--4; PDF pp. 2--10.}
\end{frame}

\begin{frame}{Sorting is a sequence of successor queries}
  \begin{columns}[T,onlytextwidth]
    \begin{column}{0.55\textwidth}
      \begin{block}{Data and target}
        Sample $K$ distinct values from $\{1,\ldots,N\}$; append \texttt{SEP}; output the values in ascending order.
      \end{block}
      \[
        x_1,\ldots,x_K,\texttt{SEP},
        x_{s(1)},\ldots,x_{s(K)}.
      \]
      At output value $x_{s(i)}$, predict its successor $x_{s(i+1)}$.
    \end{column}
    \begin{column}{0.41\textwidth}
      \begin{block}{Main protocol}
        Train at $K=16$; test from $K=2$ to $K=N$. Causal transformer, two layers, one head per layer, no positional encoding.
      \end{block}
      Online sampling; AdamW, learning rate $0.03$, batch $4096$, $60{,}000$ steps.
    \end{column}
  \end{columns}
  \papersource{Paper, Sec. 2; PDF p. 4.}
\end{frame}

\begin{frame}{Ablating attention 2 separates two solution classes}
  \begin{columns}[T,onlytextwidth]
    \begin{column}{0.47\textwidth}
      \begin{block}{Single-stage}
        Remove the second \emph{attention} layer: full-sequence sorting accuracy stays near 1. The first attention selects a wider set of nearby candidates; later MLPs can still choose the output.
      \end{block}
    \end{column}
    \begin{column}{0.47\textwidth}
      \begin{block}{Two-stage}
        The same ablation collapses full-sequence accuracy toward 0. Both attention layers contribute; attention 2 is much more focused on the correct successor.
      \end{block}
    \end{column}
  \end{columns}
  \medskip
  \textbf{Keep the metrics apart:} ablated \emph{sequence} accuracy defines the class; unablated \emph{token} accuracy measures length generalization. MLP2 remains in the ablation.
  \papersource{Paper, Sec. 3, Fig. 1; PDF pp. 2, 4--5.}
\end{frame}

\begin{frame}{At long lengths, the two-stage one-head models win}
  \centering
  \includegraphics[width=0.94\linewidth,height=0.56\textheight,keepaspectratio]{figures/fig01-sorting-panel.pdf}
  \par\smallskip
  \small Training: $K=16$, $N=256$. At $K=256$, blue two-stage curves remain near 1 token accuracy; red single-stage curves fall near 0.2.
  \papersource{Paper, Fig. 1a, PDF p. 2. Each curve is one seed; color encodes attention-2 removability.}
\end{frame}

\begin{frame}{The two circuits allocate attention differently}
  \begin{columns}[T,onlytextwidth]
    \begin{column}{0.49\textwidth}
      \centering
      \includegraphics[width=\linewidth,height=0.55\textheight,keepaspectratio]{figures/fig02-two-stage-second.pdf}
      \par\smallskip
      \small Two-stage: attention 2 sharply selects successors.
    \end{column}
    \begin{column}{0.49\textwidth}
      \centering
      \includegraphics[width=\linewidth,height=0.55\textheight,keepaspectratio]{figures/fig02-single-stage-first.pdf}
      \par\smallskip
      \small Single-stage: attention 1 spreads over nearby candidates.
    \end{column}
  \end{columns}
  \papersource{Paper, Fig. 2, PDF p. 5. Cropped panels from one input; bright cells have higher attention weight. Attention-argmax accuracies are 100\% and 62.5\% here.}
\end{frame}

\begin{frame}{Two mechanisms may explain the sorting split}
  \begin{columns}[T,onlytextwidth]
    \begin{column}{0.47\textwidth}
      \begin{block}{1. Gap specialization}
        Long lists contain many more adjacent values with gap $g=1$. In two-stage models, the first-layer path often suffices for small gaps; attention 2 handles larger gaps.
      \end{block}
    \end{column}
    \begin{column}{0.47\textwidth}
      \begin{block}{2. Query-side hint}
        Attention 1 supplies contextual information to attention 2. The second stage can search within a smaller value window and keep a narrower candidate set.
      \end{block}
    \end{column}
  \end{columns}
  \medskip
  These are mechanistic interpretations supported by ablations, interventions, score scans, and attention statistics.
  \papersource{Paper, Sec. 4; PDF pp. 5--10, Figs. 2--5.}
\end{frame}

\begin{frame}{Longer lists make unit gaps common}
  \[
    g_i=x_{s(i+1)}-x_{s(i)}, \qquad
    \mathbb E[g]=\frac{N+1}{K+1}.
  \]
  \begin{center}
    \begin{tabular}{@{}lrrr@{}}
      \toprule
      $N=256$ & $K=16$ (train) & $K=128$ & $K=256$ \\
      \midrule
      Mean adjacent gap & 15.12 & 1.99 & 1.00 \\
      $\Pr(g=1)=K/N$ & 6.25\% & 50\% & 100\% \\
      \bottomrule
    \end{tabular}
  \end{center}
  \smallskip
  The probability row follows by counting uniform $K$-subsets; it is a teaching derivation from the paper's sampling scheme. A rare training case becomes the entire $K=N$ test case.
  \papersource{Paper, Sec. 4.1 and Appendix C; PDF pp. 6, 23.}
\end{frame}

\begin{frame}{The layers specialize across gap sizes}
  \begin{columns}[T,onlytextwidth]
    \begin{column}{0.48\textwidth}
      \centering
      \includegraphics[width=\linewidth,height=0.56\textheight,keepaspectratio]{figures/fig03a-attention-vs-gap.pdf}
      \par\smallskip
      \small Attention 1 attends less to input tokens as $g$ grows.
    \end{column}
    \begin{column}{0.48\textwidth}
      \centering
      \includegraphics[width=\linewidth,height=0.56\textheight,keepaspectratio]{figures/fig03b-ablation-vs-gap.pdf}
      \par\smallskip
      \small With attention 2 removed, many seeds still solve $g=1$; accuracy collapses at larger gaps.
    \end{column}
  \end{columns}
  \papersource{Paper, Fig. 3a--b, PDF p. 7. Shading in (a): mean $\pm$ 1 s.d. across 32 two-stage models.}
\end{frame}

\begin{frame}{Interventions show a handoff to attention 2}
  \begin{columns}[T,onlytextwidth]
    \begin{column}{0.48\textwidth}
      \centering
      \includegraphics[width=\linewidth,height=0.54\textheight,keepaspectratio]{figures/fig04-gap1.png}
      \par\smallskip
      \small \textbf{Gap 1:} either path can steer the output.
    \end{column}
    \begin{column}{0.48\textwidth}
      \centering
      \includegraphics[width=\linewidth,height=0.54\textheight,keepaspectratio]{figures/fig04-gap20.png}
      \par\smallskip
      \small \textbf{Gap 20:} attention 2 dominates.
    \end{column}
  \end{columns}
  \smallskip
  \small Red: redirect attention 1's direct path. Blue: redirect attention 2. Purple: both individually succeed on the same input.
  \papersource{Paper, Fig. 4, PDF p. 8; $K=32$, $N=512$, 23 two-stage seeds. Panels cropped from the original figure.}
\end{frame}

\begin{frame}{Layer 1 changes the query used by layer 2}
  \begin{block}{Stylized single-target intervention}
  \[
    s(z,x,t,y)=\mathbf q(z,x)^\top\mathbf k(t,y),
  \]
  \[
    \mathbf q(z,x)=W_Q^{(2)}\operatorname{LN}\!\left[
      \operatorname{MLP}_1\!\left(\operatorname{LN}(e_z+V_x^{(1)})\right)
    \right].
  \]
  \end{block}
  $z$: current output value; $t$: candidate key; $x$ and $y$: first-attention targets on the query and key sides. $V_x^{(1)}$ is the projected value vector.
  \papersource{Paper, Sec. 4.2, Eq. (1), PDF p. 8; Appendix E, PDF pp. 31--33.}
\end{frame}

\begin{frame}{The hint creates a query-dependent search window}
  \begin{columns}[T,onlytextwidth]
    \begin{column}{0.52\textwidth}
      \centering
      \includegraphics[width=\linewidth,height=0.59\textheight,keepaspectratio]{figures/fig05a-window.png}
    \end{column}
    \begin{column}{0.43\textwidth}
      \begin{itemize}
        \item The score is nearly invariant to key-side target $y$, but changes strongly with query-side target $x$.
        \item High scores concentrate roughly in $[z,x]$; the preferred key moves with $x$, then saturates near 300 for $z=250$.
        \item Very small windows do not follow this pattern as cleanly.
      \end{itemize}
    \end{column}
  \end{columns}
  \papersource{Paper, Sec. 4.2, Fig. 5a, PDF p. 9; Appendix E, Fig. 20, PDF p. 32. Curve averages 23 seeds.}
\end{frame}

\begin{frame}{Two-stage attention keeps a smaller candidate set}
  \centering
  \includegraphics[width=0.92\linewidth,height=0.70\textheight,keepaspectratio]{figures/fig05b-candidates.pdf}
  \par\smallskip
  \small Candidate = key with attention weight $>0.04$. At $8\times$ training length, attention 1 averages 3.1 keys in two-stage models versus 8.7 in single-stage models.
  \papersource{Paper, Sec. 4.2, Fig. 5b, PDF pp. 9--10. The threshold count is a descriptive probe.}
\end{frame}

\begin{frame}{A small scale asymmetry steers algorithm choice}
  \begin{center}
    \begin{tabular}{@{}lrc@{}}
      \toprule
      $(\sigma_1,\sigma_2)$ & $\Delta=\sigma_2-\sigma_1$ & Two-stage seeds \\
      \midrule
      $(0.012,0.010)$ & $-0.002$ & 0/100 \\
      $(0.010,0.010)$ & $0$ & 26/100 \\
      $(0.010,0.011)$ & $+0.001$ & 82/100 \\
      $(0.010,0.013)$ & $+0.003$ & 100/100 \\
      \bottomrule
    \end{tabular}
  \end{center}
  \smallskip
  \begin{itemize}
    \item Larger layer-2 initialization favors using attention 2; larger layer-1 initialization favors a single-stage solution.
    \item At $\Delta=+0.003$, some classified two-stage seeds generalize worse: solution class alone does not fix circuit quality.
  \end{itemize}
  \papersource{Paper, Sec. 5.1, Fig. 6, PDF pp. 10--11; Appendix A, Fig. 8, PDF p. 20. Sorting: $K=16$, $N=128$.}
\end{frame}

\begin{frame}{Task difficulty and model capacity shift the choice}
  \begin{columns}[T,onlytextwidth]
    \begin{column}{0.48\textwidth}
      \begin{block}{Larger vocabulary $N$}
        At fixed training length 16, near-all seeds are single-stage at $N=64$; most are two-stage at $N=512$.
      \end{block}
      Harder numerical discrimination appears to recruit the second layer.
    \end{column}
    \begin{column}{0.48\textwidth}
      \begin{block}{Wider embedding $E$}
        At fixed $N=256$, the two-stage share falls from all trained seeds at $E=32$ to none at $E=80$.
      \end{block}
      More representational capacity appears to make a one-attention solution easier to reach.
    \end{column}
  \end{columns}
  \medskip
  These comparisons concern the \emph{probability of learning a solution class}, not the accuracy of one fixed trained model.
  \papersource{Paper, Sec. 5.2 and Appendix B, Figs. 9--10; PDF pp. 10, 21--22. The proposed optimization explanations are hypotheses.}
\end{frame}

\begin{frame}{Training length changes which gaps get learned}
  \begin{itemize}
    \item At training lengths $K\ge16$, two-stage seeds generalize essentially perfectly to the longest tested length; at shorter training lengths, none does so perfectly.
    \item At $K_{\rm train}=4$, first-layer attention to input values at gap 1 correlates with accuracy at $K=256$: $r=+0.77$.
    \item A fully consecutive length-32 sequence has expected training frequency $10^{-39}$; two-stage accuracy on its consecutive positions is 1.00, versus 0.89 for single-stage models.
  \end{itemize}
  \begin{block}{Tradeoff}
    Longer training lists teach small gaps, while making very large gaps rarer and harder to cross.
  \end{block}
  \papersource{Paper, Appendix C, Figs. 11--15; PDF pp. 23--27. Adversarial accuracy is scored on the specified consecutive positions.}
\end{frame}

\begin{frame}{Minimum-finding reverses the generalization ranking}
  \centering
  \includegraphics[width=0.93\linewidth,height=0.52\textheight,keepaspectratio]{figures/fig01-minimum-panel.pdf}
  \par\smallskip
  \small Train at $K=16$, $N=4096$, sampling \emph{with replacement}. Single-stage models (red) remain more accurate on long inputs than two-stage models (blue).
  \papersource{Paper, Sec. 6, Fig. 1b; PDF pp. 2, 11--13. Each curve is one seed.}
\end{frame}

\begin{frame}{The minimum task exposes different rare-input failures}
  \begin{columns}[T,onlytextwidth]
    \begin{column}{0.47\textwidth}
      \begin{block}{Two-stage weakness}
        Many values clustered near the minimum become more common in longer lists; two-stage models degrade on these cases.
      \end{block}
    \end{column}
    \begin{column}{0.47\textwidth}
      \begin{block}{Single-stage weakness}
        Duplicates are harder for single-stage models. If the minimum has score $a_1$ and $n$ copies of the runner-up have score $a_2$, then
        \[
          a_1-a_2>\log n
        \]
        gives the minimum more total attention.
      \end{block}
    \end{column}
  \end{columns}
  \medskip
  Which solution generalizes depends on which failure mode the length shift makes prevalent.
  \papersource{Paper, Sec. 6.2; PDF p. 13. The score-margin argument is an explanatory hypothesis.}
\end{frame}

\begin{frame}{Coin denomination shows a softer split}
  \centering
  \includegraphics[width=0.93\linewidth,height=0.60\textheight,keepaspectratio]{figures/fig01-coins-panel.pdf}
  \par\smallskip
  \small Greedy denomination is a predecessor-query task. Train with 8 distinct denominations from a vocabulary of 64; models relying more on attention 2 tend to generalize better, with more overlap and intermediate cases than sorting.
  \papersource{Paper, Sec. 6, Fig. 1c; PDF pp. 2, 11--12. The algorithm outputs successive remainders.}
\end{frame}

\begin{frame}{A second head rescues single-stage sorting}
  \begin{columns}[T,onlytextwidth]
    \begin{column}{0.49\textwidth}
      \centering
      \includegraphics[width=\linewidth,height=0.52\textheight,keepaspectratio]{figures/fig19-two-layer-two-heads.pdf}
      \par\smallskip
      \small Two layers, two heads each: all shown models are single-stage, yet generalize.
    \end{column}
    \begin{column}{0.49\textwidth}
      \centering
      \includegraphics[width=\linewidth,height=0.52\textheight,keepaspectratio]{figures/fig19-one-layer-heads.pdf}
      \par\smallskip
      \small One layer: two heads generalize; one head fails.
    \end{column}
  \end{columns}
  \smallskip
  \small Token accuracy versus evaluation length; vertical line marks train length 16. The main sorting split is specific to one head per layer.
  \papersource{Paper, Appendix D, Fig. 19b--c, PDF p. 31. Panels cropped from the original figure; embedding dimension $E=64$.}
\end{frame}

\begin{frame}{Takeaways: study the learned circuit and the shifted inputs}
  \begin{enumerate}
    \item \textbf{Training success does not identify the algorithm.} Attention-2 ablation separates distinct functional solutions to the same sorting task.
    \item \textbf{Length changes the input statistics.} Small gaps become common; gap-specialized layers and a query-dependent window help in the one-head sorting experiments.
    \item \textbf{Complexity alone does not predict extrapolation.} Minimum-finding reverses the ranking; another attention head removes the sorting failure of single-stage models.
  \end{enumerate}
  \medskip
  \centering\large Ask which rare training cases become common at evaluation time, and which path handles them.
  \papersource{Paper, Secs. 3--6 and Appendix D; PDF pp. 4--13, 30--31.}
\end{frame}

\appendix

\begin{frame}{Backup: MLP1 carries the second-stage QK signal}
  \begin{itemize}
    \item Replace attention 2's input $e+a_1+m_1$ with $m_1$ only.
    \item In 13 standard two-stage checkpoints, mean attention-distribution $\ell_1$ distance is $<0.03$; full-sequence accuracy drops by at most $0.05\%$.
    \item Two $N=1024$ checkpoints are outliers: the mechanism is common, not required by architecture.
    \item Query-side target $x$ strongly changes QK scores; key-side target $y$ has little effect.
  \end{itemize}
  \papersource{Paper, Appendix E, Figs. 20--22; PDF pp. 31--33. The 13 detailed checkpoints exclude two outliers from 15 two-stage checkpoints.}
\end{frame}

\begin{frame}{Backup: depth four preserves multiplicity, not the same mechanism}
  \begin{itemize}
    \item Four-layer, one-head models can require one, two, three, or four leading attention layers to retain sorting accuracy.
    \item Lowering initialization of layers 2--4 to $0.005$ steers 14 of 50 models to a one-layer solution; equal $0.01$ scales yield none of those.
    \item At this depth, models requiring at least two layers length-generalize, but the paper does not find the same clean gap division or iterative candidate-set reduction.
  \end{itemize}
  \papersource{Paper, Appendix D, Figs. 16--17; PDF pp. 27--29. Four-layer experiments use $K=16$, $N=128$, $E=64$.}
\end{frame}

\end{document}