← Back home

How Deepseek R1 works.

Details on Deepseek R1 working under the hood

Original paper link

Introduction

LLMs scaled to a sufficient size can exhibit reasoning abilities. However, achieving these capabilites in training demands a lot of computation. Another results we have is that LLMs can be effectively augmented using Chain of thought (COT), this involves carefully designed few shot prompts or prompts such as “think step by step”, enables models to product intermediate reasoning steps, there by solving complex tasks. But … Despited their effectiveness, these techniques have their limitations which is dependence on human. Furthermore, by constraining LLMs to replicate human thought process, we are constraining them by human-provided exemplars, thereby preventing them from exploration of non-human superior reasoning pathways.

To tackle this, Deepseek uses GRPO

Reinforcement Learning for LLMs: REINFORCE

Setup

In simple reinforcement learning, our setup looks something like:

        ┌──────────────────┐
   ┌───>│   Agent (LLM)    │──────┐     State (S_t)  {input so far}
   │    └──────────────────┘      │     Action (A_t) {next token}
Reward (r_t)                      │
   │    ┌──────────────────┐      │
   └────│   Env (tokens)   │<─────┘
        └──────────────────┘

Policy: πθ(at∣st)\pi_\theta(a_t \mid s_t) → {probability of next token}

So, in this setup, our LLM learns from the reward function and performs accordingly so that reward is maximized.

Objective

max⁡θJ(θ)=Eτ∼πθ[R(τ)]\max_{\theta} J(\theta) = \mathbb{E}_{\tau \sim \pi_\theta}\left[R(\tau)\right]

**Policy is used to produce a probability distructions over all actions/tokens

Deriving the Policy Gradient

J(θ)=E[R(τ)]J(\theta) = \mathbb{E}[R(\tau)]

∇θJ(θ)=∇θ E[R(τ)]\nabla_\theta J(\theta) = \nabla_\theta \, \mathbb{E}[R(\tau)]

∇θJ(θ)=∇θ∫πθ⋅R(τ) dτ\nabla_\theta J(\theta) = \nabla_\theta \int \pi_\theta \cdot R(\tau) \, d\tau

⇒∇θJ(θ)=∫∇θπθ R(τ) dτ\Rightarrow \nabla_\theta J(\theta) = \int \nabla_\theta \pi_\theta \, R(\tau) \, d\tau

Using the log-derivative trick:

∇θlog⁡πθ=∇θπθπθ  ⇒  ∇θπθ=πθ ∇θlog⁡πθ\nabla_\theta \log \pi_\theta = \frac{\nabla_\theta \pi_\theta}{\pi_\theta} \;\Rightarrow\; \nabla_\theta \pi_\theta = \pi_\theta \, \nabla_\theta \log \pi_\theta

⇒∇θJ(θ)=∫πθ ∇θlog⁡πθ R(τ) dτ\Rightarrow \nabla_\theta J(\theta) = \int \pi_\theta \, \nabla_\theta \log \pi_\theta \, R(\tau) \, d\tau

⇒∇θJ(θ)=E[(∇θlog⁡πθ) R(τ)]\Rightarrow \nabla_\theta J(\theta) = \mathbb{E}\left[(\nabla_\theta \log \pi_\theta) \, R(\tau)\right]

Here ∇θJ(θ)\nabla_\theta J(\theta) is the gradient.

Update the parameter as:

θ←θ+α⋅∇θJ(θ)\theta \leftarrow \theta + \alpha \cdot \nabla_\theta J(\theta)

This is the standard REINFORCE algorithm.

General Case vs. LLMs

In general case it is:

Eτ∼πθ[⋅]\mathbb{E}_{\tau \sim \pi_\theta}[\cdot]

(where πθ\pi_\theta is the policy and τ\tau is the trajectory)

In case of LLMs, it converts as:

Ex∼D[Ey∼πθ(⋅∣x)[⋅]]\mathbb{E}_{x \sim D}\left[\mathbb{E}_{y \sim \pi_\theta(\cdot \mid x)}[\cdot]\right]

Vanilla Monte-Carlo REINFORCE Algorithm

  1. Given a prompt, sample a response y∼πθ(⋅∣x)y \sim \pi_\theta(\cdot \mid x) ← Expensive step
  2. Evaluate completed response: R=R(x,y)R = R(x, y)
  3. Compute log probability gradient: g=R ∇θlog⁡πθ(y∣x)g = R \, \nabla_\theta \log \pi_\theta(y \mid x)
  4. Update parameter as: θ←θ+α⋅g\theta \leftarrow \theta + \alpha \cdot g

Challenges with this approach

  1. Gradients are noisy.
  2. No explicit token-level credit. A correct answer doesn’t mean that all tokens were equally good.
  3. No constraints on policy updation. The final answer can deviate a lot!

