Blame for code/notes/src/0106-dapo-pathologies.tex

\documentclass[11pt]{article}
\usepackage{common}
\begin{document}
\notehead{0106}{DAPO: clip-higher, dynamic sampling, token-level loss, overlong shaping}{Policy-optimisation lineage, batch M1. Companion notebook: \texttt{notebooks/0106-dapo-pathologies.ipynb}.}

\begin{problem}
\question{What exactly goes wrong when GRPO is trained on long chains of thought, and which mechanism produces each failure?}
DAPO (arXiv:2503.14476) starts from GRPO (0105) and lists four things that went wrong when training a long-chain-of-thought model: the policy's entropy collapsed, many prompts produced no learning signal, long responses were under-weighted per token, and truncated responses were punished regardless of whether their reasoning was sound. Each of its techniques is a patch for exactly one of these. This note states the pathology, derives \emph{why} the mechanism produces it, derives the patch, and says honestly what the exact toy computations confirm and what rests on DAPO's empirical evidence alone.
\end{problem}

\section{Notation}
\begin{center}\small\begin{tabular}{@{}ll@{}}\toprule
symbol & meaning\\\midrule
$\epsilon_{\rm lo}=0.2,\ \epsilon_{\rm hi}=0.28$ & decoupled clip half-widths (DAPO Sec.~4.1)\\
$G=16$, $k$ & group size, number of correct responses in a group\\
$\rho=\E_q[1-p_q^G-(1-p_q)^G]$ & fraction of groups that are \emph{live} ($0<k<G$)\\
$L_{\max}=16384,\ L_{\rm cache}=4096$ & expected max length and soft-punishment interval\\
$H(\pi)$, $z$ & entropy of a next-token distribution; its logits\\
$\tilde A_i,\hat A_i$ & centred / std-normalised group advantage (0105)\\\bottomrule\end{tabular}\end{center}
The full DAPO objective is (Eqs.~8--12)
\begin{equation}\mathcal J_{\rm DAPO}=\E\Big[\frac1{\sum_i|o_i|}\sum_{i=1}^G\sum_{t=1}^{|o_i|}\min\big(r_{i,t}\hat A_i,\ \clip(r_{i,t},1-\epsilon_{\rm lo},1+\epsilon_{\rm hi})\hat A_i\big)\Big]\quad\text{s.t. }0<k<G,\label{eq:dapo}\end{equation}
with no KL term (Sec.~2.3; see 0109) and rule-based reward $R\in\{+1,-1\}$ (Eq.~7).

\section{Derivation}
\subsection{Clip-Higher against entropy collapse}
\paragraph{Pathology (DAPO Fig.~2b, Sec.~3.1):} policy entropy falls fast under naive PPO/GRPO, samples within a group become nearly identical, exploration stops.

\paragraph{Step 1: how entropy moves.} For a softmax $\pi=\mathrm{softmax}(z)$, $\partial H/\partial z_b=-\pi_b(\log\pi_b+H)$ (derivation: $\partial\pi_a/\partial z_b=\pi_a(\delta_{ab}-\pi_b)$ and $\sum_a\pi_a(\log\pi_a+1)=1-H$). For a logit change $\Delta z$, using $-H=\E_\pi\log\pi$,
\begin{equation}\Delta H=-\sum_b\pi_b(\log\pi_b-\E_\pi\log\pi)\Delta z_b=-\Cov_{a\sim\pi}\big(\log\pi_a,\ \Delta z_a\big)\quad(\text{first order}).\label{eq:entcov}\end{equation}
For tabular policy gradient $\Delta z_a=\eta\,\pi_aA_a$ (since $\partial J/\partial z_a=\pi_aA_a$), and for natural policy gradient $\Delta z_a=\eta A_a$; this is the covariance mechanism of Cui et al.\ (arXiv:2505.22617 Secs.~3.1--3.2). A high-probability action with $A>0$ ($\log\pi_a>\E\log\pi$, $\Delta z_a>0$) makes the covariance positive and \emph{lowers} entropy; a rare action with $A>0$ makes it negative and \emph{raises} entropy.
\ver{finite-difference $\Delta H$ equals $-\Cov(\log\pi,\Delta z)$ to $6.7\times10^{-9}$ (relative; PG and NPG, six random policies); at $\pi=(.90,.05,.03,.02)$: good action dominant gives $\mathrm d H/\mathrm d\eta=-0.0357$, good action rare gives $+0.0064$.}

