1. 论文基本信息

1.1. 标题

SPECTRA: Faster Large Language Model Inference with Optimized Internal and External Speculation

1.2. 作者

Nguyen-Khang Le, Dinh-Truong Do, Nguyen Le Minh (日本高级科学技术研究院)

1.3. 发表期刊/会议

未明确提及具体期刊或会议，根据发布日期 2025-01-01T00:00:00.000Z 判断，可能为预印本（Preprint）或已接受但尚未正式刊发的论文。

1.4. 发表年份

2025

1.5. 摘要

现代大语言模型（LLM）的推理（Inference）既计算昂贵又耗时。推测解码（Speculative Decoding）已成为一种有前景的解决方案，但现有方法面临关键限制：基于训练的方法需要一个难以获取且缺乏通用性的草稿模型（Draft Model），而无需训练的方法则速度提升有限。在这项工作中，我们提出了 SPECTRA，一个无需额外训练或修改原始 LLM 即可加速 LLM 推理的新颖框架。SPECTRA 引入了两种新颖技术，用于高效利用内部和外部推测，每种技术都独立优于相应的最先进（SOTA）方法。当结合使用时，这些技术在各种基准和 LLM 架构上实现了高达 4.08 倍的速度提升，显著超越了现有的无需训练方法。SPECTRA 的实现已公开发布。

1.6. 原文链接

/files/papers/695011299c764da3f20e36ef/paper.pdf 发布状态：预印本（根据发布时间推断）。

2. 整体概括

2.1. 研究背景与动机

LLM 推理的计算效率问题： 大型语言模型（LLM）在生成长序列时，由于其自回归解码 (Autoregressive Decoding) 特性，每次只能生成一个词元 (Token)。这种逐词元生成的方式导致生成时间与序列长度呈线性关系，并且未能充分利用现代图形处理器（GPU）的并行处理能力，从而造成推理的计算昂贵 (Computationally Expensive) 和耗时 (Time-consuming)。

推测解码 (Speculative Decoding) 的局限性： 推测解码 (Speculative Decoding) 作为一种有前景的解决方案被提出，它通过“猜测-验证”（guess-and-verify）的范式来加速推理。然而，现有方法存在以下挑战：

1. 基于训练的方法 (Training-based Methods): 这类方法通常需要一个较小的草稿模型 (Draft Model) 来预测多个词元，或以特定方式训练原始 LLM 自身（自推测解码 (Self-speculative Decoding)）。这些方法需要大量的计算资源进行额外训练，并可能降低原始模型的性能或通用性。
2. 无需训练的方法 (Training-free Methods): 这类方法旨在避免额外训练，通过特定机制从 LLM 预测中直接生成推测词元，或依赖外部信息源。然而，由于猜测质量有限，它们通常只能提供有限的速度提升。

本文的切入点： SPECTRA 正是为了解决上述局限性而提出。它旨在开发一种无需训练或修改原始 LLM 的推测解码框架，从而提高猜测的质量和数量，最终实现显著的推理加速。

2.2. 核心贡献/主要发现

SPECTRA 框架的核心贡献和主要发现可以总结如下：

• 提出 SPECTRA 框架： 引入了一个新颖的、无需训练 (Training-free) 且无需修改原始 LLM (No Modification to Original LLM) 的推测解码 (Speculative Decoding) 框架。这使得它成为一个即插即用 (Plug-and-play) 的解决方案，易于部署。
• 优化内部推测 (SPECTRA-CORE): 提出了 SPECTRA-CORE 模块，它通过高效利用 LLM 预测的词元分布 (Token Distribution) 来生成高质量的猜测。该模块采用多级 N-gram 存储（包括前向和后向字典）进行双向搜索 (Bi-directional Search)，以动态生成变长猜测。同时，它优化了候选池 (Candidate Pool) 来持续更新 N-gram 字典，确保广泛的词元覆盖。
• 优化外部推测 (SPECTRA-RETRIEVAL): 提出了 SPECTRA-RETRIEVAL 模块，它通过困惑度精炼语料库 (Corpus Refinement by Perplexity) 的方式，从外部知识源中选择高质量的相关文本，从而生成更有效的猜测。这一优化解决了以往外部推测方法与其它推测解码方法集成困难的问题（例如搜索时间开销过大）。
• 显著的性能提升： SPECTRA 在结合内部和外部推测技术后，在多种基准测试（包括多轮对话、代码生成和数学推理）和 LLM 架构（Llama 2、Llama 3 和 CodeLlama，模型大小从 7B 到 70B）上实现了高达 4.08 倍的加速比 (Speedup Ratio)，显著优于现有的无需训练 (Training-free) 推测解码方法。
• 保持输出质量： 作为一种无损加速 (Lossless Acceleration) 方法，SPECTRA 能够完全保留原始 LLM 的输出分布和生成质量，无论是贪婪解码 (Greedy Decoding) 还是采样解码 (Sampling Decoding)。
• 公开发布代码： 实现了 SPECTRA 并公开了其代码，促进了社区对 LLM 推理加速的研究和应用。

3. 预备知识与相关工作

3.1. 基础概念

3.1.1. 大语言模型 (Large Language Models, LLMs)

LLM 是具有数亿到数千亿甚至更多参数的深度学习模型，通常基于 Transformer 架构。它们在大量文本数据上进行预训练，能够理解和生成人类语言，并执行各种自然语言处理任务，如文本生成、摘要、翻译和问答。

3.1.2. 自回归解码 (Autoregressive Decoding)

自回归解码 (Autoregressive Decoding) 是 LLM 默认的文本生成方式。在这种模式下，模型会根据当前已生成的文本和输入提示 (Prompt) 来预测下一个词元（Token）。这个过程是顺序进行的，每次只生成一个词元，然后将这个新生成的词元添加到输入序列中，作为预测下一个词元的上下文。

• 工作原理： 给定一个输入序列 $\mathbf{x} = (x_1, x_2, \ldots, x_s)$，LLM 计算生成下一个词元的概率分布 $P_M(x_{s+1} \mid \mathbf{x}_{1:s})$。 对于贪婪采样 (Greedy Sampling)，下一个词元 $x_{s+1}$ 被选择为概率最高的词元： $$x_{s+1} = \arg\max P_M(x_{s+1} \mid \mathbf{x}_{1:s})$$ 这个过程重复进行，直到生成结束词元或达到最大序列长度。
• 效率瓶颈： 由于每个词元的生成都需要一次完整的模型前向传播，因此生成时间与输出序列长度呈线性关系，导致效率低下，尤其是在生成长文本时。

3.1.3. 推测解码 (Speculative Decoding)

推测解码 (Speculative Decoding) 是一种旨在加速 LLM 推理的无损 (Lossless) 方法。它的核心思想是“猜测-验证” (Guess-and-Verify) 范式。

• 工作原理：
  1. 猜测阶段 (Guessing Phase): 一个更小、更快的草稿模型 (Draft Model)（或原始 LLM 通过特定机制）会提前预测（“猜测”）多个未来的词元，形成一个草稿序列 (Draft Sequence)。
  2. 验证阶段 (Verification Phase): 原始的、大型的 LLM 会并行地验证这些预测的词元。这意味着 LLM 可以一次性处理草稿序列中的多个词元，而不是逐个处理。
  3. 接受/拒绝 (Accept/Reject): 模型会检查草稿序列中的词元是否与它自己生成的词元相匹配。匹配的词元会被接受，不匹配的词元及其后续词元将被拒绝，然后 LLM 会从被拒绝词元处开始，以正常方式生成正确的词元。
• 加速原理： 通过并行验证多个词元，推测解码 (Speculative Decoding) 减少了所需的 LLM 前向传播次数，从而显著加速了生成过程。

3.1.4. N-gram

N-gram 是文本中连续 $N$ 个词元（Token）的序列。

• 应用： 在自然语言处理中，N-gram 广泛用于语言模型、文本预测和模式识别。例如，在一个 N-gram 语言模型中，下一个词元的概率是基于前面 N-1 个词元来预测的。
• 在 SPECTRA 中的应用： SPECTRA 使用 N-gram 字典来存储和检索词元序列，以生成高质量的推测词元。

3.1.5. 困惑度 (Perplexity, PPL)

