LLMの推論は数十億ドル規模の課題です。 私たちの新しい論文では、多稿投機的サンプリングにおけるSOTAアルゴリズム「グローバル・レゾリューション」を紹介し、この問題に大きな進展をもたらしました。 下の🧵👇荷ほどき

効率的な推論の一つのアプローチは推測的サンプリングと呼ばれます。 これは安価な「ドラフト」モデルを使って、より大きなターゲットモデルが何を出せるかの「推測」を生成します。

現代GPUの並列効率を活用することで、ターゲットモデルのフォワードパス数を5倍以上削減できます。

推測的サンプリングは、複数のドラフトモデルから複数の推測を受け入れることに一般化できます。 しかし、これら複数の推測を組み合わせる最良のアルゴリズムが何かは明確ではありません。

単一ステップの場合、過去の研究では最適輸送線形計画問題OTLPを解くことで最適解が得られることが示されています。

しかし、OTLPは語彙量が指数関数的に増えるため、ほぼ正確に解くのは非常に困難です。では、どうすれば解決できるのでしょうか?

重要なのは、ドラフトツリー構築で追加の構造を活用することです。

以前の研究[Huら]は、ドラフトツリーをi.i.d.サンプリングで形成し、OTLPを双対化することで、サブモジュラー最小化を通じてほぼ線形時間で最適な目的値を計算できることを示しました。

しかし、私たちの研究まで、この最適な目的値を達成する解を解く方法はなかった。この欠けている要素がなければ、これまでの研究で示されたのはブロック効率、つまり理論上の最大速度アップだけです。この加速を実現する方法も教えてくれません。

私たちの研究は、三つの洞察を用いてOTLPの次元を大幅に低減した初めてのものです。

我々は、以前の研究[Huら]でOTLPの双対化を補完的な緩みを用いて逆にし、OTLPをフロー実現可能性問題として定式化します。

多くのフロー不等式制約は冗長です。ポリマトロイド理論の貪欲アルゴリズムを用いて、これらを統合できます。

この低次元流問題の解は、低次元ベクトルのソフトマックスとしてパラメータ化でき、このベクトルは凸最小化によって計算できます。 これにより、V^{n+1}変数のOTLPはV変数の凸最小化問題に還元されます。

しかし、Vは依然としてかなり大きいことがあるため、本論文では計算時間をさらに短縮するために、有界ターゲットモデルの誤差率を用いたさらなる近似を適用します。

上記のように、Vが上位kモデルおよびn個のドラフトモデルに限定される多くの場合、グローバル解決は合理的な時間でOTLPを解ける唯一のソルバーです。

さらに、Global Resolutionを使えば、LlamaとGemmaの受け入れ率を最大6%向上させることができます。 要するに、グローバル解像度は投機的復号における最適なマルチドラフト検証のためのSOTAです。

まだやるべきことはたくさんあります。IIDの設定を緩めるか、複数のステップに拡張するかです。