\paragraph{Step 2: what the symmetric clip does to the rare tokens.} For $A>0$, $f=A\min(r,1+\epsilon)$ (0104 Eq.~(3)), so the \emph{direct} incentive to raise a token's probability $p=\pi_{\rm old}$ vanishes at $\pi_\theta=(1+\epsilon)p$: the absolute headroom is $\epsilon p$. For $\epsilon=0.2$ a token with $p=0.01$ can only be pushed to $0.012$, one with $p=0.9$ to $\min(1,1.08)=1$ (DAPO's own example). In log space the allowed move is the same ($\log1.2=0.182$) for all tokens, but in probability it is proportional to $p$: rare ``exploration'' tokens get headroom $\sim p\epsilon$ per rollout, dominant ones saturate at $1$.
\ver{cap table: $p=0.001\to0.0012$, $0.01\to0.0120$ ($\epsilon=.2$) / $0.0128$ ($\epsilon=.28$), $0.5\to0.60/0.64$, $0.9\to1.0$.}

\paragraph{Step 3: the patch.} Decouple the bounds (Eq.~10): keep $\epsilon_{\rm lo}=0.2$, raise $\epsilon_{\rm hi}$ to $0.28$ ($\log1.28=0.247$ vs $0.182$): the headroom of a rare token grows by $0.28/0.2=1.4\times$. $\epsilon_{\rm lo}$ is left alone: for tabular softmax $\partial J/\partial z_a\propto\pi_a$, so a token pushed towards probability $\approx0$ receives almost no gradient and is essentially never sampled again; a large $\epsilon_{\rm lo}$ would allow that (DAPO: ``increasing it will suppress the probability of these tokens to 0, resulting in the collapse of the sampling space'').
\ver{asymmetric-clip gradient equals $Ar\cdot\mathbb 1[\text{live}]$ with $\epsilon_{\rm lo}=.2,\epsilon_{\rm hi}=.28$ on 1600 points to $8.9\times10^{-16}$.}

\paragraph{What the exact toy shows (and does not).} On a two-action bandit with a rare rewarded action ($\pi=0.01$), exact-expectation inner ascent (400 steps per rollout iteration) needs $8$ rollout iterations to reach $\pi=0.5$ with $\epsilon_{\rm hi}=0.2$, $7$ with $0.28$, and $2$ with no upper clip: the upper clip is a strong brake, but widening it from $0.2$ to $0.28$ gains one iteration ($\approx12\%$). The first-iteration growth is $1.251$ ($\epsilon=.2$) and $1.342$ ($.28$), \emph{above} $1+\epsilon$: the clip removes only the direct push on the rare token; the unclipped, negative-advantage common action keeps moving probability mass through the softmax normalisation until \emph{its own} lower clip binds. The size of DAPO's entropy effect (Fig.~2, and $+2$ AIME points, $36\to38$, in Table~1) therefore comes from function approximation and finite samples, not from this tabular model, and is taken from their experiments, not re-derived here.

\subsection{Dynamic sampling against zero-gradient groups}
\paragraph{Pathology (Sec.~3.2, Fig.~3b):} if all $G$ responses are correct (or all wrong) then $\hat A_i\equiv0$ (0105) and the group contributes nothing; as accuracy rises the share of such groups grows.
\paragraph{Step 1: how many.} With success probability $p$, $P(\text{dead})=p^G+(1-p)^G$. For $G=16$: $p=0.9\to0.185$, $0.95\to0.44$, $0.99\to0.85$, and $p=0.02\to0.72$. Over a prompt distribution $p\sim\mathrm{Beta}(a,b)$ the live fraction is
$\rho=1-\frac{B(a+G,b)}{B(a,b)}-\frac{B(a,b+G)}{B(a,b)}$; for $\mathrm{Beta}(2,8)$, $G=16$: $\rho=0.88$.
\ver{MC dead-fraction vs.\ $p^G+(1-p)^G$ within $\le2.1$ s.e.\ in four $(G,p)$ settings; closed-form $\rho$ vs.\ 400-point Gauss--Legendre quadrature to $2.7\times10^{-14}$ for three Beta priors.}
\paragraph{Step 2: why it hurts.} With a batch of $B$ prompts and a normaliser that counts every token (Eq.~\eqref{eq:dapo}), dead groups add $0$ to the numerator but their tokens stay in the denominator: the expected update is multiplied by $\rho$, and only $m=\rho B$ prompts carry signal, whose noise grows as $\sqrt m$ against a signal $\propto m$, so the signal-to-noise ratio scales as $\sqrt{m}$.
\paragraph{Step 3: the patch is unbiased.} Keep sampling prompts, discarding dead groups, until $B$ live groups exist. A dead group has $g=0$, hence $\E[g\,\mathbb 1_{\rm live}]=\E[g]$ and $\E[g\mid{\rm live}]=\E[g]/P(\text{live}\mid q)$; since prompt $q$ is accepted with probability $\propto P(\text{live}\mid q)$ the factors cancel: the summed expected gradient equals the unfiltered one (up to the global factor $1/\rho$ from dividing by $B$ accepted rather than $\rho B$ live groups). So dynamic sampling restores the magnitude and the $\sqrt B$ signal-to-noise without re-weighting prompts. Cost: $B/\rho$ prompts per batch.
\ver{exact (25-point discretised $\mathrm{Beta}(2,8)$ prompt law, $G=16$, conditional mean computed directly from the binomial restricted to $0<k<G$): $\E[g\mid\text{accepted group}]=\E[g]/\rho$ to $<10^{-15}$; MC: prompts drawn to collect $64$ live groups $=m/\rho$ ($z=0.55$) for $\mathrm{Beta}(2,8)$, $G=16$ ($1/\rho=1.14$).}

