一、引言 现代研究发现，训练大语言模型（LLMs）时增加计算量会带来更好的结果，但在推理时增加计算量的好处却较少被关注。本文聚焦于推理时的方法，探讨了令牌级生成算法、元生成算法和高效生成这三个主题。

二、相关概念及背景 1、用户目标在生成中的作用：用户使用语言模型生成输出时，可能希望获得高质量、多样化的输出，例如解决数学问题的正确答案或符合事实且写得好的总结。为了形式化这个目标，我们引入了“可接受性”的概念，即用户对输出的满意度，并将生成输出的过程看作是从语言模型的分布中采样，以尽可能接近用户的满意度分布。2、语言模型的建模问题：语言模型是对序列的概率建模，通常采用自回归的方式，即根据前面的令牌预测下一个令牌的概率分布。生成模型与语言模型相关联，它将输入、语言模型和其他参数映射到输出的概率分布。计算这个概率分布在大多数情况下是分析上难以处理的，通常需要使用生成算法来获得样本。我们将生成方法分为最大化、采样和从指定目标分布采样三类。

三、令牌级生成算法 1、MAP解码算法：选择语言模型定义的分布中最有可能的序列，如贪心解码，但贪心解码可能会导致结果不完美，如重复序列或短序列偏好等问题。2、采样和适配器：直接从语言模型的分布中采样，如祖先采样，同时为了平衡多样性和连贯性，引入了一些采样适配器，如温度采样、核采样等。3、令牌级采样适配器：许多令牌级采样方法可以看作是调整每个下一个令牌分布的采样适配器，还包括一些使用其他模型输出重加权令牌的方法，以及为了控制统计和信息论性质的自适应和前瞻适配器，还有使用另一个语言模型调整下一个令牌分布的方法。4、受控生成：许多场景可以被框架为从语言模型的分布中采样，该分布由序列级标准调制，例如通过分类器、指示器或奖励来实现。

四、元生成算法 1、链式元生成器：通过将多个生成器链接在一起，例如在提示语言模型中，通过组合不同的操作和生成器来完成任务，如解决数学问题或生成故事。2、并行元生成器：包括reranking算法（如Best-of-N）、transformation算法（如Majorityvoting、Self-consistency等）和sequence-levelstatisticalrejectionsampling。3、步级搜索算法：通过调用生成器来实现经典搜索算法，如greedydecoding、beamsearch、stepwisebeamsearch、Tree-of-thoughts等，用于解决数学问题或定理证明等任务。4、细化算法：由初始生成器、信息源和细化器组成，通过接收信息和细化输出，直到满足停止条件，如Self-correction和Promptedrefiners等。

五、引入外部信息 1、多个模型：许多生成算法结合了多个模型，如使用小语言模型调整大模型的分布或加速生成，学习验证器模型来选择输出，以及通过提示参数化不同模型。2、外部环境信息：生成算法可以结合外部环境信息，如调用外部工具进行计算或验证，接收环境观察结果，例如在代码生成中使用执行结果或在数字代理中结合环境信息。

六、令牌成本和性能分析 1、令牌预算：元生成器的成本包括输入令牌、输出令牌和外部信息的成本，不同的元生成算法在成本上有所不同，例如step-levelsearch和sequence-levelsearch在成本上的差异，以及refinement与sequence-levelsearch的成本比较。2、增加令牌预算以提高性能：在许多推理相关任务中，生成多个序列并从中选择的算法（如Best-of-N、Majorityvoting等）通常比生成单个序列的算法（如贪心解码）性能更好，随着生成预算的增加，这些算法的性能可以单调提高。3、最小化令牌预算：一方面可以通过将生成路由到成本逐渐降低的模型来减少令牌预算，另一方面可以利用特定元生成算法的性质来减少调用次数，从而降低成本。4、对底层生成器的依赖：元生成器的性能依赖于底层的生成算法，例如采样参数的选择会影响性能，不同的元生成算法对底层生成器的依赖程度不同。

七、加速生成 1、背景：加速生成需要平衡延迟、吞吐量和质量三个指标，硬件是加速生成的关键考虑因素，不同的硬件环境对性能有重要影响。2、加速生成器：可以通过修改模型架构、压缩模型、进行硬件感知的实现或并行化来加速单个生成的时间，例如使用更高效的注意力机制、量化模型权重或激活、利用硬件特性进行优化或采用并行解码策略。3、加速元生成算法：利用共享前缀来节省计算并提高生成吞吐量，通过压缩或优化计算图来进一步加速，例如缓存模型状态、压缩KVCache、优化批处理或针对特定算法进行优化。4、库和工具：介绍了一些用于快速生成的库和工具，如vLLM、TensorRTLLM、GPT-Fast等，以及一些在CPU上实现快速解码的库。

八、讨论与结论 当前，生成算法在多个方面发挥着重要作用。一方面，令牌级截断算法等生成算法可避免模型分布中的错误，如祖先采样可能导致的不连贯序列以及MAP解码算法可能导致的重复序列，尽管未来模型或许能减少这些不完美之处，但现阶段仍需生成算法来修正。同时，语言模型的学习分布与期望的生成分布可能不一致，生成算法能通过重加权或抽样调整分布使其符合期望，虽未来可能通过微调模型实现，但目前其调整分布的作用依然重要。生成算法还可看作是在输出空间中搜索期望序列的过程，增加计算量能提高搜索效果，即便未来某些任务可能不再需要生成算法，但在一些具有挑战性的情况下仍有用武之地。此外，生成算法能够结合外部信息，如其他模型的预测、提示中的指令或外部工具的结果，在许多具有挑战性的场景中十分必要，未来也可能会有更多结合外部信息的生成算法出现。而且，无论未来序列生成器的形式如何，加速生成始终是必要的，开发新的加速方法有望带来显著收益。总之，本文对语言模型的生成算法进行了综述，统一了来自解码、LLM推理和机器学习系统社区的过去研究，并确定了未来工作的方向。大家对这篇论文有什么看法呢？欢迎来智能交互引擎搜索工业知识，展开相关讨论。