1 of 50

CSCI-SHU 376: Natural Language Processing

Hua Shen

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

2026-03-24

Spring 2026

Lecture 13: LLM and Reasoning

2 of 50

Today’s Plan

  • Introduction
  • Chain-of-Thought Prompting
  • Test-time Scaling / Deepseek R1
  • Open Research Questions

​

​

3 of 50

Hard NLP Tasks: Reasoning

3

4 of 50

Definition of Reasoning

4

Think, understand, and form judgments by a process of logic

- Oxford Languages

5 of 50

Reasoning Problems

5

6 of 50

Reasoning Problems: Math

6

  • GSM8K: Middle school math word problems

7 of 50

Reasoning Problems

7

8 of 50

Reasoning Problems: Math

8

  • MATH: Competition mathematics problems

9 of 50

Reasoning Problems: Code

9

  • Write Software
  • Automatically fix bugs
  • Help prove that code is correct
  • Tool for reasoning
  • Interact with environment
  • ...

10 of 50

Code Generation - applications�

10

11 of 50

Code Generation - applications�

11

12 of 50

Code Generation - applications�

12

13 of 50

Code Generation - History�

13

  • Classic methods for program synthesis (specification -> program)

14 of 50

Code Generation - History�

14

  • Classic methods for program synthesis (specification -> program)

​

​

  • Large search space over programs!

​

​

  • Difficult to model informal specifications!

15 of 50

Code Generation - History�

15

  • Early neural models for code (specialized architecture, for a dataset)

16 of 50

Code Generation - History�

16

  • Code generation with LLMs

17 of 50

Code Generation - History�

17

  • Code generation with LLMs

18 of 50

Why we care about language and code?

18

  • Many applications
  • Large amounts of data
  • Structured, compositional
  • Combines informal (e.g., intent) and formal (testable code)
  • Rich tooling
  • Complementary to LLMs
  • ...

19 of 50

Today’s Plan

  • Introduction
  • Chain-of-Thought Prompting
  • Test-time Scaling / Deepseek R1
  • Open Research Questions

​

​

20 of 50

20

21 of 50

Chain-of-Thought Prompting

21

  • Get the model to explain its reasoning before making an answer

22 of 50

Reasoning is an emergent ability

22

  • Only appear when models are very large

23 of 50

Program-aided Language Models

23

  • Using a program to generate outputs can be more precise than prompting
  • Especially for numerical questions

24 of 50

Today’s Plan

  • Introduction
  • Chain-of-Thought Prompting
  • Test-time Scaling / Deepseek R1
  • Open Research Questions

​

​

25 of 50

Recap: Scaling laws

25

  • Scaling up compute leads to a better model!

26 of 50

Test-time Scaling

26

  • Test-time Scaling: improve performance by generating more tokens

27 of 50

Test-time Scaling

27

  • Generate multiple times (e.g., ensemble)

28 of 50

Test-time Scaling

28

  • Generate longer outputs

29 of 50

GPT-o1: Scale up Reasoning

Our large-scale reinforcement algorithm teaches the model how to think productively using its chain of thought in a highly data-efficient training process.

30 of 50

DeepSeek V3 / R1

  • < 200 employees

​

  • Spin off of hedge fund

​

  • Consistent open-weights model releases

​

​

31 of 50

DeepSeek V3 / R1

32 of 50

DeepSeek V3

  • Mix-of-Expert architecture

​

  • Performance close to GPT 4o

​

  • Much cheaper training cost

​

​

33 of 50

DeepSeek R1

  • Primarily a post training innovation

​

  • Think GPT o1

​

​

34 of 50

DeepSeek R1-Zero: RL from scratch

Reinforcement learning

35 of 50

Group Relative Policy Optimization (GRPO)

  • For each question, GRPO samples a group of outputs and then optimizes the policy model
  • RL training is more stable (no critic model)

​

​

36 of 50

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

Recap: Rule-based rewards

37 of 50

DeepSeek R1-Zero: Reward

  • Accuracy rewards: whether the response is correct

​

  • Format rewards: whether it follows format

​

​

38 of 50

DeepSeek R1-Zero is already good

39 of 50

“Self-evolution Process” of R1-Zero

  • Naturally acquire the ability with increasing test-time compute
  • Emergence of sophisticated behaviors

​

​

40 of 50

DeepSeek R1-Zero: Aha Moment

  • Occurs in an intermediate version of model

​

  • RL can generalize!

​

​

41 of 50

DeepSeek R1: RL with Cold Start

  • Can reasoning further improved with a small amount of long CoT data?

​

  • Can we train a user-friendly model?

​

​

42 of 50

DeepSeek R1: RL with Code Start

  • R1: Cold-started from human-written data

​

  • Reasoning + Non-reasoning data: use LLM to provide CoT with basic checks

​

  • Only 800K samples

​

​

43 of 50

DeepSeek R1: RL with Code Start

44 of 50

Today’s Plan

  • Introduction
  • Chain-of-Thought Prompting
  • Test-time Scaling / Deepseek R1
  • Open Research Questions

​

​

45 of 50

Reasoning model overthinking

  • Add length penalty
  • Intermediate reward?

46 of 50

Reasoning model underthinking

  • Abandon promising reasoning paths
  • Better budget allocation

47 of 50

Tasks other than Math / Code

48 of 50

Tasks other than Math / Code

  • Task: Next Chapter Prediction
    • Predict the next chapter given story information: sketch, previous story, character, previous chapter, next chapter synopsis
  • Hypothesis: Generate reasoning trace is important and helpful

49 of 50

Tasks other than Math / Code

  • Task: Next Chapter Prediction
  • VR-CLI: Verifiable Rewards via Completion Likelihood Improvement
  • Use a reference model to get the improved likelihood of the true next chapter

50 of 50

Tasks other than Math / Code