\subsection{Token-level loss against length under-weighting}
\paragraph{Pathology (Sec.~3.3, Fig.~4):} sample-level averaging gives a token of $o_i$ the weight $\hat A_i/(G|o_i|)$, so tokens of long responses count less; long high-quality traces are learned slowly and long low-quality ones (gibberish, repetition) are penalised too weakly, so entropy and length drift upwards.
\paragraph{Derivation.} By 0105 Eq.~(3), the sample-level mean ascends $\E[(R-b)/|o|]$, a different objective whose weight on a token is $\propto1/|o|$. DAPO's fix divides by the total token count $D=\sum_i|o_i|$: every token has weight $\hat A_i/D$ \emph{regardless of the response it sits in}, so a pattern that raises or lowers reward is promoted or suppressed equally in short and long responses (Sec.~3.3).
\paragraph{Remaining bias.} $D$ is random, so $\E[N/D]\ne\E[N]/\E[D]$. The delta method gives a bias of relative order $\mathrm{CV}(D)^2\sim1/n$ in the number $n$ of responses in the denominator. A \emph{constant} denominator (Dr.\ GRPO) removes it exactly.
\ver{exhaustive enumeration with centred advantages: constant denominator gives exactly $(1-\frac1G)\nabla J/\bar L$ to $4.2\times10^{-17}$; the global-token-mean estimator deviates by $15.9\%$ ($G{=}2$) and $10.0\%$ ($G{=}3$) in relative norm, cosine to $\nabla J$ $0.9959$ and $0.9978$; with $n=512\times16$ responses in a DAPO batch the relative order $1/n$ makes this negligible.}

