メインコンテンツへスキップ
Yaniv Leviathan ほか

小型モデルが複数トークンを下書きし、大型モデルが一度に検証する。出力は変わらず推論だけ速くなる。ICML 2023、全文無料。

Fast Inference from Transformers via Speculative Decoding

Transformerからの高速推論:投機的デコーディングによる手法

Yaniv Leviathan \* 1 Matan Kalman \* 1 Yossi Matias 1

概要

Transformerのような大規模自己回帰モデルからの推論は遅い——KK個のトークンをデコードするには、モデルをKK回逐次的に実行する必要がある。本研究では、投機的デコーディング(speculative decoding)を導入する。これは、出力を一切変更することなく、複数のトークンを並列に計算することで自己回帰モデルからより高速にサンプリングするアルゴリズムである。我々のアプローチの核心には、(1) 難しい言語モデリングのタスクには、より効率的なモデルで十分に近似できる易しいサブタスクがしばしば含まれること、(2) 投機的実行と新規のサンプリング手法を用いることで、近似モデルの出力に対して大規模モデルを並列に実行し、場合によっては複数のトークンを同時に生成しつつ、分布を変更することなく、大規模モデルからの正確なデコーディングを高速化できること、という観察がある。我々の手法は、再学習やアーキテクチャの変更なしに、既存の市販モデルを高速化できる。我々はこれをT5-XXLで実証し、標準的なT5X実装と比較して、同一の出力を保ちながら2倍から3倍の高速化を達成したことを示す。

1. はじめに

大規模自己回帰モデル、特に大規模Transformer (Vaswani et al., [2017]) は、小規模モデルよりもはるかに高い能力を持つ。これは近年、テキストや画像の領域において、GPT-3 (Brown et al., [2020])、LaMDA (Thoppilan et al., [2022])、Parti (Yu et al., [2022])、PaLM (Chowdhery et al., [2022]) などで無数の例が示されている。残念ながら、これらの大規模モデルからの単一のデコードステップは、小規模な対応モデルからのステップよりも著しく遅く、さらに悪いことに、これらのステップは逐次的に行われる——KK個のトークンをデコードするには、モデルをKK回逐次的に実行する必要がある。

大規模自己回帰モデル、特に大規模Transformerの重要性を踏まえ、それらからの推論を高速化するためにいくつかのアプローチが開発されてきた。一部のアプローチは、すべての入力に対して推論コストを均等に削減することを目指す(例:Hinton et al., [2015]、Jaszczur et al., [2021]、Hubara et al., [2016]、So et al., [2021]、Shazeer [2019])。他のアプローチは、すべての推論ステップが同じように生まれるわけではない——あるものは非常に大規模なモデルを必要とするが、他のものはより効率的なモデルで十分に近似できる——という観察に基づく。これらの適応的計算手法(例:Han et al., [2021]、Sukhbaatar et al., [2019]、Schuster et al., [2021]、Scardapane et al., [2020]、Bapna et al., [2020]、Elbayad et al., [2019]、Schwartz et al., [2020])は、容易な推論ステップに対してより少ない計算資源を使用することを目指す。これらのソリューションの多くは実際に極めて有効であることが証明されているが、通常はモデルアーキテクチャの変更、学習手順の変更とモデルの再学習が必要であり、出力を同一に保つことはない。

上述の「一部の推論ステップは『難しい』が、一部は『易しい』」という重要な観察は、我々の研究の重要な動機でもある。我々はさらに、大規模モデルからの推論はしばしば算術演算ではなく、メモリ帯域幅と通信によってボトルネックとなるため、追加の計算資源が利用可能である場合があることを観察する。したがって、我々は適応的な計算量の使用に対する補完的なアプローチとして、並行性を高めることを提案する。具体的には、モデルアーキテクチャを変更せず、学習手順を変更せず、モデルの再学習も必要とせず、モデルの出力分布も変更することなく、推論を高速化できる。これは投機的実行によって達成される。

投機的実行(Burton, [1985]、Hennessy & Patterson, [2012])は、プロセッサで一般的な最適化手法であり、タスクが実際に必要かどうかを検証することと並行してタスクを実行する——その見返りは並行性の向上である。投機的実行のよく知られた例は分岐予測である。投機的実行を効果的にするには、必要とされる可能性が高いタスクを提案する効率的なメカニズムが必要である。本研究では、投機的実行を確率的設定に一般化する——そこではタスクがある確率で必要とされるかもしれない。これをTransformerのような自己回帰モデルからのデコーディングに適用し、より効率的な近似モデルから生成をサンプリングして、より遅いターゲットモデルの投機的プレフィックスとする。新規のサンプリング手法である投機的サンプリングにより、これらの投機的タスクが

図1. 無条件言語モデリングの場合における我々の手法の図解。各行はアルゴリズムの1回の反復を表す。緑色のトークンは近似モデル(ここでは、8kトークンで1m1bを用いて訓練された6MパラメータのGPT風Transformerデコーダ)が生成し、ターゲットモデル(ここでは、同じ設定で97MパラメータのGPT風Transformerデコーダ)が受理した提案である。一方、赤色と青色のトークンはそれぞれ、拒否された提案とその修正である。例えば、最初の行ではターゲットモデルは1回だけ実行され、5つのトークンが生成された。
図1. 無条件言語モデリングの場合における我々の手法の図解。各行はアルゴリズムの1回の反復を表す。緑色のトークンは近似モデル(ここでは、8kトークンで1m1bを用いて訓練された6MパラメータのGPT風Transformerデコーダ)が生成し、ターゲットモデル(ここでは、同じ設定で97MパラメータのGPT風Transformerデコーダ)が受理した提案である。一方、赤色と青色のトークンはそれぞれ、拒否された提案とその修正である。例えば、最初の行ではターゲットモデルは1回だけ実行され、5つのトークンが生成された。

受け入れられる確率を最大化しつつ、我々のシステムからの出力がターゲットモデル単独からの出力と同じ分布を持つことを保証する。例えば、図1の38個のトークンからなる文は、我々の手法によって、より小さくより効率的な近似モデル(6Mパラメータ)のおかげで、より大規模なターゲットモデル(97Mパラメータ)をわずか9回逐次的に実行するだけで生成され、しかもそれを生成する確率は変わらない。

我々は様々なタスクとモデルサイズで我々の手法を分析する:1m1bで学習された97MパラメータのGPTライクなモデルからの無条件生成、11BパラメータのT5-XXLモデルを用いた英語からドイツ語への翻訳とニュース記事の要約、そして137BパラメータのLaMDAモデルを用いた対話タスクである。我々は手法を実装し、T5-XXLの実際のウォールタイムを堅牢なT5X実装(Roberts et al., 2022)と比較し、出力に一切の変更を加えることなく、すぐに使える形で2倍から3倍のレイテンシ改善を示す(第4節)。

我々の手法は実際の本番環境で容易に採用でき、新しいモデルの学習を必要とせず、出力を変更しない。したがって、メモリ帯域幅がボトルネックであり、計算資源が利用可能であるという一般的な状況において、Transformerのような自己回帰モデルからのサンプリングを高速化するための良いデフォルトとなり得る。

まとめると、我々の主な貢献は次のとおりである:(1) 投機的実行の確率的設定への一般化と、我々が投機的サンプリングと呼ぶ新規のサンプリング手法、(2) モデルアーキテクチャ、学習方式、出力分布に一切の変更を加えることなく、自己回帰モデルからのデコーディングを高速化できる、我々が投機的デコーディングと呼ぶデコーディング機構。

