HN 日本語サマリー

← 一覧へ戻る
AI・機械学習

自動化による証明が可能になった

We have proof automation now (imperialviolet.org)

215 pointsby zdw99 コメント

要約

依存型言語における証明の労力は、その強力な型システムにもかかわらず、長らく実用化の障壁となってきました。しかし、大規模言語モデル(LLM)の登場により、証明の自動化が現実味を帯びてきました。筆者はLeanでZstandard解凍器を実装し、LLMが証明エンジニアリングの負担を軽減し、依存型言語をより実用的にする可能性を探りました。

全文翻訳

私は以前から、Coq RocqやLeanのような依存型言語に特別な思い入れがありました。これらの言語は、任意に微妙な不変条件をエンコードし強制できる型システムを提供する可能性を秘めています。通常の言語では(うまくいっても)コメントになるようなもので、チームの規模が大きくなるにつれてすぐに失われてしまいます。そうすると、微妙な誤解が生じ、コンポーネントがうまく噛み合わなくなります。多くの場合、これらのコンポーネントは十分な大きさまで成長しており、問題が発見されたときには、どちらかを調整するのは骨の折れる作業となります。おそらく、依存型型付けが誘惑的に示唆するように、それらの不変条件を形式的に記述し、機械にチェックさせることができるのではないでしょうか。

(追伸:Coqは名前を変えました!何年も前のプリンストンでのCoqカンファレンスで、英語圏においてCoqという名前のプログラミング言語を持つことは障害になると提案したのを覚えています。当時、聴衆は同意しなかったと思います。また、Tyrion Lannisterのスピーチのように聞こえる講演が多いとも冗談を言いました。なぜなら、CoqとHoareがたくさんあったからです。その番組の最終シーズンと、それを集団的に記憶から消し去る前の、面白くてタイムリーなジョークでしたが、完全に的外れでした。)

常に問題だったのは、型システムの強力さには証明の努力が伴うということです。本当に単純なことを証明するために、丸一日費やした経験は確かにあります。証明を行うことは、実際には非常に楽しいです。挑戦的で、インタラクティブで、明確な目標があります。しかし、特に私のようにやり方がわからない場合、それは本当に多くの時間を要します。また、何時間もの努力の末に、証明しようとしている目標が実際には偽であったことに気づくという、周期的な、腹立たしい経験もあります。ここでの古典的な結果は、seL4プロジェクトの回顧録であり、プロジェクトが大きすぎてエンジニアがかなりの経験を積んだにもかかわらず、設計と実装に費やした時間の約10倍の時間を証明に費やしたことがわかっています。彼らは、Cコードの20倍以上の行数の証明コードを作成しました。

このオーバーヘッドにより、依存型言語でのプログラミングは非常にニッチなものになりました。また、人々がそれを自動化しようと駆り立てられる原因にもなりました。私がかすかに知っている試みはF*で、システムはSMTソルバーに義務を自動的に discharge させようとします。これは単純なケースでは確かに機能しますが、SMTソルバーを宇宙に飛ばして何時間も実行させるようなものを簡単に作成でき、それが終わるかどうか疑問に思うことになります。これらの言語を頻繁に使用する人々は、ソルバーを満足させるものが何であるかについての第六感を発達させ、それに合わせてすべてを調整する必要があることを私は見てきました。それは助けになりますが、ある程度は問題を神秘主義に変換します。あなたは複雑で気まぐれな神に仕えることになります。

重要な事実は、少なくとも理論上は、ステートメントが正しい場合、その証明の内容は無関係であり、その存在だけが重要です。これは、2つの要因があるため、完全に真実ではありません。第一に、seL4グループが「証明エンジニアリング」と呼んだものです。コードの変更後に証明を再調整する労力を削減するように証明を構造化する必要性です。第二に、十分に複雑な証明は、型チェッカーさえも爆発させ、大量のメモリを消費する可能性があります。

私たちは今、LLMを持っており、これは証明の無関係性と組み合わさることで、非常に有能な形式の証明自動化を約束します。十分な自動化があれば、証明エンジニアリングについてそれほど心配する必要はないかもしれません。型チェッカーの爆発を避ける必要はまだありますが、私の限定的なテストでは、LLMはそれを避けることができます。潜在的に、LLMは依存型システムを劇的に実用的にします。私はこれを試したかったので、主にZstandardについても興味があったため、LeanでZstandardデコンプレッサーを構築しました。

