CSCI-SHU 376: Natural Language Processing

Hua Shen

Course Agenda: 2026 Fall-NLP-[CSCI-SHU-376]-Class Schedule

2026-10-14

Fall 2026

Lecture 11: RLHF & LLM Decoding

Today’s Plan

• RLHF
• LLM Decoding Overview
• Sampling
• Controllable Generation

​

​

Limitations of Instruction finetuning

• It is expensive to collect ground-truth data for tasks
• Some tasks like open-ended creative generation have no right answer
• E.g., write a story about a lion
• Language modelling penalizes all token-level mistakes equally, but some are worse than others
• Can we try to satisfy human preferences?

​

Reinforcement Learning from Human Feedback (RLHF)

Reinforcement Learning from Human Feedback (RLHF)

• Instruction tuning first
• Then maximize reward

​

Recap: SFT Recap

Training:

<prompter> How do you make tea?

<assistant> Remove the tea bag and enjoy.

Inference:

<prompter> What country won the most gold medals in 2008 Olympics?

<assistant>

​

• SFT = next-token prediction on instruction–response pairs�
• Special tokens define speaker roles (prompter / assistant)
• Serve as “cold start” in RLHF
• After SFT, we get a reference model (policy)

Question: Can we get a better/optimal policy?

What is an “Optimal Policy”?

A simple formula:

Key question: how to get reward for each LLM generation?

P A R T 0 2

Comparison Data

P A R T 0 2

Challenge: What is a good measure of human preference?

​

Answer: Use pairwise comparison data — humans can more reliably judge which of two responses is better than assign absolute scores.

Data: (x, y_win, y_lost)

Reward model: R(x, y_win) > R(x, y_lost)

​

Question: Why is pairwise data a desired form?

Long before LLM: ELO Rating

• Elo rating is widely adopted in chess, online games (e.g., League of Legends), etc…

​

• Elo is an online learning algorithm

​

• In preference optimization, however, we often seek a global estimation of latent rewards from all pairwise data.

Bradley-Terry (BT) model

Preference Distribution :

Parametrize + + maximum likelihood

Frame the problem as a binary classification we have the negative log-likelihood loss:

Tips: normalize the rewards for low variance

RLHF

During the RL phase, the learned reward function is used to provide feedback to the language model. The optimization is formulated as:

Due to the discrete nature of language generation, this objective is not differentiable and is typically optimized with reinforcement learning.

P A R T 0 2

Preparation：RL concepts

A common RL trajectory:

S0, A0, R1, S1, A1, R2, S2, A2, R3…

Start from initial state S0

Take action A0

Get Reward R1

Go to state S1

What is Agent and Environment in RL?

Agent:

Input: State St

Output: Action At

Usually formalized as policy: π(a | s)

​

Environment:

Input: current State St, Action At

Output: next State St+1, Reward

Usually formalized as: p(s’,r | s,a)

​

​

Example: Blackjack/21 points

You are initially given one card. You may take more cards, one at a time if you like. Stop anytime before lose.

• jack = queen = king = 10; ace = 11; No joker included
• You get 0 return if go over 21;
• Return sum of your cards, otherwise.

​

Goal: close to 21 without going over 21.

​

Blackjack: Reward, State, Action

Let X be sum of your card,

Reward: [0, 21]

0 for non-terminal state

X if X <= 21, or 0 if X > 21, in terminal state.

State: X

Action: {0, 1}

0 for “don’t take more”, 1

Stop if choose 0 or X exceed 21.

​

Blackjack: Possible trajectories

τ1 : S0 = 7, A0 = 1, R1 = 0, S1 = 12, A1 =1, R2 = 0, S2 = 20, A2 = 0, R3 = 20

τ2: S0 = 11, A0 = 1, R1 = 0, S1 = 15, A1 =1, R2 = 0, S2 = 25, A2 = 0, R3 = 0

Finally, which one is better?

Return value G ()

G1 = 0 + 0 + 20 = 20 😃

G2 = 0 + 0 + 0 = 0 😭

Episodic: only gives (useful) reward at end

p.s. Go, Chess, and LLM usually holds Episodic

​

Modeling Reward: Policy, Value, and Action-Value

Policy: π(a | s)

• Given I got 20 points, I should “stop”
• I want to take action according to this state

Value: vπ(s) = Eπ[ Gt | St = s ]

• Eπ [Rt +1 + 𝛾Rt+2 + …. | St = s ], For episodic, R: 0, 0, 0, ..., x
• I want to know how good/bad my state is

Action Value: qπ(s,a) := Eπ[ Gt| St = s, At = a]

• I want to know how good if I take this action at this state

Policy Gradient/REINFORCE algorithm

RL: Policy: π(a | s)

DRL: Policy Network

• Can be just MLP
• Input: a state vector
• Output: logit over all actions

​

After softmax, it becomes “probability”

Policy Gradient/REINFORCE algorithm

Recall that RL trajectory:

S0, A0, R1, S1, A1, R2, S2, A2, R3…

Now At = argmax (πӨ(a| St)), all a in Action space