2. 投機的デコーディング

2.1. 概要

MpM_{p}をターゲットモデルとし、そこからの推論を我々は高速化しようとしている。またp(xt∣x<t)p(x_{t}|x_{< t})を、プレフィックスx<tx_{< t}に対してモデルから得られる分布とする。MqM_{q}を同じタスクのためのより効率的な近似モデルとし、q(xt∣x<t)q(x_{t}|x_{< t})をプレフィックスx<tx_{< t}に対してモデルから得られる分布とする。核心となるアイデアは、(1) より効率的なモデルMqM_{q}を用いてγ∈Z+\gamma \in \mathbb{Z}^{+}個の補完を生成し(このパラメータを最適に選択する方法については第3.5節を参照)、次に(2) ターゲットモデルMpM_{p}を用いて、すべての推測とそれに対応するMqM_{q}からの確率を並列に評価し、同一の分布をもたらし得るものをすべて受け入れ、(3) 最初に拒否されたものを修正するために調整された分布から追加のトークンをサンプリングするか、すべてが受け入れられた場合には追加のものを1つ加える。このようにして、ターゲットモデルMpM_{p}の各並列実行は少なくとも1つの新しいトークンを生成する(したがって、ターゲットモデルの逐次実行回数は、最悪の場合でも、単純な自己回帰手法よりも多くなることは決してない)が、MqM_{q}がMpM_{p}をどれだけよく近似するかに応じて、最大γ+1\gamma +1個の多数の新しいトークンを生成する可能性がある。

2.2. 標準化されたサンプリング

まず、argmax、top-k、nucleus、温度の設定など、サンプリングには多くの手法とパラメータがあり、一般的な実装は通常ロジットのレベルでそれらを異なる方法で扱うが、それらはすべて調整された確率分布からの標準的なサンプリングに容易に変換できることに注意する。例えば、argmaxサンプリングは、分布の最大でない要素をゼロにして正規化することと等価である。したがって、我々は確率分布からの標準的なサンプリングのみを扱うことができ、他のすべての種類のサンプリングをその枠組みに変換できる。以下では、p(x)p(x)とq(x)q(x)はそれぞれMpM_{p}とMqM_{q}からの分布であり、サンプリング手法に合わせて調整されているものと仮定する。

2.3. 投機的サンプリング

x∼p(x)x\sim p(x) をサンプリングする代わりに、x∼q(x)x\sim q(x) をサンプリングし、q(x)≤p(x)q(x)\leq p(x) であればそれを保持し、q(x)>p(x)q(x) > p(x) の場合は確率 1−p(x)q(x)1 - \frac{p(x)}{q(x)} でそのサンプルを棄却し、代わりに調整済み分布 p′(x)=norm(max(0,p(x)−q(x)))p^{\prime}(x) = norm(max(0,p(x) - q(x))) から xx を再度サンプリングします。任意の分布 p(x)p(x) と q(x)q(x)、およびこの方法でサンプリングされた xx に対して、実際に x∼p(x)x\sim p(x) となることは簡単に示せます(付録 [A.1] 参照)。

条件付け prefixprefix に対して MqM_{q} を実行して得られた分布 q(x)q(x) が与えられると、トークン x1∼q(x)x_{1}\sim q(x) をサンプリングできます。次に、prefixprefix に対して MpM_{p} を実行して分布 p(x)p(x) を計算すると同時に、prefix+[x1]prefix + [x_{1}] に対して MpM_{p} を実行して次のトークン x2x_{2} の分布を投機的に並列計算します。両方の計算が完了したら、上記の手順に従って進めます。すなわち、x1x_{1} が棄却された場合は x2x_{2} の計算を破棄し、調整済み分布から x1x_{1} を再サンプリングし、x1x_{1} が受理された場合は両方のトークンを保持します。アルゴリズム [I] はこのアイデアを一般化し、一度に 1 から γ+1\gamma +1 個のトークンをサンプリングします。

アルゴリズム 1 SpeculativeDecodingStep

3. 分析

3.1. 生成されるトークン数

ターゲットモデルへの逐次呼び出し回数の削減率、すなわちアルゴリズム [I] の 1 回の実行で生成されるトークンの期待数を分析しましょう。

定義 3.1. プレフィックス x<tx_{< t} が与えられたときの受理率 βx<t\beta_{x< t} とは、セクション [2.3] に従い、投機的サンプリングによって xt∼q(xt∣x<t)x_{t}\sim q(x_{t}|x_{< t}) が受理される確率です:

このとき E(β)E(\beta) は、MqM_{q} が MpM_{p} をどれだけよく近似しているかの自然な尺度となります。β\beta が独立同分布であると仮定し、α=E(β)\alpha = E(\beta) と表記すると、アルゴリズム [I] の 1 回の実行で生成されるトークン数は、成功確率 1−α1 - \alpha、上限 γ+1\gamma +1 を持つ打ち切り幾何変数となり、アルゴリズム [I] によって生成されるトークンの期待数は式 [I] を満たします。図 [2] を参照してください。

