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 表现更好?
💡
实战一句话记忆口诀
前 B 条路并肩走,展开各路算对数,长度惩罚防短断,精选前 B 进下轮
📐 核心数学公式与机理推导
### 启发式路径搜索与长度归一化
贪心搜索每步只选局部最优,容易因一步走错导致后续全盘皆输;全量穷举搜索在词表为 时复杂度为 ,计算不可行。
Beam Search 折中方案:
每一步仅保留累计对数概率最高的 (Beam Width,如 4 或 5)条最优候选路径。
长度惩罚(Length Penalty)的必要性:
由于对数概率 是负数,路径越长累计累加的负数越多。如果不做长度归一化,Beam Search 会强烈偏向于生成极短的断句。
GNMT 提出长度惩罚公式( 通常取 0.6 ~ 0.8):
打分调整为累计对数概率除以 。
贪心搜索每步只选局部最优,容易因一步走错导致后续全盘皆输;全量穷举搜索在词表为 时复杂度为 ,计算不可行。
Beam Search 折中方案:
每一步仅保留累计对数概率最高的 (Beam Width,如 4 或 5)条最优候选路径。
长度惩罚(Length Penalty)的必要性:
由于对数概率 是负数,路径越长累计累加的负数越多。如果不做长度归一化,Beam Search 会强烈偏向于生成极短的断句。
GNMT 提出长度惩罚公式( 通常取 0.6 ~ 0.8):
打分调整为累计对数概率除以 。
🔄 张量维度与形状流转说明
当前 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)通过独立随机采样生成 条完整长思维链,配合外部代码执行器或验证器做全局评判,更能探索复杂的多步解题路径。
⚡
想检验本题的肌肉记忆?进入 3 阶闪卡主动回忆盲测
隐藏答案遮罩,自测:审题锚点 ➔ 数理公式机理 ➔ 工业标杆代码与连环追问。3 分钟攻破认知盲区!