LLaMA：文法ベースのサンプリングを追加

 (github.com/ggerganov)
1 ポイント 投稿者 GN⁺ 2023-07-23 | 1件のコメント | WhatsAppで共有
  • llama.cpp PR #1773 は、文脈自由文法でサンプリング候補を制限し、生成結果が指定した形式から外れないようにする API の追加を提案するもの
  • API は 32 ビットコードポイントベースの文法データ構造を受け取り、llama_sample_grammar で候補トークンをフィルタリングした後、llama_grammar_accept_token で選択トークンを文法状態に反映する
  • main には --grammar と --grammar-file 引数が追加され、拡張 BNF 形式の文法を入力できる。例として Chess、算術式、JSON、日本語文字範囲の生成が示されている
  • テストは M2 Max と 30B Q4_0 モデルで実施され、文法適用時は出力がチェス棋譜・算術式・JSON・日本語文字範囲に沿うよう制限される一方、文法がない場合はプロンプトと異なる通常のテキストやコードが生成される
  • 議論では、文法ファイル対応、空行・コメント処理、パーサーを API に含めるかどうか、GPU ベースのロジットマスキング、固定トークンのバッチ処理、性能オーバーヘッドといった実運用上の制約が重点的に扱われている

PR の主な変更

  • llama.cpp に文法ベースのサンプリングを追加する PR
  • 既存の取り組みとして #1397 と grantslatton の CFG 作業 を参照している
  • 新 API はシリアライズされた文脈自由文法を受け取り、サンプリングを誘導・制限する
  • main には生成文法を指定するための BNF 風文法の例が追加された

Grammar API の構造

  • llama API は 32 ビットコードポイントに対する文脈自由文法データ構造を受け取る
  • 文法要素の型は、規則終了、代替開始、規則参照、文字、文字範囲の上限、代替文字の追加を表す
  • 初期化関数は次の情報を受け取る
    • 規則配列
    • 規則数
    • 開始規則インデックス
  • llama_grammar_element は type と value を持ち、value は Unicode コードポイントまたは規則 ID として使われる

サンプリング方式

  • 文法サンプリングのコードは非決定性プッシュダウンオートマトンをモデル化している
  • 可能なパース状態を表すために N 個のスタックを維持する
  • トークンサンプリングは 2 段階で動作する
    • llama_sample_grammar が候補トークンのうち、いずれかのパーススタックに合う候補だけを残す
    • llama_grammar_accept_token が選択されたトークンを文法状態に追加する

main の文法入力機能

  • main に --grammar と --grammar-file 引数が追加された
  • 2 つの引数は簡単な拡張 BNF 文法を受け取り、生成結果を制限する
  • 文法パーサーは examples/grammar-parser.{h,cpp} に実装されている
  • 対応する文法機能は、文字範囲、グループ化、反復演算子
  • root 規則が文法の開始点を識別する
  • その後のアップデートで、文法ファイル対応、例の追加、シェル風コメント、規則間の空行、括弧グループ内の改行許可が追加された

テスト例

  • テスト環境は M2 Max、30B モデルとして示されている
  • Chess の例
    • --grammar-file grammars/chess.gbnf を使うと、1. e4 e5、2. Nf3 Nc6 のようなチェス棋譜形式が生成される
    • 文法なしで同じプロンプトを実行すると、Sir Thomas Gresham に関する通常の文章が生成される
  • 算術式の例
    • インライン文法で expr "=" ws num "\n" の形式を強制する
    • 結果は 10 *a*1 +b*2 =640 のような算術式形式に制限される
    • 文法がない場合は Go のコード片が生成される
  • JSON の例
    • grammars/json.gbnf を使うと、{ "fullName": ..., "address": ... } 形式の JSON 構造が生成される
    • 文法がない場合は自己紹介風の散文が生成される
  • 日本語の例
    • grammars/japanese.gbnf はひらがな、カタカナ、句読点、CJK 範囲を許可する
    • 文法適用時は日本語文字ベースのリストが生成される
    • 文法なしで実行すると英語のステップ一覧が生成される

レビューと設計上の議論

  • 文法をファイルで受け取る提案があり、その後 grammar file 対応と例が追加された
  • 初期利用中に見つかった問題として、--prompt-cache の衝突と文法内の空行によるクラッシュが報告された
  • 空行とコメント対応、括弧グループ内の改行許可が後続コミットに含まれた
  • パーサーを llama.cpp API に含めるかについて議論があった
    • パーサーが API 外にあると、downstream ユーザーが機能対応のためにパーサーをコピーしなければならないという懸念が示された
    • 作者は llama.cpp 自体の変更を減らそうとしており、パーサーを API に入れるほうが便利である点には同意した
  • llama_grammar がバイナリ文法のコピーを保持すれば、ユーザーが渡したコピーの寿命を維持しなくてよいという提案があった