困惑度 (Perplexity) 是衡量一个概率分布（通常是语言模型）对样本或事件预测效果好坏的指标。

• 概念定义： 困惑度 (Perplexity) 量化了模型在给定文本序列时，平均每个词元的不确定性或“惊讶”程度。困惑度 (Perplexity) 越低，表示模型对文本的预测能力越强，即文本序列与模型自身的概率分布越匹配。
• 数学公式： 给定一个文本序列 $u = (u_0, u_1, \ldots, u_t)$ 和一个语言模型 $P_M$，其困惑度 (Perplexity) 计算如下： $$\mathrm{PPL}(u) = \exp \left\{ - \frac{1}{t} \sum_{i=1}^{t} \log P_M(u_i \mid u_{<i}) \right\}$$
• 符号解释：
  • $u = (u_0, u_1, \ldots, u_t)$：一个长度为 $t+1$ 的文本序列。
  • $P_M(u_i \mid u_{<i})$：语言模型 $P_M$ 在给定前 $i$ 个词元 $u_{<i}$ 的条件下，预测第 $i$ 个词元 $u_i$ 的概率。
  • $\log P_M(u_i \mid u_{<i})$：对数概率。
  • \sum_{i=1}^{t} \log P_M(u_i \mid u_{<i})：序列中所有词元对数概率之和。
  • -\frac{1}{t} \sum_{i=1}^{t} \log P_M(u_i \mid u_{<i})：平均负对数似然（也称为交叉熵）。
  • $\exp(\cdot)$：指数函数。
• 在 SPECTRA 中的应用： SPECTRA-RETRIEVAL 利用 困惑度 (Perplexity) 来过滤外部语料库，选择那些与目标 LLM 预测最一致、质量最高的文本片段来构建猜测源。

3.1.6. 注意力机制 (Attention Mechanism) 和 FlashAttention

注意力机制 (Attention Mechanism) 是 Transformer 模型的关键组成部分，它允许模型在处理序列时，对输入序列的不同部分赋予不同的权重，从而捕获长距离依赖关系。

• FlashAttention： 是一种优化注意力机制 (Attention Mechanism) 计算的方法，特别是在处理长序列时。它通过减少对高带宽内存 (High Bandwidth Memory, HBM) 的访问次数，以及优化计算过程，显著提高了注意力机制 (Attention Mechanism) 的计算效率和速度，尤其在 GPU 上。
• 在 SPECTRA 中的应用： SPECTRA 利用了 FlashAttention 来加速其验证步骤，特别是当并行验证多个推测词元时，能够更有效地利用 GPU 的并行处理能力。

3.2. 前人工作

论文在“相关工作 (Related Works)”和“引言 (Introduction)”中提及了多种 LLM 推理加速技术和推测解码 (Speculative Decoding) 方法。

3.2.1. 通用 LLM 推理优化策略

这些方法旨在降低每次前向传播 (Forward Pass) 的计算负载，但通常会牺牲一部分模型性能。

• 量化 (Quantization): 将模型权重和激活值从高精度（如 FP32）降低到低精度（如 Int8、Int4），减少内存占用和计算量 (Liu et al., 2024b; Lin et al., 2024; Zhao et al., 2024; Park et al., 2024)。
• 剪枝 (Pruning): 移除模型中不重要或冗余的参数，减少模型大小和计算量 (Ma et al., 2023; Xia et al., 2023; Sun et al., 2023a; Le et al., 2025)。
• 知识蒸馏 (Knowledge Distillation): 使用大型模型的知识训练一个更小的模型，使其在保持性能的同时提高推理速度 (Gu et al., 2024; Friha et al., 2024; Zhang et al., 2024b)。
• 局限性： 这些方法通常会引入一定程度的模型性能下降 (Degradation)，需要在效率和质量之间进行权衡。

3.2.2. 基于训练的推测解码 (Training-based Speculative Decoding)

这类方法通过训练一个辅助模型或修改原始模型的训练方式来生成推测词元。

• 草稿模型 (Draft Model): 使用一个更小、更快的 LLM 作为草稿模型 (Draft Model) 来预测多个未来的词元，然后由大型 LLM 验证 (Chen et al., 2023; Leviathan et al., 2023; Miao et al., 2024; Sun et al., 2023b; Zhou et al., 2024; Cai et al., 2024)。
• 自推测解码 (Self-speculative Decoding): 通过特殊训练使原始 LLM 自身能够预测多个词元 (Elhoushi et al., 2024; Liu et al., 2024a; Yang et al., 2024; Zhang et al., 2024a; Li et al., 2024b)。
• 局限性： 需要额外的训练，计算资源消耗大，并且可能影响原始模型的能力 (Capabilities) 或通用性 (Generalizability)。

3.2.3. 无需训练的推测解码 (Training-free Speculative Decoding)

这类方法无需额外训练，直接利用现有模型或外部信息源来生成推测词元，使其更具实用性 (Practicality) 和即插即用 (Plug-and-play) 特性。

• 基于 LLM 预测的方法：
  • Lookahead Decoding (Fu et al., 2024): 这种方法通过分析 LLM 的概率分布来推测后续词元，并使用特殊的注意力掩码 (Attention Mask) 来并行验证。
  • Adaptive N-gram (ANPD) (Ou et al., 2024): 利用自适应的 N-gram 结构来生成推测词元。
  • Jacobi-like parallel decoding (Santilli et al., 2023): 通过缓解左-右依赖关系来并行生成和验证多个候选词元。
• 基于检索的方法 (Retrieval-based Methods):
  • REST (He et al., 2024): 使用数据存储 (Datastore) 索引已观测到的前缀 (Prefixes)，以检索猜测序列。
  • 其他类似方法 (Yang et al., 2023; Li et al., 2024a)。
• 局限性： 论文指出，这些方法的加速比 (Speedup Gain) 往往有限，主要因为猜测的质量不够高。特别是基于检索的方法，其搜索时间可能会抵消加速效果，并且难以与其他推测解码方法有效集成。

3.3. 技术演进

LLM 推理加速的技术演进大致可分为三个阶段：

1. 早期优化： 专注于单个模型的前向传播效率，通过量化 (Quantization)、剪枝 (Pruning)、知识蒸馏 (Knowledge Distillation) 等技术减少计算量。这些方法通常伴随着模型精度或能力的损失。
2. 基于训练的推测解码： 引入草稿模型 (Draft Model) 或自推测 (Self-speculative) 机制，通过提前预测和并行验证来加速生成。这些方法有效，但引入了额外的训练成本和模型管理复杂性。
3. 无需训练的推测解码（本研究关注点）： 旨在消除训练成本，直接利用现有 LLM 的特性或外部知识源来生成高质量猜测。这是为了在不改变原始模型、不增加训练负担的情况下，实现即插即用的加速。SPECTRA 正是这一演进方向上的重要一步，通过优化内部和外部猜测机制，显著提升了无需训练方法的性能上限。

3.4. 差异化分析

SPECTRA 与现有无需训练 (Training-free) 推测解码方法的主要区别和创新点在于：

• 综合优化内部与外部猜测： SPECTRA 是首个将内部 (Internal) LLM 预测分布与外部 (External) 精炼知识源相结合，并进行深度优化的框架。以往的方法通常侧重于其中之一。
• SPECTRA-CORE 的创新：
  • 多级 N-gram 存储与双向搜索： SPECTRA-CORE 利用前向和后向 N-gram 字典进行双向搜索 (Bi-directional Search)，这比 Lookahead 等方法中使用的单一方向猜测更为灵活和高效。它能够生成变长猜测 (Variable-length Guesses)，平衡猜测的质量和数量。
  • 候选池动态更新： 引入候选池 (Candidate Pool) 和基于随机性的词元选择机制 (Token Selection Mechanism) ($τ$ 参数)，确保 N-gram 字典能够动态更新并具有更广的词元覆盖率，解决了仅凭高概率词元可能导致字典稀疏的问题。
  • 子 N-gram 包含： SPECTRA-CORE 不仅添加完整的 N-gram，还将子序列添加到字典中，显著提高了字典的覆盖率 (Coverage) 和猜测质量。
