lookahead

# 前瞻解码：Jacobi 迭代 基于 ICML 2024 论文及 LMSYS 博客 ## 概览 **来源**：https://lmsys.org/blog/2023-11-21-lookahead-decoding/ **论文**：ICML 2024 **GitHub**：https://github.com/hao-ai-lab/LookaheadDecoding 前瞻解码通过 Jacobi 迭代打破了自回归解码的顺序依赖，在无需草稿模型或额外训练的情况下，实现了 1.5-2.3 倍的加速。 ## 核心概念 ### 重构为方程求解 **传统自回归**： y_t = f(x, y_1, y_2, ..., y_{t-1}) # 顺序执行 **Jacobi 迭代**： y_t^{(k+1)} = f(x, y_1^{(k)}, y_2^{(k)}, ..., y_{t-1}^{(k)}) # 并行执行 **关键洞察**：虽然精确的并行解码是不可能的，但我们可以并行生成多个不连续的 n-gram，这些 n-gram 可能匹配最终序列。 ## 双分支架构 ### 前瞻分支 **目的**：并行生成潜在的 Token 序列 (n-grams)。 **参数**： - `W` (窗口大小)：向前查看的步数 - `N` (n-gram 大小)：用于生成的历史 Token 数 python # 示例：W=5, N=3 # 使用过去 1-3 个 Token 在位置 1-5 生成 n-gram def lookahead_branch(model, tokens, W=5, N=3): """使用 Jacobi 迭代生成 n-grams。""" candidates = {} for w in range(1, W + 1): # 位置偏移 for n in range(1, N + 1): # n-gram 长度 # 使用 n 个历史 Token 预测位置 w past_tokens = tokens[-n:] future_position = len(tokens) + w # 生成 n-gram ngram = model.generate_ngram( context=past_tokens, position=future_position, length=n ) candidates[(w, n)] = ngram return candidates **输出**：可能匹配未来序列的候选 n-gram 池。 ### 验证分支 **目的**：识别并确认有潜力的 n-gram。 python def verification_branch(model, tokens, candidates): """验证哪些候选匹配实际序列。""" verified = [] for ngram in candidates: # 检查 n-gram 的第一个 Token 是否匹配最后一个生成的 Token if ngram[0] == tokens[-1]: # 使用模型验证完整 n-gram is_valid = model.verify_sequence(tokens + ngram) if is_valid: verified.append(ngram) # 返回最长的已验证 n-gram return max(verified, key=len) if verified else None **接受**：n-gram