Zstandardは、gzipを標準的な圧縮ユーティリティとして置き換える競争に勝っているようです。これは別のLZ77スタイルのコンプレッサーですが、より優れたエントロピーコーディングと、非常に印象的な解凍速度を達成できる慎重な設計を提供します。bzip2ほど美しくなることはありませんが、Burrows–Wheeler変換の輝くエレガンスは、実用的な利点が大きいという点ではあまり重要ではありません。

[画像: Zstandard、bzip2、gzip、lzmaの圧縮トレードオフと解凍スループットを示すグラフ。X軸は圧縮率(スペース節約率)、Y軸は解凍スループット(MiB/s、対数スケール)を示しています。](測定は標準の参照コンピューター、つまり著者が当時使用していたもので行われました。また、Y軸の対数スケールに注意してください。gzipとZstandardは独自の速度クラスにあります。これはAppleマシンであり、Appleのgzipは特に最適化されています。他の場所ではgzipは遅くなるはずです。)

Yann ColletによるZstandard(Jarek Dudaの画期的なANS作業を基にしています)にはRFCがありますが、非常に簡潔です。デコンプレッサーを実装するために必要なすべての情報が含まれていますが、圧縮にすでに精通していない限り、何が起こっているのかを理解するために数回読み直す必要があると思います。少なくとも、まともな理解を得たと感じるまで、セクション4.1を6回読み直す必要がありました。このプロセスの遅すぎる段階で、同僚のNigel Taoが、私が管理できるよりも優れたZstandardの解説を書いたことを発見しました。したがって、Zstandardを理解したい場合は、それを読むべきです。私は最も興味深い部分であるエントロピーエンコーダーの説明だけを行い、Leanに関するいくつかのエバンジェリズムと混ぜ合わせます。

エントロピーエンコーダーの仕事は、非均一な確率を持つシンボルのセットが与えられたときに、それらのシンボルのシーケンスを最も少ないビット数でエンコードすることです。古典的なエントロピーコーダーはハフマンエンコーダーです。ハフマンエンコーダーは、シンボルをリーフノードとする二分木を構築し、ハフマンは非常に単純なアルゴリズムが最適なプレフィックスツリーを生成することを示しました。シンボルのリストを取り、最も確率の低い2つを見つけ、それらを子とするツリーノードを形成します。そのツリーノードは、両方の子供の確率の合計を持つ確率を持ち、次に2つのシンボルが少ないセットでアルゴリズムを繰り返します。明らかに、このアルゴリズムの各ステップは要素のセットのサイズを1つ減らすため、終了し、最適なツリーを生成します。ハフマンツリーは非常に高速です。なぜなら、次のnビット(nは最長のコードの長さ)でインデックス付けされたテーブルを構築できるからです。テーブルエントリは、デコードしたシンボルと、読み戻す必要があるビット数を示します。ハフマンツリーの欠点は、各シンボルに整数ビットしか使用できないことです。シンボルがあり、-log2(p) = 2.3 の場合、理想的にはそれをエンコードするために2.3ビットを使用したいでしょう。しかし、ハフマンは3ビットに丸めるか、丸めるかのどちらかを強制され、他のシンボルはより多くのビットを消費することを強制されます。

Zstandardはハフマンツリーを使用しますが、FSEと呼ばれるより高圧縮のエントロピーエンコーダーも備えています。FSEはステートマシンです。シンボルよりも多くの状態があり、各シンボルは、ストリームでの発生確率を反映する状態の割合を受け取ります。したがって、50%の確率で出現すると予想されるシンボルがある場合、それは約50%の状態を受け取ります。各状態には3つの値があります。その状態のシンボル、その状態でビットストリームから読み取るビット数、および次の状態を取得するためにこれらのビットに追加されるベースライン状態番号です。さて、思い出してください、ハフマンツリーの問題は、整数ビットしか使用できなかったことですが、これらの状態も整数ビットを読み取ります。しかし、トリックは、与えられたシンボルに1.5ビットを読み取ることを目指している場合、その状態の半分は1ビットを読み取り、半分は2ビットを読み取ることです。そうすれば、平均で目標に到達します。状態のテーブルは送信されません。RFCは、シンボルの確率のリストからテーブルを構築するためのアルゴリズムを規定しており、したがって確率のみを送信する必要があります。