• SPECTRA-RETRIEVAL 的创新：
  • 困惑度精炼 (Perplexity Refinement): SPECTRA-RETRIEVAL 通过计算目标 LLM 的困惑度 (Perplexity) 来筛选外部语料库，只保留高质量、与模型预测一致的文本片段。这解决了 REST 等方法可能因外部猜测质量不高而导致速度提升有限的问题。
  • 高效集成： 这种精炼机制使得外部猜测能够高效地与 SPECTRA-CORE 集成，通过限制外部知识库的大小和确保高质量，避免了搜索时间抵消加速效果的问题。论文指出，简单地将 Lookahead 和 REST 结合会导致性能显著下降，凸显了 SPECTRA 优化集成策略的重要性。
• 无损加速和即插即用： 与基于训练的方法相比，SPECTRA 实现了无损加速 (Lossless Acceleration)，且不需要修改原始 LLM 或进行额外训练，是真正的即插即用 (Plug-and-play) 解决方案。

4. 方法论

4.1. 方法原理

SPECTRA 的核心思想是通过内部知识 (Internal Knowledge) 和外部知识 (External Knowledge) 的协同优化，以无损 (Lossless) 的方式加速 LLM 的推测解码 (Speculative Decoding) 过程。它包含两个主要模块：SPECTRA-CORE 负责从 LLM 自身的词元分布 (Token Distribution) 中提取高质量的猜测；SPECTRA-RETRIEVAL 则从经过困惑度 (Perplexity) 精炼的外部语料库中获取额外的高质量猜测。这两个模块可以独立工作，也可以高效地结合使用，以最大化加速效果。整个框架旨在提高猜测的接受率 (Acceptance Rate) 和每个解码步骤中接受的词元数量，从而减少所需的总解码步骤，实现显著的加速。

4.2. 核心方法详解

SPECTRA 的解码过程由 Algorithm 1 描述，它融合了 SPECTRA-CORE 和可选的 SPECTRA-RETRIEVAL 模块。

以下是 SPECTRA 解码过程的详细分解：

4.2.1. SPECTRA-CORE 模块

SPECTRA-CORE 模块主要包含一个 N-gram 存储（N-gram Storage）和一个候选池 (Candidate Pool)。

4.2.1.1. N-gram 存储与候选池初始化

在 Algorithm 1 的第 1-4 行，系统会初始化 N-gram 存储和候选池 (Candidate Pool)。

• N-gram 存储: 维护两个字典：
  • 前向字典 (Forward Dictionary) $S_{fwd}$: 初始为空 $\emptyset$。它将一个词元映射到一个序列列表（即以该词元开头的所有后续序列）。
  • 后向字典 (Backward Dictionary) $S_{bwd}$: 初始为空 $\emptyset$。它将一个序列映射到单个词元（即作为该序列后续的下一个词元）。
• 候选池 (Candidate Pool) $\mathcal{C}$: 包含 $W$ 个序列，记为 $\{c^{(0)}, c^{(1)}, \ldots, c^{(W-1)}\}$。每个序列的长度为 $N$，其中 $c_j^{(i)}$ 表示第 $i$ 个序列中的第 $j$ 个词元。初始时，这些词元也可能为空或随机填充。

4.2.1.2. 双向搜索获取猜测 (Bi-directional Search for Guesses)

在每个时间步 $t$（从 $x$ 的当前长度 $n$ 开始），SPECTRA 通过双向搜索 (Bi-directional Search) 生成 $G$ 个猜测序列 $\mathcal{G}$（Algorithm 1, 行 6-17）。

• 前向搜索 (Forward Search)（优先数量）:
  • Algorithm 1, 行 7：利用当前已生成序列的最后一个词元 $\mathbf{x}_{t-1}$ 作为键，在前向字典 $S_{fwd}$ 中搜索，获取以 $\mathbf{x}_{t-1}$ 开头的猜测序列。这部分猜测 $g'$ 旨在提供更多的猜测数量。
  • 其直觉是，如果 $x_{t-1}$ 频繁出现在训练数据或已生成的序列中，它可能引导出多种合理的后续序列。
• 后向搜索 (Backward Search)（优先质量）:
  • Algorithm 1, 行 8-14：通过迭代地使用后向字典 $S_{bwd}$，一次预测一个词元来构建高质量的猜测序列 $u$。这个过程会重复直到达到期望的序列长度 $N$。
  • 具体而言，从当前序列的末尾开始，向后查找以当前已构建序列为前缀的下一个词元。例如，如果已生成序列为 $x_{t-1}$，则从 $S_{bwd}$ 中搜索以 $x_{t-1}$ 为前缀的下一个词元 $u_0$。然后，搜索以 $x_{t-1} \oplus u_0$ 为前缀的下一个词元 $u_1$，以此类推，直到构建一个长度为 $N$ 的序列。
  • Algorithm 1, 行 11：$u_j ← S_bwd[x_{t+j-k:t-1} ⊕ u_{0:j-1}]$。这里 $x_{t+j-k:t-1}$ 表示当前序列的一个片段，$u_{0:j-1}$ 是已经构建的猜测前缀。这确保了猜测的质量，因为它基于模型过去见过的强关联序列。
  • 这种双向搜索结合了数量和质量的优点，生成多样且高质量的猜测。

4.2.1.3. 预测候选词元 (Predict Tokens for Candidate Pool)

在进行验证之前，LLM 会进行一次前向传播 (Forward Pass)。这次前向传播不仅用于验证猜测，还会同时获取用于更新候选池 (Candidate Pool) 的词元分布（Algorithm 1, 行 25-34）。

• 获取分布： LLM 会并行计算所有必要的词元分布 $P_M(\cdot)$。
• 选择新词元： 对于候选池 (Candidate Pool) 中的每个序列 $c^{(i)}$，需要预测其下一个词元 $c_{N-1}^{(i)}$。
  • 直观方法是选择概率最高的词元。然而，为了增加前向字典 $S_{fwd}$ 的覆盖率 (Coverage)，SPECTRA 引入了基于随机性 (Randomness-based) 的机制。
  • Algorithm 1, 行 28-31：随机抽取 $r \sim \text{Uniform}[0, 1]$。
    • 如果 $r > \tau$（$τ$ 是一个超参数，默认为 0.1），则选择不在 $S_{fwd}$ 中的概率最高的词元。这鼓励模型探索新的 N-gram，即使它们的概率可能略低，以扩大字典的覆盖范围。
    • 否则，选择概率最高的词元，无论其是否在 $S_{fwd}$ 中。
  • Algorithm 1, 行 43：在每个时间步结束时，候选池 (Candidate Pool) 中的所有序列都向左移动一个词元：$c_j^{(i)} \leftarrow c_{j+1}^{(i)}$。这样 $c_{N-1}^{(i)}$ 变空，准备在下一个时间步被预测。这个机制使候选池 (Candidate Pool) 能够不断更新，并为 N-gram 字典提供新鲜的 N-gram。

4.2.1.4. 更新 N-gram 字典 (Update N-gram Dictionaries)

在每个时间步结束时，候选池 (Candidate Pool) $\mathcal{C}$ 中的词元被用来更新 N-gram 字典 $S_{fwd}$ 和 $S_{bwd}$（Algorithm 1, 行 35-41）。

• 子 N-gram 更新： 与以往只添加完整 N-gram 的方法不同，SPECTRA 认为子序列也可能在后续生成中出现。因此，它添加了 N-gram 中的所有子序列。
  • Algorithm 1, 行 38-39：对于候选池 (Candidate Pool) 中每个序列 $c^{(i)}$ 的每个子序列，将其添加到 $S_{fwd}$。例如，$S_fwd[c_j^{(i)}]$ 会追加 $c_{j+1:}^{(i)}$。
  • Algorithm 1, 行 38-39：同时，更新 $S_{bwd}$，将序列的前半部分映射到其后一个词元。例如，$S_bwd[c_{0:j}^{(i)}]$ 映射到 $c_{j+1}^{(i)}$。
  • 这种更新策略增加了字典的覆盖率和猜测质量。

4.2.2. SPECTRA-RETRIEVAL 模块 (可选集成)

SPECTRA-RETRIEVAL 模块旨在从外部知识源中获取高质量猜测，并与 SPECTRA-CORE 高效集成。

4.2.2.1. 困惑度精炼语料库 (Corpus Refinement by Perplexity)