性能と最適化に関する議論

  • 次の N > 1 個のトークンが文法によって一意に決まる場合でも、現状は 1 つずつサンプリングする方式だと理解されている
  • 複数の固定トークンをバッチ評価すれば、このような場合の推論速度を大きく高められるという議論があった
  • 作者はトークンを評価する必要があり、ボトルネックは評価側に見えると答え、文字列単位のバッチ評価が最適化ポイントになり得ると見ている
  • GPU で文法を状態遷移テンソルにコンパイルしたり、全トークン集合に対して GPU ロジットマスキングを行ったりするアイデアも示された
  • torch-grammar は、全トークン集合に対して GPU 上で文法強制ロジットマスキングを行う類似アプローチとして言及された

性能観測値

  • 作者は CPU 推論しか試しておらず、自身が試した範囲では性能への影響は大きくなかったと述べている
  • M2 Max で観測した数値
    • 非制約サンプリングは約 0.5ms/token
    • 文法適用サンプリングは約 6ms/token
    • 13B Q4_K のトークン評価は約 70ms/token
  • 別のユーザーは、13B で約 20T/s から 13T/s に低下する事例を報告した
  • 作者は通常、文法オーバーヘッドを約 5ms/token 程度と見ているが、特定の文法ではより大きな影響があり、病的なケースもあり得ると考えている

関連する拡張議論

  • JSON Schema 入力を BNF に変換して使う方向が言及された
  • 作者は jsonformer README の例に合わせて動作するローカルブランチがあり、Python スクリプトで JSON Schema に合う JSON BNF を生成すると述べている
  • その後、examples : generate JSON according to schema #1887 がこの PR と関連づけて言及された
  • このアプローチはモデルの変種に依存せず、fine-tune モデルとも併用できると回答された
  • whisper.cpp にも文法ベースのサンプリングを追加した PR が別途言及された

関連記事

