トップ > テクノロジー > LLMにJSONやソースコードを出力させるStructured Generationの技術

LLMにJSONやソースコードを出力させるStructured Generationの技術

テクノロジー AI OSS

こんにちは、イノベーションセンターの加藤です。この記事では、大規模言語モデル(LLM)にJSONやソースコードを正しく出力させるための生成手法であるStructured Generationについて紹介します。

Structured Generationとは

大規模言語モデル(LLM)はよくチャットボットとしての活用が目立ちますが、LLMの入出力を外部のプログラムに繋ぎ込むことでより高度な自然言語処理システムを作ることができます。 例えばOpenAIのCode Interpreter1はLLMをPythonの実行環境と接続することで、ユーザーに要求された複雑な情報処理をまずPythonコードに書き起こし、その実行結果を使って応答するシステムです。 また、Meta社によるアシスタントロボットの取り組み2ではユーザーの音声入力をテキストに書き起こし、LLMがその文章からプログラムが解釈可能な命令列に変換することで自然言語とプログラムの橋渡しを行なっています。 このように、特定のスキーマに沿ったJSONや特定のプログラミング言語でのソースコードといった構造化データをLLMに出力させるStructured Generationが最近注目されています。

しかしながらこのようなユースケースではLLMの出力形式がブレるとシステムが動作しなくなるため、ファインチューニングやプロンプトの工夫だけでは不十分です。 下図のようにJSONの出力を例にとると、プロンプトで「JSONのみを出力してください」と指定していても、関係のない文章やコードスニペットの記法を混入させてしまうことが多々あります。

そこで、プロンプトのような確実性のないものに頼るのではなく、出力として選択されるトークンの候補をコントロールすることで、目的のフォーマットに必ず従わせる制約付き文章生成の手法が広く研究されています。

パーサーを用いた制約手法

LLMなどの文章生成モデルは、これまでの単語列から次に現れそうな単語を自信度の形で予測し、何らかの戦略のもとで出力する単語を決定します。一般的に使われている戦略は貪欲法で、毎回最も自信度の高い単語を出力することを繰り返すことで文章を生成していき、文章の終了を表すトークン(よくEOSとして表されます)を出力した時点で停止します。 Structured Generationでは以下の画像のように、選択前に好ましくない単語の自信度を全て0にすることで文法的に正しくない文章の出力を防いでいます。

そしてどの単語が文法的に好ましくないかを判定するために、その文法に対応したパーサーが使われます。 パーサーは基本的に入力文章を頭から読み取っていき、文法的に正しくない文字列が現れたところでエラーが発生するようになっています。Structured Generationではこの性質を利用して、LLMが予測する次の単語をパーサーに入れてみて、エラーが起こるようならその単語を除外することで文法的に正しい出力を実現しています。

しかし、この方法では1単語生成するたびに数万近くあるLLMの語彙を走査してパーサーに判定させる必要があるため、計算時間が非常にかかってしまいます。 そこで、パーサーの動作を利用して判定を効率化するテクニックがいくつか研究されています。 本記事ではStructured Generationでよくサポートされる正則言語と文脈自由言語の２種類のパーサーに対して効率的な制約付き生成手法を紹介します。

正則言語とは

正則言語は後方参照を用いない正規表現で表現可能な言語のことで、例えば「整数」は/0|(-?[1-9][0-9]*)/として表現できます。 正則言語のパーサーは決定性有限オートマトン(DFA)で実装できることが知られています。DFAとは入力文章を頭から読み取っていき、入力文字と現在の状態から定まる次の状態へ遷移することを繰り返す機械のことで、前述の「整数」を判定するDFAは以下のように構成できます。

この丸が状態で矢印が読み取った文字に対応する遷移先を表しており、文字を全て入力して最終的に二重丸の状態（受理状態）に移動していればOKという判定がなされます。 例えば「整数」を判定するDFAに「-16」という文章を入力すると次のように状態が遷移し、「-16は整数である」と判定されます。

一方で、例えば「0-1-1」という文章は途中で遷移に失敗します。また、「-」という文章は最終的に受理状態に到達しません。そのためこれらは整数とは判定されません。

正則言語のStructured Generation

このようなパーサーをStructured Generationに活用する場合は、「文法的に正しくない文字列が現れる」という現象を「この先受理状態へ到達し得ない状態に遷移してしまう」と読み替えることができます。 例えばLLMに整数を出力させようとしており、現状の中間出力が何もない場合、「090」や「apple」という単語は出力できませんが、「0」や「-」という単語は受理状態もしくはこの先受理状態へ到達可能な状態に遷移可能なので出力しても良いと判定されます。

そうした状態と単語の組み合わせの数は有限であることを利用するとうまく判定を効率化できます。

各状態qから各語彙tを入力した時に「この先受理状態に到達可能な状態」に遷移するかを前計算しておき、dict[q][t]として保存しておきます。この結果をマスク処理で利用することにより、状態数QとLLMの語彙数Tに対してサイズQ*Tのメモリ消費のもと、長さTのマスク処理だけで各単語の出力可否を判定できます3。

これにより、LLMの選択肢に挙がった単語を毎回DFAに入力していたことで発生する計算時間を減らすことができます。

文脈自由言語とは

