Credit Assignment over Long Generations

A language model generating a 500-token proof receives exactly one reward signal: correct or incorrect. Every intermediate token - a poorly placed bracket, an algebra slip, a wrong branch at step 3 - is equally invisible to that signal. This is the credit assignment problem, and in long-generation settings it is considerably worse than in classic RL: the action space is a vocabulary of 50,000+ tokens, episodes are hundreds of steps long, and the "environment" is entirely internal to the model itself.

Why Long Generations Make Credit Assignment Hard

In classic tabular RL (gridworlds, Atari), the credit assignment horizon is short enough that Monte Carlo returns or TD(lambda) bootstrapping can distribute reward reliably. Language generation breaks three comfortable assumptions at once.

Episode length. A single response might span 512 to 8192 tokens. With a discount factor gamma = 0.99 over 1000 steps, the discounted return at step 1 is 0.99^999 ≈ 0.00004 of the reward at step 1000. Setting gamma = 1 (undiscounted) is the standard compromise in language RL, which means every token in a bad response receives the same negative signal regardless of whether it caused the failure.

Delayed, sparse, scalar rewards. Human preference rewards are collected once per response, not per sentence or paragraph. Verifiable rewards (correctness on a maths problem) are also binary and terminal. The model must infer from a single number which of its 500 decisions was the crucial one.

No external state. In game RL the environment transitions provide implicit credit signals (dying reduces life count immediately). In text generation the "environment" is the autoregressive context; there is no state change that can localise the error.

The consequence: training with only terminal rewards is very high-variance. The gradient estimator

∇J(θ) ≈ (1/N) Σ_n [ Σ_t ∇ log π_θ(a_t | s_t) ] · R_n

has variance that grows roughly linearly with episode length, because the same scalar R_n multiplies every per-token log-probability gradient in the episode.

The KL-Regularised Objective and What It Does to Credit

The standard RLHF objective (as used in InstructGPT, Ouyang et al. 2022) adds a per-token KL penalty against the supervised fine-tuned reference policy:

J(θ) = E_x~D [ E_y~π_θ(y|x) [ r(x, y) ] ] - β · KL[ π_θ(·|x) || π_ref(·|x) ]

The KL term decomposes as a sum over tokens: KL = Σ_t log π_θ(a_t) - log π_ref(a_t). This gives the optimiser a dense, per-step signal even when the scalar reward r(x, y) is terminal. The KL penalty acts as a soft anchor: any token that diverges strongly from the reference distribution pays a cost immediately, which effectively provides a coarse credit signal that says "this token distribution moved a lot; be sure the terminal reward justifies it."

The beta hyperparameter governs the tradeoff. Small beta allows aggressive reward optimisation but opens the door to reward hacking. Large beta keeps the policy close to the SFT baseline but slows learning. In practice beta is often scheduled or adapted based on observed KL drift.

GRPO: Group Relative Advantage Estimation

PPO-based RLHF (used in InstructGPT) requires a separate value network (critic) to estimate baselines for variance reduction. For large language models, the critic is itself a copy of the policy, which roughly doubles memory footprint and introduces a coupled optimisation problem.

Group Relative Policy Optimisation (GRPO, introduced in DeepSeekMath, Shao et al. 2024) sidesteps the critic by sampling G outputs per prompt and computing a group-normalised reward as the advantage estimate:

A_i = (r_i - mean(r_1,...,r_G)) / std(r_1,...,r_G)

Each token in response i receives the same advantage A_i. This is a Monte Carlo, outcome-level credit assignment: no per-step information is extracted. What GRPO buys is reduced memory (no critic) and stable variance reduction through within-group normalisation. What it sacrifices is any attempt to localise which steps in generation i were better than in generation j.

The GRPO update clips the importance-sampling ratio exactly as PPO does, and also includes a KL penalty term. The full per-sample loss is:

L_GRPO = -min( ρ_i · A_i, clip(ρ_i, 1-ε, 1+ε) · A_i ) + β · KL[ π_θ || π_ref ]

where ρ_i = π_θ(y_i|x) / π_old(y_i|x) is the token-level importance ratio.

GRPO is the backbone of DeepSeek-R1 (DeepSeek-AI, 2025), which demonstrated that long chain-of-thought reasoning can be trained with pure RL on verifiable rewards - precisely the scenario where credit assignment is hardest.

