I4MediumPart I · 推理生成、解码与量化

Beam Search 束搜索(束宽更新与长度惩罚)

⚡闪卡盲测➔

机器翻译与语音识别经典确定性搜索,保持前 Beam_Width 个最高累计对数似然候选路径。

⏱️ 时间复杂度: O(T * B * V)
💾 空间复杂度: O(B * T)
🎯 免登录实战自测闭环(先做再看答案)
按「机制回忆 → 关键行填空 → 边界反例 → 追问与错题记录」顺序自测,进度自动保存在本地。
Step 1 · 机制口述与数值稳定性自检
Step 2 · 核心代码关键行补全
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 · 反例与边界断言核对
Step 4 · 面试追问盲答与错题记录
Q1: 为什么在代码生成与数学推理(DeepSeek-R1 / OpenAI o1)中,Best-of-N 往往比 Beam Search 表现更好?
下一题: PagedAttention 物理块分配与虚拟块表映射 →
💡

实战一句话记忆口诀

前 B 条路并肩走,展开各路算对数,长度惩罚防短断,精选前 B 进下轮

📐 核心数学公式与机理推导

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}
### 启发式路径搜索与长度归一化
贪心搜索每步只选局部最优,容易因一步走错导致后续全盘皆输;全量穷举搜索在词表为 VV 时复杂度为 O(VT)O(V^T),计算不可行。
Beam Search 折中方案:
每一步仅保留累计对数概率最高的 BB(Beam Width,如 4 或 5)条最优候选路径。
长度惩罚(Length Penalty)的必要性:
由于对数概率 log⁡P≤0\log P \le 0 是负数,路径越长累计累加的负数越多。如果不做长度归一化,Beam Search 会强烈偏向于生成极短的断句。
GNMT 提出长度惩罚公式(α\alpha 通常取 0.6 ~ 0.8):
LP(t)=(5+t)α(5+1)αLP(t) = \frac{(5 + t)^\alpha}{(5 + 1)^\alpha}
打分调整为累计对数概率除以 LP(t)LP(t)。

🔄 张量维度与形状流转说明

当前 B 条路径 -> 乘积扩展为 B*V 种可能 -> 计算带 LP 分数 -> 排序取 Top B

🛡️ 数值稳定性自检与边界要点

  • 一旦候选生成 [EOS] 终止符,需将其移入已完成序列集合(Completed Beams),剩余活跃 Beam 继续向下扩展
  • 在大模型开放式自由对话中,Beam Search 容易造成复读机单调重复,现代大模型更倾向于使用 Top-P / Min-P 采样

💻 完整参考代码实现

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

🧪 本地测试与正确性断言

可直接复制到本地 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 束搜索自测通过")

🎯 核心工程追问与标准应答

Q1:为什么在代码生成与数学推理(DeepSeek-R1 / OpenAI o1)中,Best-of-N 往往比 Beam Search 表现更好?
Beam Search 在早期局部搜索时剪枝不可逆,一步剪掉未来潜在优质解答便彻底错失;而 Best-of-N(Rejection Sampling / Pass@k)通过独立随机采样生成 NN 条完整长思维链,配合外部代码执行器或验证器做全局评判,更能探索复杂的多步解题路径。
⚡
想检验本题的肌肉记忆?进入 3 阶闪卡主动回忆盲测
隐藏答案遮罩,自测:审题锚点 ➔ 数理公式机理 ➔ 工业标杆代码与连环追问。3 分钟攻破认知盲区!
🎯 立即在闪卡中盲测此题➔
← 上一题: 投机解码(Speculative Decoding 验证与接收拒绝)返回 Part I 与全部 105 题下一题: PagedAttention 物理块分配与虚拟块表映射 →