后面的题都有点长尾了感觉,等用到了回来研究一下
31_Gradient Accumulation
Implement a training step with gradient accumulation — simulating large batches with limited memory.
Signature
def accumulated_step(model, optimizer, loss_fn, micro_batches) -> float:
# micro_batches: list of (input, target) tuples
# Returns: average loss (float)
Algorithm
optimizer.zero_grad()- For each
(x, y)in micro_batches:loss = loss_fn(model(x), y) / len(micro_batches), thenloss.backward() optimizer.step()- Return total accumulated loss
The key insight: dividing each loss by n before backward makes accumulated gradients equal to a single large-batch gradient.
import torch
import torch.nn as nn
# ✏️ YOUR IMPLEMENTATION HERE
def accumulated_step(model, optimizer, loss_fn, micro_batches):
# zero_grad, loop (forward, scale loss, backward), step
optimizer.zero_grad()
Loss = 0
for i in range(len(micro_batches)):
x, y = micro_batches[i]
loss = loss_fn(model(x), y) / len(micro_batches)
loss.backward()
Loss += loss.item()
optimizer.step()
return Loss32_Top-k / Top-p (Nucleus) Sampling
Implement sampling with top-k and top-p filtering — the standard LLM decoding strategy.
Signature
def sample_top_k_top_p(logits, top_k=0, top_p=1.0, temperature=1.0) -> int:
# logits: (V,) unnormalized log-probabilities
# Returns: sampled token index
Algorithm
- Scale by temperature:
logits /= temperature - Top-k: keep only top-k logits, set rest to
-inf - Top-p: sort by prob, mask tokens where cumulative prob exceeds p
- Sample from filtered distribution
import torch
# ✏️ YOUR IMPLEMENTATION HERE
def sample_top_k_top_p(logits, top_k=0, top_p=1.0, temperature=1.0):
logits = logits / max(temperature, 1e-8)
if top_k > 0:
top_k_val = logits.topk(top_k).values[-1]
logits[logits < top_k_val] = float('-inf')
if top_p < 1.0:
sorted_logits, sorted_idx = torch.sort(logits, descending=True)
probs = torch.softmax(sorted_logits, dim=-1)
cumsum = torch.cumsum(probs, dim=-1)
mask = (cumsum - probs) > top_p
sorted_logits[mask] = float('-inf')
logits = torch.empty_like(logits).scatter_(0, sorted_idx, sorted_logits)
probs = torch.softmax(logits, dim=-1)
return torch.multinomial(probs, 1).item()
33_Beam Search Decoding
Implement beam search — the classic decoding algorithm for sequence generation.
Signature
def beam_search(log_prob_fn, start_token, max_len, beam_width, eos_token) -> list[int]:
# log_prob_fn: takes token list, returns (V,) log-probabilities
# Returns: best sequence (list of ints)
Algorithm
- Start with
[(0.0, [start_token])] - Each step: expand each beam with top-k next tokens
- Keep top
beam_widthbeams by total log-probability - Stop when best beam ends with
eos_tokenormax_lenreached
import torch
def beam_search(log_prob_fn, start_token, max_len, beam_width, eos_token):
beams = [(0.0, [start_token])]
completed = []
for _ in range(max_len):
candidates = []
for score, seq in beams:
if seq[-1] == eos_token:
completed.append((score, seq))
continue
log_probs = log_prob_fn(torch.tensor(seq))
topk_lp, topk_idx = log_probs.topk(beam_width)
for j in range(beam_width):
candidates.append((score + topk_lp[j].item(), seq + [topk_idx[j].item()]))
if not candidates:
break
candidates.sort(key=lambda x: x[0], reverse=True)
beams = candidates[:beam_width]
all_seqs = completed + beams
all_seqs.sort(key=lambda x: x[0], reverse=True)
return all_seqs[0][1]34_Speculative Decoding
Implement the acceptance/rejection step of speculative decoding — a technique for accelerating LLM inference.
Signature
def speculative_decode(target_probs, draft_probs, draft_tokens) -> list[int]:
# target_probs: (K, V) from target (large) model
# draft_probs: (K, V) from draft (small) model
# draft_tokens: (K,) tokens sampled by draft model
# Returns: list of accepted tokens (1 to K)
Algorithm
For each position i = 0, …, K-1:
ratio = target_probs[i, token_i] / draft_probs[i, token_i]- Accept with probability
min(1, ratio) - If rejected: sample from
normalize(max(0, target - draft)), append, and stop
import torch
def speculative_decode(target_probs, draft_probs, draft_tokens):
K = len(draft_tokens)
accepted = []
for i in range(K):
t = draft_tokens[i].item()
ratio = target_probs[i, t] / max(draft_probs[i, t].item(), 1e-10)
if torch.rand(1).item() < min(1.0, ratio.item()):
accepted.append(t)
else:
adjusted = torch.clamp(target_probs[i] - draft_probs[i], min=0)
s = adjusted.sum()
if s > 0:
adjusted = adjusted / s
else:
adjusted = torch.ones_like(adjusted) / adjusted.shape[0]
accepted.append(torch.multinomial(adjusted, 1).item())
return accepted
return accepted35_Byte-Pair Encoding (BPE)
mplement a simple BPE tokenizer — the foundation of GPT/LLaMA tokenization.
Signature
class SimpleBPE:
def __init__(self): ...
def train(self, corpus: list[str], num_merges: int): ...
def encode(self, text: str) -> list[str]: ...
Algorithm (training)
- Split each word into characters +
</w>end marker - Count all adjacent pairs across the corpus
- Merge the most frequent pair into a single token
- Repeat for
num_mergesiterations
class SimpleBPE:
def __init__(self):
self.merges = []
def train(self, corpus, num_merges):
vocab = {}
for word in corpus:
symbols = tuple(word) + ('</w>',)
vocab[symbols] = vocab.get(symbols, 0) + 1
self.merges = []
for _ in range(num_merges):
pairs = {}
for word, freq in vocab.items():
for i in range(len(word) - 1):
pair = (word[i], word[i + 1])
pairs[pair] = pairs.get(pair, 0) + freq
if not pairs:
break
best = max(pairs, key=pairs.get)
self.merges.append(best)
new_vocab = {}
for word, freq in vocab.items():
new_word = []
i = 0
while i < len(word):
if i < len(word) - 1 and (word[i], word[i + 1]) == best:
new_word.append(word[i] + word[i + 1])
i += 2
else:
new_word.append(word[i])
i += 1
new_vocab[tuple(new_word)] = freq
vocab = new_vocab
def encode(self, text):
all_tokens = []
for word in text.split():
symbols = list(word) + ['</w>']
for a, b in self.merges:
i = 0
while i < len(symbols) - 1:
if symbols[i] == a and symbols[i + 1] == b:
symbols = symbols[:i] + [a + b] + symbols[i + 2:]
else:
i += 1
all_tokens.extend(symbols)
return all_tokens36_INT8 Quantized Linear
Implement a post-training quantized linear layer using INT8 weights.
Signature
class Int8Linear(nn.Module):
def __init__(self, weight: Tensor, bias: Tensor = None): ...
def forward(self, x: Tensor) -> Tensor: ...
Quantization (per-channel)¶
scale = weight.abs().max(dim=1) / 127weight_int8 = round(weight / scale).clamp(-128, 127).to(int8)- Store as
register_buffer(not trainable) - Forward: dequantize (
int8.float() * scale) then matmul
import torch
import torch.nn as nn
class Int8Linear(nn.Module):
def __init__(self, weight, bias=None):
super().__init__()
scale = weight.abs().amax(dim=1, keepdim=True) / 127.0
self.register_buffer('weight_int8',
torch.round(weight / (scale + 1e-10)).clamp(-128, 127).to(torch.int8))
self.register_buffer('scale', scale)
self.bias = nn.Parameter(bias.clone()) if bias is not None else None
def forward(self, x):
w = self.weight_int8.float() * self.scale
out = x @ w.T
if self.bias is not None:
out = out + self.bias
return out37_DPO Loss
Implement the Direct Preference Optimization loss — the standard loss for LLM alignment.
\mathcal{L}_{\text{DPO}} = -\log \sigma\Big(\beta \big[\log\frac{\pi(y_w)}{\text{ref}(y_w)} - \log\frac{\pi(y_l)}{\text{ref}(y_l)}\big]\Big)Signature
def dpo_loss(policy_chosen_logps, policy_rejected_logps,
ref_chosen_logps, ref_rejected_logps, beta=0.1) -> Tensor:
# All inputs: (B,) log-probabilities
# Returns: scalar loss
import torch
import torch.nn.functional as F
def dpo_loss(policy_chosen_logps, policy_rejected_logps,
ref_chosen_logps, ref_rejected_logps, beta=0.1):
chosen_rewards = beta * (policy_chosen_logps - ref_chosen_logps)
rejected_rewards = beta * (policy_rejected_logps - ref_rejected_logps)
return -F.logsigmoid(chosen_rewards - rejected_rewards).mean()38_GRPO Loss
Implement the Group Relative Policy Optimization (GRPO) loss — a group-wise, baseline-subtracted REINFORCE objective commonly used in RLAIF (reinforcement learning from AI feedback).
Given a batch of log-probabilities, scalar rewards, and group ids (one group per prompt), define the within-group normalized advantages:
A_i = \frac{r_i - \bar r_{g(i)}}{\text{std}_{g(i)} + \epsilon}where (\bar r_{g(i)}) and (\text{std}_{g(i)}) are the mean and standard deviation of rewards in the group of example (i).
The GRPO loss is then the negative advantage-weighted log-probability:
\mathcal{L}_{\text{GRPO}} = -\mathbb{E}_i \big[\,\text{stop\_grad}(A_i)\, \log \pi_\theta(y_i)\big].import torch
import torch.nn.functional as F
from torch import Tensor
def grpo_loss(logps: Tensor, rewards: Tensor, group_ids: Tensor,
eps: float = 1e-5) -> Tensor:
"""Group Relative Policy Optimization (GRPO) loss.
logps: (B,) policy log-probs for each sampled response
rewards: (B,) scalar rewards for each response
group_ids: (B,) integers, same id = same prompt/group
returns: scalar loss (Tensor)
"""
# Compute per-group normalized advantages A_i
unique_ids = group_ids.unique()
advantages = torch.empty_like(rewards)
for gid in unique_ids:
mask = group_ids == gid
r_g = rewards[mask]
mean_g = r_g.mean()
std_g = r_g.std(unbiased=False)
advantages[mask] = (r_g - mean_g) / (std_g + eps)
# Stop gradient through advantages
advantages_detached = advantages.detach()
# GRPO objective: -E[A_i * logpi_i]
return -(advantages_detached * logps).mean()
39_PPO Clipped Loss
Implement the PPO (Proximal Policy Optimization) clipped surrogate loss.
Given:
new_logps: current policy log-probsold_logps: old policy log-probsadvantages: advantage estimates
Define the ratio
r_i = \exp(\text{new\_logps}_i - \text{old\_logps}_i). Then compute
L^{\text{unclipped}}_i = r_i A_i \\ L^{\text{clipped}}_i = \operatorname{clip}(r_i, 1-\epsilon, 1+\epsilon) A_iThe loss is the negative batch mean of the elementwise minimum:
\mathcal{L}_\text{PPO} = -\mathbb{E}_i\big[\min(L^{\text{unclipped}}_i, L^{\text{clipped}}_i)\big].Implementation notes: detach old_logps and advantages so gradients only flow through new_logps.
Signature
from torch import Tensor
def ppo_loss(new_logps: Tensor, old_logps: Tensor, advantages: Tensor,
clip_ratio: float = 0.2) -> Tensor:
"""PPO clipped surrogate loss over a batch."""
import torch
import torch.nn.functional as F
from torch import Tensor
def ppo_loss(new_logps: Tensor, old_logps: Tensor, advantages: Tensor,
clip_ratio: float = 0.2) -> Tensor:
"""PPO clipped surrogate loss.
new_logps: (B,) current policy log-probs
old_logps: (B,) old policy log-probs (treated as constant)
advantages: (B,) advantage estimates (treated as constant)
returns: scalar loss (Tensor)
"""
# Detach old_logps and advantages so gradients only flow through new_logps
old_logps_detached = old_logps.detach()
adv_detached = advantages.detach()
# Importance sampling ratio r = pi_new / pi_old in log-space
ratios = torch.exp(new_logps - old_logps_detached)
# Unclipped and clipped objectives
unclipped = ratios * adv_detached
clipped = torch.clamp(ratios, 1.0 - clip_ratio, 1.0 + clip_ratio) * adv_detached
# PPO objective: negative mean of the more conservative objective
return -torch.min(unclipped, clipped).mean()
40_Linear Regression
Implement linear regression using three different approaches — all in pure PyTorch.
Given data X of shape (N, D) and targets y of shape (N,), find weight w of shape (D,) and bias b (scalar) such that:
\hat{y} = Xw + bSignature
class LinearRegression:
def closed_form(self, X: Tensor, y: Tensor) -> tuple[Tensor, Tensor]: ...
def gradient_descent(self, X: Tensor, y: Tensor, lr=0.01, steps=1000) -> tuple[Tensor, Tensor]: ...
def nn_linear(self, X: Tensor, y: Tensor, lr=0.01, steps=1000) -> tuple[Tensor, Tensor]: ...
All methods return (w, b) where w has shape (D,) and b has shape ().
Method 1 — Closed-Form (Normal Equation)
Augment X with a ones column, then solve:
\theta = (X_{aug}^T X_{aug})^{-1} X_{aug}^T yMethod 2 — Gradient Descent from Scratch
Initialize w and b to zeros. Repeat for steps iterations:
pred = X @ w + b
error = pred - y
grad_w = (2/N) * X^T @ error
grad_b = (2/N) * error.sum()
w -= lr * grad_w
b -= lr * grad_b
Method 3 — PyTorch nn.Linear
Create nn.Linear(D, 1), use nn.MSELoss and an optimizer (e.g., torch.optim.SGD). After training, extract w and b from the layer.
Rules
- All inputs and outputs must be PyTorch tensors
- Do NOT use numpy or sklearn
closed_formmust not use iterative optimizationgradient_descentmust manually compute gradients (noautograd)nn_linearshould usetorch.nn.Linearandloss.backward()
import torch
import torch.nn as nn
class LinearRegression:
def closed_form(self, X: torch.Tensor, y: torch.Tensor):
"""Normal equation via augmented matrix."""
N, D = X.shape
# Augment X with ones column for bias
X_aug = torch.cat([X, torch.ones(N, 1)], dim=1) # (N, D+1)
# Solve (X^T X) theta = X^T y
theta = torch.linalg.lstsq(X_aug, y).solution # (D+1,)
w = theta[:D]
b = theta[D]
return w.detach(), b.detach()
def gradient_descent(self, X: torch.Tensor, y: torch.Tensor,
lr: float = 0.01, steps: int = 1000):
"""Manual gradient computation — no autograd."""
N, D = X.shape
w = torch.zeros(D)
b = torch.tensor(0.0)
for _ in range(steps):
pred = X @ w + b # (N,)
error = pred - y # (N,)
grad_w = (2.0 / N) * (X.T @ error) # (D,)
grad_b = (2.0 / N) * error.sum() # scalar
w = w - lr * grad_w
b = b - lr * grad_b
return w, b
def nn_linear(self, X: torch.Tensor, y: torch.Tensor,
lr: float = 0.01, steps: int = 1000):
"""PyTorch nn.Linear with autograd training loop."""
N, D = X.shape
layer = nn.Linear(D, 1)
optimizer = torch.optim.SGD(layer.parameters(), lr=lr)
loss_fn = nn.MSELoss()
for _ in range(steps):
optimizer.zero_grad()
pred = layer(X).squeeze(-1) # (N,)
loss = loss_fn(pred, y)
loss.backward()
optimizer.step()
w = layer.weight.data.squeeze(0) # (D,)
b = layer.bias.data.squeeze(0) # scalar ()
return w, b41_OPD Loss
Implement the On-Policy Distillation (OPD) loss used to distill one or more teacher policies into a student policy on trajectories sampled from the student.
For each token position, OPD minimizes a weighted reverse KL from the student distribution to each teacher distribution:
\mathcal{L}_{\text{OPD}} = \sum_j w_j\,D_{\text{KL}}\big(\pi_\theta(\cdot \mid x)\;||\;\pi_{E_j}(\cdot \mid x)\big)where
D_{\text{KL}}(p||q) = \sum_v p(v)\,[\log p(v) - \log q(v)].Signature
from torch import Tensor
def opd_loss(student_logits: Tensor,
teacher_logits: Tensor,
teacher_weights: Tensor | None = None,
mask: Tensor | None = None,
temperature: float = 1.0) -> Tensor:
"""OPD reverse-KL distillation loss.
student_logits: (..., V) logits from the student policy
teacher_logits: (..., V) for one teacher, or (T, ..., V) for T teachers
teacher_weights: optional (T,) weights, normalized internally
mask: optional (...) token mask, where 1 = include and 0 = ignore
temperature: softmax temperature used for distillation
returns: scalar loss (Tensor)
"""
import torch
import torch.nn.functional as F
from torch import Tensor
def opd_loss(student_logits: Tensor,
teacher_logits: Tensor,
teacher_weights: Tensor | None = None,
mask: Tensor | None = None,
temperature: float = 1.0) -> Tensor:
"""On-Policy Distillation (OPD) reverse-KL loss.
student_logits: (..., V) logits from the student policy
teacher_logits: (..., V) for one teacher, or (T, ..., V) for T teachers
teacher_weights: optional (T,) weights, normalized internally
mask: optional (...) token mask, where 1 = include and 0 = ignore
temperature: softmax temperature used for distillation
returns: scalar loss (Tensor)
"""
if teacher_logits.dim() == student_logits.dim():
teacher_logits = teacher_logits.unsqueeze(0)
elif teacher_logits.dim() != student_logits.dim() + 1:
raise ValueError('teacher_logits must have shape (..., V) or (T, ..., V)')
teacher_logits = teacher_logits.detach()
t = float(temperature)
student_logp = F.log_softmax(student_logits / t, dim=-1)
student_prob = student_logp.exp()
teacher_logp = F.log_softmax(teacher_logits / t, dim=-1)
per_teacher_kl = (
student_prob.unsqueeze(0) * (student_logp.unsqueeze(0) - teacher_logp)
).sum(dim=-1)
num_teachers = per_teacher_kl.shape[0]
if teacher_weights is None:
weights = torch.full(
(num_teachers,),
1.0 / num_teachers,
dtype=per_teacher_kl.dtype,
device=per_teacher_kl.device,
)
else:
weights = teacher_weights.to(dtype=per_teacher_kl.dtype, device=per_teacher_kl.device)
weights = weights / weights.sum()
view_shape = (num_teachers,) + (1,) * (per_teacher_kl.dim() - 1)
per_token_kl = (weights.view(view_shape) * per_teacher_kl).sum(dim=0)
if mask is not None:
mask = mask.to(dtype=per_token_kl.dtype, device=per_token_kl.device)
loss = (per_token_kl * mask).sum() / mask.sum().clamp_min(1.0)
else:
loss = per_token_kl.mean()
return loss * (t ** 2)