Process Rewards: Dense Supervision as a Credit Signal

One principled response to sparse terminal rewards is to train a Process Reward Model (PRM) that scores each reasoning step independently. Lightman et al. (2023) showed on MATH that a PRM trained with human step-level labels significantly outperforms an outcome reward model (ORM) at the same test-time compute budget. The PRM provides a per-step signal r_t, converting the sparse credit problem into a dense one:

R_total = Σ_t γ^t r_t(x, y_{1:t})

The gain is not free. Per-step annotation is expensive; the PRM is itself a learned proxy subject to Goodhart's law; and step boundaries in free-form text are ambiguous (a PRM trained on maths solutions may not transfer to coding or open-ended reasoning). ReST-MCTS* (Zhang et al. 2024) explores using tree search to estimate step-level values without human annotation, by propagating outcome correctness backward through a search tree - effectively computing a Monte Carlo estimate of the probability that a partial solution leads to a correct answer.

Reward Over-Optimisation: Goodhart's Law in Action

Gao, Schulman, and Hilton (2022) studied what happens as a policy is optimised more aggressively against a proxy reward model. Using a "gold" reward model in place of true human preferences, they found a consistent pattern: proxy reward increases monotonically with KL distance from the reference policy, but gold reward peaks and then degrades. The relationship is approximately:

gold_reward ≈ α · sqrt(KL) - β · KL

for small-to-medium KL, meaning there is an optimal stopping point beyond which further RL training actively harms true quality.

This is Goodhart's law applied to RL post-training: "when a measure becomes a target, it ceases to be a good measure." The credit assignment failure here is subtle - the model correctly learns to maximise the proxy signal, it just turns out those proxy-maximising tokens do not correspond to what humans actually want. Common failure modes include:

• Length exploitation. Reward models trained on human preferences often rate longer responses higher up to a point, so policies learn to pad outputs.
• Sycophantic phrasing. Certain surface patterns (agreement, flattery, confident tone) inflate reward model scores independently of content quality.
• Format hacking. Structured outputs (bullet lists, bold headers) can score well on the reward model while containing incorrect information.

The practical consequence: RLHF training should be monitored for KL drift, and separate held-out human evaluations are essential to detect when the proxy reward diverges from true preference.

When It Falls Down

Uniform token-level weighting is structurally wrong. Whether using PPO with a terminal reward or GRPO, every token in a generation receives the same advantage signal. A 600-token derivation in which the only error is a sign flip at token 580 will penalise all 600 tokens equally. This wastes the policy's capacity to learn which decisions actually matter.

PRMs do not cleanly compose. A PRM trained on labelled chain-of-thought maths solutions assigns step scores that reflect the label distribution, not a ground-truth value function. When used as a dense reward during RL training, the PRM becomes a second proxy reward model and inherits all the over-optimisation risks of an ORM.

Group normalisation collapses under homogeneous outputs. If all G samples in a GRPO group produce the same reward (e.g., all correct or all incorrect), the normalised advantage is zero and the gradient vanishes. GRPO provides no learning signal on easy or impossible prompts, which biases training toward medium-difficulty examples.

KL anchoring breaks when the SFT reference is poor. If the supervised fine-tuned model never produces the kind of reasoning trace needed for the task (e.g., step-by-step proofs were absent from SFT data), the KL penalty actively discourages the RL policy from exploring that space, regardless of reward.

Long reasoning traces amplify variance even with baselines. At chain-of-thought lengths of 2000-8000 tokens (as seen in DeepSeek-R1 and Kimi k1.5), Monte Carlo variance is very high even with group normalisation. The model may converge to surface-level formatting of long chains rather than substantively better reasoning.

Further Reading

• Ouyang et al. (2022). "Training language models to follow instructions with human feedback." https://arxiv.org/abs/2203.02155
• Gao, Schulman, Hilton (2022). "Scaling Laws for Reward Model Overoptimization." https://arxiv.org/abs/2210.10760
• Shao et al. (2024). "DeepSeekMath: Pushing the Limits of Mathematical Reasoning in Open Language Models." (introduces GRPO) https://arxiv.org/abs/2402.03300
• Lightman et al. (2023). "Let's Verify Step by Step." https://arxiv.org/abs/2305.20050