\subsection{Overlong reward shaping against truncation noise}
\paragraph{Pathology (Sec.~3.4, Fig.~5):} a response cut at $L_{\max}$ usually has no extractable answer and receives the failure reward, although the reasoning may be sound; the penalty is noise correlated with length rather than quality.
\paragraph{Two patches, two meanings.}
(i) \emph{Overlong filtering} masks the loss of truncated samples $\mathcal T$. Then the gradient is $\E[\mathbb 1_{\mathcal T^c}(R-b)\,s]$. Define $R'=R$ off $\mathcal T$ and $R'=b$ on $\mathcal T$; then $\E[(R'-b)s]$ is the same vector: masking is \emph{identical to giving truncated samples a reward equal to the baseline} (zero advantage). It removes the penalty but also removes any pressure against length. ``Neutral'' is relative to the baseline, not to the alternatives: for $b>0$ a truncated sample is worth $b$, more than a wrong short answer (reward $0$, advantage $-b$), so the pressure \emph{between} those two kinds of failure is reversed.
\ver{identical to $0$ on the toy (truncated = hit the length limit without EOS).}
(ii) \emph{Soft overlong punishment} (Eq.~13) adds a length reward to the correctness reward:
\begin{equation}R_{\rm len}(y)=\begin{cases}0&|y|\le L_{\max}-L_{\rm cache}\\ \dfrac{(L_{\max}-L_{\rm cache})-|y|}{L_{\rm cache}}&L_{\max}-L_{\rm cache}<|y|\le L_{\max}\\ -1&|y|>L_{\max}.\end{cases}\label{eq:rlen}\end{equation}
It is continuous ($0$ at $L_{\max}-L_{\rm cache}$, $-1$ at $L_{\max}$) with slope exactly $1/L_{\rm cache}$, so the $-1$ cliff of a hard truncation penalty is spread over $4096$ tokens. Because $R_{\rm len}$ is a function of the sampled response, adding it is just a different reward: the policy gradient (0102) of $\E[R+R_{\rm len}]$ is the sum of the two separate gradients, with no new bias.
\ver{ramp values and slope exact; policy gradient of $\E[R+R_{\rm len}]$ equals the baselined estimator to $2.8\times10^{-17}$.}

\paragraph{DAPO's own ablation} (Table~1, AIME~24 avg@32, cumulative, as reported by the authors, not reproduced here): naive GRPO $30$; $+$overlong filtering $36$; $+$clip-higher $38$; $+$soft overlong punishment $41$; $+$token-level loss $42$; $+$dynamic sampling $50$.

\section{Boxed result}
\begin{result}
\begin{align*}
&\mathcal J_{\rm DAPO}=\tfrac1{\sum_i|o_i|}\textstyle\sum_{i,t}\min(r\hat A_i,\clip(r,1{-}\epsilon_{\rm lo},1{+}\epsilon_{\rm hi})\hat A_i)\ \text{ s.t. }0<k<G\\
&R=R_{\rm correct}+R_{\rm len}\\
&\Delta H=-\Cov_{a\sim\pi}(\log\pi_a,\Delta z_a)\\
&\text{direct up-push on an }A{>}0\text{ token vanishes at }\min\big(1,(1{+}\epsilon_{\rm hi})\,p\big)\ \ (\text{a soft cap})\\
&P(\text{dead})=p^G+(1-p)^G\\
&\rho=1-\tfrac{B(a+G,b)}{B(a,b)}-\tfrac{B(a,b+G)}{B(a,b)},\qquad\text{cost of a full batch: }B/\rho\\
&\text{masking truncated samples}\equiv\text{reward }b\text{ for them};\qquad R_{\rm len}\text{ continuous, slope }1/L_{\rm cache}
\end{align*}
\end{result}

\section{What breaks}
\begin{breaks}\small\begin{itemize}
\item \textbf{Clip-higher is a headroom argument, not a guarantee.} The cap applies only to the direct term (leak shown above); a larger $\epsilon_{\rm hi}$ allows larger per-token ratios, hence heavier IS-weight tails (0103) and, for $A<0$ tokens with $r>1+\epsilon_{\rm hi}$, unbounded gradient weight (0104, 0107). \emph{Violated:} PPO ratios stay near 1.
\item \textbf{Dynamic sampling} needs $\rho$ not too small (hard datasets: cost $1/\rho$), filters on accuracy only (shaping can make an all-correct group informative about length, yet it is still dropped), and changes the \emph{batch} composition. DAPO claims wall-clock is not dominated by this because generation time is dominated by long-tail samples (Sec.~3.2); that is a systems claim not tested here.
\item \textbf{Token-level mean} has $O(1/n)$ ratio bias, and gives long (possibly degenerate) responses proportionally more gradient mass; it does not by itself prevent length growth.
\item \textbf{Overlong shaping adds an objective.} The relative scale of $R_{\rm len}$ and $R_{\rm correct}\in\{\pm1\}$ decides the trade-off; masking instead gives zero pressure against length.
\item \textbf{No KL.} DAPO removes the KL term because the policy is allowed to move far from the initial model with a rule-based verifier (0109).
\end{itemize}\end{breaks}

\nextnote{DAPO still zeroes out gradients of tokens beyond the clip (rare, high-ratio tokens when $A>0$). Note 0107 derives CISPO, which keeps every token by clipping the \emph{importance weight} instead of the update, and tabulates which tokens PPO/GRPO silence and CISPO retains.}

\section*{References}
{\small\begin{itemize}[leftmargin=1.2em]
\item Yu et al., \emph{DAPO}, arXiv:2503.14476: Sec.~2.3 (no KL), 2.4 Eq.~7 (rule reward), Sec.~3 Eqs.~8--13, Sec.~3.1 (Clip-Higher; Figs.~2--3; the $0.01\to0.012$, $0.9\to1.08$ example), 3.2 (Dynamic Sampling, Fig.~3b, Fig.~6), 3.3 (Token-level loss, Fig.~4), 3.4 (Overlong shaping, Eq.~13, Fig.~5), 4.1 (hyper-parameters $\epsilon_{\rm lo}=0.2,\epsilon_{\rm hi}=0.28$, $L_{\max}=16384$, $L_{\rm cache}=4096$), Table~1.
\item Cui et al., \emph{The Entropy Mechanism of RL for Reasoning Language Models}, arXiv:2505.22617, Secs.~3.1--3.2 (entropy change $=-\mathrm{Cov}$).
\item Liu et al., arXiv:2503.20783, Sec.~3.1 (length bias) and Listing~1.
\item Derivations of Eq.~\eqref{eq:entcov}, $\rho$, the dynamic-sampling unbiasedness argument and the masking$\equiv$baseline-reward identity are mine (verified in the notebook where marked).
\end{itemize}}
\end{document}