% Self-authored reading presentation, based on the skill 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{\FA}{\mathrm{FA}}
\newcommand{\LA}{\mathrm{LA}}
\newcommand{\Full}{\mathrm{Full}}

\title[Tail-Replay]{Tail-Replay}
\subtitle{Escaping the Curse of Linear Attention\\in Prefix Caching for Hybrid LLMs}
\author{Paper by Yirui Liu, Ruoling Qi, Xuaner Wu,\\Penghang Liu, and Jian Chen}
\date{arXiv:2608.30310v2 \;|\; Revised October 15, 2026\\
Reading presentation \;|\; October 16, 2026}

\begin{document}

\begin{frame}
  \titlepage
  \vspace{-5mm}
  \begin{center}
  \alert{Exact FA caches + short tail replay $\longrightarrow$ flexible prefix reuse}
  \end{center}
  \papersource{\href{https://arxiv.org/abs/2608.30310v2}{https://arxiv.org/abs/2608.30310v2}. Analysis slides; not an author presentation.}
\end{frame}

\begin{frame}{A token match may have no matching recurrent state}
  \begin{columns}[T,onlytextwidth]
  \begin{column}{0.47\textwidth}
    \begin{block}{Full attention (FA)}
      Each token has its own KV entry.\\[2mm]
      Matching $t_{1:m}$ lets us retrieve $K_{1:m},V_{1:m}$.
    \end{block}
  \end{column}
  \begin{column}{0.49\textwidth}
    \begin{block}{Linear attention (LA)}
      Each update overwrites a recurrent state.\\[2mm]
      The final $S_n$ cannot simply be sliced into an earlier $S_m$.
    \end{block}
  \end{column}
  \end{columns}
  \vspace{4mm}
  Checkpoints restore selected boundaries. A hit between them needs extra recomputation.
  \begin{center}
  \alert{Tail-Replay reconstructs an approximate state at the token-match boundary.}
  \end{center}
  \papersource{Paper, Sec. 1, PDF pp. 1--2.}
\end{frame}

\begin{frame}{The design changes what is cached and reconstructed}
  \centering
  \small
  \begin{tabular}{p{0.22\textwidth}p{0.31\textwidth}p{0.37\textwidth}}
    \toprule
    Approach & Recovery material & Main design choice \\
    \midrule
    FA prefix caches & Token-indexed KV & Slice the shared prefix \\[2mm]
    Marconi / Sparse Prefix Caching & Recurrent checkpoints & Which states to keep / where to place them \\[2mm]
    LinearKV & Cached local linear states & Initialize from saved local states \\[2mm]
    Tail-Replay & FA KV + FA output hiddens & Rebuild LA states from a recent tail \\
    \bottomrule
  \end{tabular}\par
  \vspace{4mm}
  \normalsize
  Reported speedups compare with \textbf{full prefill}.\\[1mm]
  Checkpoint-system latency is not directly compared.
  \papersource{Paper, Secs. 1--2, PDF p. 2; comparison scope: Table 2, PDF p. 4.}
\end{frame}

\begin{frame}{Exact FA outputs let each LA group replay independently}
  \centering
  \includegraphics[width=\linewidth,height=0.58\textheight,keepaspectratio]{figures/fig-01-overview.pdf}
  \vspace{2mm}
  \begin{enumerate}
    \item Cache token-level FA KV and FA output hiddens.
    \item Replay a recent hidden suffix inside each LA group.
    \item Continue with exact FA KV and approximate LA states.
  \end{enumerate}
  \papersource{Original Fig. 1, Sec. 3, PDF p. 3. A group is one FA layer plus following consecutive LA layers.}
\end{frame}

\begin{frame}{A cache hit replays only the last $k=\lceil rm\rceil$ positions}
  For each FA layer, retain
  \[
    \mathcal C=\{(K_i^{\FA},V_i^{\FA},h_i)\}_{i=1}^{n}.
  \]
  \begin{enumerate}
    \item Match $m$ prefix tokens and retrieve their FA KV.
    \item Fetch $h_{m-k+1:m}$ for each group; zero its LA states.
    \item Replay the tail through that group's LA layers.
    \item Synchronize, then process the unmatched suffix.
  \end{enumerate}
  \begin{block}{Illustrative example}
    $m=10{,}000$, $r=5\%$ $\Rightarrow$ replay positions 9,501--10,000.\\
    The ratio refers to the \emph{matched prefix}, not the new suffix.
  \end{block}
  \papersource{Paper, Sec. 3, Eq. (2), PDF p. 3. Example is explanatory, not an experiment.}
\end{frame}

\begin{frame}{Gated updates can attenuate the omitted history}
  The paper writes the Gated DeltaNet recurrence as
  \[
    S_i=T_iS_{i-1}+\beta_i v_i k_i^{\top},
    \qquad T_i=\alpha_i(I-\beta_i k_i k_i^{\top}).
  \]
  \begin{itemize}
    \item $S_i$: recurrent state; $k_i,v_i$: key and value vectors.
    \item $\alpha_i\in(0,1]$: forgetting gate; $\beta_i$: update strength.
    \item Old information is transformed repeatedly; recent inputs are written into the state.
  \end{itemize}
  \begin{block}{Replay}
    Set $\hat S_{m-k}=0$ and apply the recurrence to the last $k$ positions.
  \end{block}
  \papersource{Paper, Eqs. (1)--(2), PDF pp. 2--3. Operator notation follows the paper; tensor orientation is discussed in backup.}
\end{frame}

\begin{frame}{A short tail works when old-state influence contracts}
  \textbf{Conditional derivation:} assume identical transitions and writes during replay. Let $a=m-k$.
  \[
    E_m\equiv S_m-\hat S_m=(T_m\cdots T_{a+1})S_a.
  \]
  If $\|T_i\|_2\le\rho<1$, then
  \[
    \|E_m\|_F\le\rho^k\|S_a\|_F.
  \]
  \begin{itemize}
    \item Longer replay can suppress more initial-state error.
    \item The paper does not establish a uniform contraction rate.
    \item Later layers in a group can also receive perturbed inputs.
  \end{itemize}
  \papersource{Reader derivation from Eq. (1), PDF p. 2; not a theorem claimed by the paper.}
\end{frame}

\begin{frame}{Every FA boundary provides a fresh exact replay input}
  \begin{block}{Within a group}
    Approximate LA states can alter outputs and the inputs of later LA layers.
  \end{block}
  \begin{block}{At the next group}
    Start from that FA layer's cached output hidden, taken from full prefill.
  \end{block}
  \vspace{2mm}
  \begin{itemize}
    \item This confines propagation of replay-input error to each group.
    \item It does not make all reconstructed states exact.
    \item Exact KV for the matched prefix is retained throughout.
  \end{itemize}
  \papersource{Paper, Sec. 3, ``Independent Tail-Replay,'' PDF p. 3.}
\end{frame}

\begin{frame}{Only the final FFN in each replayed group is unnecessary}
  \[
    \underbrace{\mathrm{LA}_1\!\to\!\mathrm{FFN}_1\!\to\!\cdots\!\to\!\mathrm{LA}_L}_{\text{needed to reconstruct this group's states}}
    \quad\underbrace{\mathrm{FFN}_L}_{\text{skip during replay}}
  \]
  \begin{itemize}
    \item The last LA block already updates the final recurrent state.
    \item Its FFN output would feed the next group, whose input is cached.
    \item Intermediate FFNs remain necessary for later LA layers.
    \item Normal processing of the unmatched suffix is unchanged.
  \end{itemize}
  \papersource{Paper, Sec. 3, ``Replay efficiency,'' PDF p. 3. Diagram is an explanatory abstraction.}
\end{frame}

\begin{frame}{FA KV transfer can overlap with LA reconstruction}
  Replay uses tail hiddens; it does not consume cached FA KV.
  \begin{align*}
    T_{\mathrm{serial}}&\approx T_{\mathrm{KV}}+T_{\mathrm{replay}}+T_{\mathrm{other}},\\[1mm]
    T_{\mathrm{overlap}}&\approx\max(T_{\mathrm{KV}},T_{\mathrm{replay}})+T_{\mathrm{other}}.
  \end{align*}
  \begin{itemize}
    \item Copy FA KV on a separate stream; synchronize before suffix forward.
    \item Tail hiddens must already be available to begin replay.
    \item Increasing $r$ costs more once replay lies on the critical path.
  \end{itemize}
  \papersource{Paper mechanism: Sec. 3, PDF p. 3. Timing equations are an idealized reader model, ignoring contention.}
\end{frame}

\begin{frame}{Quality and latency use different evaluation protocols}
  \begin{itemize}
    \item \textbf{Models:} OLMo-Hybrid-7B, Qwen3.5-4B, Qwen3.6-27B.
    \item \textbf{Platform:} NVIDIA H100; PyTorch 2.9.1.
    \item \textbf{Quality:} full prefill, zero-only, 5\% replay, 10\% replay.
    \item \textbf{LongBench:} five tasks; selected 16K--64K cells; F1 / ROUGE-L.
    \item \textbf{RULER:} four tasks $\times$ two lengths (8K / 16K); recall.
    \item \textbf{TTFT:} shared narrativeqa prefixes at nominal 8K / 16K / 32K; mean of 20 timed repetitions.
  \end{itemize}
  \vspace{2mm}
  \alert{Zero-only keeps matched FA KV but resets LA states without replay.}
  \papersource{Paper, Sec. 4, Tables 1--2, PDF p. 4; evaluated cells: Table 3, PDF p. 5.}
\end{frame}

\begin{frame}{LongBench: short replay restores most average quality}
  \centering
  \small
  \begin{tabular}{lrrrr}
    \toprule
    Model & Full & Zero & 5\% replay & 10\% replay \\
    \midrule
    Qwen3.6-27B & .426 & .313 & .410 (96.2\%) & .417 (97.8\%) \\
    Qwen3.5-4B & .374 & .271 & .369 (98.9\%) & .367 (98.1\%) \\
    OLMo-Hybrid-7B & .317 & .159 & .294 (92.8\%) & .297 (93.9\%) \\
    \bottomrule
  \end{tabular}
  \vspace{4mm}
  \normalsize
  \[
    \mathrm{Retention}=100\%\times\mathrm{Score}_{\mathrm{replay}}/\mathrm{Score}_{\Full}
  \]
  \begin{itemize}
    \item Replay improves substantially over zero-only.
    \item Qwen3.5's average is slightly lower at 10\% than at 5\%.
    \item Length cells differ by model; use within-model comparisons.
  \end{itemize}
  \papersource{Paper, Table 1, PDF p. 4. Parentheses reproduce reported retention; higher is better.}
\end{frame}

\begin{frame}{RULER: strong recovery, with one reporting discrepancy}
  \centering
  \small
  \begin{tabular}{lrrrr}
    \toprule
    Model & Full & Zero & 5\% replay & 10\% replay \\
    \midrule
    Qwen3.6-27B$^{\dagger}$ & .987 & .299 & .985 (99.8\%) & .986 (99.9\%) \\
    Qwen3.5-4B & .960 & .415 & .959 (99.9\%) & .958 (99.7\%) \\
    OLMo-Hybrid-7B & .812 & .215 & .756 (93.1\%) & .785 (96.7\%) \\
    \bottomrule
  \end{tabular}
  \vspace{4mm}
  \normalsize
  \begin{itemize}
    \item Qwen3.5 is already close to full prefill at 5\%.
    \item OLMo benefits more from increasing the replay budget.
  \end{itemize}
  \begin{block}{$\dagger$ Keep the two reported data sources distinct}
    Table 3 gives Qwen3.6 means .97125 / .348 / .970 / .97125.\\
    These do not match Table 1 above; details are in backup.
  \end{block}
  \papersource{Paper, Table 1, PDF p. 4; reader arithmetic from Table 3, PDF p. 5. Higher is better.}
\end{frame}

\begin{frame}{Average retention hides larger task-specific losses}
  \centering
  \small
  \begin{tabular}{llrrr}
    \toprule
    Model & Task / length & Full & 5\% & 10\% \\
    \midrule
    OLMo-Hybrid-7B & qasper / 16K & .394 & .308 & .318 \\
    OLMo-Hybrid-7B & musique / 16K & .305 & .282 & .273 \\
    Qwen3.5-4B & qasper / 16K & .487 & .482 & .461 \\
    Qwen3.6-27B & qa1 / 8K & .895 & .880 & .885 \\
    \bottomrule
  \end{tabular}
  \vspace{4mm}
  \normalsize
  \begin{block}{OLMo on Qasper}
    5\% retains only $0.308/0.394=78.2\%$ of the full score.\\
    At 10\%, retention rises to 80.7\%, still below the benchmark average.
  \end{block}
  \alert{More replay does not monotonically improve every task score.}
  \papersource{Paper, Appendix A, Table 3, PDF p. 5. Retention percentages on this slide are reader calculations.}
\end{frame}

\begin{frame}{Longer matched prefixes yield larger TTFT speedups}
  \centering
  \includegraphics[width=0.88\linewidth,height=0.74\textheight,keepaspectratio]{figures/fig-02-speedup.pdf}
  \papersource{Redrawn from Table 2, PDF p. 4. 5\% replay, H2D-OVL+skip; speedup versus same-row full prefill. Nominal lengths; exact token counts on the next slide / backup.}
\end{frame}

\begin{frame}{At 32K, doubling the budget can raise replay cost sharply}
  \centering
  \small
  \begin{tabular}{lrrrr}
    \toprule
    Model & Matched tokens & Full (ms) & 5\% (ms) & 10\% (ms) \\
    \midrule
    OLMo-Hybrid-7B & 31,366 & 1068.3 & 108.8 & 112.5 \\
    Qwen3.5-4B & 31,847 & 786.4 & 86.2 & 108.1 \\
    Qwen3.6-27B & 31,847 & 3605.2 & 251.8 & 371.3 \\
    \bottomrule
  \end{tabular}
  \vspace{4mm}
  \normalsize
  \begin{itemize}
    \item Both replay columns use H2D-OVL+skip.
    \item Qwen3.6: 5\% $\to$ 10\% increases TTFT by \textbf{47.5\%}.
    \item Its speedup drops from 14.32$\times$ to 9.71$\times$.
    \item OLMo's corresponding latency increase is only 3.4\%.
  \end{itemize}
  \papersource{Paper, Table 2, PDF p. 4. Percentage increases computed from the reported means.}
\end{frame}

\begin{frame}{Overlap and FFN skip jointly cut recovery overhead}
  \centering
  \small
  \begin{tabular}{lrrr}
    \toprule
    Model, about 32K & SER (ms) & OVL+skip (ms) & Reduction \\
    \midrule
    OLMo-Hybrid-7B, 5\% & 158.8 & 108.8 & 31.5\% \\
    Qwen3.5-4B, 5\% & 105.8 & 86.2 & 18.5\% \\
    Qwen3.6-27B, 5\% & 311.9 & 251.8 & 19.3\% \\
    OLMo-Hybrid-7B, 10\% & 191.7 & 112.5 & 41.3\% \\
    \bottomrule
  \end{tabular}
  \vspace{4mm}
  \normalsize
  \begin{itemize}
    \item These reductions use serialized Tail-Replay as the denominator.
    \item Table 2 tests the two optimizations together.
    \item Individual effects of overlap and FFN skip are not separated.
  \end{itemize}
  \papersource{Paper, Table 2, PDF p. 4. Reductions computed as 1 - (OVL+skip)/SER.}
\end{frame}

\begin{frame}{Checkpoint-free recovery still has a storage cost}
  \begin{block}{Extra cache content}
    Store an output hidden for every token at every FA layer.
  \end{block}
  With uniform layer widths and $b$ bytes per element,
  \[
    M_{\mathrm{cache}}\approx nL_{\FA}b(d_K+d_V+d_h).
  \]
  \begin{itemize}
    \item $n$: cached tokens; $L_{\FA}$: number of FA layers.
    \item $d_K,d_V$: total KV widths; $d_h$: hidden width.
    \item Hidden storage adds $nL_{\FA}bd_h$ bytes.
    \item The paper gives no equal-memory comparison with checkpoints.
  \end{itemize}
  \papersource{Reader cost model from the cache definition in Sec. 3, PDF p. 3; not a reported memory measurement.}
\end{frame}

\begin{frame}{The measured gain is a cache-hit TTFT gain}
  \begin{itemize}
    \item Timing starts at cache transfer or replay and ends at the first token.
    \item Results include this recovery path's transfer cost.
    \item Queueing, cache lookup, and concurrent serving throughput are not evaluated by Table 2.
    \item Quality tasks and latency prefixes use different length sets.
    \item Quality retention is an aggregate score ratio, not output equivalence.
  \end{itemize}
  \begin{block}{The next decisive comparison}
    Tail-Replay versus checkpoint recovery under the same cache capacity and request distribution.
  \end{block}
  \papersource{Measurement definition: Sec. 4 and Table 2, PDF p. 4. Proposed comparison is reader analysis.}
\end{frame}

\begin{frame}{Tail-Replay trades state exactness for flexible reuse}
  \begin{enumerate}
    \item \textbf{Design:} exact FA KV and hidden inputs; approximate LA recovery from a short tail.
    \item \textbf{Evidence:} strong recovery over zero-only; 9.12--14.32$\times$ TTFT speedup at about 32K with 5\% replay.
    \item \textbf{Tradeoff:} task-dependent losses, hidden storage, and budget-dependent replay latency.
  \end{enumerate}
  \vspace{4mm}
  \begin{block}{Discussion}
    What signal could choose a tail length per group or request, with a checkpoint fallback when recovery is unreliable?
  \end{block}
  \papersource{Paper, Secs. 3--5 and Tables 1--3, PDF pp. 3--5. Adaptive replay / fallback is a proposed extension.}
\end{frame}

\begin{frame}{Primary reference and evidence map}
  \textbf{Yirui Liu, Ruoling Qi, Xuaner Wu, Penghang Liu, Jian Chen.}\\[2mm]
  \emph{Tail-Replay: Escaping the Curse of Linear Attention in Prefix Caching for Hybrid LLMs.}\\[2mm]
  arXiv:2608.30310v2, revised October 15, 2026.\\[2mm]
  \href{https://arxiv.org/abs/2608.30310v2}{https://arxiv.org/abs/2608.30310v2}
  \vspace{4mm}
  \begin{itemize}
    \item Mechanism: Secs. 2--3, Eqs. (1)--(2), Fig. 1, pp. 2--3.
    \item Aggregate quality and TTFT: Tables 1--2, p. 4.
    \item Per-task quality: Appendix A, Table 3, p. 5.
  \end{itemize}
  \papersource{All paper page references use 1-based PDF page numbers. Following slides are backup material.}
\end{frame}

\appendix

\begin{frame}{Backup: the Qwen3.6 RULER averages do not reconcile}
  \centering
  \small
  \begin{tabular}{lrrrr}
    \toprule
    Source & Full & Zero & 5\% & 10\% \\
    \midrule
    Table 1 & .987 & .299 & .985 & .986 \\
    Mean of Table 3 cells & .97125 & .34800 & .97000 & .97125 \\
    \bottomrule
  \end{tabular}\par
  \vspace{3mm}
  \normalsize
  Example: the eight full-prefill recall values give
  \[
    \frac{1+1+.895+.875+1+1+1+1}{8}=.97125.
  \]
  \begin{itemize}
    \item Appendix-based retention is 99.87\% / 100.00\%.
    \item The differences exceed rounding at the displayed precision.
    \item No alternative aggregation rule is stated; keep both sources labeled.
  \end{itemize}
  \papersource{Paper, Table 1, PDF p. 4 versus Table 3, PDF p. 5; appendix means computed by the reader.}
\end{frame}

\begin{frame}{Backup: exact 8K and 16K timing rows}
  \centering
  \small
  \begin{tabular}{lrrrr}
    \toprule
    Model & Matched tokens & Full (ms) & 5\% (ms) & 10\% (ms) \\
    \midrule
    OLMo-Hybrid-7B & 8,225 & 264.3 & 82.9 & 82.7 \\
    OLMo-Hybrid-7B & 16,417 & 533.7 & 83.5 & 85.6 \\
    Qwen3.5-4B & 8,226 & 191.6 & 75.2 & 75.9 \\
    Qwen3.5-4B & 16,418 & 387.7 & 75.0 & 76.0 \\
    Qwen3.6-27B & 8,226 & 879.6 & 154.3 & 154.7 \\
    Qwen3.6-27B & 16,418 & 1797.2 & 161.6 & 218.1 \\
    \bottomrule
  \end{tabular}\par
  \vspace{4mm}
  \normalsize
  Both replay columns use H2D-OVL+skip.\\[2mm]
  These are means over 20 timed repetitions, not throughput measurements.
  \papersource{Paper, Table 2, PDF p. 4.}
\end{frame}

\begin{frame}{Backup: contraction needs more than a forgetting gate}
  For the paper's operator form, a sufficient nonexpansion condition is
  \[
    \|k_i\|_2=1,\quad \beta_i\in[0,2]
    \quad\Rightarrow\quad
    \|I-\beta_i k_i k_i^\top\|_2\le1.
  \]
  \begin{itemize}
    \item A uniform $\alpha_i\le\rho<1$ then yields a $\rho^k$ bound.
    \item The paper explicitly states only $\alpha_i\in(0,1]$.
    \item With perturbed replay inputs, the general error includes
  \end{itemize}
  \[
    E_i=T_iE_{i-1}+(T_i-\hat T_i)\hat S_{i-1}+(b_i-\hat b_i).
  \]
  \papersource{Reader derivation from Eq. (1), PDF p. 2. $b_i$ is the additive write; hats denote replay quantities.}
\end{frame}

\begin{frame}{Backup: matrix layout matters when implementing Eq. (1)}
  The paper writes $T_iS_{i-1}+\beta_i v_i k_i^\top$ without specifying axes.\par
  \vspace{3mm}
  For a value-by-key state layout,
  \[
    S_i\in\mathbb R^{d_v\times d_k},\quad
    k_i\in\mathbb R^{d_k},\quad v_i\in\mathbb R^{d_v},
  \]
  a key-space operator acts on the \emph{right}:
  \[
    S_i=\alpha_i S_{i-1}(I-\beta_i k_i k_i^\top)+\beta_i v_i k_i^\top.
  \]
  \begin{itemize}
    \item A transposed state layout requires transposing the write term too.
    \item The main derivation treats $T_i$ as an abstract state operator.
  \end{itemize}
  \papersource{Reader dimensional clarification of the notation in Eq. (1), PDF p. 2; model head dimensions are not supplied.}
\end{frame}

\end{document}