E(#generated tokens)=1−αγ+11−α(1)E(\# \text{generated tokens}) = \frac{1 - \alpha^{\gamma + 1}}{1 - \alpha} \quad (1)
図2. 様々な \gamma の値に対する、\alpha の関数としてのアルゴリズム[I]によって生成されるトークンの期待数。
図2. 様々な γ\gamma の値に対する、α\alpha の関数としてのアルゴリズム[I]によって生成されるトークンの期待数。

3.2. α\alpha の計算

次に、プレフィックスと 2 つのモデル MpM_{p}、MqM_{q} が与えられたときに α\alpha を計算するための簡単な公式を導出します。まず、自然なダイバージェンス DLKD_{LK} を定義します:

定義 3.2. DLK(p,q)=∑x∣p(x)−M(x)∣=∑x∣q(x)−M(x)∣D_{LK}(p,q) = \sum_{x}|p(x) - M(x)| = \sum_{x}|q(x) - M(x)| ここで M(x)=p(x)+q(x)2M(x) = \frac{p(x) + q(x)}{2} です。

補題 3.3. DLK(p,q)=1−∑xmin⁡(p(x),q(x))D_{LK}(p,q) = 1 - \sum_{x}\min (p(x),q(x))

証明。 DLK(p,q)=∑x∣p(x)−M(x)∣=∑x∣p−q∣2=D_{LK}(p,q) = \sum_{x}|p(x) - M(x)| = \sum_{x}\frac{|p - q|}{2} = 1−∑xp+q−∣p−q∣2=1−∑xmin⁡(p(x),q(x))1 - \sum_{x}\frac{p + q - |p - q|}{2} = 1 - \sum_{x}\min (p(x),q(x))

補題[3.3]から、直ちに以下の結果が得られる:系3.4。DLK(p,q)D_{LK}(p,q) は [0,1][0,1] における対称なダイバージェンスである。DLK(p,q)=0  ⟺  p=qD_{LK}(p,q) = 0 \iff p = q。DLK(p,q)=1  ⟺  pD_{LK}(p,q) = 1 \iff p と qq のサポートが互いに素である。

定理3.5。 β=1−DLK(p,q)\beta = 1 - D_{LK}(p,q)

証明.β=Ex∼q(x){1q(x)≤p(x)p(x)q(x)q(x)>p(x)Ex∼q(x)min⁡(1,p(x)q(x))=∑xmin⁡(p(x),q(x))(3)\begin{array}{rcl}{\mathrm{証明.}\beta} & = & {E_{x\sim q(x)}\left\{ \begin{array}{ll}1 & q(x)\leq p(x)\\ \frac{p(x)}{q(x)} & q(x) > p(x) \end{array} \right.}\\ {E_{x\sim q(x)}\min (1,\frac{p(x)}{q(x)}) = \sum_{x}\min (p(x),q(x))} \end{array} \quad (3)

最終的に次が得られる:

系3.6。 α=1−E(DLK(p,q))=E(min⁡(p,q))\alpha = 1 - E(D_{LK}(p,q)) = E(\min (p,q))

我々の実験において経験的に観測された α\alpha の値については表3を参照されたい。

3.3. 実時間(ウォールタイム)の改善

i.i.d.仮定の下では、我々のアルゴリズムがターゲットモデルへの呼び出し回数を 1−αγ+11−α\frac{1 - \alpha^{\gamma + 1}}{1 - \alpha} 倍に削減することを示した。一般的な投機的実行、特に我々のアルゴリズムは、増加した並行性を支えるだけの計算資源があることを前提としていることに注意されたい(3.4節)。ウォールタイムの分析では、ウォールタイムを増加させることなく MpM_{p} の γ+1\gamma + 1 回の並行評価を並列に実行できると仮定する。総ウォールタイムの改善量を求めるために、次に近似モデル MqM_{q} の実行コストを考える。

定義3.7。コスト係数 cc を、MqM_{q} の1回の実行時間と MpM_{p} の1回の実行時間の比とする。

モデルとタスクの本質的な性質である α\alpha とは異なり、cc の値はハードウェア構成とソフトウェア実装の詳細に依存することに注意されたい。我々の実験では MqM_{q} は通常 MpM_{p} より2桁程度小さいため、cc は常に0.05未満であり、しばしば無視できるほど0に近かった。

定理3.8。アルゴリズム1による総ウォールタイムの期待改善率は 1−αγ+1(1−α)(γc+1)\frac{1 - \alpha^{\gamma + 1}}{(1 - \alpha)(\gamma c + 1)} である。

証明。MpM_{p} の1ステップの実行コストを TT と表す。このとき、アルゴリズム1の各実行には Tcγ+TT c\gamma + T のコストがかかり(近似モデル MqM_{q} を γ\gamma 回実行し、MpM_{p} を1回実行するため)、式(1)によれば平均して 1−αγ+11−α\frac{1 - \alpha^{\gamma + 1}}{1 - \alpha} 個のトークンを生成する。したがって、アルゴリズム1でトークンを生成する際の全体的な期待コストは (cγ+1)(1−α)1−αγ+1T\frac{(c\gamma + 1)(1 - \alpha)}{1 - \alpha^{\gamma + 1}} T である。標準的なデコーディングアルゴリズムで1つのトークンを生成するコストは TT であるから、求める結果が得られる。\(\square\)

定理3.8は十分に長い生成を仮定していることに注意されたい(例えば、MpM_{p} を少なくとも1回は実行するため、改善率は生成されるトークン数によって上限が定められる)。

系3.9。α>c\alpha >c ならば、改善が得られる γ\gamma が存在し、その改善率は少なくとも 1+α1+c\frac{1 + \alpha}{1 + c} となる。

証明。ある γ\gamma で改善が得られるならば、任意の 0<γ∗<γ0 < \gamma^{*} < \gamma でも改善が得られる。したがって、我々の手法が改善をもたらすかどうかを評価するには、定理3.8を γ=1\gamma = 1 で評価すればよく、1−α2(1−α)(c+1)=1+α1+c\frac{1 - \alpha^{2}}{(1 - \alpha)(c + 1)} = \frac{1 + \alpha}{1 + c} が得られる。□\square

3.4. 演算回数

アルゴリズム1は MpM_{p} を γ+1\gamma +1 回並列に実行するため、同時演算回数は γ+1\gamma +1 倍に増加する。また、アルゴリズム1は1回の実行あたり最大 γ+1\gamma +1 個のトークンを生成するため、総演算回数は標準的なデコーディングアルゴリズムより多くなる可能性がある。MqM_{q} からのサンプルを受理する場合、増加した並行性は「無料」であり、総演算回数は増加しない。しかし、推測を棄却する場合には計算が無駄になる。次に、我々の手法が総演算回数に与える影響を分析する。

定義3.10。c^\hat{c} を、近似モデル MqM_{q} のトークンあたりの演算回数とターゲットモデル MpM_{p} のトークンあたりの演算回数の比とする。

定理3.11。アルゴリズム1の総演算回数の期待増加率は (1−α)(γc+γ+1)1−αγ+1\frac{(1 - \alpha)(\gamma c + \gamma + 1)}{1 - \alpha^{\gamma + 1}} である。

証明。標準的なデコーディングのベースラインがトークンあたりに行う演算回数、すなわち MpM_{p} の1回の実行の演算回数を T^\hat{T} と表す。このとき、アルゴリズム1の1回の反復には T^c^γ+T^(γ+1)\hat{T} \hat{c} \gamma + \hat{T} (\gamma + 1) 回の演算がかかる(MqM_{q} の γ\gamma 回の実行と MpM_{p} の γ+1\gamma + 1 回の並列実行のため)。これを、アルゴリズム1が生成する期待トークン数、すなわち式(1)と T^\hat{T} で割ることで、求める結果が得られる。□\square

α\alpha が低い場合、演算回数の増加は大きくなり、逆もまた同様である。Transformerデコーダの場合、アルゴリズム1による総演算回数(MqM_{q} の実行を除く)は、同じサイズのTransformerエンコーダの1回の実行によって上から抑えられることに注意されたい。

算術演算の総数とは異なり、メモリアクセスの総数は我々の手法によって減少し得る。具体的には、ターゲットモデルの重みとKVキャッシュはアルゴリズム1の各実行につき一度だけ読み込まれ得るため、それらを読み込むためのメモリアクセスの回数は、式(1)によれば1−αγ+11−α\frac{1 - \alpha^{\gamma + 1}}{1 - \alpha}倍に減少する。

3.5. γ\gammaの選択

ccとα\alphaが与えられ、十分な計算資源を仮定すると(セクション3.4参照)、最適なγ\gammaはウォールタイム改善の式(定理3.8)を最大化するものである:

図3. 様々な \(c\) の値に対する、\(\alpha\) の関数としての最適な \(\gamma\)。
図3. 様々な \(c\) の値に対する、\(\alpha\) の関数としての最適な \(\gamma\)。

1−αγ+1(1−α)(γc+1)\frac{1 - \alpha^{\gamma + 1}}{(1 - \alpha)(\gamma c + 1)}。γ\gammaは整数であるため、数値的に容易に求めることができる。図3を参照されたい。

表1と図4は、c=c^=0c = \hat{c} = 0を仮定した場合の、様々なα\alphaとγ\gammaの値に対する推論速度と算術演算の総数の間のトレードオフを示している。図5は簡略化したトレース図を示している。

αγ演算数速度
0.621.53X1.96X
0.731.58X2.53X
0.821.23X2.44X
0.851.63X3.69X
0.921.11X2.71X
0.9101.60X6.86X
表1. c=c^=0c = \hat{c} = 0 と仮定した場合の、さまざまな γ\gamma と α\alpha の値に対する、ベースラインと比較した演算数の総数および推論速度

β\betaは一定ではないため、α\alphaに基づいて単一のγ\gammaの値を選ぶ代わりに、β\betaの値を予測し、それに応じてアルゴリズム1の実行中にγ\gammaの値を変化させることで、さらなる改善を得ることができる。追加の改善係数の上限を得るために、γ\gammaに関するオラクルがあると仮定しよう。その場合、E(#生成トークン数)=11−αE(\# \text{生成トークン数}) = \frac{1}{1 - \alpha}となる。ccとα\alphaの典型的な値に対して、無制限の計算資源を仮定すると、強化されたウォールタイム改善係数は、固定のγ\gammaによる改善係数よりも最大で約60%高くなり得る。この探求は今後の課題とする。

図4。様々な \gamma の値に対する、\alpha の関数としての速度向上係数と算術演算数の増加。
図4。様々な γ\gamma の値に対する、α\alpha の関数としての速度向上係数と算術演算数の増加。

3.6. 近似モデル

投機的サンプリング、ひいては投機的デコーディングは、近似モデルMqM_{q}の選択がいかなるものであっても、無制限に同一の出力分布を保証する(付録A.1参照)。我々の実験では、主に既存の市販のより小さなTransformerを近似モデルとしてテストした。さらに、我々はターゲットモデルMpM_{p}と同じアーキテクチャを持ち、同じ確率標準化を用いる近似モデルのみをテストした。この設定では、MqM_{q}をMpM_{p}よりも約2桁小さく選ぶことが、α\alphaとccのバランスを取る上で通常最もうまく機能した(定理3.8)。

別の種類の近似モデルである無視できるコストのモデルとは、c≈0c \approx 0となるもの、すなわちターゲットモデルに対して無視できるコストの近似モデルである。この場合、期待されるウォールタイム改善は1−αγ+11−α\frac{1 - \alpha^{\gamma + 1}}{1 - \alpha}となり、これは上から11−α\frac{1}{1 - \alpha}で抑えられる(γ\gammaが大きければ等号に近づく)。興味深い無視できるコストの近似モデルの一種として、n-gramモデルがあり、その評価はテーブルルックアップに相当する。興味深いことに、実証実験(セクション4.2)では、このような自明なn-gramモデルに対しても非ゼロのα\alphaが得られた。例えば、英独翻訳タスクにおいて、MpM_{p}をT5-XXL 11B、MqM_{q}を自明なバイグラムモデルとした場合、α≈0.2\alpha \approx 0.2が得られ、γ=3\gamma = 3で1.25倍の推論速度改善係数につながる。

他の単純なヒューリスティクスも無視できるコストの近似モデルとして使用できる。例えば、要約タスクやチャット形式のインターフェースのように長いシーケンスが繰り返される可能性が高い場合、一致するプレフィックスが見つかったときにコンテキストからトークンを単に

図5. 完全なエンコーダ・デコーダTransformerスタックの簡略化されたトレース図。最上段は \gamma = 7 の投機的デコーディングを示しており、M_{p} への各呼び出し(紫色のブロック)の前に、M_{q} への7回の呼び出し(青色のブロック)が先行している。左側の黄色のブロックは M_{p} のエンコーダへの呼び出しであり、オレンジ色のブロックは M_{q} のエンコーダへの呼び出しである。同様に、中段は \gamma = 3 の投機的デコーディングを示しており、最下段は標準的なデコーディングを示している。
図5. 完全なエンコーダ・デコーダTransformerスタックの簡略化されたトレース図。最上段は γ=7\gamma = 7 の投機的デコーディングを示しており、MpM_{p} への各呼び出し(紫色のブロック)の前に、MqM_{q} への7回の呼び出し(青色のブロック)が先行している。左側の黄色のブロックは MpM_{p} のエンコーダへの呼び出しであり、オレンジ色のブロックは MqM_{q} のエンコーダへの呼び出しである。同様に、中段は γ=3\gamma = 3 の投機的デコーディングを示しており、最下段は標準的なデコーディングを示している。

コピーする近似モデルは、高いα\alpha値をもたらす可能性がある。これらのパラメータを持たない近似モデルは、本番環境の観点から展開がさらに簡単であるという追加の利点を持つ。

投機的デコーディングで使用できる別の種類の近似モデルは、Sternら[2018]によるもののような非自己回帰モデルである。その場合、アルゴリズム1の自己回帰ループの代わりに、非自己回帰モデルを一度呼び出すだけでよい。

最後の例は、主に理論的な観点から興味深いものであるが、トークンをランダムに選ぶ近似モデルであり、これはすべてのモデルMpM_{p}に対してある程度の改善(ただし非常に小さい)を保証する。

4. 実験

4.1. 実証的なウォールタイム改善

我々はアルゴリズムを実装し、T5-XXLの高速化のためにT5Xコードベースの実装と比較する。

セットアップ 我々は、標準的なエンコーダ・デコーダ型のT5バージョン1.1モデル(Raffel et al., [2020])を、T5論文の2つのタスクでテストする:(1)WMT EnDeでファインチューニングされた英語からドイツ語への翻訳、および(2)CNN/DMでファインチューニングされたテキスト要約である。両タスクにおいて、MpM_{p} にはT5-XXL(11B)を用いる。近似モデル MqM_{q} については、いくつかの既存の構成、すなわちT5-large(800M)、T5-base(250M)、T5-small(77M)をテストする(Raffel et al., [2020])。すべてのモデルには既存のチェックポイントを用いる。我々は、単一のTPU-v4上でバッチサイズ1とし、argmaxサンプリング(temp=0)と標準サンプリング(temp=1)の両方について、実時間(walltime)の改善を測定する。

結果 表2は我々の手法による実証結果を示す。T5-small(77M)が、cc と α\alpha の良好なバランスにより、テストした近似モデルの中で最高の高速化を提供することがわかる。予想通り、α\alpha は近似モデルのサイズとともに増加することがわかる。興味深いことに、α\alpha と実時間の改善はargmaxサンプリング(temp=0)の方が高い。翻訳タスクでは2.6倍(temp=1)および3.4倍(temp=0)の高速化が観測され、要約タスクではやや低い2.3倍(temp=1)および3.1倍(temp=0)の高速化が観測された。これらの実証結果は理論的予測とよく一致しており、実装の詳細によるいくらかのばらつきがある(付録A.3を参照)。

タスクMqTEMPγαSPEED
ENDET5-SMALL ★070.753.4X
ENDET5-BASE070.82.8X
ENDET5-LARGE070.821.7X
ENDET5-SMALL ★170.622.6X
ENDET5-BASE150.682.4X
ENDET5-LARGE130.711.4X
CNNDMT5-SMALL ★050.653.1X
CNNDMT5-BASE050.733.0X
CNNDMT5-LARGE030.742.2X
CNNDMT5-SMALL ★150.532.3X
CNNDMT5-BASE130.552.2X
CNNDMT5-LARGE130.561.7X
表2. T5-XXL 11Bモデルからの推論を高速化するための実証結果。

4.2. 実証的な α\alpha 値

我々は手法をT5に対してのみ実装したが、さまざまなタスク、サンプリング手法、ターゲットモデル MpM_{p}、および近似モデル MqM_{q} について α\alpha 値を測定した。具体的には、以下の各設定について、MpM_{p} によって生成された10Kトークン上で系3.6の期待値を評価した。

GPTライク(97Mパラメータ) 我々は、lm1b(Chelba et al., [2013])で訓練された無条件言語生成において、デコーダのみのTransformerモデルをテストする。ここでのモデルは、Gelu活性化(Hendrycks & Gimpel, [2016])を用いたGPTライクなTransformerデコーダである。MqM_{q} については、6MパラメータのTransformerデコーダモデル:dim 256、フィードフォワードdim 1024、2層、4アテンションヘッド、ならびに単純なユニグラムおよびバイグラムモデルを実験した。MpM_{p} は97Mパラメータを持つ:dim 768、フィードフォワードdim 3072、12層、12アテンションヘッド。すべてのモデルで8kトークンのBertトークナイゼーション(Devlin et al., [2019])を用いた。

LaMDA(137Bパラメータ) 我々は、対話タスクにおいてデコーダのみのLaMDAモデルをテストした(Thoppilan et al., [2022])。MpM_{p} としてLaMDA 137Bの既存のチェックポイントを、MqM_{q} としてLaMDA 8B、LaMDA 2B、およびLaMDA 100Mを用いた。

T5-XXL(11Bパラメータ)モデルのセットアップについてはセクション4.1を参照されたい。

表3は、テストしたケースの α\alpha 値をまとめたものである。ターゲットモデルより数桁小さい近似モデルは、0.5から0.9の間の α\alpha 値を生成する傾向があることがわかる。興味深いことに、すべてのモデルにおいて、調整された分布が鋭いほど α\alpha 値が高くなることも確認できる。最後に、取るに足らないユニグラムおよびバイグラム近似でさえ、無視できない α\alpha 値を生み出すことを述べておく。例えば、英語からドイツ語への翻訳の場合、バイグラムモデルは α\alpha 値が0.2であり、この場合 c=0c = 0 であるため、1.25倍の速度改善をもたらす。これはこの取るに足らない近似モデルにしては驚くほど高い(しかし、T5-smallを近似モデルとして用いて得られる高速化よりは依然として低い)。

5. 関連研究

大規模モデルからの推論の効率性は広く研究されてきた(Dehghani et al., [2021])。多くのアプローチは、一般に大規模モデルからの推論を、特にTransformerのような自己回帰モデルからの推論を高速化することを目的としている。数多くの技術が、すべてのトークンに対して推論をより効率的にしようと試みている。例えば、蒸留(Hinton et al., [2015])、スパース化(Jaszczur et al., [2021])、量子化(Hubara et al., [2016])、およびアーキテクチャの変更(So et al., [2021]; Shazeer [2019])である。我々のアプローチに近いのは、問題の難しさに応じて計算量を適応させる適応的計算手法である(Han et al., [2021])。例としては、入力の部分集合へのアテンション(Sukhbaatar et al., [2019])や早期終了(Schuster et al., [2021]; Scardapane et al., [2020]; Bapna et al., [2020]; Elbayad et al., [2019]; Schwartz et al., [2020])がある。特に、Wisdom of Committees(Schwartz et al., [2020])は既製のより小さなモデルを活用するが、適応的計算アプローチであるため、いつ停止するかを決定するためにヒューリスティックを用いており、ターゲットモデルの出力と同一の出力という保証を失っている。一般に、適応的計算手法は通常、モデル自体の中か補助モデルを用いて、計算のショートカットをいつ取ることができるかを学習する。通常、これらの手法は推論時間と演算回数の両方を節約するが、アーキテクチャの変更、訓練手順の変更、およびカスタムモデルの訓練または

MpMqSMPLα
GPT-LIKE(97M)UNIGRAMT=00.03
GPT-LIKE(97M)BIGRAMT=00.05
GPT-LIKE(97M)GPT-LIKE(6M)T=00.88
GPT-LIKE(97M)UNIGRAMT=10.03
GPT-LIKE(97M)BIGRAMT=10.05
GPT-LIKE(97M)GPT-LIKE(6M)T=10.89
T5-XXL(ENDE)UNIGRAMT=00.08
T5-XXL(ENDE)BIGRAMT=00.20
T5-XXL(ENDE)T5-SMALLT=00.75
T5-XXL(ENDE)T5-BASET=00.80
T5-XXL(ENDE)T5-LARGET=00.82
T5-XXL(ENDE)UNIGRAMT=10.07
T5-XXL(ENDE)BIGRAMT=10.19
T5-XXL(ENDE)T5-SMALLT=10.62
T5-XXL(ENDE)T5-BASET=10.68
T5-XXL(ENDE)T5-LARGET=10.71
T5-XXL(CNNDM)UNIGRAMT=00.13
T5-XXL(CNNDM)BIGRAMT=00.23
T5-XXL(CNNDM)T5-SMALLT=00.65
T5-XXL(CNNDM)T5-BASET=00.73
T5-XXL(CNNDM)T5-LARGET=00.74
T5-XXL(CNNDM)UNIGRAMT=10.08
T5-XXL(CNNDM)BIGRAMT=10.16
T5-XXL(CNNDM)T5-SMALLT=10.53
T5-XXL(CNNDM)T5-BASET=10.55
T5-XXL(CNNDM)T5-LARGET=10.56
LAMDA(137B)LAMDA(100M)T=00.61
LAMDA(137B)LAMDA(2B)T=00.71
LAMDA(137B)LAMDA(8B)T=00.75
LAMDA(137B)LAMDA(100M)T=10.57
LAMDA(137B)LAMDA(2B)T=10.71
LAMDA (137B)LAMDA (8B)T=10.74
表3. 様々なターゲットモデル MpM_{p}、近似モデル MqM_{q}、およびサンプリング設定に対する実証的な α\alpha 値。T=0 と T=1 はそれぞれ argmax と標準サンプリングを表す。

既存モデルの再訓練を必要とする。また、通常はモデルの出力を変化させる。上記の手法の多くはメモリ対演算回数の比率を改善するが、比率が高いままである場合には、これらの手法と我々の投機的デコーディング手法が相乗的に効果的であり得ることに注意する。

自己回帰モデルからのデコーディングを高速化するために投機的実行を活用する先行手法が2つある。Blockwise Parallel Decoding(Stern et al., [2018])は我々の研究と同様に複数のトークンを並列にデコードする。しかし、これは貪欲デコーディング(温度 =0= 0)のみをサポートし、一般的な確率的設定はサポートせず、カスタムモデルの追加訓練を必要とし、同一の出力を保証するのではなく下流タスクの品質を維持することに焦点を当てている。Shallow Aggressive Decoding(SAD)(Sun et al., [2021])も我々の研究と同様に複数のトークンを並列にデコードする。我々の研究とは異なり、SADは入力の出力へのコピーのみをサポートし、一般的な近似モデルはサポートしないため、文法誤り訂正のように入力と出力が非常に類似している場合にのみ適している。さらに、Blockwise Parallel Decodingと同様に、SADは一般的な確率的サンプリング設定をサポートしていない。

我々の研究を最初に発表した後、投機的デコーディングの独立した実装(Chen et al., [2023])がChinchilla 70Bにおいて同様の2倍から2.5倍の改善を示した。

6. 議論

我々は、効率的な確率的投機的実行、すなわち確率的設定における投機的実行を可能にする投機的サンプリングを提示した。我々は、投機的デコーディングを介したTransformerのような自己回帰モデルからのデコーディングへのその影響を分析し、十分な計算資源が与えられれば、一般的な最適化実装であるT5Xと比較して実際に意味のある2倍から3倍の高速化が得られることを示した。

一般に投機的実行の、特に投機的デコーディングの一つの限界は、レイテンシが演算回数の増加を犠牲にして並行性の増加を通じて改善されることである。したがって、我々の手法は追加の計算資源が利用できない構成には役立たない。しかし、追加の計算資源が利用可能な一般的なケース(例えばメモリ帯域幅がボトルネックである場合)においては、我々の手法は大きな利点を伴う高速化を提供する:モデルアーキテクチャは変わらず、再訓練は不要であり、最も重要なことに、出力分布は同一に保たれることが保証される。我々の手法は実装が容易であり、カスタムスキームを開発・評価することなく、既製のモデルを用いた推論の高速化に使用できる。

今後の研究にはいくつかの方向性がある。重要なのは、投機的デコーディングとビーム探索との互換性をさらに調査することである(付録[A.4]参照)。また、我々の手法は既存の市販の近似モデルで大幅な高速化を実現するが、カスタム近似モデル(セクション[3.6])—例えばカスタムアーキテクチャ(カスタムサイズ、非自己回帰モデル、各種ヒューリスティクスなど)やカスタム訓練手順(MpM_{p}からのソフトターゲットを用いた標準的な蒸留、あるいはα\alphaに対して直接MqM_{q}を最適化するなど)—によって、より大きな改善が得られる可能性がある。アルゴリズムの階層的バージョンを探索することも興味深いかもしれない。そこでは近似モデル自体がさらに高速なモデルによって加速され、より能力の高い近似モデルが可能になる。本研究では推論全体を通じて近似モデルと推測数γ\gammaを固定したが、推論中にこれらを変化させることで追加の改善が得られる可能性がある(セクション[3.5])。我々の実験では、近似モデルが生成する分布に対して、ターゲットモデルに望まれるものと同じ標準化を常に適用した(セクション[2.2])が、異なる変換を適用することでさらなる改善が得られるかもしれない。我々は投機的デコーディングをテキストモダリティでのみテストしたが、他の領域(例えば画像)でもうまく機能する可能性があり、実験するのは興味深いだろう。

最後に、確率的投機的実行と投機的サンプリングは、自己回帰モデルからの投機的デコーディングの範囲外でも有用であり得ることに言及する。例えば、2つの遅い関数f(x)f(x)とg(y)g(y)が与えられ、f(x)f(x)がggの入力がサンプリングされる分布を生成する場合、我々の手法を用いてffとggを並列に実行できる。このような設定は、例えば物理シミュレーションや、ffが行動に関する分布を生成する大規模モデルでありggが世界シミュレーションである強化学習において生じる可能性があり、探索するのは興味深いだろう。

謝辞

LaMDA関連のすべてにおいて助けていただき、本論文のLaMDAの図を計算していただいたYaGuang Liに、またXLAに関する優れた洞察と助けをいただいたBlake Hechtmanに、特別な感謝を捧げる。また、洞察に満ちたコメントをいただいたレビュアーの皆様、ならびにAsaf Aharoni、Reiner Pope、Sasha Goldshtein、Nadav Sherman、Eyal Segalis、Eyal Molad、Dani Valevski、Daniel Wasserman、Valerie Nygaard、Danny Vainstein、GoogleのLaMDAチームとTheta Labsチーム、そして我々の家族に感謝する。

参考文献

Bapna, A., Arivazhagan, N., and Firat, O. Controlling computation versus quality for neural sequence models. ArXiv, abs/2002.07106, 2020.

Brown, T. B., Mann, B., Ryder, N., Subbiah, M., Kaplan, J., Dhariwal, P., Neelakantan, A., Shyam, P., Sastry, G., Askell, A., Agarwal, S., Herbert- Voss, A., Krueger, G., Henighan, T., Child, R., Ramesh, A., Ziegler, D. M., Wu, J., Winter, C., Hesse, C., Chen, M., Sigler, E., Litwin, M., Gray, S., Chess, B., Clark, J., Berner, C., McCandlish, S., Radford, A., Sutskever, I., and Amodei, D. Language models are few- shot learners. In Proceedings of the 34th International Conference on Neural Information Processing Systems, NIPS'20, Red Hook, NY, USA, 2020. Curran Associates Inc. ISBN 9781713829546.

Burton, F. W. Speculative computation, parallelism, and functional programming. IEEE Transactions on Computers, C- 34(12):1190- 1193, 1985. doi: 10.1109/TC.1985.6312218.

Chelba, C., Mikolov, T., Schuster, M., Ge, Q., Brants, T., Koehn, P. T., and Robinson, T. 統計的言語モデリングの進歩を測定するための10億語ベンチマーク。In Interspeech, 2013.

Chen, C., Borgeaud, S., Irving, G., Lespiau, J.- B., Sifre, L., and Jumper, J. M. 投機的サンプリングによる大規模言語モデルのデコーディングの高速化。ArXiv, abs/2302.01318, 2023.

Chowdhery, A., Narang, S., Devlin, J., Bosma, M., Mishra, G., Roberts, A., Barham, P., Chung, H. W., Sutton, C., Gehrmann, S., Schuh, P., Shi, K., Tsvyashchenko, S., Maynez, J., Rao, A., Barnes, P., Tay, Y., Shazeer, N. M., Prabhakaran, V., Reif, E., Du, N., Hutchinson, B. C., Pope, R., Bradbury, J., Austin, J., Isard, M., Gur- Ari, G., Yin, P., Duke, T., Levskaya, A., Ghemawat, S., Dev, S., Michalewski, H., Garcia, X., Misra, V., Robinson, K., Fedus, L., Zhou, D., Ippolito, D., Luan, D., Lim, H., Zoph, B., Spiridonov, A., Sepassi, R., Dohan, D., Agrawal, S., Omernick, M., Dai, A. M., Pillai, T. S., Pelat, M., Lewkowycz, A., Moreira, E., Child, R., Polozov, O., Lee, K., Zhou, Z., Wang, X., Saeta, B., Diaz, M., Firat, O., Catasta, M., Wei, J., Meier- Hellstern, K. S., Eck, D., Dean, J., Petrov, S., and Fiedel, N. Palm: Pathwaysによる言語モデリングのスケーリング。ArXiv, abs/2204.02311, 2022.

Dehghani, M., Arnab, A., Beyer, L., Vaswani, A., and Tay, Y. 効率性という誤称。ArXiv, abs/2110.12894, 2021.

Devlin, J., Chang, M.- W., Lee, K., and Toutanova, K. Bert: 言語理解のための深層双方向トランスフォーマーの事前学習。ArXiv, abs/1810.04805, 2019.

Elbayad, M., Gu, J., Grave, E., and Auli, M. 深さ適応型トランスフォーマー。ArXiv, abs/1910.10073, 2019.

Han, Y., Huang, G., Song, S., Yang, L., Wang, H., and Wang, Y. 動的ニューラルネットワーク:サーベイ。IEEE Transactions on Pattern Analysis and Machine Intelligence, 44: 7436- 7456, 2021.

Hendrycks, D. and Gimpel, K. ガウス誤差線形ユニットによる非線形性と確率的正則化器の橋渡し。ArXiv, abs/1606.08415, 2016.

Hennessy, J. L. and Patterson, D. A. コンピュータアーキテクチャ:定量的アプローチ。Morgan Kaufmann, Amsterdam, 第5版, 2012. ISBN 978- 0- 12- 383872- 8.

Hinton, G. E., Vinyals, O., and Dean, J. ニューラルネットワークにおける知識の蒸留。ArXiv, abs/1503.02531, 2015.

Hubara, I., Courbariaux, M., Soudry, D., El- Yaniv, R., and Bengio, Y. 量子化ニューラルネットワーク:低精度の重みと活性化によるニューラルネットワークの学習。ArXiv, abs/1609.07061, 2016.

Jaszczur, S., Chowdhery, A., Mohiuddin, A., Kaiser, L., Gajewski, W., Michalewski, H., and Kanerva, J. トランスフォーマーのスケーリングにおいてスパース性で十分である。In Neural Information Processing Systems, 2021.

Raffel, C., Shazeer, N., Roberts, A., Lee, K., Narang, S., Matena, M., Zhou, Y., Li, W., and Liu, P. J. 統一的なテキスト-to-テキストトランスフォーマーによる転移学習の限界の探求。The Journal of Machine Learning Research, 21(1):5485- 5551, 2020.

Roberts, A., Chung, H. W., Levskaya, A., Mishra, G., Bradbury, J., Andor, D., Narang, S., Lester, B., Gaffney, C., Mohiuddin, A., Hawthorne, C., Lewkowycz, A., Salcianu, A., van Zee, M., Austin, J., Goodman, S., Soares, L. B., Hu, H., Tsvyashchenko, S., Chowdhery, A., Bastings, J., Bulian, J., Garcia, X., Ni, J., Chen, A., Kenealy, K., Clark, J., Lee, S., Garrette, D. H., Lee- Thorp, J., Raffel, C., Shazeer, N. M., Ritter, M., Bosma, M., Passos, A., Maitin- Shepard, J. B., Fiedel, N., Omernick, M., Saeta, B., Sepassi, R., Spiridonov, A., Newlan, J., and Gesmundo, A. 5xとseqioによるモデルとデータのスケーリング。ArXiv, abs/2203.17189, 2022.

Scardapane, S., Scarpiniti, M., Baccarelli, E., and Uncini, A. なぜニューラルネットワークに早期出口を追加すべきなのか?Cognitive Computation, 12(5):954- 966, 2020.

Schuster, T., Fisch, A., Jaakkola, T., and Barzilay, R. 自信に基づく適応型トランスフォーマーによる一貫した高速推論。In Conference on Empirical Methods in Natural Language Processing, 2021.

Schwartz, R., Stanovsky, G., Swayamdipta, S., Dodge, J., and Smith, N. A. 仕事に適したツール:モデルとインスタンスの複雑さのマッチング。In Annual Meeting of the Association for Computational Linguistics, 2020.

Shazeer, N. M. 高速トランスフォーマーデコーディング:必要な書き込みヘッドは1つだけ。ArXiv, abs/1911.02150, 2019.

So, D. R., Ma'ake, W., Liu, H., Dai, Z., Shazeer, N. M., and Le, Q. V. Primer: 言語モデリングのための効率的なトランスフォーマーの探索。ArXiv, abs/2109.08668, 2021.

Stern, M., Shazeer, N., and Uszkoreit, J. 深い自己回帰モデルのためのブロックワイズ並列デコーディング。Advances in Neural Information Processing Systems, 31, 2018.

Sukhbaatar, S., Grave, E., Bojanowski, P., and Joulin, A. トランスフォーマーにおける適応型アテンションスパン。In Annual Meeting of the Association for Computational Linguistics, 2019.

Sun, X., Ge, T., Wei, F., and Wang, H. 浅いアグレッシブデコーディングによる即時文法誤り訂正。ArXiv, abs/2106.04970, 2021.

Thoppilan, R., Freitas, D. D., Hall, J., Shazeer, N. M., Kulshreshtha, A., Cheng, H.- T., Jin, A., Bos, T., Baker, L., Du, Y., Li, Y., Lee, H., Zheng, H., Ghafouri, A., Menegali, M., Huang, Y., Krikun, M., Lepikhin, D., Qin, J., Chen, D., Xu, Y., Chen, Z., Roberts, A., Bosma, M., Zhou, Y., Chang, C.- C., Krivokon, I. A., Rusch, W. J., Pickett, M., Meier- Hellstern, K. S., Morris, M. R., Doshi, T., Santos, R. D., Duke, T., Soraker, J. H., Zevenbergen, B., Prabhakaran, V., Díaz, M., Hutchinson, B., Olson, K., Molina, A., Hoffman- John, E., Lee, J., Aroyo, L., Rajakumar, R., Butryna, A., Lamm, M., Kuzmina, V. O., Fenton, J., Cohen, A., Bernstein, R., Kurzweil, R., Aguera- Arcas, B., Cui, C., Croak, M., hsin Chi, E. H., and Le, Q. Lamda: 対話アプリケーションのための言語モデル。ArXiv, abs/2201.08239, 2022.

Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A. N., Kaiser, L., and Polosukhin, I. Attention is all you need. Advances in neural information processing systems, 30, 2017.

Yu, J., Xu, Y., Koh, J. Y., Luong, T., Baid, G., Wang, Z., Vasudevan, V., Ku, A., Yang, Y., Ayan, B. K., Hutchinson, B. C., Han, W., Parekh, Z., Li, X., Zhang, H., Baldridge, J., and Wu, Y. Scaling autoregressive models for content-rich text- to- image generation. ArXiv, abs/2206.10789, 2022.

A. 付録

A.1. 投機的サンプリングの正当性

ここでは、任意の分布 p(x)p(x) および q(x)q(x) に対して、p(x)p(x) と q(x)q(x) から投機的サンプリングによってサンプリングされたトークンが、p(x)p(x) のみからサンプリングされたトークンと同一の分布に従うことを示す。β\beta を受理確率とする(定義3.1)。

p′(x)=norm(max(0,p(x)−q(x)))=p(x)−min(q(x),p(x))∑x′(p(x′)−min(q(x′),p(x′)))=p(x)−min(q(x),p(x))1−βp^{\prime}(x) = n o r m(m a x(0,p(x) - q(x))) = \frac{p(x) - m i n(q(x),p(x))}{\sum_{x^{\prime}}(p(x^{\prime}) - m i n(q(x^{\prime}),p(x^{\prime})))} = \frac{p(x) - m i n(q(x),p(x))}{1 - \beta} であるから、調整後の分布 p′(x)p^{\prime}(x) の正規化定数は 1−β1 - \beta である。ここで、最後の等式は補題3.3および定理3.5から直ちに従う。

今、以下が成り立ちます。

P(x=x′)=P(guess accepted,x=x′)+P(guess rejected,x=x′)P(x = x^{\prime}) = P(\text {guess accepted}, x = x^{\prime}) + P(\text {guess rejected}, x = x^{\prime})

ここで、

P(guess accepted,x=x′)=q(x′)min⁡(1,p(x′)q(x′))=min⁡(q(x′),p(x′))P(\text {guess accepted}, x = x^{\prime}) = q(x^{\prime}) \min (1, \frac{p(x^{\prime})}{q(x^{\prime})}) = \min (q(x^{\prime}), p(x^{\prime}))

および、

P(guess rejected,x=x′)=(1−β)p′(x′)=p(x′)−min⁡(q(x′),p(x′))P(\text {guess rejected}, x = x^{\prime}) = (1 - \beta) p^{\prime}(x^{\prime}) = p(x^{\prime}) - \min (q(x^{\prime}), p(x^{\prime}))

全体としては、

P(x=x′)=min⁡(p(x′),q(x′))+p(x′)−min⁡(p(x′),q(x′))=p(x′).P(x = x^{\prime}) = \min (p(x^{\prime}), q(x^{\prime})) + p(x^{\prime}) - \min (p(x^{\prime}), q(x^{\prime})) = p(x^{\prime}).

となり、意図したとおりです。

A.2. 投機的サンプリングと棄却サンプリング

棄却サンプリングは、一見すると我々の手法に似ている以下の反復サンプリング手順です。

1. x∼q(x)x \sim q(x) および r∼U(0,1)r \sim U(0, 1) をサンプリングする。

2. もし r<p(x)Mq(x)r < \frac{p(x)}{M q(x)} なら xx を返す。

3. 1 に戻る。

ここで M=maxxp(x)q(x)M = m a x_{x} \frac{p(x)}{q(x)} です。投機的サンプリングの代わりに、棄却サンプリングの非反復版を採用することもできます。具体的には、上記のステップ 1 と 2 を行い、そうでなければ修正されていない p(x)p(x) から直接サンプリングします。しかし、それは我々の手法よりはるかに非効率でしょう。具体的には、ここでの期待採択確率は Ex∼q(x)p(x)Mq(x)=∑xp(x)min⁡x′q(x′)p(x′)≤∑xp(x)min⁡(1,q(x)p(x))=∑xmin⁡(p(x),q(x))=αE_{x \sim q(x)} \frac{p(x)}{M q(x)} = \sum_{x} p(x) \min_{x^{\prime}} \frac{q(x^{\prime})}{p(x^{\prime})} \leq \sum_{x} p(x) \min (1, \frac{q(x)}{p(x)}) = \sum_{x} \min (p(x), q(x)) = \alpha であり、我々の手法における期待採択確率 α\alpha よりも(場合によってははるかに)低くなります。

A.3. 理論的予測と実測実行時間

表 4 は、定理 3.8 に基づく期待実行時間改善率と、表 2 の実測実行時間を比較しています。我々はプロファイラのトレースに基づいて、各種モデルに対する cc の値を推定しました。理論的予測はおおむね実測実行時間と一致していることがわかります。より大きな差は、(1) 我々の実装とベースラインの間の最適化の違い、および (2) β\beta が独立同一分布に従うという単純化仮定が近似にすぎないこと(セクション 3.1 を参照)に起因します。

タスクMQTEMPγαcEXPEMP
ENDET5-SMALL070.750.023.23.4
ENDET5-BASE070.80.043.32.8
ENDET5-LARGE070.820.112.51.7
ENDET5-SMALL170.620.022.32.6
ENDET5-BASE150.680.042.42.4
ENDET5-LARGE130.710.112.01.4
CNNDMT5-SMALL050.650.022.43.1
CNNDMT5-BASE050.730.042.63.0
CNNDMT5-LARGE030.740.112.02.2
CNNDMT5-SMALL150.530.021.92.3
CNNDMT5-BASE130.550.041.82.2
CNNDMT5-LARGE130.560.111.61.7

表 4. 期待改善率(Exp)と実測改善率(EMP)。

A.4. ビームサーチへの応用

本手法は、多少の性能低下を伴いますが、ビームサーチサンプリングにも適用できます。元のビーム幅 ww が与えられたとき、近似モデル MqM_{q} とビーム幅 u≥wu\geq w を用いて γ\gamma ステップのビームサーチを行えます。次に、MpM_{p} を用いてすべての候補を並列に検査します(MpM_{p} の (w+uγ)(w + u\gamma) 回の実行に相当する計算予算を要します)。最後に、各ステップで topw(Mp)⊆topu(Mq)t o p_{w}(M_{p})\subseteq t o p_{u}(M_{q}) である限り MqM_{q} の推測を採択することにより、MpM_{p} 単独での通常のビームサーチと同一の結果が得られます(より精巧な手順を用いれば、得られた候補がたまたま MpM_{p} 単独の場合よりも高い確率を持つケースも採択できます)。この設定における本手法の解析はより複雑であり、今後の課題とします。

A.5. 寛容性

アルゴリズム \boxed{ \begin{array}{r l} \end{array} } の強い性質は、出力分布が変わらないことが保証される点です。とはいえ、良好な保証付きで多少の変化を許容するのであれば、さらなる推論速度の改善が得られます。これをさらに動機づけるために、同一のアーキテクチャとサイズを持つ 2 つのモデルを同じデータセットで訓練した場合、生成される確率分布は同一にはならないため、ある程度の寛容性が理にかなう場合があることに注意してください。本節を除く本論文の結果は、アルゴリズム \boxed{ \begin{array}{r l} \end{array} } の最も厳格なバージョンを用いており、いかなる種類の寛容性も許容していないことに注意してください。

寛容性パラメータ l∈[0,1]l\in [0,1] を含め、アルゴリズム \boxed{ \begin{array}{r l} \end{array} } において p(x)p(x) と比較する前に q(x)q(x) に ll を掛けることもできます。これにより、どのトークンも p(x)l\frac{p(x)}{l} を超える確率でサンプリングされないという良好な保証が依然として維持されます。これは例えば、l=110l = \frac{1}{10} の場合、どのトークンも真の確率の 10 倍を超える確率ではサンプリングされないことを意味するため、極めて稀なトークンは極めて稀なままであることを保証できます(最小確率に関する保証はないため、寛容性はサンプルの多様性を損なう可能性があります)。

具体的には、寛容性因子 ll を用いると、\begin{array}{r l r}{{\alpha}~=}&{{}E_{x\sim q(x)}\left\{\begin{array}{l l}{1}&{l q(x)\leq p(x)}\\ {\frac{p(x)}{l q(x)}}&{l q(x)>p(x)}\end{array}\right.}&{{}=}&{{}E_{x\sim q(x)}\frac{p(x)}{m a x(p(x),l q(x))}}}\end{array} ∑xp(x)q(x)max(p(x),lq(x))=1l∑xmin⁡(p(x),lq(x))=∑xmin⁡(p(x)l,q(x))\begin{array}{r}{\sum_{x}\frac{p(x)q(x)}{m a x(p(x),l q(x))} = \frac{1}{l}\sum_{x}\min (p(x),l q(x)) = \sum_{x}\min (\frac{p(x)}{l},q(x))} \end{array} となります。

表 5 は、MpM_{p} が T5-XXL (11B) で MqM_{q} が T5-small (77M) の場合の、標準サンプリングにおけるさまざまな ll の値に対する α\alpha の値を示しています。c=0.015c = 0.015 において、寛容性の値 1、0.5、0.3、0.1(つまり、どのトークンも真の確率の 1 倍、2 倍、3 倍、10 倍を超える確率ではサンプリングされないことを意味します)を用いると、それぞれ 2.5 倍、3.1 倍、3.6 倍、5 倍の改善率が得られます。

MQl = 1l = 0.5l = 0.3l = 0.1
UNIGRAM0.070.10.110.16
BIGRAM0.190.230.250.32
T5-SMALL (77M)0.620.710.760.84
T5-BASE (250M)0.680.80.830.90

表 5. MpM_{p} が T5-XXL (11B) の EnDe 翻訳タスクにおける標準サンプリングでの、さまざまな ll の値に対する α\alpha の値。

温度=0= 0(すなわちargmaxサンプリング)を使用する場合、上記のような寛容さはもはや使用できないことに注意されたい。代わりに、分布を標準化する前にいくらかの寛容さを許容することができる。例えば、p(x)≤l⋅max⁡(p)p(x) \leq l \cdot \max (p) の場合に、MqM_{q} からサンプリングされたトークン xx を受け入れることができる。この場合、温度=1= 1 の場合と同様の α\alpha 値の経験的な増加が測定される。例えば、英語-ドイツ語翻訳において MpM_{p} T5-XXL と MqM_{q} T5-small に対して寛容さの値1、0.5、0.3、0.1を使用すると、α\alpha 値として0.75、0.75、0.8、0.87が得られる。例えば c=0.015c = 0.015 および γ=8\gamma = 8 とすると、それぞれ3.3倍、3.3倍、3.9倍、4.9倍の速度改善係数が得られる。7