后面的题都有点长尾了感觉,等用到了回来研究一下

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

  1. optimizer.zero_grad()
  2. For each (x, y) in micro_batches: loss = loss_fn(model(x), y) / len(micro_batches), then loss.backward()
  3. optimizer.step()
  4. 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 Loss

32_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

  1. Scale by temperature: logits /= temperature
  2. Top-k: keep only top-k logits, set rest to -inf
  3. Top-p: sort by prob, mask tokens where cumulative prob exceeds p
  4. 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

  1. Start with [(0.0, [start_token])]
  2. Each step: expand each beam with top-k next tokens
  3. Keep top beam_width beams by total log-probability
  4. Stop when best beam ends with eos_token or max_len reached
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:

  1. ratio = target_probs[i, token_i] / draft_probs[i, token_i]
  2. Accept with probability min(1, ratio)
  3. 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 accepted

35_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)

  1. Split each word into characters + </w> end marker
  2. Count all adjacent pairs across the corpus
  3. Merge the most frequent pair into a single token
  4. Repeat for num_merges iterations
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_tokens

36_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)

  1. scale = weight.abs().max(dim=1) / 127
  2. weight_int8 = round(weight / scale).clamp(-128, 127).to(int8)
  3. Store as register_buffer (not trainable)
  4. 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 out

37_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-probs (B,)(B,)
  • old_logps: old policy log-probs (B,)(B,)
  • advantages: advantage estimates (B,)(B,)

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_i

The 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 + b

Signature

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 y

Method 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_form must not use iterative optimization
  • gradient_descent must manually compute gradients (no autograd)
  • nn_linear should use torch.nn.Linear and loss.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, b

41_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)

Related Posts