LLM Decode不需要Beam Search——理解LLM输出的序列空间
TLDR
输出序列的序列总概率的性质并非我们所想，对于区分语义的可靠性几乎没用，beam search在此场景也没有用。
1、回顾 LLM 的 Decode
1.1、贪心解码
LLM是一种语言模型，在将序列映射到token层面后建模条件概率，也就是建模下一个token的条件概率。既然是一种局部的概率生成模型，那么就可以对其能够输出的整个空间做探索，最简单和常用的方式就是每次贪心的选择概率最大的一个token来逐步探索，这也被称作贪心解码或者temperature=0。
但相对于其他领域来说，LLM的应用中对于贪心解码的使用倾向要弱很多，目前主要使用的场景大致有：
【R1】Benchmark中
【R2】希望输出无随机性的场景中，（虽然现在不少API不保证也无法实现这点）
【R3】希望通过通过倾向于更高概率token来提升结果的准确性。
而我对以上几种使用方式都颇有微词。R2的问题我之前在 2024Q1再谈商用LLM的输出随机性 V2 中已经讨论过，而本文则是部分否定了R3的效果。如果都没有太多需要使用贪心解码的场景，那么在benchmark中采用较小的temperature也就没有太多意义了。
1.2、Beam Search
Beam search是贪心解码的一个自然扩展，通过在探索过程中保存更多的状态来试图寻找更高概率的输出序列，并可以给出已经探索到的Top K的序列。
在对语言模型不足够熟悉的人来看，beam search似乎是个挺不错的方案，概率越大的序列正确的概率也最大，目前贪心解码输出的结果在实际应用中正确率（符合期望率）还不够高，那么通过beam search寻找更高概率的序列，以及召回剩下其他概率较高的序列应该都可以作为更正确答案的候选。“这似乎可以作为一种降低LLM幻觉的方式”。
但实际用过beam search做序列生成的人会知道，在一些条件下它并不能实现期望的目标：
【C1】序列的粒度太过细碎，且对于同样的内容的表达方式很多时
【C2】整个生成的空间太大，且中间包含一些小概率的局部“山峰”
C1会导致beam search的探索过程陷入到同一个语义的很多不同表达方式的探索上，这些同样语义的序列数量随着序列的长度增加而成指数上升。C2会迫使beam search优先把概率更低的不完整序列都探索完，直到山峰的代价成为所有探索路径中比较小的才能继续探索，类似于只有水填满了环形山后，它才能从环形上上的某个缺口溢出。
很遗憾的是，LLM decode的场景同时满足C1和C2。这也是我一直说目前的token并不是一个好的表示方式的原因，我目前也确实没有替代方案。
那么这就是在LLM Decode中beam search不值得使用的原因么，C1、C2以及成本较高？本文接下来有一个不同的回答。
2、实际体验LLM输出的序列空间
以上都是一些理论分析，但实际上LLM输出的空间到底是什么样的，却很少有人进行测试和公开讨论。我唯一看到的是在1年多前知乎上的 空门（https://www.zhihu.com/people/nullgate） 的一些数值实验，但他主要关注的是序列的信息熵和量化、微调等对信息熵的影响等方面，并没有太多关注空间的探索和语义方面。
那么我们应该实际观察一下LLM输出的序列空间到底是什么样的。
2.1、准备工作
从去年到现在，我们有了比较好的小规模中文模型（例如GLM-4-9B、Qwen2-7B），也有了低成本的推理加速框架vLLM，云端算力的租用市场也很成熟，早就可以开始做这方面的实验了。
但目前仍然缺少一个可以较为完整和低成本的探索输出序列空间的工具。所以我基于vLLM做了一些定制，简单做了一套用来探索整个输出空间的方案。这个简单的框架开源在
https://github.com/SomeoneKong/llm_decode_space
方案细节和使用经验放在本文末尾的附录中，减少对于读者阅读的影响。
至此，做一些简单的实验的成本已经很低，有兴趣的同学可以基于我的方案去探索一些自己的想法，云端租一个卡的成本已经很便宜了。vLLM目前不支持Windows，无法在家用PC上拿自己显卡来玩是唯一的缺憾。
2.2、实验结果
我的实验基于GLM-4-9B-Chat的未量化版本进行。
【序列的空间远比预想的还要大的多】
虽然一般我们只考虑top_p的token，在实际场景中每个位置的token选择很少，不少位置只有一个选项，但即使如此能够采样出序列也是极多的。
例如我测试的一个开放性的问题，回答平均有300 token长，采样了1200条序列只能覆盖所有可能性的10^-25，连说这是九牛一毛都不合适。
【Token序列的概率显著与语义概率偏离】
在茫茫多的输出结果中，两个序列的概率即使差几十甚至上百个数量级，他们表达的语义也可能是非常相似的。做实验前大家可能会觉得虽然Token序列的概率是会偏离语义的，但好歹还能看出某种正相关。但实际上这种相关性是看不到的，同样语义的序列的概率可以分布在一个非常大的范围内。
即使把temperature开到1，把top_p和top_k的限制都放开，在【实际能抽样出的序列】集合中语义和序列概率几乎没有任何关联。即使一些关键token处的概率能够与结果正确率有某种关系，这些信息也完全被序列中其他语义不关键的内容的概率完全摊平了，甚至都不是能够主导总体概率的因素。
【语义多样性非常小】
与序列的多样性极多形成对比的是，这些多样的序列的语义差别很小，可以说（在给定prompt的条件下）LLM很不擅长生成多样性。
这很符合我们对LLM这种概率模型和decode方式的某种直觉：这种模型学到的一般都是某种平均效果，例如“基于所有人脸的数据，得到一个模型只能生成某些有代表性的平均脸”，使用中使用temperature<1和限制的top_p和top_k都进一步加剧了这种只生成平均结果的趋势。
但与直觉不同的是，LLM decode可以生成很多样的token序列，但只是它们的语义都非常单调。
【Token的n-gram很少重复】
如果语义很接近，而序列很多，那么是否这些序列中有很多重复的token片段，只是被以不同的顺序和不同的中间口水词连在一起了呢？
从我的实验结果来看并不是，LLM是语义的“复读机”，但并不是token chunk的复读机。想要在输出空间上重新做一个该prompt下的更粗粒度的token词表并不能有效的覆盖所有输出序列。
2.3、总结
Token序列的概率与语义没有任何相关性
Token序列的空间很大，Token chunk（n-gram）也很少重复
输出序列中语义的多样性很小
3、如何理解这些现象
3.1、序列的概率是一个糟糕的metric
从实验结果来看，毫无疑问序列的概率与我们期望的目标没有任何关联。但这是为什么呢？
我对此有几方面的解释：
输出结果中可以或多或少的掺入一些承上启下的内容、格式性的内容甚至跑题的内容，这些内容几乎不会影响序列结果的语义，但因为其涉及的token较多所以会显著的影响序列整体的概率。
语言的表达方式是很多样的，LLM建模了这些多样性，但当在一个位置有多种语义接近但都是常用的表达方式出现时，每种token的概率都被摊低了，虽然不影响语义，但却影响了token概率的计算。毕竟token序列的概率是对于token的，这里包含了对于表达方式的建模，我们想把它当作语义的metric只是一厢情愿。
也有文章试图提出更好的metric，例如
Chain-of-Thought Reasoning Without Prompting
https://arxiv.org/abs/2402.10200
这个文章也认为token的概率本身影响不大，更重要的是Top-1的token与Top-2的token的概率差，这体现了LLM的“自信程度”。我相信这会有一些改进，但它仍然无法应对因为措辞多样性而带来了的token概率被不同表达方式分摊导致的问题。
3.2、LLM的语义纠偏能力 与 语义多样性
输出结果的语义多样性较低，这还大致能够接受，但LLM似乎能在不同的回答前缀中产生同样语义的回答，这就有点意外了。
一种简单的解释是：LLM具有把不同的回答前缀都逐步调整回某些它默认会产生几种语义上的能力，而且这个能力比我想象的还要强。我之前曾倾向于回答前缀中的某些细微措辞差异可能会在后续引入一些新的相关性而导致后续输出结果导向不同的语义。但目前来看这种效果可能并不强，更主要的受到了LLM本身能输出的语义多样性较少的影响。究其原因，应该是仍然受到prompt中其他token的主导。
不可否认的是，LLM的输出过程确实会在某些关键位置由于采样的问题导致语义的分叉，例如不该引入的地方引入了一个否定词，由于LLM decode不能回退的因素（它也不知道何时该回退），会导致后续输出的语义显著不同。但从控制的角度上来说，几乎无法实现确定某次采样过程中哪些位置的token是这种语义关键的token，以及该如何在此时进行选择。
4、推论
4.1、Self Consistency
在LLM decode中，即使使用贪心解码，也不能保证LLM计算的每个token位置的最大概率都是我们所期望的。而允许输出非最大概率的token，似乎也不太会影响对于结果语义的生成。过程中确实与某些因素有影响，但这是我们很难事先了解和干预的，简单的靠是否选择概率最大的token这样的decode方式对此的效果贡献并不多。
从这个角度上来说就有了一种新的思路：多次抽样生成序列，然后对他们的语义结果进行投票取最多的。这种方式能够通过多次采样的方式平均掉一些偶然的关键token上犯错的影响。
所有简单且有用的方式都已经被发现了，这个方式在
https://arxiv.org/abs/2203.11171 中就已经提出了类似的。
4.2、多次抽样的有效方式
从以上内容来看，如果需要多次抽样不同的生成序列，已经没必要用beam search类的方案，也没有必要对于高概率的序列做太多倾斜，直接独立的多次进行随机抽样就好了。
恰巧这是一个已经被实现的功能，就是OpenAI API的【n】参数。OpenAI API并不提供beam search，而是仅仅提供了 n 参数，也不知道是他们早就已经认知到了这就是beam search的最佳替代（成本更低但效果接近），还是只是一个偶然的误打误撞。
5、结语
本文只是Decode输出空间探索的一个阶段性结果，但这其中确实发现了一些出乎我意料的、大概也是出乎大家意料的结果。
希望这能引发更多的人在对LLM输出空间的理解和decode阶段工作的兴趣。
附录 A、探索方案的细节说明
https://github.com/SomeoneKong/llm_decode_space
项目的基础功能是为了高效的探索给定prompt时LLM可能输出的整个序列空间。后续可以基于此方案做一些decode策略的实验。
A.1、对LLM API的特殊需求
【top_logprob】
很多LLM API输出是不带有概率信息的，这个概率信息虽然可以靠很多次抽样来统计，但更好的方式是像OpenAI的top_logprob功能一样直接由API给出，这个的成本也是较低的。从我目前的测试来看，top_logprob目前大家设置的20上限也不太够用，想要完整的覆盖各种情况的话，建议给到100。
【基于token id指定的Partial mode】
剩下是在某个前缀下继续生成的能力，虽然它有点像是大家已经逐渐废弃的completions接口，但也不完全是。completions还需要配合chat template才可以。目前我看到的最接近的功能是moonshot的partial mode。
但partial mode也不能完全实现，因为同一个字符串可能有多种encode方式，如果LLM以非最短的方式输出了某个序列，光靠partial mode就无法完全模拟了。所以仍然需要直接以token id方式指定的前缀的能力。
现在流行的方式是提供token_count API，而不是直接提供token词表，也许是为了一定保密方面的考虑。对此我的建议是可以对token_id做重新映射之后在response时提供给用户，用户可以以某些token id重新要求继续续写。只要映射后的token_id不连续，很难估计token词表大小、很难以某种方式遍历所有词表token就行了。
【对vLLM的定制】
vLLM支持top_logprob功能，但对于后者是不支持的，所以我对vLLM的OpenAI compatible server做了一些修改使其能支持。虽然我已经尽量对齐了各种因素，但仍然发现从概率上来说与原始生成过程还有微小差异，原因未知，好在这对整体实验的影响不大。
除此之外还做了一些必要的小功能的增加，可以参考我vLLM定制版本的commit。
A.2、探索过程的控制
如果不对小概率长尾token进行截断，那么整个输出序列空间是大的吓人，也显著脱离了实际使用场景。对token的截断进行控制的最好方式还是跟LLM decode一样的使用temperature、top_p、top_k来实现。
不过vLLM的temperature、top_p、top_k会影响输出的top_logprob，即top_logprob是在vLLM的token截断之后重新归一化的，这与本方案的追求的目标有差异，需要注意。所以本项目使用了收到结果后手工的top_p截断，没有使用top_k。经过测试，vLLM在temperature=0时，会给出与temperature=1时一样的top_logprob。
由于beam search在本场景已经意义不大，所以我采用的是模拟重新抽样的过程。为了避免重复计算，每次会选择概率最大的未探索到EOS的叶子节点进行继续探索。
为了加速整个探索过程，不是每次展开一级叶子节点，而是按照LLM的常规方式直接抽样到EOS，并记录中间所有节点的token分布，对于其他分支可能性产生新的节点进行代表。
任务量采用token概率空间的调整参数（temperature、top_p）和最大LLM调用次数进行控制，并支持“Ctrl+C取消剩余任务输出已完成部分的结果”的方式进行人工干预。
交流与合作
如果希望和我交流讨论，或参与相关的讨论群，或者建立合作，请私信联系，见 联系方式。
本文于2024.7.4首发于微信公众号与知乎。
知乎链接 https://zhuanlan.zhihu.com/p/707076469