\documentclass[aspectratio=169,11pt]{beamer}
\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage{amsmath,amssymb,graphicx,booktabs,array}
\newcolumntype{P}[1]{>{\raggedright\arraybackslash}p{#1}}

\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{\pcot}{p_{\mathrm{cot}}}
\newcommand{\EOS}{\langle\mathrm{EOS}\rangle}

\title[RL after NTP]{How Reinforcement Learning After\\ Next-Token Prediction Facilitates Learning}
\subtitle{A paper discussion: learning from rare long demonstrations}
\author{Paper by N. Tsilivis, E. Malach, K. Ullrich, and J. Kempe}
\date{\href{https://arxiv.org/abs/2510.11495v2}{arXiv:2510.11495v2} \quad 25 October 2026}

\begin{document}

\begin{frame}
  \titlepage
  \vfill
  \centering\small Research group reading presentation
\end{frame}

\begin{frame}{A model can sample a good long answer yet fail greedily}
  \begin{block}{Research question}
    Why can reinforcement learning after next-token prediction rapidly improve accuracy and increase response length when correct long demonstrations are rare?
  \end{block}
  \begin{itemize}
    \item Pre-training can learn the long path while greedy decoding chooses a short path.
    \item Rewarding correct generations enriches long answers in the next training round.
    \item The paper proves this for a linear autoregressive parity model and tests related behavior in transformers.
  \end{itemize}
  \papersource{Tsilivis et al., arXiv:2510.11495v2, Sec. 1, PDF pp. 1--3.}
\end{frame}

\begin{frame}{The data contain two correct formats for one parity task}
  \centering
  \includegraphics[width=0.98\linewidth,height=0.39\textheight,keepaspectratio]{figures/concept-data.pdf}
  \vspace{2mm}
  \begin{itemize}
    \item Input: $x\in\{-1,+1\}^d$; answer: $s_d=\prod_{i=1}^d x_i$.
    \item Long fraction $\pcot$: output every partial parity $s_j=\prod_{i=1}^j x_i$.
    \item Short fraction $1-\pcot$: output only $s_d$.
  \end{itemize}
  \papersource{Paper, Fig. 1 (data panel), PDF p. 2; Sec. 2, PDF pp. 3--4. Figure cropped from the author source.}
\end{frame}

\begin{frame}{Long traces turn global parity into local updates}
  \begin{columns}[T,onlytextwidth]
    \begin{column}{0.48\textwidth}
      \begin{block}{Short route}
        Predict $\prod_{i=1}^{d}x_i$ in one output step from all input bits.
      \end{block}
    \end{column}
    \begin{column}{0.48\textwidth}
      \begin{block}{Long route}
        Start with $s_1=x_1$, then repeat $s_j=s_{j-1}x_j$ for $j=2,\ldots,d$.
      \end{block}
    \end{column}
  \end{columns}
  \vspace{4mm}
  \centering
  \large $x=(+1,-1,+1,-1,+1)$\quad$\Rightarrow$\quad $(s_1,\ldots,s_5)=(+1,-1,-1,+1,+1)$
  \vspace{3mm}
  \begin{itemize}
    \item The parity task is representable by a shallow transformer; the key parity experiment probes \alert{learning from limited samples}.
  \end{itemize}
  \papersource{Paper, Secs. 2, 3.1, 5, PDF pp. 3--6 and 9--10. Example is pedagogical.}
\end{frame}

\begin{frame}{Training first fits demonstrations, then filters generations}
  \begin{block}{Next-token prediction on the mixed dataset}
    \[\mathcal L_{\mathrm{NTP}}(\theta)
      =\mathbb E_{(x,y)\sim\mathcal D(\pcot)}
      \left[-\sum_{j=1}^{|y|}\log\pi_{\theta,j}(y_j\mid x,y_{<j})\right].\]
  \end{block}
  \begin{enumerate}
    \item Sample outputs from the current model for new inputs.
    \item Verify the final answer ($r_{\mathrm{e2e}}$) or the entire trace ($r_{\mathrm{cot}}$).
    \item STaR refits accepted outputs; experiments also use REINFORCE and GRPO.
  \end{enumerate}
  \papersource{Paper, Sec. 2 and Appendix A, PDF pp. 4, 18--19.}
\end{frame}

\begin{frame}{Pre-training learns a calibrated mixture, not a greedy solver}
  \centering
  \includegraphics[width=0.98\linewidth,height=0.56\textheight,keepaspectratio]{figures/parity-pretrain.pdf}
  \begin{itemize}
    \item Dashed curves: temperature-1 sampling; solid curves: greedy decoding.
    \item At $\pcot=0.25$, sampled accuracy is about $62.5\%$ while greedy accuracy stays near $50\%$.
  \end{itemize}
  \papersource{Paper, Fig. 2, PDF p. 5. Left/center: $d=50$; right: $d=25$; 3 seeds.}
\end{frame}

\begin{frame}{The $1/3$ threshold is a second-token decision}
  \begin{block}{After the first output is $x_1$}
    \[P(\mathrm{continue}\mid y_1=x_1)=\frac{2\pcot}{1+\pcot},\qquad
      P(\EOS\mid y_1=x_1)=\frac{1-\pcot}{1+\pcot}.\]
  \end{block}
  \begin{itemize}
    \item If $\pcot<1/3$, stopping has higher probability: greedy output is $(x_1,\EOS)$.
    \item $x_1$ equals the full parity on only half of random inputs.
    \item The derivation assumes the first-step predictor has not learned a full-parity feature.
  \end{itemize}
  \papersource{Paper, Sec. 4, PDF p. 8; Appendix D.2, PDF p. 60.}
\end{frame}

\begin{frame}{Correctness filtering doubles the long-to-short odds}
  \begin{columns}[T,onlytextwidth]
    \begin{column}{0.48\textwidth}
      \begin{block}{Before filtering}
        Correct long: $p_n$\\[1mm]
        Correct short: $(1-p_n)/2$
      \end{block}
    \end{column}
    \begin{column}{0.48\textwidth}
      \begin{block}{After fitting accepted outputs}
        \[p_{n+1}=\frac{2p_n}{1+p_n},\qquad
        \frac{p_{n+1}}{1-p_{n+1}}=2\frac{p_n}{1-p_n}.\]
      \end{block}
    \end{column}
  \end{columns}
  \vspace{2mm}
  \begin{itemize}
    \item Idealized example: $p_0=0.25\Rightarrow p_1=0.40>1/3$.
    \item More long responses become greedy choices, increasing test-time computation.
  \end{itemize}
  \papersource{Paper, Sec. 3.2 and Sec. 4, PDF pp. 7--9. Example uses the noiseless recurrence.}
\end{frame}

\begin{frame}{Theorem 1 explains the pre-training state}
  \begin{block}{Simplified model: per-position linear autoregressive heads}
    With $\ell_2$-regularized logistic loss and polynomially many SGD iterations:
    \[P(\text{correct long}\mid x)\approx\pcot,\qquad
      P(\text{correct short}\mid x)\approx\frac{1-\pcot}{2}.\]
  \end{block}
  \begin{itemize}
    \item For $\pcot<1/3$, greedy decoding returns $(x_1,\EOS)$ and chance-level parity accuracy.
    \item Local updates are learnable via degree-two features; no direct full-parity feature is supplied.
    \item The guarantee needs sufficient accuracy away from the threshold.
  \end{itemize}
  \papersource{Paper, Theorem 1, PDF p. 8; formal version in Appendix D.3, PDF pp. 73--76.}
\end{frame}

\begin{frame}{Theorem 2 reaches perfect greedy parity via STaR}
  \begin{block}{Conditions and result}
    Start with $\pcot<1/3$, small calibration error, full-trace reward $r_{\mathrm{cot}}$, and sufficient SGD work per round. Then
    \[n^\star=O\!\left(\log\frac{1-\pcot}{\pcot}\right)\]
    STaR rounds suffice for the greedy model to output the entire correct trace.
  \end{block}
  \begin{itemize}
    \item Actual effective weights $q_n$ track the ideal recurrence: $|q_n-p_n|\lesssim 2^n\varepsilon$.
    \item If $\pcot\in\Omega(d^{-\kappa})$, total SGD steps are polynomial in $d$.
  \end{itemize}
  \papersource{Paper, Theorem 2, PDF p. 9; proof in Appendix D.4, PDF pp. 77--81.}
\end{frame}

\begin{frame}{Parity RL rapidly unlocks greedy accuracy}
  \centering
  \includegraphics[width=0.96\linewidth,height=0.61\textheight,keepaspectratio]{figures/parity-accuracy.pdf}
  \begin{itemize}
    \item $d=50,\pcot=0.25$: NTP alone stays around chance even near $10^7$ sequences.
    \item GRPO from sufficiently mature checkpoints quickly approaches full accuracy.
  \end{itemize}
  \papersource{Paper, Fig. 1 right, PDF p. 2; upper panel cropped from author source; median of 3 seeds.}
\end{frame}

\begin{frame}{The parity accuracy jump accompanies longer responses}
  \centering
  \includegraphics[width=0.96\linewidth,height=0.62\textheight,keepaspectratio]{figures/parity-length.pdf}
  \begin{itemize}
    \item Greedy NTP responses remain length 1; successful GRPO runs shift toward length $d=50$.
    \item Starting RL too early can lengthen outputs without reliable generalization.
  \end{itemize}
  \papersource{Paper, Fig. 1 right, PDF p. 2; lower panel cropped from author source.}
\end{frame}

\begin{frame}{The effect depends on checkpoint and reward protocol}
  \begin{tabular}{@{}P{0.27\linewidth}P{0.67\linewidth}@{}}
    \toprule
    Setting & Observation \\
    \midrule
    $\pcot=0.25$, parity & STaR, REINFORCE, and GRPO usually improve; high-temperature STaR with final-answer reward is unstable. \\
    $\pcot=0.05$, parity & At 20k NTP iterations RL is unreliable; at 50k iterations success becomes more likely. \\
    Partial traces & A later checkpoint can benefit from a length penalty; an earlier one may fail. \\
    \bottomrule
  \end{tabular}
  \vspace{3mm}
  \begin{itemize}
    \item Fig. 3 uses 3,200 generated samples per STaR round versus 64 per GRPO/REINFORCE iteration.
  \end{itemize}
  \papersource{Paper, Sec. 3 and Fig. 3, PDF pp. 5--7; Appendix C.1--C.2, PDF pp. 23--30.}
\end{frame}

\begin{frame}{Five-digit multiplication shows a deeper-task analogue}
  \centering
  \includegraphics[width=0.96\linewidth,height=0.61\textheight,keepaspectratio]{figures/multiplication-accuracy.pdf}
  \begin{itemize}
    \item Scratch GPT-2; long examples contain grade-school multiplication traces.
    \item At $\pcot=0.25$, greedy NTP stays near $0\%$; GRPO from useful checkpoints approaches $100\%$.
  \end{itemize}
  \papersource{Paper, Sec. 5.1 and Fig. 5 left, PDF pp. 10--11; top panel cropped from author source.}
\end{frame}

\begin{frame}{The multiplication failure identifies a necessary seed}
  \begin{block}{A limit of reward amplification}
    For $7\times7$ digit multiplication at $\pcot=0.1$, none of the three seeds learned useful long solutions during pre-training, even after the reported 38 GPU hours; subsequent RL did not succeed.
  \end{block}
  \begin{itemize}
    \item The model must generate some valid long outputs for correctness filtering to enrich them.
    \item The training set has 808k unique examples per task, reused over multiple epochs.
    \item Reward for multiplication checks complete agreement of the final number.
  \end{itemize}
  \papersource{Paper, Sec. 5.1, PDF p. 10; Appendix B.2/C.5, PDF pp. 20--21 and 36--39.}
\end{frame}

\begin{frame}{GSM8K: sparse long SFT traces precede rapid GRPO gains}
  \centering
  \includegraphics[width=0.96\linewidth,height=0.61\textheight,keepaspectratio]{figures/gsm8k-accuracy.pdf}
  \begin{itemize}
    \item Llama 3.2 3B base, $\pcot=0.05$: stars are SFT checkpoints; colored lines are GRPO continuations.
    \item Runs rapidly reach the dashed full-CoT SFT baseline, then continue above it.
  \end{itemize}
  \papersource{Paper, Sec. 5.2 and Fig. 5 right, PDF p. 11; top panel cropped from author source.}
\end{frame}

\begin{frame}{GSM8K length grows while answer quality improves}
  \centering
  \includegraphics[width=0.96\linewidth,height=0.61\textheight,keepaspectratio]{figures/gsm8k-length.pdf}
  \begin{itemize}
    \item Early completions are brief and often wrong; later ones resemble long SFT demonstrations.
    \item Later responses can depart from SFT style, suggesting an additional mechanism.
  \end{itemize}
  \papersource{Paper, Fig. 5 right, PDF p. 11; Appendix C.6 examples, PDF pp. 43--46. Lower panel cropped from author source.}
\end{frame}

\begin{frame}{MATH improves too, with stronger attribution concerns}
  \centering
  \includegraphics[width=0.96\linewidth,height=0.60\textheight,keepaspectratio]{figures/math8b-accuracy.pdf}
  \begin{itemize}
    \item Llama 3.1 8B instruct at $\pcot=0.01$: GRPO raises test accuracy from SFT checkpoints.
    \item Some responses depart from SFT traces; the authors suspect prior exposure to MATH-like data.
  \end{itemize}
  \papersource{Paper, Sec. 5.2, PDF pp. 11--12; Appendix Fig. 29, PDF p. 42. Panel cropped from author source.}
\end{frame}

\begin{frame}{Separate the proved mechanism from the empirical analogy}
  \begin{tabular}{@{}P{0.22\linewidth}P{0.72\linewidth}@{}}
    \toprule
    Evidence & Supported conclusion \\
    \midrule
    Formal theory & A linear autoregressive parity learner with full-trace STaR reward crosses the greedy threshold in logarithmically many rounds. \\
    Controlled simulations & Scratch transformers show length-calibrated sampling, poor greedy NTP output, and RL gains under tested configurations. \\
    Llama benchmarks & Similar accuracy/length trajectories occur; late improvements may also use knowledge acquired before SFT. \\
    \bottomrule
  \end{tabular}
  \vspace{3mm}
  \begin{itemize}
    \item In Sec. 5.2 / Appendix B, ``drop CoT with probability $\pcot$'' conflicts with the paper's definition and $\pcot=1$ full-CoT plots.
  \end{itemize}
  \papersource{Paper, Secs. 2--6 and Appendix B, PDF pp. 3--12, 21--22.}
\end{frame}

\begin{frame}{Takeaways for discussion}
  \begin{enumerate}
    \item \textbf{Latent sampled skill:} rare long demonstrations can teach a useful path without making it the greedy choice.
    \item \textbf{Reward-weighted data shift:} correct long outputs become more common in accepted batches, raising both response length and accuracy.
    \item \textbf{Practical dependence:} a mature checkpoint, valid reward signal, and available long solutions matter; extra test-time tokens are part of the tradeoff.
  \end{enumerate}
  \vspace{3mm}
  \begin{block}{Open question}
    How does this mechanism change with noisy, partial, or task-mismatched reasoning traces?
  \end{block}
  \papersource{Paper, Sec. 6 and Appendix C, PDF pp. 12, 23--35.}
\end{frame}

\begin{frame}{Paper and evidence}
  \begin{itemize}
    \item Tsilivis, Malach, Ullrich, Kempe. \emph{How Reinforcement Learning After Next-Token Prediction Facilitates Learning.} arXiv:2510.11495v2.
    \item Full 81-page PDF, including appendices: \href{https://arxiv.org/pdf/2510.11495v2}{arxiv.org/pdf/2510.11495v2}.
    \item Key locators: parity Figs. 1--3 (PDF pp. 2, 5--6); Theorems 1--2 (pp. 8--9); multiplication/GSM8K Fig. 5 (p. 11); MATH appendix (pp. 41--42).
  \end{itemize}
  \vfill
  \centering\Large Questions?
\end{frame}

\end{document}