1件のコメント

 
GN⁺ 2023-07-23
Hacker Newsのコメント

  • 私の理解では、動作はこうです。言語モデルはプロンプトを出発点にしてトークンを1つずつ出力し、LLMとの対話も、ユーザーがトークン列を渡し、モデルがいくらか生成し、またユーザーが続きをつなげる形で捉えられます。
    この文法手法は、トークンをはるかに細かく制御できるようにします。たとえば Give me the address of the White House as JSON: {"street": " まで与えると、LLMが 1600 Pennsylvania Ave NW" を返し、閉じ引用符が見えた瞬間にユーザーが ", "City": " を注入して、Washington, DC" を受け取る、といった具合です。
    しかもこれは文法ベースなので、JSONだけでなく、はるかに多くのことができます。以前Twitterで見た提案もよくて、OpenAIが決定的文脈自由文法をAPI引数として受け取るようにするか、さらに進めて、サンプラー自体である小さなWASMバイナリを数KB受け取り、数MBのメモリで実行できるようにすれば、LLMの能力を大きく拡張できる、という内容でした。
    https://twitter.com/grantslatton/status/1637692033115762688

    • それだけでなく、LLMは個々のトークンをそのまま出力するのではなく、重み付きの候補リストを出します。もっともそれらしいトークンが最も高い重みを持ちますが、引用符のようなJSON記号を含め、代替候補が複数あることもあります。
      temperature 設定は、最上位ではないトークンが選ばれる可能性を調整して、繰り返し出力を減らします。LLMに文法を守らせるというのは、だいたいの場合、トークン選択の前に候補リストをフィルタリングすることであり、それでもtemperatureが制御するランダム性は残り得ます。
      さらに高度な機能として、AIが行き詰まって有効な出力を作れないときにバックトラックを許可する方式もあります。
    • 実際の動作は、現在の出力とサンプリング候補である次のトークンを文法で検査し、合わない候補トークンをすべて取り除くというものです。残った有効トークンのリストに対して、通常のサンプリング戦略を適用します。
    • この説明は違う気がします。以前から、LLMでトークンを1つずつ読みながら、停止文字に出会ったら止める、という形で出力を制御することはできました。
      文法ベースのサンプリングPRの肝は、llama.cppが文法を使って次に出力できるトークンを、可能なトークンの制限された集合へと絞り込めるようにすることだと思います。
    • これを実装する、より詳しい説明もあります: https://github.com/normal-computing/outlines/pull/131
      Outlinesライブラリの開発者の1人が書いたもので、Outlinesも良いLLMワークフローライブラリです。
    • 何の話なのかよく分かりません。"passing up" のあたりから、この人が用語を勝手に作ったのかと思ってしまいます。LLMに入れられる入力は、トークン化されるプロンプトだけです。
      リクエストの一部としてDCFGルールやそのコンパイル済み版を送るとしても、それがトークン予測の仕組みを根本的にどう変えるのか分かりません。モデルが要求された文法に合わないものを予測したら、合うまでまたプロンプトを入れ直す、という意味なのでしょうか?

  • これは、モデルが生成するテキストに文法的制約をかけるだけで、内容のアラインメントをきちんとしてくれるわけではない、という点は押さえておくべきです。サーバーがきちんと整形されたJSONを出力することを保証したいときには有用ですが、現在の言語生成における多くのアラインメント問題を解決するものではなさそうです。
    たとえば、現在のLlamaやGPTはMarkdownのコードブロックのラベルを間違えることがよくあります。文法ベースのサンプリングでラベルを付けること自体は強制できますが、それが正しいラベルかどうかは文脈依存なので強制できません。新しいドメイン特化言語を作ったうえで、その言語に合わせてアラインさせもせずに良い出力を期待するのも難しいでしょう。

    • 自由形式の文字列が出てくると、LLMが完全に見当違いの方向へ飛んでいくための開かれた招待状になり得る、という点も重要です。だから、こうした方法は、自由テキスト領域に入ったときに反復ペナルティのような別のヒューリスティックでサンプリングにバイアスをかけるやり方と組み合わせて使うのがよいです。
    • それでもLlamaなら、いくつかの例をLoRAに学習させることはできるでしょう。
      たとえば、Markdown用LoRAとMarkdown文法ファイルを必要に応じてホットスワップするシステムを想像できます。

  • これは本当に気に入りました。以前、Constrained Text Generation Studioを作ってみたことがあり(https://github.com/Hellisotherpeople/Constrained-Text-Genera...)、関連論文としてCOLING 2022にも採択されました(https://paperswithcode.com/paper/most-language-models-can-be...)。
    それでも、この方式や、この論文で列挙されている関連アイデアこそが進むべき道だとずっと思っていました: https://arxiv.org/abs/2306.03081
    次は、音節数や統語規則のようなものを強制する文法をどう作れるか考えてみる必要がありそうです。現在のLLMは、トークナイズ方式のせいで、その種の作業がとても苦手です。

    • 意外でしたが、Nous Hermesは俳句をかなりもっともらしく書きます。

  • PyTorch向けにもこれを実装しました: https://github.com/Shopify/torch-grammar。これを使うtext-generation-inferenceのハック版もあるので、必要なら共有できます。

    • 共有してもらえるとうれしいです。LLM UIの1つでトークン確率ベクトルをダンプしてみようとしていたのですが、別の出発点があるとかなり助かりそうです。

  • 多肢選択の文字列列挙型、要するにドロップダウンのようなケースでは、最終選択をするときに貪欲アルゴリズムではなく、ロジットが与えられた状態での全体の結合確率を考慮したほうがうまく動くのか気になります。
    先頭トークンがリスト中の複数項目で共有されている場合、最も一般的な先頭トークンを含む選択肢ではなく、正しい選択肢を優先できるかもしれません。もちろん、ロジットの一部が0になった後は、確率を調整しないと実際には意味をなさないでしょう。

  • この文法「ライブラリ」が形式例として引用されていた: https://github.com/antlr/grammars-v4
    ここにはアセンブリやC++からGLSL、スクリプト言語、算術、ゲーム、freedesktopショートカット、LLVM IR、Verilogのような変わった形式まで一通りそろっている

    • 推論APIでHTML、JSON、Pythonのような 標準文法ショートカット を指定できると便利そう。OpenAIがCode Interpreterモデルの微調整に注いだ労力を考えると、まだこういうことをしていないのは正直不思議
    • ANTLR4文法構文 をサポートしてくれると本当に良さそう。素晴らしいツール

  • 誰か簡単に説明してくれない？ LLMはある程度わかるけど、Georgiがここで何をしているのか、なぜ一部の人がこんなに興奮しているのかがいまひとつピンと来ない

    • LLMは「次のトークン」をそのまま生成しているわけではない。入力テキストの各位置についてトークンに対応する 確率ベクトル を作っていて、各値はそのトークンが次に出る確率に近いと考えればいい
      ChatGPTのようなプログラムはその確率ベクトルを「解釈」して上位トークンのどれか1つを選び、つまりサンプリングしてテキストを作る。だがこの方式は時に柔軟すぎて、JSON出力が欲しくてもJSON文法に合わないトークンを選んで不正なJSONを作ってしまうことがある
      LLMにJSONのようなものを生成するよう「強制」する方法は、サンプリング過程を変えること。上位トークンなら何でも選ぶのではなく、まずJSON文法に合うトークンだけを残し、その部分集合から上位トークンをサンプリングする
    • LLMにJSONや文法を持つ他の言語を生成させると、ときどき不正な構文を作る。このPRは、ユーザーが与えた文法に従って 有効な構文だけを出力 するようLLMを制限するもので、サンプリング手順を変更している
      LLMはテキストをトークン単位で生成する。まず巨大なニューラルネットワークがあり得るすべてのトークンに確率を割り当て、サンプリング手順がその確率を使って1つのトークンを選び、これを繰り返す
      サンプリング手順はニューラルネットワークではないので、さまざまな形に変更できる。常に最も確率の高いトークンを選ぶ貪欲サンプリングも可能だが、通常は確率で重み付けしたランダム選択のほうが良い。多様性が生まれ、ループにはまる可能性も減る。ただし0でない確率を持つトークンなら何でも選ばれうるため、不正なJSONが出ることがある。このPRは、文法的に無効なすべてのトークンの確率を0にして選ばれないようにする
      サンプリング過程には他にも面白い変更が可能。トークンを1つずつサンプリングしていくと行き止まりに入り、選択肢がなくなることがあるので、バックトラックを許すこともできる。さらに各段階で複数の選択肢を考慮して可能な出力の木を作り、最後に全体確率が最も高い経路を選ぶこともできる。すべての選択肢を考えると、可能なトークン数だけ分岐する完全木になって指数的に大きくなるので、各段階で上位たとえば5本の経路だけを残して枝刈りできる。これが ビームサーチ。確率を生成するニューラルネットワークの実行コストが非常に高く、コストが5倍になるようなやり方は負担が大きいため、LLMでは通常使われないが、可能ではあり、結果もある程度良くなる。チェスエンジンのように モンテカルロ木探索 を使うことも考えられる
    • LLMは任意の文字列を平気で生成する。たとえば「Alice: 42」のようなものが欲しいのに、「こんにちは、私は役に立つモデルで、私の見る限りAliceは正確にはforty twoですが、私はただの言語モデルです」みたいなものを出してくることがある
      そこで、応答は大文字1文字のあとに小文字が続き、コロン、空白、数字が来て終わる、という文法を与える。すると最初のトークンを探すとき、そのパターンと両立するトークンだけを考慮し、その後も次のパターンと両立するトークンだけを続けて考慮する
      こうした文法は、その仕事を柔軟で有用なパターンとして実現してくれる
    • ここにある私のコメントを見ればいい: https://news.ycombinator.com/item?id=36820884

  • これは面白いので、自分のやっていることに組み込んでみようと思う。ただ、Bitter Lesson の観点では、ごく短期を除けば最善のアプローチではないかもしれないという気もする: http://www.incompleteideas.net/IncIdeas/BitterLesson.html

    • その場しのぎかもしれないが、重要なその場しのぎではある。今後数年のうちにLLMが制約付きテキスト生成の問題を「自然に」解決するようになるかははっきりしない
    • 専門家では全然ないけれど、OpenAIはプログラミング向けの一部GPT APIでこうした方式を使っていると理解している。単純な文法処理を、それに適した単純なプロセスに渡せば、LLMはより複雑な仕事に 計算資源 をもっと効率よく使える、という推測も見た。本当かどうかはわからない

  • 似た方法を使うプロジェクトもある: https://github.com/automorphic-ai/trex
    Playground: https://automorphic.ai/playground

  • エンドツーエンドのニューラルネットワーク時代に サンプリング/デコーディング がどのように行われているのかを説明する論文や概要を知りたい。HMM時代の機械翻訳や音声認識でデコーディングがどう行われていたかは知っていて、たとえば https://en.wikipedia.org/wiki/Viterbi_algorithm や https://en.wikipedia.org/wiki/Beam_search のようなもの。
    最近は人々が単に「貪欲」方式でやっているような印象があるが、よく分かっていない。このテーマに関する資料のおすすめがあればうれしい

    • 貪欲でありつつランダムでもある :) 論文よりは、たいていのLLM実装のアルゴリズムを見るのを勧める。rwkv.cpp には比較的きれいなPython実装がある: https://github.com/saharNooby/rwkv.cpp/blob/master/rwkv/samp...
    • GPT-4 のドキュメントを読むと、挙げられているものと大きな違いはあまりないように見える
      https://platform.openai.com/docs/api-reference/completions/c...
      もちろん、いまでは GPT-4 が Mixture of Experts 構造であることが分かっているので、内部では計算を並列化している。また、presence/frequency penalty 項でロジットを修正する方法も含まれている