Robust Multi-Agent LLMs under Byzantine Faults

技術的概要：ビザンチン障害下におけるロバストなマルチエージェント LLM

問題定義
大規模言語モデル（LLM）エージェントは、協調的合意を通じてタスクを解決するため、ピアツーピア型マルチエージェントシステム（LLM-MAS）への導入が増加しています。しかし、これらのシステムは重大な脆弱性に直面しています。不安定なエージェントやビザンチンエージェント（幻覚による故障、または意図的な操作による敵対的なエージェント）は、誠実なエージェントを誤った結論へと誘導する可能性があります。既存のアプローチ、例えば CP-WBFT は、エージェントが自身の信頼スコアを自己報告し、それに基づいて隣接エージェントの応答に重み付けを行う方式に依存しています。このアプローチは根本的に欠陥があります。なぜなら、ビザンチンエージェントは自身の信頼スコアを偽造して集約プロセスを支配できるからです。さらに、従来の手法はしばしば原理的な通信トポロジーを欠いており、その結果、協力を行わない場合よりもパフォーマンスが低下する事態を招いています。核心的な課題は、恣意的または誤った情報を注入する可能性のあるビザンチンエージェントが存在する状況下でも、誠実なエージェントが反復的に応答を洗練させ、正しい合意に到達できるような分散型プロトコルを設計することです。

手法：自己アンカー型合意（SAC）
著者は、完全分散型で反復的なフィルタおよび洗練プロトコルである**自己アンカー型合意（Self-Anchored Consensus: SAC）**を提案します。送信者が報告する信頼性を信頼する従来の手法とは異なり、SAC は評価の負担を受信側にシフトさせます。このプロトコルは、1 ラウンドあたり以下の 4 つの段階で動作します：

1. ブロードキャスト：各エージェントは、現在の応答を隣接エージェントに対してブロードキャストします。
2. 受信側スコアリング：隣接エージェントからの応答を受信すると、各エージェント $i$ は自身の LLM を用いて、各隣接エージェント $j$ に対して評価スコア $s_{i \to j}$ を独立して計算します。このスコアは、クエリに対する隣接エージェントの応答の正しさを検証するプロンプトから導き出され、送信者による自己報告の信頼スコアとは完全に切り離されています。
3. フィルタリング：エージェント $i$ は、自身の自己スコアよりも厳密に低いスコアを持つ隣接エージェントを特定します。その後、このセットからビザンチン隣接エージェントの数の上限 $F$ に相当する、最もスコアの低い $F$ 人の隣接エージェントを除外します。このステップにより、潜在的な悪意のある入力や低品質な入力が、洗練プロセスの前に除去されます。
4. 洗練：エージェント $i$ は、元のクエリ、現在の応答、および受信側スコアで重み付けされた保持された隣接応答のセットを用いて LLM を再プロンプトし、自身の応答を洗練させます。

理論的枠組みとトポロジー条件
誠実なエージェントが信頼できる情報を保持することを保証するために、著者は古典的なビザンチン耐性合意理論、特にMean-Subsequence-Reduced (MSR) ファミリのアルゴリズムと$r$-ロバスト性を活用します。

• $(F+1)$-ロバスト性：著者は、通信グラフ $G$ が $(F+1)$-ロバストである場合、フィルタリング機構が以下の 2 つの重要な性質を確保することを立証しています：
  1. 局所耐性：フィルタリング後、すべての誠実なエージェントは、すべての信頼できるエージェント間の最小スコアと同等かそれ以上の応答を持つ少なくとも 1 人の隣接エージェントを保持します。これにより、ビザンチンエージェントが洗練プロセスを汚染するのを防ぎます。
  2. 大域的接続性：フィルタリング後も、誠実なエージェントによって誘起される部分グラフは接続されたまま（具体的には、根付き外向き枝分かれ構造を含む）であり、ネットワーク全体で情報が正しく伝播し、分断されないことを保証します。
• 本論文は、この設定において $F$ 人の局所的ビザンチンエージェントの影響を封じ込めるために $(F+1)$-ロバスト性が必要条件であることを証明しており、アドホックなトポロジー選択に対する数学的に裏付けられた代替案を提供しています。

主要な貢献

1. 自己アンカー型合意（SAC）：脆弱な送信者報告型信頼に代わり、受信側評価と自然言語相互作用に特化した MSR 由来のフィルタリング機構を組み込んだ、完全分散型アルゴリズムの導入。
2. グラフ理論的保証：非ビザンチンエージェントがビザンチンの影響を封じ込め、正しい答えに収束することを保証する理論的基盤として、$(F+1)$-ロバスト性条件の確立。
3. 実証的検証：SAC が多様な通信トポロジー（MERG、完全グラフ、Erdős–Rényi）および推論ベンチマークにおいてビザンチンの影響を効果的に抑制し、敵対的条件下では従来の手法が崩壊するのに対し、SAC が機能することを示した実証。

実験結果
著者は、SAC を 2 つの困難なベンチマーク、MATH500（レベル 4 の記号推論）とCommonsense170k（多様な常識推論）で評価しました。設定は、$n=7$ のエージェント（4 人の強力な誠実エージェント、2 人の弱い誠実/故障エージェント、1 人の敵対的ビザンチンエージェント）で、$F=3$ としました。

• ベースラインのパフォーマンス低下：ベースライン手法である CP-WBFT は、ビザンチンの影響下で壊滅的な失敗を招きました。MATH500 において、ビザンチン耐性改善度（BFTI）は $-10.4\%$ から $-24.8\%$ の負の値を示し、協力によってエージェントの単独能力以下のパフォーマンスに低下しました。強力なエージェントは著しく引きずり下げられました（例：精度が $84\%$ から $49\%$ に低下）。
• SAC の有効性：これに対し、SAC はすべてのトポロジーにおいて MATH500 で $+3.8\%$ から $+7.6\%$ の正の BFTI を達成しました。強力なエージェントのパフォーマンスを維持しつつ、弱いエージェントのパフォーマンスを向上させることに成功しました。
• ロバスト性指標：SAC は高い「誠実な多数派」（真の答えに多数の誠実なエージェントが同意するクエリの割合）を維持し、MATH500 において $83.3\%$ から $96.7\%$ に達しました。一方、CP-WBFT は $36.7\%$ から $46.7\%$ にとどまりました。
• 安定性：ラウンドごとの分析により、CP-WBFT では最初のラウンドですぐに汚染が発生し持続したのに対し、SAC は反復を通じて安定または精度が向上し、漸進的な低下は見られませんでした。

意義と主張
本論文は、現在の分散型 LLM 協調における主要な脆弱性は、敵対的な操作のための攻撃面を創出する送信者報告型信頼への依存にあると主張しています。受信側評価へ移行することで、SAC はビザンチンエージェントが信頼シグナルを操作する能力を排除します。さらに、この研究はトポロジー設計が単なるヒューリスティックではなく数学的必然であることを浮き彫りにしています。ビザンチンの影響を封じ込めるためには、$(F+1)$-ロバスト性を満たすことが不可欠です。著者は、分散型 LLM 協調を信頼できるものにするためには、システムが受信側信頼評価とロバスト性を意識したネットワークトポロジーを統合する必要があると結論付けています。また、論文は限界を認めており、現在の評価は小規模（$n=7, 9$）の静的ネットワークと単一ターン応答に限定されており、ロバスト性は受信者のスコアリング機能の品質に依存していることを指摘しています。