例を挙げましょう。4つのシンボルがあり、16の状態を使用するとします。したがって、シンボルの確率を16分の1の単位で近似する必要があります。(確率のより正確な近似が必要な場合は、より大きな状態数を使用できます。zstdは実際には32未満の状態数を使用しません。)

state0123456789101112131415
SymbolAABDABCABCABCAAB
Num_Bits2124123122112111
Baseline1204028841206048102

どのシンボルも他のどのシンボルにも続く可能性があり、シンボルは単一の状態しか持たない場合があります。したがって、すべてのシンボルはすべての状態に到達できる必要があります。状態3を見てください。これはシンボルDの唯一の状態です。唯一の状態なので、4ビットを読み取る必要があり、これは他のどの状態もエンコードするのに十分です。しかし、シンボルBのようなものを見ると、その状態は1ビットまたは2ビットしか読み取らないことを要求します。しかし、16の可能な次の状態のセットは、シンボルBの状態の間で正確に分割されています。したがって、特定の状態ごとに、それに到達できるシンボルBの状態は正確に1つだけです。

[画像: FSEデコードテーブルセルが状態空間をタイリングしています。16セルのデコードテーブルで、シンボルBは状態2、5、8、11、15を占めています。矢印はBの各セルを下の宛先範囲に接続しています。状態11は次の状態0〜1をカバーし、状態15は2〜3をカバーし、状態2は4〜7をカバーし、状態5は8〜11をカバーし、状態8は12〜15をカバーします。合計で5つの範囲が16の状態すべてをカバーします。0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 A A B D A B C A B C A B C A A B 0–11ビット 2–31ビット 4–72ビット 8–112ビット 12–152ビット]

再び、シンボルB、確率が5/16であると述べたものを考えてみましょう。そのシンボルをエンコードするのに理想的なビット数は-log2(5/16) = 1.68です。2ビットを読み取る3つのシンボルBの状態と1ビットを読み取る2つの状態があります。状態は均等には使用されず、使用頻度で重み付けされると、平均は量子化された確率の正しい値にほぼ正確になります。真のシンボル確率をより正確に捉えたい場合は、より大きなテーブルを使用してください。

中心的なトリックは、より一般的なシンボルに複数の状態を与えることで、エンコーダーは単にシンボルを選択するだけでなく、そのシンボルのどの状態に着地するかを選択し、その選択が次のシンボルに情報を伝達することです。そこに情報量の小数ビットが行きます。しかし、このエントロピーエンコーダーは依然としてテーブルベースであるため、非常に高速に実行されます。

問題は、順方向に作業できないことです。C、Dをエンコードしたいと仮定します。どのCの状態から開始しますか?まあ、Dは1つの状態しか持たないので、それに到達できるCの状態である必要があります。Dに複数の状態がある場合、Dの後に何が来るかを知って、それらのうちのどれが必要かを知る必要があります。FSEは、シーケンスの末尾から開始して逆方向に作業することを強制します。(通常、シンボル確率を計算するためにシーケンス全体を知る必要があるため、これはそれほど悪くはありません。)さらに、Zstandardコンプレッサーはシンボルを逆順にエンコードしますが、出力を段階的に書き込むため、デコンプレッサーはブロックの末尾にシークしてビットを逆に読み取る必要があります。それはフォーマットのより広範な詳細に入り込み、私はカバーしません。Nigelの記事を参照してください。

基本的なエントロピーエンコーダーは、シンボル間の確率を気にしません。つまり、英語では文字Qの後に文字Uが不均衡に続くという事実を利用できません。それらの冗長性を悪用する何らかの別のエンコーディングが必要です。Zstandardでは、それは従来のLempel–Ziv構造であり、リテラルバイトまたは以前にデコードされたデータへの後方参照をエンコードします。したがって、FSEは主にこれらの後方参照オフセットと長さを効率的にエンコードするために使用されます。

Lean

Leanについて話しましょう!上記で、依存型言語であると述べましたが、これは複雑な定義よりも例でよりよく説明できる概念です。したがって、ストリームからnバイトを読み取り、例外が発生しない場合は、型システムがnバイトの長さであることを知っているバイト配列を返す関数の型を次に示します。

