LLM 推理是一个数十亿美元的问题。 我们的新论文介绍了一种在多草稿推测采样中的 SOTA 算法——全球分辨率，显著解决了这个问题。 下面详细说明 🧵👇

一种高效推理的方法称为推测采样。 这使用一个便宜的“草稿”模型来产生对更大目标模型可能输出的“猜测”。

通过利用现代GPU的并行效率，这可以将目标模型的前向传递次数减少超过5倍。

投机性采样可以推广到从多个草稿模型中获取多个猜测。 但目前尚不清楚结合这些多个猜测的最佳算法是什么。

在单步情况下，先前的研究表明，最优解可以通过求解最优运输线性规划（OTLP）来找到。

然而，OTLP在词汇量增长时极其难以近似精确地解决。那么我们该如何解决它呢？

关键在于利用草图树构建中的额外结构。

之前的工作[Hu et. al.]显示，当草图树通过独立同分布采样形成时，通过对偶化OTLP，可以通过子模最小化在近线性时间内计算出最优目标值。

然而，在我们的工作之前，没有任何方法能够解决实现这一最优目标值的方案。没有这一缺失的部分，所有以前的工作只给我们提供了区块效率，即理论上的最大加速。这并没有告诉我们如何实现这种加速。

我们的工作是首次显著降低OTLP的维度，利用了三个见解。

我们通过互补松弛逆转了之前工作[Hu et. al.]中的OTLP双重化，将OTLP表述为流可行性问题。

许多流不等式约束是多余的。利用多项体理论中的贪心算法，我们可以将这些约束合并。

这个减少流动问题的解决方案可以参数化为低维向量的softmax，而这个向量可以通过凸最小化计算得出。 这将OTLP在V^{n+1}变量中简化为V变量的凸最小化问题。

然而，V 仍然可能相当大，因此在我们的论文中，我们应用了更多的近似方法，并设定了有界的目标模型误差率，以进一步减少计算时间。

在许多情况下，V 限制为 top-k 和 n 个草稿模型，如上所示，Global Resolution 是唯一能够在合理时间内解决 OTLP 的求解器。

此外，通过使用全球解析，我们可以将 Llama 和 Gemma 的接受率提高多达 6%： 简而言之，全球解析在投机解码中的最佳多草稿验证方面是 SOTA。

这里仍然有很多工作要做，可以通过放宽独立同分布的设置，或者扩展到多个步骤。