大規模言語モデルの効率的なガイド付き生成: 反復的な FSM 処理とインデックス作成

リンク一覧

• 概要と序文
• LLM サンプリングとガイド付き生成
• 反復的な FSM 処理とインデックス作成
• 反復解析の拡張
• 議論、参考文献および謝辞

3. 反復FSM処理とインデックス作成

正確には、5組の有限オートマトン形式の正規表現を考えます[Sipser、1996、定義1.5]。

定義 1 (有限オートマトン)。有限オートマトン、または有限状態マシンは、(Q、Σ、δ、q0、F) で表されます。ここで、Q は有限の状態の集合、Σ は有限のアルファベット、δ : Q × Σ → Q は遷移関数、q0 ∈ Q は開始状態、F ⊆ Q は受け入れ状態の集合です。

V 内の文字列を構成する文字は Σ から抽出されます。つまり、V ⊂ P(Σ) です。全体を通して、FSM 状態 Q は、簡潔にするために整数値で表されます。

例 1。図 1 では、浮動小数点数を生成するために使用できる正規表現 ([0-9]*)?\.?[0-9]* の FSM サンプリング プロセスを示しています。簡単にするために、語彙 V は文字列 "A"、"."、"42"、".2"、および "1" のみで構成されているものとします。

生成が始まると、FSM は状態 0 になります。そのため、アルゴリズムは文字列「A」をマスクします。これは FSM によって受け入れられないためです。この場合、「.」、「42」、「.2」、および「1」のみをサンプリングできます。

「.2」をサンプリングすると、FSM は状態 3 に進みます。この場合、「42」と「1」のみが有効な補完であるため、サンプリング前に他の値をマスクします。代わりに「1」をサンプリングすると、FSM は状態 1 に進みます。この場合、「.」、「.42」、「.2」、および「1」が有効な補完であり、マスクは変更されません。

語彙をループして有効な次のトークンを決定することが、依然として最大の問題です。そのために、正規表現の FSM を使用して語彙を前処理し、インデックスを構築します。重要なのは、語彙内の文字列が正規表現の任意の部分と一致する可能性があり、それらの部分が暗黙的に FSM 状態であるため、実行可能なすべての FSM 状態から開始することを検討することです。

FSM 内の任意のポイントから始まる一致を生成する手順は、アルゴリズム 3 に示されています。結果は、提供された文字列を受け入れるときに FSM が通過する状態の詳細を示すサブシーケンスのリストです。

これらのサブシーケンスの開始状態を、アルゴリズム 2 のループの 1 つのステップで到達した最後の FSM 状態に一致させることにより、FSM 状態と、それらの状態で FSM によって受け入れられる語彙の要素のセットを接続するマップ σ : Q → P(V) を使用して、語彙を効率的にインデックス付けできます。

アルゴリズム4はσの構築について説明します。

σ にハッシュマップを使用すると、アルゴリズム 2 の m ステップのコストは平均で O(1) のみになります。さらに、σ はトークン サンプリング手順の外部で構築されるため、実行時のコストは実質的に無関係ですが、理論的には FSM の状態数 (つまり |Q|) に等しいメモリが必要です。幸い、正規表現と語彙の非病的な組み合わせの場合、語彙内のすべての文字列が FSM に受け入れられるわけではなく、すべての FSM 状態が V の文字列で表されるわけではありません。

3.1 例

このセクションでは、GPT2-medium (355M パラメータ) を使用して、正規表現ガイド生成が実際にどのように機能するかを説明します。生成にはライブラリ Outlines を使用します。

リスト3.1 – 続き

リスト3.3 – 続き

3.2 現在の方法との比較

ここで説明し、Outlines に実装されているインデックス作成アプローチの効率性を示すために、Guidance ライブラリとの簡単な比較を行います。この記事の執筆時点では、Guidance ライブラリは部分的な正規表現マッチング (毎回、サンプリングされたシーケンスの先頭から適用) を使用しており、各ステップで LLM の語彙 (N = 50、257) を反復処理する必要があります。

この比較に使用されるガイダンス コードとプロンプトは次のとおりです。

リスト3.4 – 続き

対応するアウトライン コードは次のとおりです。

リスト3.5 – 続き

max_tokens の値は変化し、単一のループと単一の繰り返し値に対して timeit を使用してタイミングが記録されます (つまり、max_tokens の各値に対して 1 つのサンプルのみが収集されます)。結果はセクション 3.2 にプロットされています。

大きな実行時の不一致を引き起こす可能性のある構成の見落としがなければ、サンプリングされたトークンの最大数の観察されたスケーリングは顕著であり、このアプローチによって暗示される計算上の問題が増大していることを示しています。