• 外部知识源构建： 处理一个文本语料库，并将其索引到一个支持快速前缀搜索的数据结构中，例如Trie (Trie) 树。
• 质量筛选： 观察到随机选择的语料文本可能会限制加速效果，SPECTRA-RETRIEVAL 提出通过困惑度 (Perplexity) 对语料库进行精炼。
  • 使用目标 LLM 计算语料库中所有文本序列的困惑度 (Perplexity)。
  • 选择困惑度 (Perplexity) 最低的文本片段，因为这些片段与 LLM 的预测最一致，最有可能产生高质量的猜测。
  • 利用这些精炼后的文本构建Trie (Trie) 结构。

4.2.2.2. 与 SPECTRA-CORE 集成 (Integration with SPECTRA-CORE)

• Algorithm 1, 行 16：在生成猜测的步骤中，SPECTRA-RETRIEVAL 产生的猜测 $\mathcal{G}_{retrieve}$ 会被添加到 SPECTRA-CORE 生成的猜测 $\mathcal{G}$ 中。
• 优先级： 由于 SPECTRA-CORE 产生的内部猜测通常具有更高的接受率，SPECTRA 会优先处理内部猜测，如果猜测数量限制 $G$ 尚未达到，再添加外部猜测。
• 高效性： 通过困惑度 (Perplexity) 精炼，SPECTRA-RETRIEVAL 限制了外部知识源的大小并确保了其高质量，从而避免了因外部猜测搜索时间过长或质量不佳而抵消加速效果的问题，实现了与 SPECTRA-CORE 的无缝集成。

4.2.3. 并行前向传播与验证 (Parallel Forward Pass and Verification)

SPECTRA 的一个关键优化是所有必要的分布（用于预测候选词元和验证猜测）都在 LLM 的单次前向传播 (Single Forward Pass) 中并行获取（Algorithm 1, 行 19；Figure 2）。

• 特殊注意力掩码 (Specially Designed Attention Mask): 这通过一个特殊的注意力掩码 (Attention Mask) 实现，该掩码指定了词元之间允许的交互。例如，$c_2$ 词元只关注 $c_1^(1)$、$c_0^(1)$ 和输入。

• 验证： Algorithm 1, 行 20-22：获取分布后，会执行验证步骤。根据采样方法（贪婪解码 (Greedy Decoding) 或采样解码 (Sampling Decoding)），选择相应的验证函数 (VerificationFunction)。验证函数会检查所有猜测，找到拥有最多正确预测词元的序列，并返回被接受的词元 hits。

• Algorithm 1, 行 23-24：将接受的词元添加到序列 $x$ 中，并更新当前序列长度 $t$。

  接下来详细介绍贪婪验证和采样验证的算法。

4.2.3.1. 贪婪验证 (Greedy Verification)

Algorithm 3 详细描述了 SPECTRA 中的贪婪验证 (Greedy Verification) 过程。

输入：

• 序列 $\mathbf{X}$：当前已生成的词元序列。
• 模型 $P_M$：目标 LLM。
• 猜测 $\mathcal{G} = \{g^i\}$：一系列预测的猜测序列，其中 $i \in [0, G-1]$。

输出：

• $o$：被接受的词元序列。

函数 GREEDYVERIFICATION $(\mathbf{x}, P_M, \mathcal{G})$ 步骤：

1. 初始化：
   • D ← ∅：用于存储 LLM 输出的概率分布。
   • V ← G：用于存储当前的猜测序列，初始化为所有输入的猜测序列 $\mathcal{G}$。
2. 获取初始分布：
   • 对于每个猜测序列 $g^i \in \mathcal{G}$（Algorithm 3, 行 4-6）：
     • 计算并存储 $P_M(g^{\prime(i)}, x_{next} \mid g^{(i)}, \mathbf{x})$ 的分布。这里的 $g^{\prime(i)}$ 是在给定 $\mathbf{x}$ 和 $g^{(i)}$ 的前缀下，模型预测的下一个词元。这个步骤实际上是在 LLM 的单次前向传播 (Forward Pass) 中完成的，用于获取所有猜测序列中每个词元在每个位置的条件概率分布。
3. 迭代验证猜测：
   • 对于每个可能的猜测位置 $i$（从 1 到 N-1，其中 $N$ 是最大 N-gram 长度）（Algorithm 3, 行 7-35）：
     • j ← 1：当前要验证的猜测的索引。
     • is_accept ← 0：标志位，表示是否已接受当前位置的词元。
     • P ← D[1]_i：获取第一个猜测序列在当前位置 $i$ 的概率分布（这里的 D[1]_i 表示从所有猜测中选择第一个有效猜测的第 $i$ 个词元的分布，实际上这部分逻辑在原文中描述为并行验证，可能在实际实现中是更复杂的树形验证）。
     • 循环验证当前位置的多个猜测：
       • $while j ≤ size(V)$（Algorithm 3, 行 11-28）：遍历当前有效的猜测序列 $V$。
         • $s_j ← V[j]_i$：获取第 $j$ 个猜测序列在当前位置 $i$ 的词元。
         • 如果 $s_j$ 被接受： $if s_j = argmax P$（Algorithm 3, 行 13）：
           • 将 $s_j$ 添加到接受词元序列 $o$ 中：$o.append(s_j)$。
           • 设置 is_accept ← 1。
           • 更新有效猜测和分布： 创建新的有效猜测列表 V_new 和分布列表 D_new。只保留那些在当前位置 $i$ 也预测为 $s_j$ 的猜测序列及其分布（Algorithm 3, 行 17-23）。这表示只有与当前接受词元一致的猜测序列才能继续被验证。
           • 更新 V ← V_new, D ← D_new。
           • 跳出内层 while 循环，进入下一个位置的验证。
         • 如果 $s_j$ 被拒绝： else（Algorithm 3, 行 25）：
           • 尝试验证下一个猜测序列：$j ← j + 1$。
     • 处理当前位置的验证结果：
       • if is_accept（Algorithm 3, 行 29-30）：如果当前位置的词元被接受，则继续验证下一个位置。
       • else（Algorithm 3, 行 31-33）：如果所有猜测在当前位置都被拒绝：
         • 强制生成一个词元：o.append(argmax P)。
         • 跳出外层 for 循环，结束验证。这意味着从这个点开始，将回退到自回归解码 (Autoregressive Decoding)。
4. 处理最后一个词元（如果所有猜测都被接受）：
   • if is_accept（Algorithm 3, 行 36-37）：如果所有猜测序列都被完全接受，并且没有提前结束，则将最后一个猜测位置的词元（即 argmax D[1]_N）添加到 $o$ 中。
5. 返回接受的词元序列 $o$。

4.2.3.2. 采样验证 (Sample Verification)

Algorithm 4 详细描述了 SPECTRA 中的采样验证 (Sample Verification) 过程。与贪婪验证 (Greedy Verification) 的主要区别在于，它使用采样 (Sampling) 来决定是否接受词元，并相应地调整概率分布。

输入：

• 序列 $x$：当前已生成的词元序列。
• 模型 $P_M$：目标 LLM。
• 猜测 $g^i$：一系列预测的猜测序列，其中 $i \in [0, G-1]$。

输出：

• $o$：被接受的词元序列。

函数 SAMPLEVERIFICaTION $(x, P_M, g)$ 步骤：

1. 初始化： 与贪婪验证 (Greedy Verification) 类似。

   • D ← ∅：用于存储 LLM 输出的概率分布。
   • V ← G：用于存储当前的猜测序列，初始化为所有输入的猜测序列 $\mathcal{G}$。

2. 获取初始分布： 与贪婪验证 (Greedy Verification) 类似。

   • 对于每个猜测序列 $g^i \in \mathcal{G}$，计算并存储 $P_M(g^{\prime(i)}, x_{next} \mid g^{(i)}, \mathbf{x})$ 的分布。

