土曜日に七つのO(N²)アルゴリズムを置き換える

あなたのAIは動くコードを書ける。それをスケールするコードにすることこそが、空間ランタイムの勝敗が決まる場所だ——そしてそれはまさにRakuAIが軸としている規律だ。

エージェントたちは動くコードを書くのが得意だ。彼らはスケールするコードを書くのが時々苦手だ。これは私が認識し、それに向けて予算を組むようになったパターンだ:issueの枠組みがXを行う関数を求めるとき、エージェントは小さな入力に対しては正しく動くが実サイズの入力では破綻する関数を書く。

今週の土曜日、私は意図的にそういう関数を探しに行った。七つ見つかった。土曜日の終わりまでに、七つ全部が、エージェントが元々着地させたブルートフォースのプレースホルダーではなく、実際の本番アルゴリズムを実行するようになっていた。

これは、それぞれが何だったか、なぜそれが重要だったか、エージェントがそれぞれについて何を間違えたかについての投稿だ。

パターン

パターンはこのように現れる。issueが提出される。「オブジェクトAとBの間の衝突検出を実装する。オブジェクトが重なったときに検出すること。受け入れ基準:重なったときはtrueを、そうでなければfalseを返すbool関数」

エージェントは関数を書く。関数は動く。関数はO(N²)のブルートフォースだ。オブジェクトが二つなら、それでいい。オブジェクトが二百なら、それでいい。オブジェクトが二千なら、フレームレートは消え去る。

エージェントのプロンプトは漸近的な計算量を指定していなかった。エージェントはプロンプトを満たした。プロンプトはエンジンを満たさなかった。

これは私側の規律の問題であり、エージェントの問題ではない。修正は、プロンプトで計算量目標について具体的にすること、重要なときはアルゴリズムのクラスを明示的に指定すること、そしてこの種のブルートフォースのフォールバックを定期的な頻度で監査することだ。今週の土曜日は監査の頻度だった。

七つの具体的な置き換え

それぞれについて具体的に述べたい。なぜならパターンは同一で、教訓は積み重なるからだ。

一つ目。2D物理のブロードフェーズ衝突検出。 元の実装は、すべてのオブジェクトペアに対する二重の入れ子ループだった。フレームあたりO(N²)。スイープ&プルーン(Baraff、1992年)で置き換えた:軸並行境界ボックスを最小X座標でソートし、一度スキャンする。ペアは、一方のボックスの最大Xが他方の最小Xより大きい場合にのみX軸で重なる。ソートはO(N log N)。スキャンはO(N + K)で、Kは実際に重なっているペアの数。典型的なシーンでは、KはN²よりはるかに小さい。それがこの手法の全趣旨だ。

二つ目。エージェント個体群サブシステムの空間衝突検出。 同じパターン、異なる面。元の実装は、すべてのエージェントを他のすべてのエージェントに対してチェックする二重の入れ子ループだった。空間ハッシュグリッドで置き換えた。各エージェントは、境界セルの座標によってハッシュされる。衝突は、同じまたは隣接するセルのエージェント間でのみチェックされる。セルサイズは、平均エージェント半径のおおよそ二倍に選ばれる。期待計算量はO(N)、全員が同じセルにいる最悪ケースではO(N²)だが、これは通常のプレイでは起こらない。ハッシュ関数はFNV方式の3D座標ハッシュ。ペアの重複排除は、(min(a,b), max(a,b))ペアの順序付きuint64_tセットによる。

三つ目。モデルローダーの頂点キャッシュ最適化。 元の実装は、アセット作者が指定した順序で頂点と三角形をレンダラーに読み込んでいた。ほとんどのオーサリングツールはGPUの頂点キャッシュ向けに最適化しないため、レンダラーはすでに持っていた頂点を再フェッチすることに多くのサイクルを無駄にしていた。Tom Forsythの2006年の頂点キャッシュ最適化で置き換えた:サイズ32のLRUキャッシュモデルで、各候補三角形をキャッシュ内位置の減衰関数とバレンスボーナス(未処理の他の多くの三角形と頂点を共有する三角形はより高くスコアされる)によってスコアリングする。結果は、典型的なメッシュトポロジーに対してほぼ最適な償却キャッシュミス率だ。実装はO(T)、Tは三角形数。