def IO.FS.Stream.readExact (st : Stream) (n : Nat) :
    IO {ba : ByteArray // ba.size = n} := …

2つの数値とバイト配列を返す関数を次に示します。最初の数値は素数であり、2つの数値の合計は6で割り切れ、バイト配列はそれら2つの数値のうち小さい方と同じ長さ以上です。

def getResult :
    IO (Σ a b : Nat, { bytes : ByteArray //
      Nat.Prime a ∧
      6 ∣ a + b ∧
      Nat.min a b ≤ bytes.size }) := …

これは誰も必要としない型ではありません。好きなだけワイルドに行けることを示しているだけです。依存型言語は、非常に複雑な数学的構造さえもエンコードするのに十分であり、Leanの現在の主な用途は、数学を記述し証明するための形式言語としてのものです。最近の本、The Proof in the Codeは、Leanがどのようにして生まれたかの物語の短くよく書かれた説明です。著者は数段落にわたって構成的数学を完全に台無しにしていますが、それ以外は楽しかったです!

LeanはHaskellのような純粋関数型言語ですが、プログラミング言語として非常に便利になる可能性のあるいくつかの特性を持っています。第一に、Leanは厳密ですが、Haskellは遅延評価です。厳密性は、関数への引数が呼び出しの前に評価されることを意味しますが、Haskellでは引数の評価は値が実際に必要とされるまで延期されます。したがって、Haskellでは、高価な式を自由に記述して関数に渡すことができます。なぜなら、それらが実際に使用される場合にのみ計算されるからです。しかし、それはプログラムの非常に驚くべき場所で計算が発生する可能性があることも意味します。これは議論の多いトピックですが、遅延評価のエレガンスは理解できますが、プログラムのパフォーマンスを推測するのは難しい場合があります。

次に、Leanにはいくつかの素敵な糖衣構文があります。そのモナディック do 表記には、forループ、returnステートメント、breakステートメントが含まれています。命令型スタイルでプログラミングしたい場合は、かなり合理的に行うことができます!

最後に、Leanには、参照カウントが1である限り、オブジェクトに変更可能な更新を行う最適化があります。したがって、参照がどこかにあることを確認しない限り、命令型言語と同じくらい効率的に配列をインプレースで変更できます。残念ながら、Leanには私が知っている線形型システムの側面がありません。そのため、値への単一の参照があることを保証するのに役立ちません。コードへのわずかな変更が、どこか目立たない場所に大きな配列への参照を保持することによってパフォーマンスを完全にクラッシュさせる可能性があるという、少し鋭いエッジです。しかし、パフォーマンスを最適化しようとしている場合、より多くのツールが利用可能であることを意味します。

ここに、私がスケッチしたzstdデコーダーからの例をいくつか示します。

while true do
    let some blockHeaderBytes ← input.readExactOrEof 3 | break
    let some blockHeader := BlockHeader.fromBytes blockHeaderBytes frameHeader
      | throw (.userError "invalid block header")
    let blockBytes ← input.readExact blockHeader.contentSize

    match hty : blockHeader.type with
    | .rle =>
      let b := blockBytes.val[0]'(by
        rw [blockBytes.property, blockHeader.contentSize_rle hty]; omega)

9行目に注目してください。配列インデックスがあり、これはまさに暗黙の不変条件が存在する場所です。blockBytesが空であってはなりません!Cライクな言語では、その場合に未定義の動作が発生します。最新の言語では実行時に例外が発生するか、それを回避するためにオプションの値しか提供されません。Leanには別のオプションがあります。空ではないことを証明することです。それが10行目で行われていることです。blockBytes.propertyは、要求された読み取りと同じ長さ、つまり正確にblockHeader.contentSizeバイトの長さであるという事実です。blockHeader.contentSize_rleは次のとおりです。

theorem BlockHeader.contentSize_rle (h : BlockHeader) (hty : h.type = .rle) :
    h.contentSize = 1 := by
  simp [contentSize, hty]

これは、タイプがrleの場合、contentSizeは常に1であることを証明するものです。これらの事実があれば、Leanは残りを理解できます。

これは非常に短い証明であり、おそらく私自身もそれを理解できたでしょうが、私たちははるかに高い目標を掲げることができます。

RFCからFSEテーブル構築アルゴリズムの実装を作成しました。RFCにはそれに対する「テストベクトル」が含まれています。つまり、与えられた確率からの3つのサンプル出力です。明らかに、それらは単体テストに入ります。しかし、Leanでは、関数の普遍的なプロパティを証明することもできます。