3. 迭代验证猜测：

   • 对于每个可能的猜测位置 $i$（从 1 到 N-1）（Algorithm 4, 行 7-39）：
     • j ← 1：当前要验证的猜测的索引。
     • is_accept ← 0：标志位，表示是否已接受当前位置的词元。
     • $P_j ← D[j]_i$：获取第 $j$ 个猜测序列在当前位置 $i$ 的概率分布。
     • 循环验证当前位置的多个猜测：
       • $while j ≤ size(V)$（Algorithm 4, 行 11-31）：
         • $s_j ← V[j]_i$：获取第 $j$ 个猜测序列在当前位置 $i$ 的词元。
         • sample r ∼ U(0, 1)：从均匀分布中随机抽取一个值 $r$。
         • 如果 $s_j$ 被接受： $if r ≤ P_j(s_j)$（Algorithm 4, 行 14）：
           • 将 $s_j$ 添加到接受词元序列 $o$ 中：$o.append(s_j)$。
           • 设置 is_accept ← 1。
           • 更新有效猜测和分布： 与贪婪验证 (Greedy Verification) 类似，只保留那些在当前位置 $i$ 也预测为 $s_j$ 的猜测序列及其分布。
           • 更新 V ← V_new, D ← D_new。
           • 跳出内层 while 循环。
         • 如果 $s_j$ 被拒绝： else（Algorithm 4, 行 26）：
           • 将当前词元 $s_j$ 的概率设置为 0：$P_j(s_j) ← 0$。
           • 归一化 (Normalize) 概率分布：$P_{j+1} = norm(P_j)$。这确保了在排除了被拒绝的词元后，剩余词元的概率和仍为 1。
           • 尝试验证下一个猜测序列：$j ← j + 1$。
     • 处理当前位置的验证结果：
       • if is_accept（Algorithm 4, 行 32-33）：如果当前位置的词元被接受，则继续验证下一个位置。
       • else（Algorithm 4, 行 34-38）：如果所有猜测在当前位置都被拒绝：
         • 从当前归一化后的分布 $P_j$ 中采样 (Sample) 一个词元：$sample x_{next} ∼ P_j$。
         • 将采样的词元添加到 $o$ 中：$o.append(x_{next})$。
         • 跳出外层 for 循环，结束验证。

4. 处理最后一个词元（如果所有猜测都被接受）：

   • if is_accept（Algorithm 4, 行 40-41）：如果所有猜测序列都被完全接受，并且没有提前结束，则从最后一个猜测位置的分布中采样 (Sample) 一个词元（即 $sample x_{next} ∼ D[1]_N$）并添加到 $o$ 中。

5. 返回接受的词元序列 $o$。

   Algorithm 2 提供了更通用的推测解码 (Speculative Decoding) 框架，它概括了猜测、并行验证和词元接受的流程。Algorithm 3 和 Algorithm 4 是 Algorithm 2 中“验证”步骤的具体实现，分别针对贪婪采样 (Greedy Sampling) 和采样 (Sampling)。

Algorithm 2: 具有贪婪采样的推测解码

输入：

• 序列 $\mathbf{x} = (x_1, x_2, \ldots, x_n)$
• 模型 $P_M$
• 最大 N-gram 大小 $N$
• 候选池 (Candidate Pool) 大小 $W$
• 最大猜测数 $G$
• 最大新词元数 $m$
• 精炼阈值 $\tau$

输出：

• $\mathbf{x}_{n+1:n+m} = (y_1, y_2, \ldots, y_m)$：生成的序列。

函数 SPECTRA_DECODING 步骤：

1. 初始化：
   • S_fwd ← ∅
   • S_bwd ← ∅
   • 初始化候选池 (Candidate Pool) $\mathcal{C}$ 中的词元 $c_j^{(i)}$。
   • $t ← n + 1$：当前生成词元的起始索引。
2. 主循环： $while t ≤ n + m$（Algorithm 1, 行 5-44）：循环直到生成目标数量的词元。
   • 获取猜测：
     • $g' ← S_fwd[x_{t-1}]$：从前向字典中获取以最后一个已知词元 $x_{t-1}$ 开头的猜测。
     • $u = ∅$：用于构建后向猜测。
     • $for j = 0 to N-1$：构建变长猜测。
       • $for k = N-1 to 1$：
         • $u_j ← S_bwd[x_{t+j-k:t-1} ⊕ u_{0:j-1}]$：从后向字典中构建高质量的猜测 $u$。
         • $break if found value for u_j$：一旦找到值就停止。
     • G.append(u)：将构建的 $u$ 添加到猜测列表。
     • G ← G ⊕ G_retrieve：检索集成 (Retrieval Integration) (可选)。将 SPECTRA-RETRIEVAL 的猜测添加到猜测列表。
     • $G ← G_{0:G-1}$：确保猜测数量不超过最大限制 $G$。
   • 前向传播与验证：
     • $Obtain necessary distributions of P_M in parallel.$：在 LLM 中并行获取所有必要的概率分布。
     • $hits ← VerificationFunction(x, P_M, G)$：调用适当的验证函数（Greedy verify 或 Sampling verify）来验证猜测。
     • x ← x ⊕ hits：将接受的词元 hits 添加到当前序列 $x$ 中。
     • t ← t + size(hits)：更新当前序列长度。
   • 预测候选词元：
     • $for i = 0 to W-1$：对于候选池 (Candidate Pool) 中的每个序列。
       • r ∼ Uniform[0, 1]：随机采样。
       • $P_c(c_{N-1}^{(i)}) ← P_M(c_{N-1}^{(i)} \mid c_{:N-2}^{(i)}, x)$：获取预测下一个词元的概率分布。
       • $if r > τ then$：如果随机数大于阈值 $τ$。
         • $c_{N-1}^{(i)} ← argmax P_c(c_{N-1}^{(i)})$：选择概率最高的词元。
       • else：否则。
         • $c_{N-1}^{(i)} ← argmax P_c(c_{N-1}^{(i)})$：选择概率最高的词元。
   • 更新 N-gram 字典：
     • $for i = 0 to W-1$：对于候选池 (Candidate Pool) 中的每个序列。
       • $for j = 0 to N-2$：
         • $S_fwd[c_j^{(i)}].append(c_{j+1:}^{(i)})$：更新前向字典。
         • $S_bwd[c_{0:j}^{(i)}] ← c_{j+1}^{(i)}$：更新后向字典。
     • $c_j^{(i)} ← c_{j+1}^{(i)}, ∀j ∈ [0, N-2], ∀i$：候选池 (Candidate Pool) 中的序列向左移动。
3. 返回生成的序列。

5. 实验设置

5.1. 数据集

实验评估了 SPECTRA 在多种生成任务上的性能，涵盖对话、数学推理和代码生成。

• LLM 模型:
  • LLaMA-2-Chat：7B, 13B, 70B 版本 (Touvron et al., 2023)。
  • CodeLlama：7B, 13B 版本 (Rozière et al., 2024)。
  • LLaMA-3-Instruct：8B, 70B 版本 (Dubey et al., 2024)。 所有模型检查点 (Checkpoints) 均来自官方或 Hugging Face 仓库，未进行微调或修改。
• 任务数据集:
  • 多轮对话 (Multi-turn Conversation): MT-Bench (Zheng et al., 2023)。
  • 数学推理 (Mathematical Reasoning): GSM8K (Cobbe et al., 2021)。
  • 代码生成 (Code Generation): HumanEval (Chen et al., 2021), MBPP (Austin et al., 2021), ClassEval (Du et al., 2023)。
• SPECTRA-RETRIEVAL 的外部语料库来源:
  • 对话任务 (MT-Bench): 从 UltraChat 数据集 (Ding et al., 2023) 中收集约 100k 个困惑度 (Perplexity) 最低的示例。
  • 代码任务 (HumanEval, MBPP): 从 TheStack (Kocetkov et al., 2023) 中选择 100k 个困惑度 (Perplexity) 最低的代码片段。

5.2. 评估指标

SPECTRA 是一种无损加速 (Lossless Acceleration) 方法，因此生成质量与原始 LLM 保持一致。评估主要关注加速性能和效率。

5.2.1. 加速比 (Speedup Ratio)