We can then do Gradient Ascent to raise Return G:

​

Policy Gradient/REINFORCE algorithm

By Policy Gradient Theorem, the gradient can be written like RHS

Thus, Deep learning training can be carried out

Policy Gradient/REINFORCE algorithm

Simplified LLM

current state:

Sentence input

LLM

(include tokenizer)

Logit output

(Over vocab)

Probability output

(Over vocab)

RL formalization of LLM problem

Episodic RL problem:

- initial state S0 = prompt

- action space A = vocabulary

- action At = token in vocabulary

- state St = prompt + all response tokens generated so far

- policy πӨ(a| St) = LLM output prob

- episode ends when <|endoftext|> token is sampled

Reward model would assign rφ(x,y)

Try to maximize Ex~D,y~πθ [ rφ(x,y) ]

P A R T 0 1

Reinforcement Learning (RL) Summary

• The field of reinforcement learning has studied these problems for many years
• Circa 2013: resurgence of interest in RL applied to deep learning in game playing
• New area: Applying RL to modern LMs

​

Reinforcement Learning (RL)

RL: Language Generation

• State: a prompt and tokens-generated so far
• Action: generate a token
• Policy: generator (e.g., Language Model)
• Environment: append token
• Reward: how good is the current token?

-> decomposed from reward on the full sequence

RL: One step Language Generation

• State: a prompt
• Action: generate a full response
• Policy: generator (e.g., Language Model)
• Reward: reward on the full sequence

Reinforcement Learning (RL)

• The task criteria / preference is directly optimized via the reward
• Data is generated by the model, and a reward tells us how to use data for training
• Model generations are in the training loop

• Human-in-the-loop is expensive!
• Instead of directly asking humans for preference, model their preferences as a separate NLP problem

​

• Rule-based rewards

​

• Model-based rewards

​

How do we get rewards?

• A verifiable property of output
• Example: reward for solving a math problem

Rule-based rewards

• A verifiable property of output
• Example: write a program that passes test cases

Rule-based rewards

Model-based rewards

• Model R(x, y) that scores output sequences
• Example: classify whether the output is “helpful”

​

Model-based rewards: Preference

• Human judgments are noisy and miscalibrated!
• Instead of directly asking for ratings, ask for pairwise comparisons that are more reliable

​

• Human judgments are noisy and miscalibrated!
• Instead of directly asking for ratings, ask for pairwise comparisons that are more reliable

​

Model-based rewards : Preference

Evaluating reward models

Optimizing for human preferences

Optimizing for human preferences

• How do we actually change our LM parameters to maximize this?

​

• Policy gradient methods in RL give us tools for estimating and optimizing this objection

​

RLHF provides additional gains

RLHF Summary

Instruct GPT: scaling up RLHF to many tasks

Instruct GPT: scaling up RLHF to many tasks

• Labeler collected tasks

​

Instruct GPT: scaling up RLHF to many tasks

Today’s Plan

• RLHF
• LLM Decoding Overview
• Sampling
• Controllable Generation

​

​

​

What is inside LLM?

• A model defines a conditional probability distribution

​

​

LMs are locally normalized

• It could be the sequence starts with low probability tokens, but have high overall probability
• Therefore, it is hard to do inference with global constraints

​

Probability distribution -> Hallucination

• Model generally assigns non-zero probability to any (incorrect) outputs

​

Our goal: Get “Good” Outputs

• A “good” output given a probability distribution
• Changing the decoding algorithms

​

Today’s Plan

• LLM Decoding Overview
• Sampling
• Controllable Generation

​

​

​

Recap: Greedy Decoding

• Greedy Decoding: Compute argmax (over entire vocab) at every step

Recap: Beam Search

• At every step, keep track of the k most probable partial translations
• Score of each hypothesis = log probability of sequence so far

​

​

• Not guaranteed to be optimal, but more efficient than exhaustive search

Highest probability always best?

• Outputs with low probability tend to be worse

​

​

​

​

• Difference between top outputs is unclear…

Highest probability always best?

• Many outputs are meaningful!

Ancestral Sampling

• Exactly samples from model distribution!

​

Ancestral Sampling

• Long-tail problem
• Even if each individual token in the long-tail has low probability, these small probabilities add up…

​

Top-K Sampling

• Only sample from the most probable <k> tokens

Top-p Sampling

• Also called nucleus sampling
• Only sample from the top <p> probability mass
• Ignore the long-tails

Epsilon Sampling

Contrastive Decoding

• Smaller models make different mistakes

​

• Choose outputs that the “expert” finds much more likely than the “amateur”

Today’s Plan

• LLM Decoding Overview
• Sampling
• Controllable Generation

​

​

​

Different types of Constraints

• Low-level constraints: structured output, length etc

63

Different types of Constraints

• High-level constraints: semantic, avoid hallucination etc

64

Prompting is not enough!

65

Constrained decoding: Manipulate logits

• Set P(“climb” | X, y) = 0?

​

66

Constrained decoding: Rejection Sampling

• Generate a lot of samples, then reject

​

67