在llama.cpp中提示查找草拟速度提高42倍 Hayder Tirmazi [主页] [github] [推特] 本文最初发表于2026年09月26日。摘要：我通过一系列简单的性能优化，使提示查找解码的草拟速度提高了42倍，同时使用的内存减少了2.6倍，这些优化主要基于Daniel Lemire和Martin Ankerl的工作。更新：Daniel Lemire提交了一个PR，使得在我原有优化的基础上，提示查找草拟速度提高到4.2倍。他的工作使整体加速达到140倍。以下我将进一步讨论。许多流行的推理引擎，包括llama.cpp和vllm，以及机器学习库，例如hugging face的transformers库，支持提示查找解码（也称为n-gram推测），以加快令牌生成。提示查找解码在技术上是推测性解码的一个特例，它使用一个非常简单的草拟模型，即n-gram模型。当使用提示查找解码时，推理引擎使用以下规则草拟下一个$k$个令牌。设$x_1, ext{…}, x_t$为模型的当前令牌。n-gram是由$n$个连续令牌组成的序列。例如，一个3-gram可以是$(x_1, x_2, x_3)$或$(x_2, x_3, x_4)$，或一般的$(x_i, x_{i+1}, x_{i+2})$，对于任何$i ext{在} ext{1到} (t - 2)之间$。现在，一个n-gram模型是一个概率模型，它根据之前的$n - 1$个令牌预测下一个令牌。这个想法非常简单。您首先选择一些文本语料库并将其解析为n-gram。然后，您统计每个n-gram的频率。当您的n-gram模型需要预测在一系列$n-1$个令牌之后的下一个令牌时，您使n-gram模型选择最常见的在您的语料库中跟随该序列的$n-1$个令牌的令牌。llama.cpp维护三种类型的n-gram缓存。设$ au$为任何n-gram，$y$为任何令牌。n-gram缓存是一个数据结构，它存储$c( au, y)$，即令牌$y$跟随n-gram$ au$的次数，对于给定的语料库和词汇表中的所有n-gram$ au$和所有令牌$y$。llama.cpp使用的三种n-gram缓存分别为上下文缓存、动态缓存和静态缓存。llama.cpp的上下文缓存存储当前正在被模型处理的令牌$x_1, ext{…}, x_t$的1到4美元的n-gram。上下文缓存在模型生成新的令牌时更新。动态缓存存储模型先前运行(n之前的对话等)的n-gram的计数。最后，静态缓存存储从静态文本语料库中提取的大小为2的n-gram，使用llama-lookup-create构建。我用$c_{ ext{ctx}}$、$c_{ ext{dyn}}$和$c_{ ext{st}}$分别表示上下文、动态和静态缓存。llama.cpp以以下方式使用其n-gram缓存草拟新令牌。设$X_n = (x_{t-n+1}, ext{…}, x_t)$为模型处理的以前$n$个令牌。对于词汇表中的所有令牌$y$，llama.cpp使用公式计算分数$$s_n^{f}(y) = f(X_n, y) ullet w(y) ext{其中} w(y) = egin{cases} 100 ullet c_{ ext{st}}(X_2, y) & ext{如果} c_{ ext{st}}(X_2, y) > 0 \ 1 & ext{否则} ext{注意}