• 概念定义： 加速比 (Speedup Ratio) 是 SPECTRA 方法相对于标准自回归解码 (Autoregressive Decoding) 的速度提升倍数。它衡量了在相同任务和输出质量下，SPECTRA 能够缩短多少生成时间。数值越大，表示加速效果越好。
• 数学公式： $$\text{Speedup Ratio} = \frac{\text{Time}_{\text{Autoregressive}}}{\text{Time}_{\text{Speculative}}}$$
• 符号解释：
  • $\text{Time}_{\text{Autoregressive}}$：使用标准自回归解码 (Autoregressive Decoding) 生成相同序列所需的总时间。
  • $\text{Time}_{\text{Speculative}}$：使用 SPECTRA 推测解码 (Speculative Decoding) 生成相同序列所需的总时间。

5.2.2. 压缩比 (Compression Ratio) $\tau$

• 概念定义： 压缩比 (Compression Ratio) $\tau$ 是生成相同序列长度所需的自回归步骤 (Autoregressive Steps) 总数与 SPECTRA 推测解码步骤 (Speculative Decoding Steps) 总数之比。它是一个与具体硬件配置无关的指标，反映了 SPECTRA 每个解码步骤平均能“压缩”多少个词元 (Token)。数值越大，表示每次推测解码迭代接受的词元越多，效率越高。
• 数学公式： $$\tau = \frac{\text{Total Autoregressive Steps}}{\text{Total SPECTRA Decoding Steps}}$$
• 符号解释：
  • $\text{Total Autoregressive Steps}$：使用标准自回归解码 (Autoregressive Decoding) 生成相同长度序列所需的总步骤数。
  • $\text{Total SPECTRA Decoding Steps}$：使用 SPECTRA 推测解码 (Speculative Decoding) 生成相同长度序列所需的总步骤数。

5.2.3. 微观吞吐量 (Micro Throughput, Mic-TP)

• 概念定义： 微观吞吐量 (Mic-TP) 计算为生成的词元 (Token) 总数除以总耗时。它反映了系统在整个生成过程中平均每秒处理的词元数量。
• 数学公式： $$\text{Mic-TP} = \frac{\text{Total Generated Tokens}}{\text{Total Elapsed Time}}$$
• 符号解释：
  • $\text{Total Generated Tokens}$：在整个生成过程中生成的词元总数。
  • $\text{Total Elapsed Time}$：整个生成过程的总耗时。

5.2.4. 宏观吞吐量 (Macro Throughput, Mac-TP)

• 概念定义： 宏观吞吐量 (Mac-TP) 计算为每个生成步骤中词元处理速率 (Token Processing Rates) 的平均值。它更关注生成过程中的瞬时效率。
• 数学公式： $$\text{Mac-TP} = \text{Average}\left(\frac{\text{tokens}_i}{\text{time}_i}\right)$$
• 符号解释：
  • $\text{tokens}_i$：在第 $i$ 个生成步骤中接受或生成的词元数量。
  • $\text{time}_i$：完成第 $i$ 个生成步骤所需的时间。

5.2.5. ROUGE 分数 (ROUGE Scores)

ROUGE (Recall-Oriented Understudy for Gisting Evaluation) 是一组用于评估文本摘要和机器翻译质量的指标，通过比较模型生成的文本与参考文本之间的重叠来计算。

• ROUGE-1： 基于单个词元（unigram）的重叠。
• ROUGE-2： 基于两个连续词元（bigram）的重叠。
• ROUGE-L： 基于最长公共子序列（Longest Common Subsequence, LCS）。
• 概念定义： 这些指标衡量生成文本的连贯性、信息完整性和与参考文本的语义相似度。在采样解码 (Sampling Decoding) 设置下，ROUGE 分数用于验证 SPECTRA 是否能保持与原始模型相当的生成质量。

5.3. 对比基线

论文将 SPECTRA 与以下无需训练 (Training-free) 的推测解码 (Speculative Decoding) 方法进行比较：

• 标准自回归解码 (Standard Autoregressive Decoding): 作为所有加速性能的基准，其加速比 (Speedup Ratio) 定义为 $1.00 \times$。
• Adaptive N-gram (ANPD) (Ou et al., 2024): 一种利用自适应 N-gram 结构来生成推测词元 (Token) 的方法。
• REST (Retrieval-Based Speculative Decoding) (He et al., 2024): 一种基于检索的推测解码方法，通过预先构建的数据存储 (Datastore) 来查找猜测序列。
• Lookahead (Fu et al., 2024): 通过分析 LLM 的概率分布来推测后续词元 (Token)，并使用特殊注意力掩码 (Attention Mask) 并行验证的方法。

5.4. 实现细节

• 框架和库： PyTorch 2.1.0 和 Hugging Face transformers 库 (版本 4.36.2)。
• 模型精度：
  • 7B 和 13B 模型：使用 16 位浮点精度 (FP16)，并预分配键值缓存 (Key-Value Cache)。
  • 70B 模型：主要结果报告为 8 位量化 (Int8) 精度，附录中也提供了 FP16 精度下的评估。
• 硬件：
  • 大多数实验在一块 NVIDIA A100 GPU (80GB 内存) 上进行。
  • 为了分析硬件可扩展性 (Scalability)，还在 RTX 3090、RTX 8000、A40 和 A6000 等 GPU 上进行了测试。
  • 对于 FP16 精度下超出单 GPU 内存限制的最大模型（70B），通过 Hugging Face 的流水线并行 (Pipeline Parallelism) 在多块 GPU（2x, 4x 或 8x H100）上进行分布式计算。
• 超参数：
  • SPECTRA：
    • N-gram 设置：默认使用 5-gram。
    • 候选池 (Candidate Pool) 大小 $W$：每个键维护 15 个序列，用于生成新的 N-gram 记录。
    • 精炼阈值 (Refine Threshold) $τ$：默认设置为 0.1，用于词元选择 (Token Selection) 中的随机性机制，以增加前向字典的覆盖率。
    • 最大猜测数 $G$：每个推测解码步骤最多允许 15 个猜测。内部猜测具有优先级，如果未达到猜测限制，则添加外部猜测。
    • 外部查询：使用 Trie 结构进行快速前缀查询，设计类似于 REST。
  • 基线方法 (Lookahead, REST, ANPD): 均使用其原始论文中概述的默认设置和超参数 (Hyperparameters)。
• 其他设置：
  • 所有加速比 (Speedup) 和吞吐量 (Throughput) 指标均在批处理大小 (Batch Size) 为 1 的情况下计算。
  • 代码生成任务的最大生成长度通常为 512 词元 (Token)。
  • 对话任务 (MT-Bench, GSM8K) 的最大生成长度为 1024 词元 (Token)，或在模型输出序列结束词元 (End-of-Sequence Token) 时提前停止。
  • 所有随机种子均设置为 0。

6. 实验结果与分析

6.1. 核心结果分析

6.1.1. 整体性能

以下是原文 Table 1 的结果：

分析：

• 最高加速比： 在贪婪解码 (Greedy Decoding) 模式下，SPECTRA 持续实现最高的加速，在 Llama3-8B 上的 MBPP 任务中达到高达 $4.08 \times$ 的加速比。这表明 SPECTRA 的猜测机制能够非常有效地减少所需的前向传播次数。
• 对小模型效果显著： 对于 7B 模型，SPECTRA 通常能实现超过 $3 \times$ 的加速，这突出显示了其多词元压缩 (Multi-token Compression) 的有效性。
• 模型大小与加速： 13B 模型的加速比略低（$1.6 \times$ 至 $3 \times$），而 70B 模型的加速比（约 $1.7 \times$ 至 $2.4 \times$）相对较小。这可能与大模型的计算复杂度和其固有的推理瓶颈有关，但 SPECTRA 仍然能提供显著优于基线的加速。
• 稳健性： SPECTRA 在各种模型和数据集上都表现出稳健的性能，始终超越其他无需训练 (Training-free) 的推测解码 (Speculative Decoding) 方法，这归因于其优化的猜测质量 (Guess Quality) 和接受率 (Acceptance Rate)。
• REST 的局限性： REST 在许多任务上表现不佳，甚至在 GSM8K 和 MBPP 上出现加速比低于 $1.0 \times$ 的情况（例如 CL-13B 和 CL-7B），这可能是因为其外部检索机制的开销抵消了潜在的加速。
• 压缩比： SPECTRA 在所有测试数据集和 LLM 上均实现了最高的平均压缩比 (Compression Ratio)。每次草稿-验证 (Draft-and-Verify) 迭代通常产生 2.1-4.8 个词元 (Token)，几乎是 REST 接受长度的两倍。这直接解释了其更高的加速比。