文脈自由言語は正則言語よりも表現力の高い言語で、JSONのようにネスト構造を持つ言語もこれに属しています。 文脈自由言語を表現する文法の定義は少し複雑で、以下の4つをまとめたものになっています。

  • 終端記号の集合 (文を構成する最小単位)
  • 非終端記号の集合
  • 開始記号と呼ばれる特別な非終端記号
  • 1つの非終端記号から0個以上の記号列への変換規則

そしてこの文法が表現する言語は開始記号から変換を繰り返して生成可能な終端記号列の集合となります。例として次のような文法を考えてみます。

  • 終端記号 a, b
  • 非終端記号 S, E
  • 開始記号 S
  • 変換規則 S→aE, E→Sb, E→b

Sから適当に変換規則を選んでいくと、例えば S→aE→aSb→aaEb→aabb と繰り返して aabb が生成されます。 そのため aabb はこの文法で表現された言語に含まれていることが言えます。 実はこの文法は「任意の正整数Nに対して、aをN個並べ、その後bをN個並べた言語」を表しています。 このように正規表現では作れないような言語も表現できることが文脈自由文法の特長です。

よくプログラミング言語などの定義で現れるBNF(バッカスナウア記法)やEBNF(拡張BNF)はこの文脈自由文法を簡易的に記述するための記法です。 例えば先ほどの文脈自由文法に対応するBNFは次のようになります。

<S> ::= "a" <E>
<E> ::= <S> "b" | "b"

""で囲われている単語は終端記号、<>で囲われている単語は非終端記号と見なすと、これが文脈自由文法のいち記法に過ぎないことがわかりやすいかと思います。

こういった文脈自由言語を解析するときは、基本的には与えられた文章を生成するための変換の過程を特定できれば解析できたことになります。 この過程は構文木と呼ばれるもので表現でき、例えば先ほどの文法に対してaabbという文章はS→aE→aSb→aaEb→aabbと変換されたわけですが、これを以下のような木で表現できます。

文脈自由言語のパーサーはこの構文木を作成するのが最終目的ですが、解析手法にはさまざまなものがあります。 一般的にパーサーで広く使われているのはLALR(1)法と呼ばれているもので、文頭から1単語ずつ読み出していき、構文木を右の葉側から特定していく手法です。 例えば前述の文法に対して「a a b」までを入力すると次のように作りかけの構文木が出来上がります。

字句解析について

一般的なプログラミング言語のパースにおいては、文脈自由文法での解析を行う際の複雑さを減らすために、文字レベルでは無くある程度まとまった文字列にまとめてから分析を行います。 例えばJSONでは以下のように文字列がまとめられて終端記号に変換されます。

  • 文字列リテラル ("John" など) → STRING
  • 数値リテラル (-3, 1.2 など) → NUMBER
  • 配列用の開きカッコ [ や閉じカッコ ] → LBRACK, RBRACK
  • 配列内のカンマ → COMMA
  • 辞書用の開きカッコ { や閉じカッコ } → LBRACE, RBRACE
  • 辞書内のコロン → COLON
  • 真偽値やnull → TRUE, FALSE, NULL

このルールにもとづくと、例えば {"temperature": 25.7} というJSON文字列は LBRACE STRING COLON NUMBER RBRACE という終端記号列に変換されます。 このように文字列から終端記号の列への変換を字句解析と呼び、正則言語などの比較的シンプルなルールで解析が行われています。

正則言語+文脈自由言語のStructured Generation

前節で説明したように、一般的なプログラミング言語にLLM出力を制約したい場合はDFAによる字句解析とLALR(1)による文法解析を行うパーサーを利用します。 このパーサーには次に現れるべき終端記号の候補がわかるという特徴があり、これをLLMの出力制約に用いることができます。 具体的には次のようにLLMの語彙に制約を与えられます。

  • LLMの中間出力をパーサーに与えて途中まで字句解析させる
    • 例：{“key”: [ → LBRACE({) STRING(“key”) COLON(:) LBRACK([)
  • 確定した終端記号をパーサーに与えて途中まで文法解析させる
  • 次に続くことができる終端記号を列挙する
    • 例：{"key": [ に続く終端記号は文字列STRING, 数値NUMBER, 辞書の開きカッコLBRACE, 配列の開きカッコLBRACK, 配列の閉じカッコRBRACK
  • 各終端記号を判定するDFAから、前計算しておいた語彙マスクを取り出す
  • 語彙マスクの和集合を取り、次に続くことができるLLMの単語を列挙する

これにより、文脈自由文法の終端記号の種類数に比例した計算量でStructured Generationを行うことができます。この終端記号の種類数はLLMの語彙よりもずっと少なく、例えばPythonでも94種に抑えられることが知られています4。

まとめ

今回はLLMにJSONの出力やプログラムのソースコードの出力などを安定させたい場合に有用なStructured Generationについて紹介し、 語彙に制約を与えるための具体的な手法と効率化のアルゴリズムについて解説しました。

  1. https://platform.openai.com/docs/assistants/tools/code-interpreter↩
  2. https://languageguidedskillcoordination.github.io↩
      1. Willard and R. Louf, "Efficient Guided Generation for Large Language Models", https://arxiv.org/abs/2307.09702
    ↩
    1. Ugare et al., "SynCode: LLM Generation with Grammar Augmentation", https://arxiv.org/abs/2403.01632
    ↩
© NTT Communications Corporation 2014