アルゴリズム主義者Iの初期発見：大規模での検証可能なアルゴリズム合成の約束

Abstract

実運用でも良好に機能し、かつ保証を厳密に証明できるアルゴリズムを設計することは依然として難しく、数学的な推論と慎重な実装の両方が必要です。最悪の場合の理論と経験的な性能を橋渡しする既存の手法、たとえば beyond-worst-case（最悪の場合を超えた）解析やデータ駆動型のアルゴリズム選択では、通常、事前の分布に関する知識を仮定するか、あるいは固定されたアルゴリズムの集合に対象を限定しています。近年のLLMの進展は、新たな可能性を示唆しています。それは、必要に応じてその場で証明可能なアルゴリズム合成を行うという考え方です。これを研究するために、GitHub Copilot の上に構築した、自律型の研究者エージェント Algorithmist を作りました。Algorithmist は、アイデア生成、アルゴリズムと証明の開発、証明に導かれた実装、証明・コード・それらの整合性のレビューという別々の段階を持つ、多エージェントによる研究とレビューのループを実行します。私たちは、Algorithmist を、非公開データ解析およびクラスタリングに関する研究レベルの課題で評価しました。プライバシー、近似、解釈可能性という要求を同時に満たす実用的な方法を設計するよう求められたとき、Algorithmist は、研究スタイルの書き起こしと監査済みの実装とともに、証明的に健全であり、かつ経験的にも効果的なアルゴリズムを生成しました。また、一部の設定では改善されたアルゴリズムを見つけ、別の場面では原理的な障壁を説明し、さらに先行して公開された研究に潜む微妙な証明のバグを発見しました。より広く言えば、私たちの結果は、LLMシステムが、各データセットとデプロイ環境に合わせて調整された研究論文品質のアルゴリズム成果物を生成する、新しいパラダイムを示しています。加えて、コードが、構造化された自然言語の証明の中間表現とともに開発され、合成の過程を通じてその表現と整合が保たれる、証明優先のコード合成パラダイムの可能性も示しています。