四つ目。ビジョンの特徴記述子マッチング。 ランタイムのコンピュータビジョン・パイプラインは、すべてのフレームで特徴検出を行い、追跡のために連続フレーム間で特徴をマッチングする。元の実装には、入力記述子の固定割合を「マッチした」として返すプレースホルダーがあった。そのプレースホルダーはブルートフォースですらなかった。意図的なスタブだった。置き換えは、Loweの比率テスト(2004年)を用いた実際のブルートフォース記述子マッチングだ。ORB記述子(バイナリ)については、距離指標はXORとカーニハンのビットカウントによるハミング距離。SIFTと浮動小数点記述子については、距離はL²。比率テストは、最良と次点の候補が距離的に近すぎる曖昧なマッチを棄却する。比率テストの閾値は0.75で、これは文献のデフォルトだ。計算量はO(N₁ × N₂ × D)で、Dは記述子の次元であり、ORBでは32バイト。これは文字通りの意味でブルートフォースだが、私たちが扱う記述子の長さと特徴数では十分速く、文献が比較対象とするものでもある。よりスマートな近似(FLANN、階層的k平均)は後の週末のキューに入っている。

五つ目。クロス物理の制約ソルバー。 元の実装は、低い反復回数で固定順序で制約を反復しており、収束しないぐらついたクロスを生んでいた。反復間で適切な制約シャッフルを行う位置ベースダイナミクス・ソルバーで置き換えた。シャッフルが重要なのは、常に同じ順序で制約を処理する制約ソルバーはバイアスがかかるからだ:クロスは予測可能な一方向に伸びてしまう。各反復でシャッフルすることでバイアスが取り除かれる。反復回数は本番品質のために4から12に引き上げられ、ローエンドデバイス向けの4反復の高速パスも用意した。

六つ目。群衆サブシステムのAIエージェント経路計画。 元の実装は、各ステップで有効な隣接ノードをランダムに選ぶプレースホルダーだった。エージェントはランダムな方向をさまよい、時折運良く目的地に到達した。ナビゲーションメッシュ上での適切なA*経路計画で置き換えた。ヒューリスティックはユークリッド距離で、コスト関数は地形の傾斜と地表タイプで重み付けされる。実装はオープンセットにバイナリヒープ、クローズドセットにハッシュセットを使い、ステップあたりのコストはヒープでO(log N)、ハッシュセットでO(1)になる。

七つ目。複数クリップにまたがるアニメーションブレンド。 元の実装は、直近にリクエストされたクリップのみを再生し、他を無視するプレースホルダーだった。適切な重み付きブレンドツリーで置き換えた:各出力フレームは、アニメーション作者が指定するブレンドツリーのトポロジーによって駆動される重みを持つ、寄与クリップのボーンごとの変換の重み付き和だ。ブレンド計算はボーン階層の順序を尊重し、子ボーンが親のブレンドされた変換を正しく継承するようにする。

何を学んだか

三つのことで、振り返れば驚くようなものは何もない。

issueにアルゴリズムを指定する。 自明でない入力サイズを扱うあらゆる関数について、issueの枠組みは期待される計算量を指定しなければならない。「N個のオブジェクト間の衝突を検出する」では不十分だ。「Baraff 1992のスイープ&プルーンまたは同等の手法を使い、最悪ケースO(N log N)でN個のオブジェクト間の衝突を検出する」で十分だ。引用こそが規律だ。それがなければ、エージェントは最も書きやすい正しいもの、つまりブルートフォースを書く。

監査パスは不可欠だ。 着地したPRを読むだけでは、これらを捕まえられなかっただろう。個々のPRはそれぞれ、合格するテストとともに動く関数だった。「ランタイム内でO(N²)以上のすべての関数を見つけ、それがそうあるべきかを評価する」という監査パスが、それらを表面化させる。監査を頻度に加えよう。

文献はチートコードだ。 これらの置き換えのそれぞれは、数十年前の論文に裏打ちされた公開済みアルゴリズムだ。Baraff 1992。Forsyth 2006。Lowe 2004。位置ベースダイナミクス。A*。これらは新奇なものではない。どの論文を読むべきか伝えれば、エージェントはそのどれについても文献に相当するバージョンを書く。

パートナーとビルダーがここから学ぶべきこと

パートナーシップのためにエンジンを評価していて、チームがコードベースのアルゴリズム監査を行っていないなら、一つやるよう依頼してほしい。監査は何かを表面化させる。チームがそれに対してどう反応するかは、どんな機能リストよりも雄弁だ。

パフォーマンスに敏感なコードベースでエージェント駆動のワークフローを実行しているなら、監査パスは省略可能ではない。エージェントは動くコードを着地させる。動くコードは時にブルートフォース版であることがある。監査は、どちらであるかを知る方法だ。

パフォーマンスに敏感な作業のためのコーディングエージェントを構築しているAIラボなら、私が最適化したい指標は「名前がスケーリングの懸念を示唆する関数を実装するとき、エージェントは漸近的計算量について尋ねるか」だ。ほとんどのエージェントは尋ねない。尋ねるエージェントはより良いコードを生み出す。

土曜の午後。七つのブルートフォースアルゴリズムが実際の本番バージョンに置き換わった。エンジンは速くなった。コードベースはより誠実になった。

構築に戻る。