6.1.2. 采样解码加速

• 在采样解码 (Sampling Decoding) 模式下（$temperature = 1.0$），SPECTRA 相对于标准自回归解码 (Autoregressive Decoding) 仍能提供约 $1.15 \times$ 至 $2.77 \times$ 的加速。
• 尽管加速效果不如贪婪解码 (Greedy Decoding) 显著，但这是预期的结果，因为采样解码 (Sampling Decoding) 的验证阶段 (Verification Phase) 接受率较低，与早期研究结果一致。这表明 SPECTRA 也能在更具随机性的生成场景下提供价值。

6.2. 消融实验/参数分析

以下是原文 Table 2 的结果：

分析：

• SPECTRA 各组件的贡献：
  • CORE Module（完整版）在 GSM8K 上达到了 $2.04 \times$ 的加速比 (Speedup) 和 2.50 的压缩比 (Compression Ratio)。
  • 移除前向字典 (Forward Dict) 后，性能显著下降到 $1.50 \times$ (GSM8K)，表明前向字典 (Forward Dict) 对生成猜测数量至关重要。
  • 移除后向字典 (Backward Dict) 后，性能略微下降到 $1.94 \times$ (GSM8K)，表明后向字典 (Backward Dict) 在提升猜测质量方面发挥作用。
  • 移除子 N-gram (Sub-Ngram) 更新机制后，性能降至 $1.95 \times$ (GSM8K)，这强调了包含子序列对字典覆盖率和猜测质量的重要性。
  • RETRIEVAL Module（独立运行）提供了 $1.18 \times$ (GSM8K) 的加速。
  • 移除困惑度精炼 (PPL refine) 后，性能略有下降，这验证了困惑度精炼 (PPL refine) 在提升外部猜测质量方面的有效性。
• 组合策略的重要性： Lookahead 与 REST 的朴素组合 (Naive Combination) 性能（$1.08 \times$ 在 GSM8K 上）显著低于 Lookahead 单独表现（$1.66 \times$），甚至低于 REST 单独表现。这有力地证明了简单地堆叠 (Stacking Naively) 两种技术是无效的，必须采用精心设计的集成策略，正如 SPECTRA 所做的那样。
• 整体优势： 完整的 SPECTRA 框架在 GSM8K 上达到了 $2.14 \times$ 的加速比 (Speedup) 和 2.64 的压缩比 (Compression Ratio)，优于任何独立组件或朴素组合，突出了所有组件协同工作的重要性。

6.2.1. 猜测来源的优先级

以下是原文 Figure 3 的结果：

分析：

• 内部猜测接受率更高： SPECTRA-CORE 模块（通过前向字典 (Forward Dictionary) 和后向字典 (Backward Dictionary)）生成的猜测比 SPECTRA-RETRIEVAL 模块（通过外部知识源）获得的猜测具有更高的接受率 (Acceptance Rate)。
• 优先级策略： 基于这一发现，SPECTRA 在 Algorithm 1 中优先使用 SPECTRA-CORE 的内部猜测，如果仍有猜测预算 (Guess Budget) 未用完，再补充 SPECTRA-RETRIEVAL 的外部猜测。这个优先级策略能够最大化每个推测解码 (Speculative Decoding) 步骤中被接受的词元 (Token) 数量。

6.2.2. FlashAttention 的影响

以下是原文 Figure 4 的结果：

分析：

• 普遍加速： FlashAttention 的启用普遍提高了所有方法的加速比 (Speedup)，尽管程度不同。
• SPECTRA 受益最大： SPECTRA 在 GSM8K 和 MTBench 上获得了额外的 $0.24 \times$ 加速比 (Speedup) 提升，这比其他方法更为显著。
• 原因： FlashAttention 能够更有效地利用推测解码 (Speculative Decoding) 的并行结构，通过减少注意力开销 (Attention Overheads)。由于 SPECTRA 提供了最长的验证分支 (Verification Branches)（即每次验证的词元数量最多），它从 FlashAttention 带来的更高效注意力计算 (Attention Computations) 中受益最大。

6.2.3. 词元接受率分析

以下是原文 Figure 6 的结果：

分析：

• 更少的解码步骤： Figure 6 展示了在不同数据集上，SPECTRA 与其他方法相比，在更少的解码步骤内累积了更多的被接受词元 (Token)。SPECTRA 的曲线明显更陡峭，例如在 MT-Bench 上，它比 ANPD 快了几乎两倍。
• 更高的接受率： 这种现象直接归因于 SPECTRA 拥有更高的词元接受率 (Token Acceptance Rate)。这意味着在每次推测解码 (Speculative Decoding) 迭代中，SPECTRA 能够成功验证并接受更多的猜测词元。
• 效率提升： 更高的词元接受率 (Token Acceptance Rate) 导致了更少的总解码迭代次数，从而显著提高了生成过程的效率和整体加速比。

6.3. 多 GPU 环境中的评估

以下是原文 Table 6 的结果：

分析：

• 稳健的可扩展性 (Scalability)：SPECTRA 在多种多 GPU 配置下，对 LLaMA-2-70B 模型（FP16 精度）实现了稳定的加速比，范围在 $2.00 \times$ 到 $2.03 \times$ 之间。同时，压缩比 (Compression Ratio) 保持稳定在 2.52 左右。这表明 SPECTRA 能够有效地扩展到大型模型和分布式推理场景，模型权重分区引入的额外开销很小，且推测验证 (Speculative Verification) 过程在跨 GPU 通信 (Inter-GPU Communication) 的情况下仍然保持高效。
• 量化设置下的表现： 即使在量化 (Quantized) Int8 单 GPU (1xH100) 设置下，SPECTRA 也能提供 $2.43 \times$ 的加速，优于标准自回归解码 (Autoregressive Decoding)。这验证了 SPECTRA 在内存受限部署中的实用性。

6.4. 生成质量验证

以下是原文 Table 7 的结果：

分析：

• 贪婪解码 (Greedy Decoding) 性能：
  • 在 FP32 精度下，SPECTRA 贪婪解码 (Greedy Decoding) 产生的输出与 Hugging Face 的标准贪婪搜索 (Greedy Search) 完全相同。
  • 在 FP16 精度下，SPECTRA 产生的差异（26 处不一致，共 160 个对话轮次）与 Hugging Face 原生贪婪搜索 (Greedy Search) 产生的差异（25 处不一致）相似。这表明 SPECTRA 在标准半精度推理库通常观察到的数值误差范围内，保持了输出分布。
• 采样解码 (Sampling Decoding) 性能：
  • 在采样解码 (Sampling Decoding) 设置下（$temperature = 1.0$），SPECTRA 在 CNN/DailyMail 和 XSum 摘要数据集上的 ROUGE-1、ROUGE-2 和 ROUGE-L 分数与标准自回归采样 (Autoregressive Sampling) 几乎相同。
  • 同时，SPECTRA 在这些任务上实现了显著的加速（CNN/DailyMail 为 $1.60 \times$，XSum 为 $1.69 \times$），且压缩比 (Compression Ratio) 分别为 2.05 和 2.08。
• 无损加速结论： 这些结果一致证实，SPECTRA 实现了对 LLM 推理的无损加速 (Lossless Acceleration)，无论是在贪婪解码 (Greedy Decoding) 还是采样解码 (Sampling Decoding) 模式下，都不会降低生成质量。

6.5. 详细吞吐量结果

以下是原文 Table 4 的结果：

分析：

• SPECTRA 的吞吐量优势： SPECTRA 在所有模型、数据集和贪婪解码 (Greedy Decoding) 以及采样解码 (Sampling Decoding) 模式下，始终保持最高的宏观吞吐量 (Mac-TP) 和微观吞吐量 (Mic-TP)。例如，在 CL-7B 上，SPECTRA 的 Mic-TP 普遍高于其他基线方法。

• 与其他加速方法对比： SPECTRA 的吞吐量 (Throughput) 明显高于自回归解码 (Autoregressive Decoding)，并且在大多数情况下也优于 ANPD 和 Lookahead。REST 在吞吐量 (Throughput) 方面表现最差，尤其是在 GSM8K 和 MBPP 等任务上，甚至低于自回归解码 (Autoregressive Decoding)，这再次证实了其外部检索带来的额外开销。

