% Self-authored reading presentation, based on the local 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}
\definecolor{TraceOrange}{RGB}{184,106,0}
\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{\tas}{{\rmfamily\scshape Trace as State}}
\newcommand{\tap}{{\rmfamily\scshape Trace Append}}
\pdfstringdefDisableCommands{\def\translate#1{#1}}
\newcommand{\ctx}{\colorbox{AcademicBlue!9}{\strut\ $x$: long context\ }}
\newcommand{\trc}{\colorbox{TraceOrange!13}{\strut\ $T$: prior traces\ }}
\newcommand{\qry}{\colorbox{AcademicTeal!10}{\strut\ $q$\ }}
\setlength{\tabcolsep}{6pt}
\renewcommand{\arraystretch}{1.2}

\title[Trace as State]{Trace as State}
\subtitle{Reasoning Traces as Conditional States\\for Long-Context Transformers}
\author{\texorpdfstring{Paper authors: Xu Zou (Z.ai), Jie Tang (Tsinghua University)\\[3pt]\small An independent paper-reading presentation}{Paper authors: Xu Zou and Jie Tang; independent reading presentation}}
\date{arXiv:2609.02702v1 \enspace$\cdot$\enspace 2 September 2026\\Reading: 30 September 2026}

\begin{document}

% 1 -- Main presentation: approximately 25 minutes, including discussion.
\begin{frame}
\titlepage
\vspace{-4mm}
\begin{center}\small\color{AcademicTeal}Put previously discovered task information before the next reading pass.\end{center}
\end{frame}

% 2
\begin{frame}{Useful task state may arrive after the evidence}
\begin{block}{The mismatch}
A causal model encodes a long context before later reasoning resolves what to look for.
\end{block}
\begin{itemize}
\item A target, a resolved reference, or a search frontier can emerge late.
\item Later reasoning can use the existing cache, but cannot revise earlier token representations in that pass.
\item A fresh pass can make that information available while the context is encoded again.
\end{itemize}
\papersource{Paper, Sec. 1, PDF pp. 1--2; Sec. 3.2, p. 4.}
\end{frame}

% 3
\begin{frame}{The central experiment changes where the same trace appears}
\begin{center}
\begin{tabular}{ll}
First pass & \ctx\quad\qry \\[8pt]
\tap & \ctx\quad\trc\quad\qry \\[8pt]
\tas & \trc\quad\ctx\quad\qry
\end{tabular}
\end{center}
\medskip
\begin{itemize}
\item Same model, same long context, same realized trace block $T$.
\item The question $q$ stays at the end in the evaluated prompts.
\item The comparison isolates a placement intervention, not a unique internal mechanism.
\end{itemize}
\papersource{Paper, Sec. 3.3, Eq. (5), p. 5; Sec. 4.1, pp. 5--6; final bullet: reading analysis.}
\end{frame}

% 4
\begin{frame}{Feedback crosses passes; each pass stays causal}
\centering
\includegraphics[width=\linewidth,height=0.62\textheight,keepaspectratio]{figures/fig-01d-feedback.pdf}
\begin{itemize}
\item Source reasoning fields become $T$; separate answer fields are excluded.
\item Models remain frozen. The paper's diagram suppresses the final question.
\end{itemize}
\papersource{Original paper, Fig. 1D, PDF p. 3, cropped from the author's vector figure; App. C, p. 13.}
\end{frame}

% 5
\begin{frame}{Knowing the initial condition selects one state path}
\[
s_i=U(s_{i-1},c_i),\qquad s_0=z,\qquad i=1,\ldots,n.
\]
\begin{itemize}
\item $C=(c_1,\ldots,c_n)$: information sequence; $U$: known fixed update rule.
\item $s_i\in\mathcal S$: current task state; $z$: supplied initial condition.
\item Let $m=|\mathcal S|$ and $b=\log_2m$.
\end{itemize}
\begin{block}{Condition first: $[z,C]$}
Keep one $\mathcal S$-valued register and update it as each unit arrives.\par
Persistent input-dependent memory: $\lceil b\rceil$ bits suffice.
\end{block}
\papersource{Paper, Sec. 3.1, Eq. (1), PDF pp. 3--4; App. A, p. 12.}
\end{frame}

% 6
\begin{frame}{A late condition may require an entire response map}
For each sequence, define $\phi_C(z)=t(C,z)$ and let $\mathcal K$ count distinct maps.
\begin{enumerate}
\item Read $C$ before knowing which $z$ will be queried.
\item Different maps must produce different persistent configurations.
\item Otherwise, a shared suffix $z$ forces an incorrect answer for one map.
\end{enumerate}
\[
\text{Late-order memory}\ \geq\ \lceil\log_2\mathcal K\rceil.
\]
\begin{block}{Worst-case construction: all $m^m$ self-maps are attainable}
Late: $\lceil b2^b\rceil$ bits \qquad Early: $\lceil b\rceil$ bits.\par
For $m=4$: 256 possible maps require 8 bits; one state needs 2 bits.
\end{block}
\papersource{Paper, Eq. (2), PDF p. 4; App. A construction and distinguishability proof, p. 12.}
\end{frame}

% 7
\begin{frame}{The theorem motivates an ordering principle}
\begin{columns}[T,onlytextwidth]
\begin{column}{0.48\textwidth}
\begin{block}{What is proved}
\begin{itemize}
\item Deterministic, exact, one-pass computation.
\item An adversarial task family with every state self-map.
\item All persistent writable input-dependent storage is counted.
\end{itemize}
\end{block}
\end{column}
\begin{column}{0.48\textwidth}
\begin{block}{How the paper uses it}
\begin{itemize}
\item Finite-context, finite-precision causal models fit a finite-state abstraction.
\item Text traces are imperfect proxies, not the formal condition $z$.
\item No exponential GPU-memory reduction is demonstrated.
\end{itemize}
\end{block}
\end{column}
\end{columns}
\papersource{Paper, Sec. 3.2, p. 4; App. A scope, pp. 12--13. Last point: evidence boundary.}
\end{frame}

% 8
\begin{frame}{The implementation reuses five imperfect reasoning traces}
\[
(r_j,a_j)\sim\mathcal M(\cdot\mid[x,q]),\qquad
T=\pi(r_1,\ldots,r_5).
\]
\begin{itemize}
\item Fixed ordering, labels, delimiters, and a warning to verify against the task.
\item Each reused trace is capped at its first \alert{50,000 characters}.
\item Separate visible answers $a_j$ are excluded; traces can still contain answer-relevant information.
\item Five fresh second-pass repeats per placement are averaged for evaluation.
\end{itemize}
\begin{block}{Deployment accounting}
Five source calls plus one feedback call are needed for one answer with five source traces.
\end{block}
\papersource{Paper, Sec. 4.1, pp. 5--6; Sec. 4.4, p. 7; App. C, pp. 13--14.}
\end{frame}

% 9
\begin{frame}{Evaluation spans graph state, retrieval, and novel reading}
\begin{center}
\begin{tabular}{lll}
\toprule
Task & Evaluated problems & Metrics ($\uparrow$) \\
\midrule
GraphWalks 256K & 100 BFS + 100 Parents & Set EM, set F1 \\
MRCRv2, 8-needle & 100 at 256K + 100 at 512K & EM, Seq. ratio \\
NUB-1M Season 2 & 20 novel questions & Judged accuracy \\
\bottomrule
\end{tabular}
\end{center}
\begin{itemize}
\item Models: DeepSeek V4 Pro Preview, Qwen 3.7 Max, GLM-5.2.
\item Five repeats; invalid, missing, overlong, or filtered outputs score zero.
\item NUB uses a DeepSeek judge; its novel is about 400--700K tokens.
\end{itemize}
\papersource{Paper, Tables 1-1 and 1-2, p. 6; Apps. B and E, pp. 13, 18. Seq. is not set F1.}
\end{frame}

% 10
\begin{frame}{Parents shows the largest placement gains}
\begin{center}
\begin{tabular}{lrrrr}
\toprule
\multicolumn{5}{c}{GraphWalks Parents: exact match (\%, higher is better)} \\
\midrule
Model & First & Append & State & Gain vs. Append \\
\midrule
DeepSeek & 29.2 & 43.0 & \textbf{81.8} & +38.8 pp \\
Qwen & 60.8 & 71.0 & \textbf{96.4} & +25.4 pp \\
GLM & 66.4 & 83.2 & \textbf{100.0} & +16.8 pp \\
\bottomrule
\end{tabular}
\end{center}
\medskip
\begin{itemize}
\item DeepSeek gains 52.6 percentage points over the first pass.
\item All three paired Parents EM intervals are wholly above zero.
\item GLM's 100\% applies to the evaluated problems and repeats.
\end{itemize}
\papersource{Paper, Table 2, PDF p. 7; paired intervals in Table 5, p. 18.}
\end{frame}

% 11
\begin{frame}{BFS gains vary; exact match and F1 can disagree}
\begin{center}
\begin{tabular}{lrrr}
\toprule
\multicolumn{4}{c}{GraphWalks BFS: EM / set F1 (\%)} \\
\midrule
Model & First & Append & State \\
\midrule
DeepSeek & 31.6 / 36.4 & 41.8 / 48.3 & \textbf{58.8 / 65.9} \\
Qwen & 60.0 / 68.1 & 60.4 / 70.4 & \textbf{63.8 / 71.7} \\
GLM & 55.8 / 70.7 & 60.0 / \textbf{75.8} & \textbf{63.4} / 75.0 \\
\bottomrule
\end{tabular}
\end{center}
\begin{itemize}
\item GLM BFS F1 is the sole mean-score loss among 27 reported comparisons.
\item More fully correct sets need not imply better partial overlap elsewhere.
\item Qwen BFS F1 and both GLM BFS paired intervals cross zero.
\end{itemize}
\papersource{Paper, Tables 2 and 5, PDF pp. 7, 18.}
\end{frame}

% 12
\begin{frame}{Retrieval and binding also benefit from earlier traces}
\begin{center}
\begin{tabular}{llrrrr}
\toprule
\multicolumn{6}{c}{MRCRv2 8-needle: exact match (\%)} \\
\midrule
Model & Bin & First & Append & State & Difference (pp) \\
\midrule
DeepSeek & 256K & 53.8 & 66.6 & 76.8 & +10.2 \\
DeepSeek & 512K & 45.4 & 49.4 & 52.6 & +3.2 \\
Qwen & 256K & 79.8 & 84.0 & 88.4 & +4.4 \\
Qwen & 512K & 36.2 & 40.4 & 46.8 & +6.4 \\
GLM & 256K & 40.2 & 40.0 & 61.2 & +21.2 \\
GLM & 512K & 42.6 & 44.6 & 55.4 & +10.8 \\
\bottomrule
\end{tabular}
\end{center}
DeepSeek 512K EM: paired 95\% interval $[-2.6,+9.4]$ pp crosses zero.\par
\papersource{Paper, Table 2, p. 7; Table 5, p. 18. Length bins are different problem sets.}
\end{frame}

% 13
\begin{frame}{Novel reading gives weaker evidence for placement}
\begin{columns}[c,onlytextwidth]
\begin{column}{0.49\textwidth}
\includegraphics[width=\linewidth,height=0.59\textheight,keepaspectratio]{figures/fig-05-nub-ci.pdf}
\end{column}
\begin{column}{0.48\textwidth}
\begin{tabular}{lrr}
\toprule
Accuracy (\%) & Append & State \\
\midrule
DeepSeek & 71.0 & 73.0 \\
Qwen & 49.0 & 51.0 \\
GLM & 65.0 & 66.0 \\
\bottomrule
\end{tabular}
\medskip
\begin{itemize}
\item Only 20 questions; wide intervals.
\item Extra placement gain: 1--2 pp.
\item No paired NUB contrast is reported in Table 5.
\end{itemize}
\end{column}
\end{columns}
\papersource{Paper, Table 2, p. 7; Fig. 5 NUB panel, p. 19. Bars are problem-bootstrap 95\% intervals.}
\end{frame}

% 14
\begin{frame}{26 of 27 higher means is not 26 significant wins}
\begin{block}{Paired uncertainty for GraphWalks and MRCR}
20 of 24 unadjusted 95\% intervals lie wholly above zero.\par
Average five repeats within each problem; resample 100 problems per cell.
\end{block}
\begin{center}
\begin{tabular}{lrr}
\toprule
The four intervals crossing zero & Difference (pp) & 95\% interval \\
\midrule
DeepSeek MRCR 512K EM & +3.20 & $[-2.60,9.40]$ \\
Qwen BFS F1 & +1.29 & $[-0.56,3.90]$ \\
GLM BFS EM & +3.40 & $[-1.00,7.80]$ \\
GLM BFS F1 & $-0.83$ & $[-3.94,1.62]$ \\
\bottomrule
\end{tabular}
\end{center}
\papersource{Paper, App. E and Table 5, p. 18: 20,000 bootstrap resamples, seed 0; no multiplicity correction.}
\end{frame}

% 15
\begin{frame}{Task-specific traces beat several simpler feedback choices}
\begin{center}
\begin{tabular}{llrr}
\toprule
DeepSeek GraphWalks & Prompt & BFS EM & Parents EM \\
\midrule
First pass & $[x,q]$ & 31.6 & 29.2 \\
Question First & $[q,x,q]$ & 33.4 & 53.0 \\
Re2 (evaluated form) & $[x,q,x,q]$ & 49.0 & 50.0 \\
Answer Feedback & $[a,x,q]$ & 35.4 & 45.4 \\
Random Trace & $[T_{\mathrm{rand}},x,q]$ & 22.4 & 14.2 \\
\tas & $[T,x,q]$ & \textbf{58.8} & \textbf{81.8} \\
\bottomrule
\end{tabular}
\end{center}
\begin{itemize}
\item Generic trace formatting and answer access do not explain the full gain.
\item Question First has 182 zero-scored termination/format failures.
\end{itemize}
\papersource{Paper, Table 3, p. 8; App. B, p. 13. Scores are percentages; controls are not cost matched.}
\end{frame}

% 16
\begin{frame}{The feedback pass can improve on all five existing answers}
\begin{center}
\begin{tabular}{lrr}
\toprule
DeepSeek GraphWalks & BFS EM (\%) & Parents EM (\%) \\
\midrule
Majority@5 & 35.0 & 31.0 \\
Oracle@5 & 50.0 & 50.0 \\
Trace Only: $[T,q]$ & 46.2 & 43.8 \\
Trace Append: $[x,T,q]$ & 41.8 & 43.0 \\
Trace as State: $[T,x,q]$ & \textbf{58.8} & \textbf{81.8} \\
\bottomrule
\end{tabular}
\end{center}
\begin{itemize}
\item Traces already contain useful information; rereading adds further value.
\item Oracle@5 selects the best score retrospectively using ground truth.
\item Exceeding it uses new computation, not a free improvement at equal cost.
\end{itemize}
\papersource{Paper, Table 3, p. 8; Fig. 6 caption, p. 20. Majority@5 votes on individual set elements.}
\end{frame}

% 17
\begin{frame}{One trace helps; additional traces generally help more}
\begin{columns}[c,onlytextwidth]
\begin{column}{0.44\textwidth}
\centering
\includegraphics[width=\linewidth,height=0.76\textheight,keepaspectratio]{figures/fig-02-trace-count.pdf}
\end{column}
\begin{column}{0.53\textwidth}
\begin{itemize}
\item DeepSeek, GraphWalks 256K only.
\item Nested first 1--5 eligible traces; same $T$ for both placements at each count.
\item With one trace, Parents F1 is 76.7\% before versus 47.0\% after context.
\item More traces increase both information and inference cost.
\end{itemize}
\papersource{Original Fig. 2, PDF p. 8; Sec. 4.4, pp. 7--8. Shading: 95\% problem-bootstrap intervals.}
\end{column}
\end{columns}
\end{frame}

% 18
\begin{frame}{Difficulty profiles describe heterogeneity}
\centering
\includegraphics[width=0.93\linewidth,height=0.60\textheight,keepaspectratio]{figures/fig-04-bfs-f1.pdf}
\begin{itemize}
\item Plotted values are gains over the shared first pass, not absolute scores.
\item Yellow ranges were chosen after seeing outcomes; they do not establish a capacity threshold or mechanism.
\end{itemize}
\papersource{Paper, Fig. 4 top panels, p. 17; App. D, pp. 14--18. Original author figure.}
\end{frame}

% 19
\begin{frame}{Quality gains come with extra inference and variable caching}
\begin{center}
\begin{tabular}{llrr}
\toprule
DeepSeek task & Total usage (million tokens) & Append & State \\
\midrule
GraphWalks & Output, including reasoning & 97.738 & 90.482 \\
NUB & Uncached input & 12.878 & 25.055 \\
NUB & Output, including reasoning & 1.001 & 1.215 \\
\bottomrule
\end{tabular}
\end{center}
\begin{itemize}
\item Totals include the shared source stage plus the feedback stage.
\item Prefix changes can reduce reuse of the original context cache.
\item Output length and cache behavior vary across tasks and models.
\item No measured universal speedup or equal-cost frontier is established.
\end{itemize}
\papersource{Paper, Limitations, p. 9; App. F and Table 6, pp. 20--21. Retained responses with API usage only.}
\end{frame}

% 20
\begin{frame}{The evidence has clear interface and scope boundaries}
\begin{itemize}
\item \textbf{Interface:} this realization needs exposed reasoning traces; answer-only APIs require another state interface.
\item \textbf{Trace quality:} incomplete or incorrect text can mislead the new pass.
\item \textbf{Coverage:} three models, three task families; no multi-round agent evaluation.
\item \textbf{Reproducibility:} effective provider output caps are unknown; full NUB-specific templates are not given.
\item \textbf{Mechanism:} the intervention supports conditional rereading, but does not identify a faithful internal state representation.
\end{itemize}
\papersource{Paper, Sec. 3.2, p. 4; Sec. 4.1, p. 6; Limitations, p. 9; App. C, pp. 13--14.}
\end{frame}

% 21
\begin{frame}{The usable idea is conditional rereading}
\begin{block}{Empirical result}
Moving the same prior traces before the context usually helps, with especially large gains on GraphWalks Parents.
\end{block}
\begin{block}{Conceptual contribution}
When information becomes available can matter as much as whether it is available.
\end{block}
\begin{block}{Next experiments}
Compare compressed states and trace selection at equal total cost; test preregistered difficulty contrasts and multi-round use.
\end{block}
\papersource{Paper, Sec. 5, p. 8, and Limitations, p. 9. Equal-cost and preregistered tests: reading suggestions.}
\end{frame}

% 22
\begin{frame}{Source and reading map}
\textbf{Xu Zou and Jie Tang.} 2026.\par
\emph{Trace as State: Reasoning Traces as Conditional States for Long-Context Transformers.}\par
\href{https://arxiv.org/abs/2609.02702v1}{arXiv:2609.02702v1} (2 September 2026).
\medskip
\begin{itemize}
\item Method and theory: Sec. 3, pp. 3--5; Appendix A, pp. 12--13.
\item Results and controls: Tables 2--3 and Fig. 2, pp. 7--8.
\item Uncertainty and cost: Appendix E--F, pp. 18--21.
\end{itemize}
\medskip
\small Prepared from the versioned PDF and the author's TeX source.\par
Original figures are attributed on their slides; tables are selected/reformatted from the paper.\par
All following slides are optional backup material.
\end{frame}

\appendix

% 23
\begin{frame}{Backup: model budgets are not verified request caps}
\begin{center}
\begin{tabular}{lrrl}
\toprule
Model & Input budget & Output budget & Reasoning \\
\midrule
DeepSeek V4 Pro Preview & 1,048,576 & 131,072 & max \\
Qwen 3.7 Max & 983,616 & 65,536 & xhigh text \\
GLM-5.2 & 1,048,576 & 65,536 & max \\
\bottomrule
\end{tabular}
\end{center}
\begin{itemize}
\item The authors requested no custom maximum-output value; effective provider defaults are not established by the records.
\item DeepSeek uses the 2026-04-24 version, not the 2026-08-13 release.
\item Qwen uses prompt text, not a provider-side reasoning-effort parameter.
\end{itemize}
\papersource{Paper, Table 1-1 and Sec. 4.1, p. 6; App. C.2, pp. 13--14. Budgets in tokens.}
\end{frame}

% 24
\begin{frame}{Backup: scoring includes interface failures}
\begin{itemize}
\item \textbf{GraphWalks:} parse the terminal answer line as a node set. Both sets empty scores one; malformed or nonterminal output scores zero.
\item \textbf{Question First:} 121 null termination markers plus 60 length-limited outputs, and one malformed answer, all score zero.
\item \textbf{MRCR:} validate and strip the random prefix, then calculate exact match and SequenceMatcher ratio. Filtering remains in the denominator.
\item \textbf{NUB:} judge correctness against reference answers without solver identity or placement labels; authors report manual checking.
\end{itemize}
\papersource{Paper, App. B, PDF p. 13. Question First failures: 161 BFS and 21 Parents outputs.}
\end{frame}

% 25
\begin{frame}{Backup: all GraphWalks main-result scores}
\begin{center}
\begin{tabular}{llrrr}
\toprule
\multicolumn{5}{c}{EM / set F1 (\%); five-repeat means; higher is better} \\
\midrule
Model & Subtask & First & Append & State \\
\midrule
DeepSeek & BFS & 31.6 / 36.4 & 41.8 / 48.3 & 58.8 / 65.9 \\
DeepSeek & Parents & 29.2 / 46.5 & 43.0 / 65.3 & 81.8 / 91.3 \\
Qwen & BFS & 60.0 / 68.1 & 60.4 / 70.4 & 63.8 / 71.7 \\
Qwen & Parents & 60.8 / 87.2 & 71.0 / 91.7 & 96.4 / 99.1 \\
GLM & BFS & 55.8 / 70.7 & 60.0 / 75.8 & 63.4 / 75.0 \\
GLM & Parents & 66.4 / 88.5 & 83.2 / 92.7 & 100.0 / 100.0 \\
\bottomrule
\end{tabular}
\end{center}
\papersource{Paper, Table 2, PDF p. 7. 100 problems per subtask.}
\end{frame}

% 26
\begin{frame}{Backup: all MRCR main-result scores}
\begin{center}
\begin{tabular}{llrrr}
\toprule
\multicolumn{5}{c}{EM / SequenceMatcher ratio (\%); higher is better} \\
\midrule
Model & Length bin & First & Append & State \\
\midrule
DeepSeek & 256K & 53.8 / 78.5 & 66.6 / 79.6 & 76.8 / 88.7 \\
DeepSeek & 512K & 45.4 / 63.6 & 49.4 / 66.9 & 52.6 / 73.3 \\
Qwen & 256K & 79.8 / 83.1 & 84.0 / 87.1 & 88.4 / 91.3 \\
Qwen & 512K & 36.2 / 43.7 & 40.4 / 47.4 & 46.8 / 52.5 \\
GLM & 256K & 40.2 / 48.2 & 40.0 / 58.3 & 61.2 / 71.9 \\
GLM & 512K & 42.6 / 52.0 & 44.6 / 59.9 & 55.4 / 70.1 \\
\bottomrule
\end{tabular}
\end{center}
\papersource{Paper, Table 2, PDF p. 7. 100 problems per bin, five repeats.}
\end{frame}

% 27
\begin{frame}{Backup: the worst case uses a very rich input alphabet}
Choose $n=1$ and
\[
\mathcal C=\{c_f:f\in\mathcal S^{\mathcal S}\},\qquad U(s,c_f)=f(s).
\]
\begin{itemize}
\item Every possible self-map is encoded by one input symbol: $\mathcal K=m^m$.
\item Late order: store which map arrived before the queried $z$ is known.
\item Early order: store $z$, then replace it with $f(z)$.
\item Identity-map suffixes also prove the early cut needs at least $m$ configurations.
\end{itemize}
\begin{block}{Accounting matters}
The fixed transition rule is known. The bound counts persistent input-dependent state, not its implementation cost or the transition-table size.
\end{block}
\papersource{Paper, App. A, PDF p. 12. Restricted update families can yield far fewer residual maps.}
\end{frame}

% 28
\begin{frame}{Backup: difficulty is not a monotone placement effect}
\begin{columns}[c,onlytextwidth]
\begin{column}{0.45\textwidth}
\centering
\includegraphics[width=\linewidth,height=0.78\textheight,keepaspectratio]{figures/fig-03-difficulty-em.pdf}
\end{column}
\begin{column}{0.51\textwidth}
\begin{itemize}
\item Rows: DeepSeek, Qwen, GLM. Left: BFS depth. Right: parent-set size.
\item Blue/orange: State/Append gains over the common first pass.
\item GLM BFS reverses in the final depth bin.
\item Parents EM never favors Append in these plotted bins.
\item Bins and highlighted ranges are exploratory, outcome-informed analyses.
\end{itemize}
\papersource{Paper, original Fig. 3, p. 16; App. D, pp. 14--18.}
\end{column}
\end{columns}
\end{frame}

\end{document}