没有沟通的耦合与草稿不变的推测解码

在现代的算法研究中，耦合问题一直是一个颇具挑战性的领域。尤其是在没有任何通信的情况下，如何让两个独立的参与者（假设我们称他们为爱丽丝和鲍勃）从各自拥有的分布中生成相同的样本，是一个引人入胜的难题。本文将探讨“没有沟通的耦合”这一问题的深度及其实际应用，尤其是在加速自回归语言模型中的推测解码技术。

引言

动机

设想一下：爱丽丝拥有分布 \mathcal{P}，而鲍勃则掌握分布 \mathcal{Q}。他们的目标是从各自的分布中生成样本 a \sim \mathcal{P} 和 b \sim \mathcal{Q}，使得 a = b 的概率尽可能高。在允许通信的情况下，这一问题的解决方案显而易见——他们可以通过构建一个最优的耦合来实现。然而，若没有任何通信，这一目标的实现就变得复杂起来。

根据研究，尽管没有通信，爱丽丝和鲍勃仍可以利用公共随机性（例如，随机数生成器）来接近这一目标。具体而言，如果他们能够使用一种简单的协议，比如加权 MinHash 算法或 Gumbel 采样方法，他们便能在没有直接沟通的情况下生成相似的样本。

沟通自由的协议

加权 MinHash

首先，我们来看加权 MinHash 方法。该方法基于一种简单的随机采样策略，允许爱丽丝和鲍勃各自从他们的分布中独立采样，同时利用预先生成的随机数来增加 a = b 的概率。研究表明，使用这种方法，爱丽丝和鲍勃可以达到以下概率界限：

其中 D_{\mathrm{TV}}(\mathcal{P}, \mathcal{Q}) 是两者分布之间的总变差距离。这一结果显示，即使在没有沟通的情况下，通过合适的随机抽样策略，仍然可以获得相对较高的相同样本生成概率。

Gumbel 采样

接下来，我们讨论 Gumbel 采样。这是一种广泛应用于机器学习中的方法，通过从 Gumbel 分布中抽样，可以将离散分布的采样问题转化为连续分布的采样问题。使用 Gumbel 采样，爱丽丝和鲍勃能够以类似的方式独立生成样本，且同样可以达到上述的概率界限。

这些协议的最优性

在研究这些无沟通协议的最优性时，我们发现无论是加权 MinHash 还是 Gumbel 采样，在最坏情况下都无法超过上述概率界限。这意味着在没有任何信息共享的情况下，爱丽丝和鲍勃的相似样本生成概率是受限的。

此外，通过对这些协议的深入分析，我们能得出结论：使用公共随机性可以使得相同样本生成的概率接近于最优耦合所能达到的概率。这一发现为没有沟通的耦合问题提供了新的视角，并为未来的研究方向奠定了基础。

应用：草稿不变的推测解码

在机器学习的实际应用中，我们将这一理论结果应用于一种称为“推测解码”的技术中。推测解码是一种通过小型神经网络来加速大型自回归语言模型（如 GPT-4）的推理过程的方法。它通过预测即将生成的多个 token 来实现这一目标。

然而，推测解码存在一个潜在的问题：如果草稿模型发生变化，那么生成的结果也会发生变化。这在需要固定输出的应用场景中是不可接受的。为了解决这个问题，我们提出了一种新的方法，称为“草稿不变的推测解码”。该方法利用无沟通的耦合协议，使得生成的输出与所使用的草稿模型完全无关，从而确保了在同一随机种子下的输出一致性。

结论

我们的研究表明，即使在没有通信的情况下，通过合适的随机抽样协议，依然能够实现高概率的样本耦合。更重要的是，这一理论结果在实际应用中显示出了巨大的潜力，尤其是在推动语言模型推理过程的高效性和一致性方面。

参考文献

1. Majid Daliri, Christopher Musco, Ananda Theertha Suresh. Coupling without Communication and Drafter-Invariant Speculative Decoding. arXiv:2408.07978v1, 2024.
2. Leviathan, Y., Kalman, M., & Matias, Y. (2023). Fast inference from transformers via speculative decoding. In Proceedings of the 40th International Conference on Machine Learning (ICML).
3. Gumbel, E. J. (1935). Les valeurs extrêmes des distributions statistiques. Annales de l’institut Henri Poincaré, 5, 115-158.
4. Wu, Y. (2020). Information-theoretic methods for high-dimensional statistics. Lecture notes, Yale University.
5. Chen, C., et al. (2023). Accelerating large language model decoding with speculative sampling. arXiv:2302.01318.

通过对这些技术的深入分析，我们期待在未来的研究中，能够进一步提升无沟通耦合的效果，并探索其在更多领域中的应用。