theorem ofDistribution_wellFormed (h : ofDistribution accuracyLog probs = some t) :
    t.entries.size = 2 ^ accuracyLog ∧
    (∀ s : Fin probs.size,
      t.entries.toList.countP (fun e => e.symbol == s.val) = probCells probs[s]) ∧
    (∀ (i : Nat) (hi : i < t.entries.size) (v : Nat), v < 2 ^ (t.entries[i]'hi).nbBits →
      (t.entries[i]'hi).baseline + v < 2 ^ accuracyLog) ∧
    (∀ (s : Fin probs.size), 0 < probCells probs[s] → ∀ x < 2 ^ accuracyLog,
      ∃! i : Nat, ∃ hi : i < t.entries.size,
        (t.entries[i]'hi).symbol = s.val ∧ (t.entries[i]'hi).baseline ≤ x ∧
          x < (t.entries[i]'hi).baseline + 2 ^ (t.entries[i]'hi).nbBits) := …

それを言葉で繰り返します。

テーブル構築関数が、「精度」定数とシンボル確率のリストを与えられたときに値を出力すると仮定すると、次のようになります。

  1. テーブルは、その精度に対して正しいサイズです。
  2. 与えられたシンボルの状態数は、その確率を考慮すると正しいです。
  3. すべての場合において、nbBitsビットを読み取り、その状態のベースライン値を追加すると、有効な状態番号が得られます。
  4. 確率がゼロより大きいすべてのシンボルと、すべてのターゲット状態に対して、ターゲット状態に到達できるそのシンボルの状態は正確に1つだけです。

これらは、最適化されたデコードの内部ループが必要とする微妙な仮定であり、より弱い型システムでは暗黙的または単なるコメントにすぎないものです。seL4の回顧録で説明されている10倍の労力の一部であり、通常のソフトウェアへの依存型型の採用における大きな障壁です。いくつかのLLMは、現在約20分で自動的にこれを行うことができ、月額20ドルのサブスクリプションクォータのごく一部しか使用しません。来年には標準になるでしょう。それを行う際にテーブル生成コードを変更する必要があったことを認めなければなりません。Id.run(つまり、命令型モードへのドロップ)を使いすぎたため、証明機構がそれと連携するのが難しくなりました。(しかし、Leanはそれに取り組んでいます。)証明が型チェックされ、sorryがないことを確認しました。

依存型とLLMを組み合わせることは新しいアイデアではありませんが、それを日常のソフトウェアエンジニアリングに適用した例はあまりありません。さらに多くの経験が必要になるでしょう。非常に強力な型は、派生型全体に伝播する必要があるため、変更の範囲を増幅する可能性があります。おそらく、証明の労力は大規模システムではうまくスケーリングしないため、最新のLLMでも追いつけない可能性があります。Leanは高レベル言語であり、すべてに適しているわけではありません。(私のトイのZstandardデコーダーは、コマンドラインのzstdよりも10倍遅いです。)それでも、証明自動化は今ここにあり、実質的に、私たちは新しいタイプのプログラミング言語を利用できるようになりました。それはエキサイティングです!

(コードを公開していませんが、率直に言って、このようによく定義された小さなケースでは、LLMが私よりも良い仕事をする可能性があります。私はLeanを少し学ぶためにこれを行いました。そして、私の探求を模範として提示するつもりはありません。これはlean-zipに触発されたもので、さらに多くのことを行い、コンプレッサーを含み、ラウンドトリップを証明します!)

余談:検証済みアセンブリ

AWSはLNSymを作成しました。これはAArch64のセマンティクスとシミュレーターです。それはクールです。おそらく、それを使用して、関数の最適化されたアセンブリ実装とそのLean対応物との同等性を示し、実行時にアセンブリコードを使用できるでしょうか?そうすれば、LLMに最適化を実行させることができ、機能的なバグを導入できなくなります。検証済みアセンブリは、暗号実装ではよく研究されていますが、おそらく今では安価になるでしょうか?

私はこれを試すために(主にLLMの)時間を費やしました。リポジトリの小さなpopcount例はbv_decideを使用しています。これは認定SATソルバーであり、その例は私のシステムが持っているよりも多くのメモリを必要とします。これは良い兆候ではありません。非常に小さな関数は機能し、小さなLean関数との同等性証明を取得することは可能です。そして、externを使用して実行時にそれらを呼び出すことができます!しかし、私といくつかのLLMは、それをそれ以上スケーリングさせることができませんでした。