一、引言
現代研究發現，訓練大語言模型（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推理和機器學習系統社區的過去研究，并確定了未來工作的方向。大家對這篇論文有什么看法呢？歡迎來智能交互引擎搜索工業知識，展開相關討論。