I4MediumPart I · Inference, Decoding & Quantization
Beam Search Decoding with Length Penalty
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?
💡
Core Mental Anchor / Mnemonic
Expand B beams across vocab V, normalize scores by length penalty, prune back to top B.
📐 Mathematical Derivation & Core Formula
### Heuristic Beam Width & Length Normalization
Greedy decoding is shortsighted, while exact decoding costs . Beam Search retains the top highest-scoring partial hypotheses per step.
Because summed token log-probabilities decrease monotonically with sequence length , unnormalized scores favor overly short outputs. Length penalty divides cumulative log-prob so longer coherent sequences remain competitive.
Greedy decoding is shortsighted, while exact decoding costs . Beam Search retains the top highest-scoring partial hypotheses per step.
Because summed token log-probabilities decrease monotonically with sequence length , unnormalized scores favor overly short outputs. Length penalty 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.