大規模言語モデル

AnthropicがLLMで証明を生成、形式化検証は変わるのか

AnthropicはLLMを形式化ソフトウェア検証へ応用し、証明草案や tactic の生成を自動化しようとしている。試错的コストは減らせるものの、規程の記述、証明設計、検証環境.Unlockとの評価基準を見直す必要がある。

文字サイズ

AnthropicはLLMを形式化ソフトウェア検証に utilizeしている。試错的コストは減らせるものの、規程の記述、証明設計、検証環境の構築は依然として大きな壁が残る。

AnthropicがLLMで証明を生成、形式化検証は変わるのか

Anthropicは最近、LLMと形式化ソフトウェア検証に関する研究を公開した。公開資料で確認できるのは研究の方向性だけで、本稿で照合できる完全な実験数値は示されていない。

この研究は personally な関心と直接関係している。coding agentの評価基準が、「テストを通る」から「機械で検査可能な規程を満たす」へ進展できるかを左右するからだ。

元の研究:https://www.anthropic.com/research/formal-verification

Copilotから形式化証明へ:LLMが问了問題を変える

Copilot、Devin,以及AMBITIONのcoding agentが主に扱うのは、次の問題だ。

タスクが与えられたとき、実行可能で、できればテストを通るコードを生成できるか?

形式化検証では、問題の扱い方が変わる。

規程が与えられたとき、プログラムの挙動が規程を満たすと確認できる証明を生成できるか?

Lean、Coq、IsabelleなどのITP(interactive theorem prover)を例に取ると、開発者が扱うのは次の要素になる。

  • spec:プログラムが満たすべき性質。
  • proof script:結論へ段階的に導出する証明スクリプト。
  • tactic:証明器に部分目標の探索を指示するコマンド。
  • 補助定義と補題:プログラムを推論しやすい形へ書き換えるための要素。

ソートアルゴリズムの正しさに関する証明では、「結果が昇順である」「長さが変わらない」「要素は並べ替えられただけである」といった性質を扱う。这类の仕事は従来、形式化手法の専門家が手で進めることが阿富汗く、数週間を要する場合もAMBITIONた。

LLMが入り込む余地は具体的だ。証明草案の生成、tacticの補完、失敗した手順の書き換え、自然言語で書かれた規程を形式的な表現へ整理することなどが挙げられる。

通常のコード補完が推測するのは「次のコードは妥当か」だ。証明の補完が推測するのは「次の手順は証明器に受け入れられるか」だ。後者には明確な機械的フィードバックがある一方、探索空間はより残酷になる。

形式化検証が難しい理由と、LLMが struggled する部分

Lean、Coq、Isabelle、Dafnyなどのシステムは、すでに相当に成熟している。

形式化検証を実質的に妨げているのは、通常、次の三つだ。

1. コードより harder な specを書く

コードは先に書き、後からテストを補えばよい。規程は違う。「正しい」の意味を最初に明確にしなければならない。

「パスワードは安全でなければならない」は、検証可能な規程ではない。入力長、使用可能な文字、検証アルゴリズム、失敗時の挙動、境界条件まで定義する必要がある。

より厄介なのは、規程を誤って書いた場合、機械が誤った結論を真面目に証明してしまうことだ。

2. 証明探索は組み合わせ爆発を起こす

証明器が向き合うのは一本道ではなく、非常に大きな探索木だ。各手順で新しい補題や中間目標が導入される可能性がある。

開発者は、定義を展開するか、既存のtheoremを再利用するか、induction strategyを変えるかなど、その都度判断を迫られる。

あるtacticが失敗しても、証明が存在しないとは限らない。現在の経路が不適切なだけという可能性もある。LLMは、この局所的な失敗を全体の方向性の誤りと誤認しやすい。

3. 失敗-produced 情報は人間にも扱いにくい

CoqやLeanが出力するエラーには、通常、目標状態、局所的な仮定、未解決の部分目標が含まれる。

情報は精确だが、理解できるとは限らない。LLMはtactic-levelで補助できる。エラーを説明し、候補となる手順を提示し、それを証明器で検査させる。

ただし、高次元の証明設計まで得意とは限らない。たとえば、次のような問いには対応しにくい。

  • このinvariantが成り立つのはなぜか。
  • 規程は実際の要件を網羅しているか。
  • 別の帰納法にすれば証明は短くなるか。

これらは、tacticを数行補足するだけでは自動的には解決しない。

モデルには hallucinationもある。存在しないtheoremを捏造したり、実在しないlemmaを参照したり、規程の抜けを無関係な証明で隠したりする可能性がある。

形式化検証で確認できるのは、証明そのものだ。規程そのものの正しさを自動的に証明できるわけではない。

