I4MediumPart I · Inference, Decoding & Quantization

Beam Search Decoding with Length Penalty

⚡Flashcard Drill➔

Maintain top-B partial decoding hypotheses scored with GNMT length penalty normalization.

⏱️ Time: O(T * B * V)
💾 Space: O(B * T)
🎯 Interactive Self-Practice Loop (Attempt Before Peeking)
Practice in 4 steps: recall mechanism, complete core lines, check edge cases, and log mastery locally.
Step 1 · Mechanism Recall & Stability Self-Check
Step 2 · Complete Key Implementation Lines
import numpy as np
def simple_beam_search_step(
current_beams: list, # [(score, [token_ids])] 长度为 B 的当前候选路径
next_token_log_probs: np.ndarray, # (B, V) 各路径扩展下一词的对数概率
beam_width: int = 3,
alpha: float = 0.6
) -> list:
all_candidates = []
# 遍历当前每条活跃的 Beam
for b_idx, (prev_score, seq) in enumerate(current_beams):
log_probs =
for token_id, lp in enumerate(log_probs):
new_seq = seq + [token_id]
new_raw_score = prev_score + lp
# 计算长度惩罚
length = len(new_seq)
lp_factor = ((5.0 + length) / 6.0) ** alpha
normalized_score =
all_candidates.append((new_raw_score, normalized_score, new_seq))
# 按归一化分数降序排序,仅截取前 beam_width 条
all_candidates.sort(key=lambda x: x[1], reverse=True)
best_beams = [(raw, seq) for raw, norm, seq in all_candidates[:beam_width]]
return best_beams
Step 3 · Verify Boundary Cases & Assertions
Step 4 · Follow-Up Drill & Review Outcome
Q1: Why does Best-of-N (sampling + verifier) outperform Beam Search for code generation and math reasoning?
Next: PagedAttention KV Block Allocator & Mapping →
💡

Core Mental Anchor / Mnemonic

Expand B beams across vocab V, normalize scores by length penalty, prune back to top B.

📐 Mathematical Derivation & Core Formula

Score(y1,…,yt)=∑i=1tlog⁡P(yi∣y<i)LP(t),LP(t)=(5+t)α(5+1)α\mathrm{Score}(y_1, \dots, y_t) = \frac{\sum_{i=1}^t \log P(y_i \mid y_{<i})}{LP(t)}, \quad LP(t) = \frac{(5 + t)^\alpha}{(5 + 1)^\alpha}
### Heuristic Beam Width & Length Normalization
Greedy decoding is shortsighted, while exact decoding costs O(VT)O(V^T). Beam Search retains the top BB highest-scoring partial hypotheses per step.
Because summed token log-probabilities log⁡P≤0\log P \le 0 decrease monotonically with sequence length tt, unnormalized scores favor overly short outputs. Length penalty LP(t)=(5+t)α(5+1)αLP(t) = \frac{(5 + t)^\alpha}{(5 + 1)^\alpha} divides cumulative log-prob so longer coherent sequences remain competitive.

🔄 Tensor Dimensions & Shape Flow

B beams -> expand B*V candidates -> score / length_penalty -> keep top B hypotheses

🛡️ Numerical Stability & Pitfalls Checklist

  • Move hypotheses hitting [EOS] into completed beams while continuing search on active beams.
  • Open-ended chat models generally prefer stochastic Top-P / Min-P sampling to avoid repetitive beam output.

💻 Reference Code Implementation

import numpy as np

def simple_beam_search_step(
    current_beams: list,        # [(score, [token_ids])] 长度为 B 的当前候选路径
    next_token_log_probs: np.ndarray, # (B, V) 各路径扩展下一词的对数概率
    beam_width: int = 3,
    alpha: float = 0.6
) -> list:
    all_candidates = []
    
    # 遍历当前每条活跃的 Beam
    for b_idx, (prev_score, seq) in enumerate(current_beams):
        log_probs = next_token_log_probs[b_idx] # (V,)
        for token_id, lp in enumerate(log_probs):
            new_seq = seq + [token_id]
            new_raw_score = prev_score + lp
            
            # 计算长度惩罚
            length = len(new_seq)
            lp_factor = ((5.0 + length) / 6.0) ** alpha
            normalized_score = new_raw_score / lp_factor
            
            all_candidates.append((new_raw_score, normalized_score, new_seq))
            
    # 按归一化分数降序排序,仅截取前 beam_width 条
    all_candidates.sort(key=lambda x: x[1], reverse=True)
    best_beams = [(raw, seq) for raw, norm, seq in all_candidates[:beam_width]]
    return best_beams

🧪 Runnable Assertions & Validation

Copy and run directly in Python / Jupyter:

import numpy as np
init_beams = [(0.0, [101])] # [CLS]
# 假设词表大小 3
next_lps = np.array([[-0.1, -2.0, -5.0]])
step1 = simple_beam_search_step(init_beams, next_lps, beam_width=2)
assert len(step1) == 2
# 概率最高的词 0 应排在第 1 位
assert step1[0][1][-1] == 0
print("✓ Beam Search 束搜索自测通过")

🎯 Core Follow-up Inquiries & Reference Answers

Q1:Why does Best-of-N (sampling + verifier) outperform Beam Search for code generation and math reasoning?
Beam Search prunes greedily step-by-step and cannot recover if a valid solution starts with a low-probability reasoning setup, whereas Best-of-N samples diverse complete chains and scores them end-to-end with compilers or test verifiers.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔
← Prev: Speculative Decoding Verification & Accept/RejectBack to Part I & All 105Next: PagedAttention KV Block Allocator & Mapping →