大規模言語モデルの効率的なガイド付き生成: 反復解析の拡張

リンク一覧

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

4. 反復解析の拡張

このセクションでは、一般的なパーサーガイド付き生成に焦点を移し、CFG として提供される Python のような文法の簡単なウォークスルーから始めます。

暗黙の CFG に従って Python のような構文を生成するために組み合わせることができる「d」や「ef」などの文字列で構成される語彙を検討し、これらの文字列がアルゴリズム 1 のようなプロセスに従って順番にサンプリングされ、連結されると仮定します。

さらに、CFG 内の終端記号 DEF は文字列 "def" に対応し、単純な正規表現 def で与えられます。また、正規表現 [^\W\d]\w* (例: Python 識別子) で与えられる NAME 記号も考えます。前述の語彙からサンプリングされた文字列を、Python 構文に準拠した方法で順次解析します。

たとえば、次のようなシーケンスが考えられます: ["d", "ef", " f", "oo(", "):", " ", "pass"]。シーケンスのすべての要素は、定義により語彙の要素です。シーケンスを連結すると、"def foo(): pass" が生成されます。これは、関数を定義するトークンの有効なシーケンスです。ここで検討している状況では、特定のポイントまでのすべてのトークンを観察しましたが、そのポイント以降のトークンについては何も知りません。

たとえば、例のシーケンスの 3 番目の観測では、連結された文字列「def f」があります。この文字列を解析/解析する場合、従来のアプローチではシンボル シーケンス DEF NAME が返されますが、これは「f」を完全な NAME トークンとして誤って識別します。シーケンスの残りの部分からわかるように、正しい NAME トークンは「foo」になります。

一般的に、語彙から抽出できる次の有効な文字列は、

1. 現在「f」で始まっているNAMEを拡張/前進させ続ける（この例の完全なシーケンスのように）、および/または

   
   

2. 「(」で始まるもの、つまり正規表現 ( を含む LPAR シンボルであり、有効な引数シグネチャの指定に進みます。

最初のケースでは、「f」は Python で部分的に一致する NAME シンボルとして見ることができ、その正規表現が [^\W\d]\w* であることを思い出すと、正規表現の両方のサブパターン (つまり [^\W\d] と \w*) に一致すると言えます。FSM の使用は、FSM の状態によってサブパターンの概念を形式化します。この場合、NAME の正規表現は、0 (つまり初期状態 q0)、1 (つまり [^\W\d])、および 2 (つまり \w*) の 3 つの状態を持つ FSM M で表すことができます (1、2 ∈ F)。

アルゴリズム 3 を使用すると、「f」の FSM 状態シーケンス (0, 1)、(1, 2)、(2, 2) と、NAME シンボルに対応する FSM M が得られます。「f」のこれらの FSM シーケンスは、この語彙文字列のマッチングが状態 0、1、または 2 で開始され、状態 1 または 2 で終了できることを示しています。

上記のケース 1. によると、NAME シンボルの解析は、以前に状態 1 または 2 で終了した後でも続行できます。ケース 2. によると、次の文字列は LPAR で始まるか LPAR を含む可能性があり、これは M が終了したことを意味します。これは、1 と 2 が M の最終状態であり、"f" を読み取った後に解析が停止していることを考えると可能です。M の終了は、NAME シンボルが完了し、LPAR を受け入れる状態への遷移が文法によって許可されたことも示しています。

この図では、次に有効な語彙文字列は少なくとも「d」、「ef」、「pass」、「」、「oo(」です。これらの文字列はすべて部分的に一致する NAME を拡張し、最後の文字列は解析状態を LPAR を読み取る状態に進めるからです。検討した語彙のサブセットの残りの文字列「:」は、無効な構文のシーケンスになります。

FSM インデックス作成アプローチに関連して、これは、アルゴリズム 4 が、シンボル NAME とその FSM M のサブセット「d」、「ef」、「pass」、「」、「oo(」に FSM 状態 0、1、および 2 をマッピングすることを意味します。

この図では、どの文法記号と遷移が許可されるかを決定する基礎となるパーサー状態は省略されています。 FSM アプローチを拡張し、残りの詳細に対処する手段として、プッシュダウン オートマトン (PDA) を使用します。

4.1 プッシュダウンオートマトン定式化

プッシュダウンオートマトンを次の6組の表現[Sipser, 1996, 定義 2.13]を使用して定義します。

PDA 駆動型パーサーのインデックス作成アプローチを構築するには、CFG のシンボル (対応する PDA のアルファベット経由) と、PDA によって読み取られるシンボルを生成する字句解析およびスキャンの手順との間の接続を使用する必要があります。

より具体的には、セクション 4 で暗黙的に説明したように、パーサーは文字入力のシーケンスからシンボルを識別するレキサーとスキャナーによってサポートされます。各状態のマップ δ によって許可されるシンボルとスタックの遷移に基づいて、各解析/PDA 状態に対して終端シンボルの順序付きリストを構築できます。つまり、各解析状態に対して、その状態によって読み取られた終端シンボルに対応する各 FSM の和集合である FSM を構築できます。

次に、スキャン ステップで、構文解析プロセスで最後に完全に識別された記号以降に読み取られた文字の可能な終端記号のセット V ⊂ Σ を識別します。たとえば、セクション 4 の Python のような CFG の PDA の初期状態 q0 では、文字列 "de" をスキャンして解析すると、V = {DEF, NAME} になります。つまり、文字列 "def" を完成させる任意の語彙文字列の場合は DEF になり、その後に NAME FSM によって読み取られない文字列 (例 "def ") が続き、その FSM によって読み取られるその他の文字列の場合は NAME になります (例 "default")。スキャナのステップと LLM のサンプリング ステップによって、最終的にセット V が縮小され、単一の終端記号 v ∈ V が決定されることに注意してください。

各解析状態の組み合わせられた FSM を使用して V 内の各文字列にアルゴリズム 3 を適用することにより、PDA 状態、対応する FSM 状態、および潜在的な終端記号で構成されるパーサー構成を決定できます。

アルゴリズム 3 の手順と同様に、PDA の遷移マップのプリイメージを使用して、PDA 状態 q ∈ Q とパーサー構成の終端記号セット V を読み取る PDA スタック値を決定できます。

このマップによって提供されるスタック値は、可能なパーサー構成から始めて、V 内の各文字列の完全な解析を成功させる PDA 経由のパス (存在する場合) を見つけるために必要です。LALR(1) パーサーの REDUCE 操作に対応するパーサー状態とターミナルの組み合わせの場合、これらのパーサー構成は、Γ 内のスタックの最上位値だけでなく、語彙文字列によって必要な REDUCE 操作のすべての有効なプレフィックスに対応するサブスタックで構成されます。最終的に、語彙文字列の完全な解析を許可する各パーサー構成は、PDA のインデックスのエントリとして追加されます。この場合、パーサーのスタック値に対するクエリを可能にするために、インデックスはトライデータ構造である必要があります。