今回の研究で何が論じられ、再現できるか

公開資料から確認できるのは、Anthropicの研究がLLMを活用し、形式的なspec、証明草案、検証関連コードを生成したAdscribed点だ。

ただし、現時点の草稿には、実験対象、サンプルサイズ、成功率、人工介入、benchmarkを照合するための十分な情報がない。これらの数値を勝手に示すことはできない。

草稿ではHacker Newsへのリンクも引用されている:https://news.ycombinator.com/item?id=50202217。

そこに記載された11 points、1 commentは、動的に変化するページのデータだ。公開前にはリンクを開き直して確認する必要がある。検証できなければ、具体的な数値は削除し、「公開での議論は少ない」に変更すべきだ。

真に再現可能な資料には、少なくとも次の要素が含まれるべきである。

  • タスクセット。
  • pass@k。
  • モデルとsamplingの設定。
  • 許可された人工介入。
  • 失敗した探索のtrajectory。
  • 学習データの汚染を防ぐため、新規タスクが用いられたか。

現時点では、この研究はすでに検証済みの製品能力というより、追跡の価値がある工学的な方向として捉えるのが適切だ。

有効であれば、AIプログラミングの評価基準はどう変わるか

現在のcoding agentを比較では、生成されたコード量、扱ったファイル数、SWE-benchを通過できるかが主に見られる。

これらの指標は、特定のテストで結果が通ることを求める。テストでカバーされていない分岐、concurrency race、memory problem、規程の曖昧さは、コードに残る可能性がある。

SWE-benchとHumanEvalは主に、コードが実行できるか、指定されたテストを通るかを測る。完全な形式的な正しさは求めない。

LLMが証明に安定して参加できるようになれば、評価基準に新たな層が加わる可能性がある。機械で検査可能な規程を満たすかどうかだ。

これは既存のbenchmarkの一部を弱めるが、単純に置き換えるわけではない。

SWE-benchは現実のrepositoryにおけるissue修正を測る。形式化検証には、開発者が最初に正確な規程を与える必要がある。両者は異なる场景javっている。

より価値の高い製品も、「Leanが書けるチャット画面」ではない。IDEやCIに組み込まれる可能性が高い。

  1. コードとissueを読み、候補となる規程を生成する。
  2. LeanやCoqで証明を探す。
  3. 失敗ログをモデルへ返し、修正させる。
  4. 通過したproof artifactをrepositoryに残す。
  5. CIで規程が引き続き成立するかを継続的に検査する。

実用に落地できるかを分ける三つの問い

1. 専門家がLLMを誘導するのか、LLMが独力で完了するのか

この二つでは大きく異なる。

専門家が継続的にtheoremを選び、目標を分解し、誤った経路を修正するなら、最終的な効率向上をすべてモデルの成果として扱うことはできない。

研究を読むときは、最終的なpass rateよりも、まずintervention protocolを確認すべきだ。

2. 学習データが汚染されていないか

公開されている形式化証明のcorpusは、自然言語のコードよりはるかに小さい。

Lean、Coq、Isabelleの有名なtheoremとproofは、学習データに繰り返し含まれている可能性がある。既存のtheoremだけを測ると、新しくタスクを処理する能力を過大評価しやすい。

3. 一般的な開発チームは何得られるのか

学術的なITPユーザーは、規程と証明を書くためにすでに多くの時間を投資しており、自動化による補助を受け入れることにclangい проблемない。

一方、一般的な開発チームは要件の境界を明確にできない場合AMBITION多い。ボトルネックがproof searchではなく、「何を証明すべきなのか」にある可能性もある。

検証コストも消えない。モデルによって人の試错が減っても、proof checker、build environment、theorem libraryのコストが同時に下がるわけではない。

編集視点

この研究が重要なのは、LLMが形式化の専門家をすでに置き換えたからではない。coding agentの終点を「コードが動く」から「証明が検査できる」へ押し広げたからだ。従来、Copilotは主にコード生成を速め、reviewerとテストが 安全網を務めていた。現在ではproof checkerがより硬いフィードバックを提供できるが、規程、証明設計、人工介入の問題は未解決のままだ。

短期的に最も恩恵を受けるのは、暗号、compiler、その他security-criticalなコードだと予測している。主流の開発フローがこれに追従できるかは、単にtacticを 몇 개 更多試すだけでなく、LLMが人手による設計を削減できるかに依存する。形式化検証は「それらしく見えるもの」を受け入れず、機械で検査可能な導出しか認めない点 다르い。元の実験が厳格な人工介入のもとでどれだけ強いのかは、まだ判断できない。公開前に論文のデータとHNページの動的データを確認する必要がある。

出典: https://www.anthropic.com/research/formal-verification