← All problems
#109 GRPO Surrogate Loss Medium

For each of B prompts, GRPO compares the rewards of G sampled responses. It uses each response's reward relative to the rest of its group as an advantage, rather than learning a separate critic. That advantage is applied to every one of the response's S tokens in a clipped policy objective with a reference-policy KL regularizer.

At position [b, g, s], log_pi, log_pi_old, and log_ref all score the same sampled token y[b,g,s], conditioned on prompt b and the preceding response tokens.

group-normalized advantage → token-level surrogate one prompt b shown; identical for all B prompts rewards [B,G] R[b,0] R[b,1] ⋮ R[b,G-1] group mean / std μ[b] , σ[b] over G A = (R−μ)/(σ+1e-8) advantage [B,G] A[b,0] A[b,1] ⋮ A[b,G-1] ×S same A for all S tokens A A A ⋯ A s = 0 … S−1 log π , log π_old [B,G,S] r = exp(log π − log π_old) clip(r, 1−ε, 1+ε) L_clip = min(r·A, clip(r)·A) log π , log π_ref [B,G,S] d = log π_ref − log π K = eᵈ − d − 1 (k₃) − β · K ℒ = −mean over B·G·S → output[0] blue = tensors passed to solve()

Implementation Requirements

Loss Calculation

For one prompt b, normalize the G response rewards using the group's population mean and standard deviation. Let R denote rewards.

\[ \mu_b = \frac{1}{G}\sum_{g=0}^{G-1} R_{b,g} \] \[ \sigma_b = \sqrt{\frac{1}{G}\sum_{g=0}^{G-1}(R_{b,g}-\mu_b)^2} \] \[ A_{b,g} = \frac{R_{b,g}-\mu_b}{\sigma_b + 10^{-8}} \]

This is an outcome-level GRPO advantage. The same advantage is broadcast to every token of response g:

\[ A_{b,g,s} = A_{b,g} \]

Compare the current policy with the old policy that sampled the response.

\[ r_{b,g,s} = \exp\!\left(\log\pi_{b,g,s} - \log\pi^{\mathrm{old}}_{b,g,s}\right) \]

Clamp that ratio around one, then take the less optimistic of the clipped and unclipped values. Let epsilon denote clip_eps. This min applies correctly to both positive and negative advantages.

\[ \widehat{r}_{b,g,s} = \operatorname{clip}\!\left(r_{b,g,s}, 1-\varepsilon, 1+\varepsilon\right) \] \[ L^{\mathrm{clip}}_{b,g,s} = \min\!\left(r_{b,g,s}A_{b,g,s},\; \widehat{r}_{b,g,s}A_{b,g,s}\right) \]

GRPO also penalizes divergence from the frozen reference policy. Let beta be the KL coefficient. The non-negative k3 sample estimator is:

\[ d_{b,g,s} = \log\pi^{\mathrm{ref}}_{b,g,s} - \log\pi_{b,g,s} \] \[ K_{b,g,s} = \exp(d_{b,g,s}) - d_{b,g,s} - 1 \]

GRPO maximizes the clipped objective minus this penalty. Because this challenge returns a loss for minimization, write the negated mean over all prompts, responses, and tokens to output[0]:

\[ \text{output}[0] = -\frac{1}{BGS}\sum_{b=0}^{B-1}\sum_{g=0}^{G-1}\sum_{s=0}^{S-1} \left(L^{\mathrm{clip}}_{b,g,s} - \beta K_{b,g,s}\right) \]

Examples

For B = 1, G = 2, S = 2, clip_eps = 0.2, and beta = 0.01:

\[ \begin{aligned} \text{rewards} &= \begin{bmatrix} 10.0 & 0.0 \end{bmatrix} \\[6pt] \text{log_pi} &= \begin{bmatrix} 0.1 & 0.2 \\ -0.5 & -0.4 \end{bmatrix} \\[6pt] \text{log_pi_old} &= \begin{bmatrix} 0.0 & 0.0 \\ 0.0 & 0.0 \end{bmatrix} \\[6pt] \text{log_ref} &= \begin{bmatrix} 0.0 & 0.0 \\ 0.0 & 0.0 \end{bmatrix} \end{aligned} \] \[ \text{output}[0] \approx -0.17563 \]

Constraints

Reference

DeepSeekMath: Pushing the Limits of Mathematical Reasoning in Open Language Models (GRPO), Shao et al. (2024)

Guided walkthrough coming soon. Below is the official starter signature in each language; the clickable line-by-line explanation hasn't been authored yet.
Problem text & starters from the official AlphaGPU/leetgpu-challenges. Solve it on leetgpu.com.