Proximal Policy Optimization (PPO)

Original paper link

GRPO is the RL framework for Deepseek. It was originally proposed to simplify the training process and reduce the resource consumption of PPO

The proposed solution

The proposed solution for the challenges mentioned above is PPO.

PPO:  J(θ)=Maximize advantages⏟  +  Don’t deviate too much from before⏟Proximal part\text{PPO}: \; J(\theta) = \underbrace{\text{Maximize advantages}}_{} \;+\; \underbrace{\text{Don't deviate too much from before}}_{\text{Proximal part}}

For a probability distribution given by the policy, we don’t have a target distribution to compare it. PPO finds a so-called “scaling factor” for these distributions denoted by AtA_t.

at∼πθ(st){sample action from probability}a_t \sim \pi_\theta(s_t) \quad \{\text{sample action from probability}\}

P(at)=πθ(at∣st)P(a_t) = \pi_\theta(a_t \mid s_t)

We want to scale up this probability by AtA_t.

Update: ∇θ πθ(at∣st)⋅At\nabla_\theta \, \pi_\theta(a_t \mid s_t) \cdot A_t

Loss=πθ(at∣st)⋅At\text{Loss} = \pi_\theta(a_t \mid s_t) \cdot A_t

Total loss=∑t=0Tπθ(at∣st)⋅At\text{Total loss} = \sum_{t=0}^{T} \pi_\theta(a_t \mid s_t) \cdot A_t

Mathematically convenient to add a log:

Total loss=∑t=0Tlog⁡πθ(at∣st)⋅At\text{Total loss} = \sum_{t=0}^{T} \log \pi_\theta(a_t \mid s_t) \cdot A_t

Advantage AtA_t and the Value function

PPO defines AtA_t as “How much better than the average was the action we took?”

→ To answer this, we introduce a Value function VϕV_\phi. VϕV_\phi is another model used by the agent, separate from the LLM, with its own weights ϕ\phi.

Agent:  (S_0) --A_0,a_0--> (S_1) --A_1,a_1--> ... --A_{T-1},a_{T-1}--> (S_{T-1}) --A_T,a_T--> (S_T)      Env
         V_φ(S_0)          V_φ(S_1)                                      V_φ(S_{T-1})            V_φ(S_T)

VϕV_\phi → tells how good the response so far is regardless of what we predict next.

V(St)=Eτ∼π[rt+rt+1+⋯+rT∣St]{Expectation of future rewards}V(S_t) = \mathbb{E}_{\tau \sim \pi}\left[r_t + r_{t+1} + \dots + r_T \mid S_t\right] \quad \{\text{Expectation of future rewards}\}

Computing this is impossible as it would result in a ridiculously large tree. So, instead of calculating, our model uses agent VϕV_\phi to estimate it.

We can also add a discount factor:

V(St)=Eτ∼π[rt+γrt+1+⋯+γT−trT∣St],γ∈[0,1]V(S_t) = \mathbb{E}_{\tau \sim \pi}\left[r_t + \gamma r_{t+1} + \dots + \gamma^{T-t} r_T \mid S_t\right], \qquad \gamma \in [0, 1]

V(St)=Eτ∼π[Gt∣St](Gt=total discounted return)V(S_t) = \mathbb{E}_{\tau \sim \pi}\left[G_t \mid S_t\right] \quad (G_t = \text{total discounted return})

Training the Value function

To train our model VϕV_\phi to converge to the ideal value GtG_t, we use gradient descent:

LtVF=(Vϕ(St)−Gt)2(the loss function)L_t^{VF} = \left(V_\phi(S_t) - G_t\right)^2 \quad \text{(the loss function)}

Now, to compute the quality of action that we took, let’s denote the quality of action =Q(st,at)= Q(s_t, a_t).

At=Q(st,at)−V(St)A_t = Q(s_t, a_t) - V(S_t)

Q(st,at)=rt+γrt+1+⋯+γT−trTQ(s_t, a_t) = r_t + \gamma r_{t+1} + \dots + \gamma^{T-t} r_T

Defining QQ this way is the Monte-Carlo approach.

This has downsides →

  1. We need to wait for the complete action to unfold.
  2. This value will be trivial when we don’t have intermediate rewards.

Instead we can do,

Q(st,at)=rt+γ[rt+1+γrt+2+⋯+γT−2rT]Q(s_t, a_t) = r_t + \gamma\left[r_{t+1} + \gamma r_{t+2} + \dots + \gamma^{T-2} r_T\right]

Q^(st,at)=rt+γVϕ(st+1)←this is bootstrapping\hat{Q}(s_t, a_t) = r_t + \gamma V_\phi(s_{t+1}) \quad \leftarrow \text{this is bootstrapping}

So,

A^t=rt+γVϕ(st+1)−Vϕ(st)\hat{A}_t = r_t + \gamma V_\phi(s_{t+1}) - V_\phi(s_t)

In practice

In practice, things are let’s say different!

In theory, we define expectation over a very large sample size. But in practice, our sample size is not that large. Also sometimes we deal with noisy environments, rewards also comes from humans so we can’t expect them to be correct. This problem is Variance → can be fixed by giving less importance to rewards but that leads to a very conservative model that can’t discover the optimal solution. This over correction is called bias. And all this is called the Bias-Variance tradeoff.

Q(st,at)=rt+γrt+1+⋯+γT−1rT(high variance, low bias)Q(s_t, a_t) = r_t + \gamma r_{t+1} + \dots + \gamma^{T-1} r_T \quad \text{(high variance, low bias)}

Q^(st,at)=rt+γVϕ(st+1)(low variance, high bias)\hat{Q}(s_t, a_t) = r_t + \gamma V_\phi(s_{t+1}) \quad \text{(low variance, high bias)}

Between these two ends of spectra, we can have:

Q^2(st,at)=rt+γrt+1+γ2Vϕ(st+2)\hat{Q}_2(s_t, a_t) = r_t + \gamma r_{t+1} + \gamma^2 V_\phi(s_{t+2})

Q^3(st,at)=rt+γrt+1+γ2rt+2+γ3Vϕ(st+3)\hat{Q}_3(s_t, a_t) = r_t + \gamma r_{t+1} + \gamma^2 r_{t+2} + \gamma^3 V_\phi(s_{t+3})

⋮\vdots

The corresponding advantage estimates will be:

A^1=rt+γVϕ(st+1)−V(st)=δt\hat{A}_1 = r_t + \gamma V_\phi(s_{t+1}) - V(s_t) = \delta_t

A^2=rt+γrt+1+γ2Vϕ(st+2)−V(st)=δt+1\hat{A}_2 = r_t + \gamma r_{t+1} + \gamma^2 V_\phi(s_{t+2}) - V(s_t) = \delta_{t+1}

⋮\vdots

A^T=rt+γrt+1+⋯+γT−1rT−V(sT)\hat{A}_T = r_t + \gamma r_{t+1} + \dots + \gamma^{T-1} r_T - V(s_T)

Generalized Advantage Estimation (GAE)

A^t\hat{A}_t = exponentially weighted average (A^1…A^T\hat{A}_1 \dots \hat{A}_T) with weight λ\lambda.

A^t=∑k=0T−t(γλ)k δt+k(General advantage estimation)\hat{A}_t = \sum_{k=0}^{T-t} (\gamma\lambda)^k \, \delta_{t+k} \quad \text{(General advantage estimation)}

Summarising

Initialize policy θ0\theta_0 and value function ϕ0\phi_0

for n=0,1,2,…n = 0, 1, 2, \dots

Importance Sampling

In supervised learning, it’s std. to have multiple epochs. PPO revisits the sets of trajectories multiple times. But this creates a problem: sampling the response is using policy parameters from nnth model update (πθn\pi_{\theta_n}) but we are computing loss using new parameters θn+epoch\theta_{n+\text{epoch}}. This can break the training process as we are backpropagating the wrong gradient.

There’s a maths trick called Importance Sampling. It allows us to estimate expectations under one distribution p(x)p(x) from another distribution q(x)q(x).

Ex∼p[g(x)]=Ex∼q[g(x)⋅p(x)q(x)⏟Surrogate loss]\mathbb{E}_{x \sim p}[g(x)] = \mathbb{E}_{x \sim q}\left[g(x) \cdot \underbrace{\frac{p(x)}{q(x)}}_{\text{Surrogate loss}}\right]

LPG=∑t[πθnew(at∣st)πθold(at∣st) At]=∑t[r(θ)⋅At]L^{PG} = \sum_t \left[\frac{\pi_{\theta_{new}}(a_t \mid s_t)}{\pi_{\theta_{old}}(a_t \mid s_t)} \, A_t\right] = \sum_t \left[r(\theta) \cdot A_t\right]

Finally: Clipping in PPO

πθnew(at∣st)πθold(at∣st)\dfrac{\pi_{\theta_{new}}(a_t \mid s_t)}{\pi_{\theta_{old}}(a_t \mid s_t)} reflects how much the model changes between two updates.

PPO clips this between 1−ϵ1-\epsilon and 1+ϵ1+\epsilon, where ϵ←\epsilon \leftarrow hyperparameter.

LCLIP=∑t[min⁡(rt(θ),  clip(1−ϵ,  rt(θ),  1+ϵ))]⋅AtL^{CLIP} = \sum_t \left[\min\left(r_t(\theta), \; \text{clip}\left(1-\epsilon, \; r_t(\theta), \; 1+\epsilon\right)\right)\right] \cdot A_t

We can also penalise the difference in policy distribution by substrating the KL divergence between both the policies

LPPO(θ)=Es,a∼πθ[min⁡(rt(θ)A^t,  clip(rt(θ),1−ϵ,1+ϵ)A^t)]−βDKL(πref ∥ πθ)\mathcal{L}_{\text{PPO}}(\theta) = \mathbb{E}_{s,a \sim \pi_\theta}\left[\min\left(r_t(\theta)\hat{A}_t, \; \text{clip}\left(r_t(\theta), 1-\epsilon, 1+\epsilon\right)\hat{A}_t\right)\right] - \beta D_{\text{KL}}\left(\pi_{\text{ref}} \,\|\, \pi_\theta\right)

KL(P ∥ Q)=∫log⁡(p(x)q(x))p(x) dx=Ex∼p[log⁡(p(x)q(x))]\text{KL}(P \,\|\, Q) = \int \log\left(\frac{p(x)}{q(x)}\right) p(x) \, dx = \mathbb{E}_{x \sim p}\left[\log\left(\frac{p(x)}{q(x)}\right)\right]

I found this very helpful video for understanding PPO

Group Relative Policy Optimization (GRPO)

GRPO eliminates the need of having a value function!

Instead of a value function, it uses the average reward of multiple sampled outputs, produced in response to the same question as baseline.

For each question qq, GRPO samples a group of outputs {o1,o2,…,oG}\{o_1, o_2, \dots, o_G\} from the old policy πθold\pi_{\theta_{old}} and then optimizes the policy model by maximizing the following objective:

JGRPO(θ)=E[q∼P(Q), {oi}i=1G∼πθold(O∣q)]1G∑i=1G1∣oi∣∑t=1∣oi∣{min⁡[πθ(oi,t∣q,oi,<t)πθold(oi,t∣q,oi,<t)A^i,t,  clip⁡(πθ(oi,t∣q,oi,<t)πθold(oi,t∣q,oi,<t), 1−ε, 1+ε)A^i,t]−β DKL[πθ ∥ πref]},\mathcal{J}_{GRPO}(\theta) = \mathbb{E}_{\left[q \sim P(Q),\, \{o_i\}_{i=1}^{G} \sim \pi_{\theta_{old}}(O|q)\right]} \frac{1}{G}\sum_{i=1}^{G}\frac{1}{|o_i|}\sum_{t=1}^{|o_i|} \left\{ \min\left[ \frac{\pi_\theta(o_{i,t}\mid q, o_{i,<t})}{\pi_{\theta_{old}}(o_{i,t}\mid q, o_{i,<t})}\hat{A}_{i,t},\; \operatorname{clip}\left( \frac{\pi_\theta(o_{i,t}\mid q, o_{i,<t})}{\pi_{\theta_{old}}(o_{i,t}\mid q, o_{i,<t})},\, 1-\varepsilon,\, 1+\varepsilon \right)\hat{A}_{i,t} \right] - \beta\,\mathbb{D}_{KL}\left[\pi_\theta \,\|\, \pi_{ref}\right] \right\},

where ε\varepsilon and β\beta are hyperparameters.

Also note that, instead of adding KL penalty in the reward, GRPO regularizes by directly adding the KL divergence between the trained policy and the reference policy to the loss, avoiding complicating the calculation of Advantage

Algorithm: Iterative Group Relative Policy Optimization

Input: initial policy model π_θinit; reward models r_φ; task prompts D;
       hyperparameters ε, β, μ

policy model π_θ ← π_θinit
for iteration = 1, …, I do
    reference model π_ref ← π_θ
    for step = 1, …, M do
        Sample a batch D_b from D
        Update the old policy model π_θold ← π_θ
        Sample G outputs {o_i}, i=1..G ~ π_θold(· | q) for each question q ∈ D_b
        Compute rewards {r_i}, i=1..G for each sampled output o_i by running r_φ
        Compute Â_{i,t} for the t-th token of o_i through group relative
        advantage estimation
        for GRPO iteration = 1, …, μ do
            Update the policy model π_θ by maximizing the GRPO objective
            (Equation 21)
    Update r_φ through continuous training using a replay mechanism

Output: π_θ

Outcome supervision provides the normalized reward at the end of each output oio_i and sets the advantages A^i,t\hat{A}_{i,t} of all tokens in the output as the normalized reward, i.e.,

A^i,t=r~i=ri−mean⁡(r)std⁡(r),\hat{A}_{i,t} = \widetilde{r}_i = \frac{r_i - \operatorname{mean}(\mathbf{r})}{\operatorname{std}(\mathbf{r})},

and then optimizes the policy by maximizing the objective defined in the reward function equation.