% Research discussion deck derived from the arxiv-paper-reader template. % Build: 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{\R}{\mathbb R} \newcommand{\bits}{\mathrm{bits}} \newcommand{\FC}{\mathsf{FuncComp}} \newcommand{\Eva}{\mathsf{Eva}} \newcommand{\PC}{\mathsf{PerCom}} \newcommand{\polylog}{\operatorname{polylog}} \newcommand{\viewpoint}[1]{\par\smallskip{\color{AcademicTeal}\textbf{Reading:} #1\par}} \title[Hybrid attention hierarchy]{A Provable Expressiveness Hierarchy\newline in Hybrid Linear-Full Attention} \subtitle{Finite-state communication and sequential retrieval} \author[Ye et al.]{Paper: Xiaowei Ye, Xiaoyu He, Chao Liao,\\Chen Wu, and Pinyan Lu} \date{arXiv:2602.01763v1 \;|\; 2 February 2026\\Research discussion prepared on 15 October 2026} \begin{document} \begin{frame} \titlepage \vspace{-5mm} \begin{center} \small On a constructed task family, many recurrent layers cannot replace\newline enough rounds of query-dependent access to the original input. \end{center} \papersource{Paper reading presentation; presenter is not a paper author.\quad \href{https://arxiv.org/abs/2602.01763v1}{arxiv.org/abs/2602.01763v1}} \end{frame} \begin{frame}{The question is whether recurrent depth buys retrieval rounds} \begin{block}{A concrete dependency} Retrieve one value, turn it into the next address, and retrieve again. \end{block} \begin{itemize} \item Full attention accesses prefix tokens using the \emph{current} query. \item A recurrent layer passes a finite summary formed before future queries. \item A hybrid combines both: can many summaries compensate for fewer full-attention layers? \end{itemize} \viewpoint{Count both state capacity and opportunities to access the input.} \papersource{Paper, Secs. 1--2, PDF pp. 1--5. The paper is theoretical; it reports no training experiments.} \end{frame} \begin{frame}{The headline separation comes with a capacity condition} For a constructed $L$-step task, let $A=2^{3L^2}$ and $c=Hdp$. \begin{center} \begin{tabular}{p{7.3cm}p{5.2cm}} \toprule Architecture & Capacity result\\ \midrule $L$ full-attention layers & Polynomial capacity necessary\\[2mm] $L+1$ full-attention layers & $c=\polylog(n)$ is sufficient\\[2mm] $L-1$ full layers, each followed by $A$ recurrent layers & Fails if $c\le n^{2^{-4L-2}}$\\ \bottomrule \end{tabular} \end{center} \alert{Fixed $L$; causal models; deterministic, exact correctness on every input.} \papersource{Paper, Theorem 1.1, PDF pp. 1--2; Table 1, p. 2. The first two rows are attributed to Chen et al.} \end{frame} \begin{frame}{Finite precision turns representations into bit budgets} \begin{columns}[T] \begin{column}{0.47\textwidth} \begin{block}{Model quantities} $H$: attention heads\\[1mm] $d$: dimension per head\\[1mm] $p$: bits per number\\[1mm] $n$: prompt tokens \end{block} \end{column} \begin{column}{0.49\textwidth} \begin{block}{Two budgets} Token representation: \[c=Hdp.\] Standard linear-attention state: \[C=Hd(d+1)p.\] \end{block} \end{column} \end{columns} \medskip Local MLPs may be arbitrary functions. The lower bound restricts information flow between positions. \papersource{Paper, Secs. 2.1--2.2 and Lemma 2.2, PDF pp. 3--4. These quantities are not total parameter counts.} \end{frame} \begin{frame}{A matrix and a vector carry the linear-attention prefix} With column-vector notation and $q_i,k_i,v_i\in\R^d$: \[ S_i=S_{i-1}+v_i\varphi(k_i)^\top,\qquad Z_i=Z_{i-1}+\varphi(k_i), \] \[ S_i\in\R^{d\times d},\quad Z_i\in\R^d,\qquad y_i=\frac{S_i\varphi(q_i)}{Z_i^\top\varphi(q_i)}. \] \begin{itemize} \item Each head carries $d^2+d$ numbers across a token boundary. \item Arbitrary recurrent updates can fit the communication framework. \item For a particular architecture, count its \emph{actual total state bits}. \end{itemize} \papersource{Paper, Lemma 2.2, p. 4; Appendix D, p. 24. Formula orientation normalized for column vectors.} \end{frame} \begin{frame}{Each function lookup determines the next address} \[ N_0=m,\qquad N_\ell=m\prod_{j=1}^{\ell}n_j,\qquad z_\ell:[N_{\ell-1}]\to[N_{\ell-1}]. \] \[ i_0=z_0,\qquad i_1=z_1(i_0),\qquad i_{\ell+1}=z_{\ell+1}(w_\ell,i_\ell). \] \begin{itemize} \item Query: $w_\ell\in[n_\ell]$. Encode $(w_\ell,i_\ell)$ in $[N_\ell]$. \item Return $i_L$ at the final query position. \item Prompt order: $z_L\,|\,\cdots\,|\,z_1\,|\,z_0\,|\,w$. \end{itemize} \alert{The causal scan encounters the tables before it knows the needed addresses.} \papersource{Paper, Definition 2.5, PDF pp. 4--5. Product indices follow the consistent Eq. (7), p. 17.} \end{frame} \begin{frame}{A three-step example makes the order mismatch visible} \centering \includegraphics[width=\linewidth,height=0.68\textheight,keepaspectratio]{figures/composition-example.pdf} \papersource{Original teaching diagram based on Definition 2.5, PDF pp. 4--5. Other function entries may be arbitrary.} \end{frame} \begin{frame}{One initial read plus $L$ lookups gives the upper bound} \begin{enumerate} \item At the query token, retrieve the initial value $z_0$. \item Use a full-attention layer to retrieve $z_1(z_0)$. \item For each subsequent layer, construct $(w_\ell,i_\ell)$ and retrieve from $z_{\ell+1}$. \end{enumerate} \begin{block}{Why retrieval is cheap in representation size} Binary addresses use $O(\log n)$ dimensions. A scaled score gap concentrates softmax on the matching address; local readout recovers the discrete value. \end{block} \papersource{Paper, Table 1, p. 2 (Chen et al. upper bound); Appendix C, pp. 23--24 (retrieval head).} \end{frame} \begin{frame}{The quantitative guarantee is strongly asymptotic} \begin{center} \begin{tabular}{c@{\hspace{8mm}}c@{\hspace{8mm}}c} \toprule $L$ & Recurrent layers per block & Failure condition\\ \midrule 2 & $2^{12}=4{,}096$ & $Hdp\le n^{1/1024}$\\[2mm] 3 & $2^{27}=134{,}217{,}728$ & $Hdp\le n^{1/16384}$\\[2mm] 4 & $2^{48}$ & $Hdp\le n^{1/262144}$\\ \bottomrule \end{tabular} \end{center} Total recurrent depth is $(L-1)2^{3L^2}$. \begin{block}{A scale check} At $L=2$ and $n=2^{20}$, the threshold is $Hdp\le1.0136$, below the proof's assumption $Hdp\ge2$. \end{block} \papersource{Values substituted into Theorem 1.1; the scale check is our calculation, not an experiment.} \end{frame} \begin{frame}{The protocol exposes two different information channels} Players $L,L-1,\ldots,0,-1$ hold $z_L,z_{L-1},\ldots,z_0,w$. \begin{center} \begin{tabular}{>{\raggedright\arraybackslash}p{3.0cm}>{\raggedright\arraybackslash}p{5.7cm}>{\raggedright\arraybackslash}p{3.8cm}} \toprule Channel & Information flow & Message budget\\ \midrule Full attention & Query-dependent replies from prefix blocks & $2Hdp\,m_{(i)}$ bits per sender\\[3mm] Recurrent layer & State passed along $L\to\cdots\to-1$ & $Hd(d+1)p$ bits per edge\\ \bottomrule \end{tabular} \end{center} One epoch is one full-attention round followed by $a_\ell$ recurrent rounds. \par\medskip Prefix players forget received future queries after replying: causal states remain causal. \papersource{Paper, Sec. 3, PDF p. 5. $m_{(i)}$ is the number of tokens held by the receiving player.} \end{frame} \begin{frame}{Indistinguishability must survive later full-attention rounds} Construct a pair of input sets: \[ R_{\ge\ell}\subseteq A_L\times\cdots\times A_\ell, \qquad Z_{<\ell}=Z_{-1}\times\cdots\times Z_{\ell-1}. \] $A_j$ contains all possible functions held by player $j$. \begin{block}{Invariant} For each fixed $z_{<\ell}$, all inputs in $R_{\ge\ell}$ give the same relevant soft and recurrent transcripts through epoch $\ell$. \end{block} Preserve both: \begin{itemize} \item many possible prefix functions in $R_{\ge\ell}$; \item many reachable intermediate values in $\mathcal I_{\ell-1}(Z_{<\ell})$. \end{itemize} \papersource{Paper, Definition 4.1, p. 6; Definition B.4 and Lemmas B.5--B.7, pp. 18--19.} \end{frame} \begin{frame}{The induction fixes messages while retaining input diversity} \begin{enumerate} \item \textbf{Initialize.} Fix a first-round message pattern by pigeonhole; retain many functions and reachable values. \item \textbf{Extract a rectangle.} Choose $S_1\times S_2\subseteq R_{\ge\ell}$ and set $Z_\ell=S_2$. \item \textbf{Fix new soft transcripts.} Earlier indistinguishability removes their dependence on the choice of $z_\ell$. \item \textbf{Fix recurrent transcripts.} Charge their total bits to the allowable set-size loss. \end{enumerate} \viewpoint{Lemma B.11 tracks recurrent messages so they cannot reintroduce hidden distinctions.} \papersource{Paper, Secs. 4.2--4.3, pp. 7--8; Appendix B.2--B.3, pp. 20--23. Base-case qualification on slide 14.} \end{frame} \begin{frame}{Too many functions must agree on too many addresses} At the final epoch, let $N=N_{L-1}$ and \[ t=n_{L-1}|\mathcal I_{L-1}(Z_{N^{N-t}.\] \end{block} \papersource{Teaching expansion of Lemma B.5, PDF p. 19, using Eqs. (10)--(11), p. 17.} \end{frame} \begin{frame}{The first-epoch distinction matters in the v1 proof} \begin{itemize} \item Sec. 4.1 uses $(L,0,A,\ldots,A)$: no recurrent layer after the first full layer. \item Appendix B states the stronger allowance $a_1\le1$. \item Its base case fixes a soft transcript and claims the query state is independent of $z_1$. \item With $a_1=1$, a recurrent message can still carry $z_1$; this dependence needs an additional argument. \end{itemize} \begin{block}{How we use the argument} Explain the main route with $a_1=0$. Prepending an identity full layer embeds the headline $L-1$-full-layer architecture in this layout. \end{block} \papersource{Our reading concern: compare Sec. 4.1, p. 6; Theorem B.2, pp. 17--18; base case, p. 20. Not a counterexample to Theorem 1.1.} \end{frame} \begin{frame}{Lookup and permutation tasks yield simpler state lower bounds} $\PC(\sigma,\tau)=(\sigma(\tau(1)),\ldots,\sigma(\tau(n)))$ for two permutations. \begin{center} \begin{tabular}{p{3.3cm}p{4.8cm}p{4.0cm}} \toprule Task & Linear attention needs & Log-linear needs\\ \midrule $\Eva(f,x)=f(x)$ & $LHd(d+1)p\ge n\log_2n$ & $LHd^2p=\Omega(n)$\\[3mm] $\PC(\sigma,\tau)$ & $LHd(d+1)p\ge\log_2(n!)$ & $LHd^2p=\Omega(n)$\\ \bottomrule \end{tabular} \end{center} \begin{itemize} \item A prefix summary must distinguish $n^n$ functions or $n!$ permutations. \item Log-linear communication carries $O(\log n)$ matrix states per layer. \item One full-attention layer suffices with $Hdp=\polylog(n)$. \end{itemize} \papersource{Paper, Theorems A.3--A.8, PDF pp. 12--15; Appendix C, pp. 23--24.} \end{frame} \begin{frame}{Appended CoT cannot restore information absent from the state} \[ \underbrace{\text{Alice}}_{\text{function table}} \ \xrightarrow{\text{finite summaries}}\ \underbrace{\text{Bob}}_{\text{query}} \ \xrightarrow{\text{states and outputs}}\ \underbrace{\text{Charles}}_{\text{generated tokens}} \] \begin{itemize} \item Charles receives only information already available to Bob. \item Bob could simulate all of Charles's subsequent computation. \item Thus these pure recurrent/log-linear retrieval bounds also hold with appended CoT under this access model. \end{itemize} \alert{The main hybrid theorem is a single-forward-pass result.} \papersource{Paper, Appendix A.2--A.4, PDF pp. 13--15. A new channel to original tokens changes the model.} \end{frame} \begin{frame}{Sparse retrieval first compresses, then chooses blocks} For $q=n/B$ blocks, the query player receives: \begin{enumerate} \item an $Hdp$-bit summary from each block; \item all raw tokens from $k$ selected blocks. \end{enumerate} \begin{block}{The collision construction} Two blocks $a,b$ have the same summary but different value sets. Put $b$ in every inspected block. An uninspected block can switch from $b$ to $a$ and change membership of a value $v$. \end{block} Querying $-v\bmod M$ converts that hidden difference into a 2-Sum answer. \papersource{Paper, Definition 2.4, p. 4; Sec. 5, p. 8; Appendix A.6, p. 16. Shared compression and summary-based selection.} \end{frame} \begin{frame}{The sparse counting bound needs a range for $B$ and $k$} For a value universe of size $n$, the collision argument requires \[ Hdp\ge\log_2\!\left(\sum_{j=1}^{\min(B,n)}\binom nj\right). \] \begin{itemize} \item There must be an uninspected block: for one head, $k0$. \end{itemize} \alert{Theorem 1.2 states $\Omega(B\log n)$ without these qualifications.} \papersource{Our range analysis of Appendix A.6, p. 16; compare Theorem 1.2, p. 2. With multiple heads, use the union of inspected blocks.} \end{frame} \begin{frame}{The 2-Sum appendix changes the value universe} \begin{columns}[T] \begin{column}{0.47\textwidth} \begin{block}{Definition 2.6} $M=O(n)$. \medskip At most $2^M=2^{O(n)}$ distinct value sets. \end{block} \end{column} \begin{column}{0.49\textwidth} \begin{block}{Proof of Theorem A.9} Takes $M=n^2$. \[ \log_2\binom{n^2}{n-1}=\Theta(n\log n). \] \end{block} \end{column} \end{columns} \medskip \begin{itemize} \item The larger universe supports the proof's $n\log n$ information count. \item That count does not establish the same bound under the stated $M=O(n)$ definition. \item The proof also needs a consistent modulus $M$. \end{itemize} \papersource{Our consistency analysis: Definition 2.6, p. 5; Theorem A.9 and proof, pp. 15--16.} \end{frame} \begin{frame}{The useful distinction is access depth versus state capacity} \begin{enumerate} \item \textbf{Core idea.} Preserve indistinguishable input families across both query-dependent replies and recurrent state transfers. \item \textbf{Architectural implication.} Count full-attention opportunities, their placement, and actual recurrent state bits. \item \textbf{Evidence scope.} Exact worst-case tasks and very large asymptotic instances; no measured accuracy or optimal mixing ratio. \item \textbf{Reading judgment.} Keep the main proof route separate from the v1 strengthening and auxiliary statements needing clarification. \end{enumerate} \papersource{Synthesis of the paper and the qualifications on slides 14, 18, and 19.} \end{frame} \begin{frame}{References and discussion route} \begin{itemize} \item Xiaowei Ye, Xiaoyu He, Chao Liao, Chen Wu, Pinyan Lu.\\ \emph{A Provable Expressiveness Hierarchy in Hybrid Linear-Full Attention}.\\ \href{https://arxiv.org/abs/2602.01763v1}{arXiv:2602.01763v1}, 2026. \item Lijie Chen, Binghui Peng, Hongxun Wu.\\ \emph{Theoretical limitations of multi-layer Transformer}.\\ \href{https://arxiv.org/abs/2412.02975v1}{arXiv:2412.02975v1}; cited as FOCS 2025 in the paper. \item Clayton Sanford, Daniel Hsu, Matus Telgarsky.\\ \emph{Representational Strengths and Limitations of Transformers}. NeurIPS 2023; source cited for the full-attention 2-Sum bound. \end{itemize} \papersource{Main discussion: slides 1--20, approximately 25 minutes. Backup: parameters, invariants, and retrieval construction.} \end{frame} \appendix \begin{frame}{Backup: the task size absorbs recurrent transcript bits} Let $c=Hdp$ and $C=Hd(d+1)p$. \[ K=(cL)^8 8^{2L^2},\qquad m=K^{1+\sum_{r=0}^{L-1}8^r}, \] \[ n_\ell=K^{4\cdot8^{L-\ell-1}},\qquad x_\ell=K^{8^{L-\ell-1}}. \] The communication condition is \[ C\sum_{r=1}^{\ell+1}a_r \le\sqrt K(x_0\cdots x_{\ell-1})(n_1\cdots n_{L-1}). \] \begin{itemize} \item Fixing $s$ transcript bits costs a factor of at most $2^s$. \item Lemma B.1 bounds the constructed prompt size by $c^{4\cdot16^L}$. \end{itemize} \papersource{Paper, Eqs. (5)--(12), pp. 17--18. In Lemma B.3, use $C\le2c^2$ to repair a dropped factor of $d$.} \end{frame} \begin{frame}{Backup: two size bounds are maintained together} \[ |R_{\ge\ell}|\ge\frac{|A_L|\cdots|A_\ell|}{\Delta_\ell}, \qquad |\mathcal I_{\ell-1}|\ge\Theta_{\ell-1}. \] \[ \Delta_\ell=2^{4\sqrt K(x_0\cdots x_{\ell-2})(n_1\cdots n_{L-1})}, \] \[ \Theta_\ell=8^{-L\ell}(x_0\cdots x_\ell)(n_1\cdots n_{\ell-1}). \] \begin{itemize} \item A large $R$ preserves ambiguity about prefix functions. \item A large $\mathcal I$ prevents all ambiguity from hiding at unreachable addresses. \item Rectangle extraction lets new local inputs vary independently. \end{itemize} \papersource{Paper, Eqs. (10)--(11), p. 17; Lemmas B.5--B.9, pp. 19--21.} \end{frame} \begin{frame}{Backup: a consistent scaling implements the retrieval head} For binary addresses, define $u(a)=(a,\mathbf1-a)$ and set \[ q=\sqrt\lambda\,u(a),\qquad k_i=\sqrt\lambda\,u(a_i),\qquad v_i=b_i. \] Then \[ q^\top k_i=\lambda\bigl(D-\operatorname{Ham}(a,a_i)\bigr), \qquad \alpha_*\ge\frac1{1+(n-1)e^{-\lambda}}. \] \begin{itemize} \item Choose $\lambda=\Theta((\log n)^2)$; the unique match dominates. \item Binary readout can recover the retrieved value at finite precision. \item The v1 text scales both $Q,K$ by $\log^2 n$ but writes a $\log^2 n$ dot-product factor; the formula above normalizes that mismatch. \end{itemize} \papersource{Teaching rewrite of Appendix C, PDF p. 24. The scaling repair does not change the polylogarithmic capacity claim.} \end{frame} \end{document}