• 模型规模与吞吐量： 随着模型规模的增大（例如从 7B 到 70B），所有方法的吞吐量 (Throughput) 均显著下降，这是大模型固有的计算成本。但即使在 70B 模型上，SPECTRA 仍能提供最佳的吞吐量 (Throughput) 表现。

  以下是原文 Table 5 的结果：

  GPU	Method	GSM8K		MTBench
  		Mac-TP	Mic-TP	Mac-TP	Mic-TP
  A40	Autoregressive	32.66	32.66	32.14	31.66
  	Lookahead	48.59	48.73	49.13	47.96
  	SPECTRA	62.56	61.52	59.00	56.80
  A6000	Autoregressive	39.15	39.17	38.78	38.24
  	Lookahead	58.13	58.30	58.84	57.40
  	SPECTRA	75.20	74.16	71.30	69.28
  RTX8000	Autoregressive	34.03	34.27	34.21	34.02
  	Lookahead	45.25	45.42	45.73	44.16
  	SPECTRA	57.95	57.09	54.16	52.32
  RTX3090	Autoregressive	40.67	40.76	41.17	41.22
  	Lookahead	53.69	53.75	53.51	52.09
  	SPECTRA	74.87	73.88	71.58	69.79

分析：

• 硬件兼容性： SPECTRA 在不同 GPU 类型（A40、A6000、RTX8000、RTX3090）上都保持了领先的吞吐量 (Throughput)。无论 GPU 的内存带宽和计算能力如何，SPECTRA 都能提供比自回归解码 (Autoregressive Decoding) 和 Lookahead 更高的 Mic-TP 和 Mac-TP。
• 对旧 GPU 的适用性： 即使在较旧的 GPU（如 RTX3090 或 RTX8000）上，SPECTRA 的领先优势仍得以保持，这表明其优化方法在不同硬件世代上都有效。在这些 GPU 上，Lookahead 和 SPECTRA 之间的差距可能略有缩小，这可能是由于并行效率的差异，但 SPECTRA 始终保持领先。

7. 总结与思考

7.1. 结论总结

本文提出了 SPECTRA，一个新颖的无需训练 (Training-free) 框架，通过优化内部 (Internal) 和外部 (External) 推测 (Speculation) 来加速大语言模型 (LLM) 推理。

• SPECTRA-CORE 模块利用多级 N-gram 存储和双向搜索 (Bi-directional Search)，并结合候选池 (Candidate Pool) 动态更新机制，高效地从 LLM 内部知识生成高质量猜测。
• SPECTRA-RETRIEVAL 模块通过困惑度精炼 (Perplexity Refinement) 外部语料库，提供高质量的外部猜测，并能与 SPECTRA-CORE 无缝集成。
• 在各种基准测试和 LLM 架构上，SPECTRA 实现了高达 $4.08 \times$ 的显著加速比，同时作为一种无损加速 (Lossless Acceleration) 方法，完全保留了原始模型的输出质量。
• SPECTRA 在不同 GPU 类型和多 GPU 环境中均表现出强大的稳健性 (Robustness) 和可扩展性 (Scalability)，并且与 FlashAttention 等加速工具兼容，进一步提升性能。

7.2. 局限性与未来工作

论文作者指出了 SPECTRA 的以下局限性：

• 构建外部数据存储的成本 (Cost of Building External Datastores): 虽然 SPECTRA-CORE 不依赖外部数据，但 SPECTRA-RETRIEVAL 需要从大型语料库中构建和索引一个庞大的外部数据存储 (Datastore)。这个过程可能非常耗时且占用大量内存，尤其是在数据更新频繁或存储受限的领域。虽然这种投资能带来显著加速，但并非普遍可行或具有成本效益。
• 有限的评估范围 (Limited Evaluation Scope): 实验主要集中在英语基准测试中的对话和代码生成任务，并使用了 LLaMA 系列模型。虽然 SPECTRA 原则上适用于其他模型或语言，但特定领域 (Domain-specific) 的词元化 (Tokenization) 或特殊的文本结构可能会影响接受率 (Acceptance Rate) 和整体加速效果。未来工作需要评估 SPECTRA 在不同语言环境（例如低资源语言 (Low-resource Languages) 或专业技术文档）和更广泛的模型家族（超出 LLaMA 架构）中的通用性 (Generality)，以确认和完善其适用性。

7.3. 个人启发与批判

7.3.1. 个人启发

1. 无需训练的巨大优势： SPECTRA 再次强调了无需训练 (Training-free) 方法在 LLM 推理加速中的巨大实际价值。它规避了训练草稿模型 (Draft Model) 的高昂成本和模型管理复杂性，使得即插即用 (Plug-and-play) 成为可能，这对于快速迭代和部署至关重要。
2. 内部与外部知识的巧妙结合： SPECTRA 成功地将 LLM 自身的词元分布 (Token Distribution) 知识与经过精炼的外部知识源相结合，实现了“1+1>2”的效果。SPECTRA-CORE 通过双向 N-gram 字典 (Bi-directional N-gram Dictionaries) 动态生成高质量猜测，而 SPECTRA-RETRIEVAL 则通过困惑度过滤 (Perplexity Filtering) 确保外部知识的有效性，这种分而治之再合而用之的策略非常值得借鉴。
3. 困惑度过滤的实用性： 使用困惑度 (Perplexity) 来筛选外部语料库是一个非常实用的方法。它利用了目标 LLM 自身的语言建模能力来评估外部文本的“质量”或“相关性”，从而确保了外部猜测与模型本身的风格 (Style) 和内容 (Content) 保持一致，避免了引入低质量猜测而拖慢推理的情况。
4. 工程优化细节： 论文在工程细节上做得非常出色，例如在单次前向传播 (Single Forward Pass) 中并行获取所有所需分布、利用特殊注意力掩码 (Special Attention Mask)、以及FlashAttention 的集成，都体现了对硬件特性和计算效率的深刻理解。

7.3.2. 批判

1. 外部数据存储的维护挑战： 尽管论文承认了外部数据存储的成本，但其维护 (Maintenance) 和更新 (Update) 在动态变化的领域（如新闻、实时代码库）中仍是一个实际挑战。如何自动化和优化这个过程，确保Trie 结构始终反映最新、高质量的信息，是实际部署中需要进一步解决的问题。
2. $τ$ 参数的鲁棒性分析： SPECTRA-CORE 中引入的精炼阈值 (Refine Threshold) $τ$ 用于平衡词元选择 (Token Selection) 中的探索性与贪婪性。论文将其默认为 0.1，但这个参数的最优值可能依赖于具体的模型、任务甚至生成阶段。缺乏对其敏感性和自适应调整 (Adaptive Adjustment) 机制的更深入分析，可能限制其在不同场景下的最佳性能。
3. 多级 N-gram 的空间效率： 论文通过包含子 N-gram 来提高字典覆盖率，但这可能导致 N-gram 字典的空间占用 (Space Consumption) 快速增长。尤其是在处理非常大的词汇表或非常长的 N-gram 时，字典的大小可能成为内存瓶颈。虽然这有助于猜测质量，但需要在内存效率 (Memory Efficiency) 方面进行进一步的权衡和优化。
4. 验证效率的极限： 尽管 FlashAttention 带来了显著提升，但推测解码 (Speculative Decoding) 仍然受到每次前向传播 (Forward Pass) 所能验证的词元数量上限的限制。对于需要生成极长序列的场景，即使是最高的压缩比 (Compression Ratio) 也可能无法满足极低延迟的要求。探索除了注意力机制 (Attention Mechanism) 优化之外，如何进一步提升验证步骤 (Verification Step) 的并行性和效率，仍是未来研究方向。
5. 跨语言和模型泛化性的进一步验证： 论文提及了其在英语 LLaMA 系列模型上的评估范围有限。未来的工作需要通过更广泛的实验来证实 SPECTRA 在非英语语言、不同词元化 (Tokenization) 方案、以及其他 Transformer 架构变体（例如循环神经网络 (Recurrent Neural Networks) 或状态空间模型 (State-Space Models)）上的泛化性 (Generalizability) 和有效性。