技術要約: Tensor-Coord

問題提起

大規模言語モデル（LLM）は、生成の流暢さと構造化された推論との間の乖離により、マルチエージェント・プランニングにおいて根本的な限界を露呈している。LLMはもっともらしい個別の計画を生成することはできるが、協調行動に必要とされる決定論的な状態追跡や体系的な探索能力を欠いている。複数のエージェントが独立して計画を立てると、その計画は空間的な衝突、リソースの競着、時間的なデッドロックといった集団的な不整合を引き起こすことが多い。

既存の調整手法は、この問題に効果的に対処できていない：

• 結合プロンプティング（Joint Prompting）: 全エージェントのコンテキストを連結すると、結合アクション空間が指数関数的（$|A|^N$）に増大するため、実用的なコンテキストウィンドウを超過してしまう。
• 逐次プランニング（Sequential Planning）: 順序バイアスを導入し、循環依存関係を解決できない。
• 古典的アルゴリズム（例：Conflict-Based Search）: PDDLのような形式的なドメイン仕様を必要とし、LLMの自然言語による柔軟性を損なう。

核心となる課題は、ドメイン固有のルールや形式的な状態空間モデルに依存することなく、LLMが生成した結合計画における調整失敗を検出し、解決することである。

メソドロジー: Tensor-Coord フレームワーク

本論文では、$N$ 個のエージェントの結合計画を第3階テンソル $\mathbf{T} \in \mathbb{R}^{N \times T \times A}$ （エージェント $\times$ タイムステップ $\times$ アクション）として符号化し、多重線形代数を適用して潜在的な調整構造を発見するフレームワークである Tensor-Coord を提案する。

1. ソフトテンソル表現

数値的安定性と完全な多重線形ランクを確保するため、本フレームワークはハードなバイナリ符号化を避ける。代わりに、**ソフト計画テンソル（Soft Plan Tensor）**を使用する：
$$\mathcal{T}(i, t, k) = \gamma \cdot \mathbb{1}[a_i^t = a_k] + \frac{1-\gamma}{K-1} \cdot \mathbb{1}[a_i^t \neq a_k]$$
ここで $\gamma$ は信頼度パラメータ（例：0.8）である。これにより、選択されたアクションに高い確率を割り当て、残りの確率を他のアクションに分散させることで、支配的な構造を維持しつつランク欠損を防ぐ。

2. カノニカル・ポリャディック（CP）分解と複雑度指標

本フレームワークは、テンソルをランク1の成分の和へと分解するためにCP分解を適用する：
$$\mathcal{T} \approx \sum_{r=1}^{R} \lambda_r \cdot \mathbf{u}_r \otimes \mathbf{v}_r \otimes \mathbf{w}_r$$

• 理論的洞察: エージェントが独立している場合、テンソルランク $R^*$ はエージェント数 $N$ と等しくなる。もし $R^* > N$ であれば、超過したランクはエージェント間の依存関係（結合）を表している。
• *調整複雑度指標 ($CC$):**$CC(\Pi) = \frac{R^ - N}{N}$ として定義される。
  • $CC(\Pi) = 0$ は相互独立を意味する（衝突は起こり得ない）。
  • $CC(\Pi) > 0$ は統計的な依存関係と調整の必要性を意味する。

3. 残差に基づく衝突検出

分解残差 $\mathbf{E} = \mathcal{T} - \mathcal{T}_{R^*}$ は、独立したスレッドでは説明できない挙動を捉える。

• 衝突スコア: $CS(i, j, t) = \rho(i, t) \cdot \rho(j, t)$、ここで $\rho(i, t) = \|\mathbf{E}(i, t, :)\|_2$ である。
• メカニズム: 同一タイムステップ $t$ における両エージェント $i$ と $j$ の高い残差は、独立したモデルでは説明できない調整失敗（例：衝突）を示唆する。これにより、ドメイン固有のルールなしに、代数的に衝突を局所化できる。

4. 解釈性のためのタッカー（Tucker）分解

再計画を導くために、本フレームワークはタッカー分解（$\mathcal{T} \approx \mathcal{G} \times_1 \mathbf{U} \times_2 \mathbf{V} \times_3 \mathbf{W}$）を用いて解釈可能な因子を抽出する：

• $\mathbf{U}$ (エージェントの役割): 類似した調整役割を持つエージェントをクラスタリングする。
• $\mathbf{V}$ (時間的フェーズ): 重要な調整ウィンドウを特定する。
• $\mathbf{W}$ (アクションタイプ): 機能的に等価なアクションをグループ化する。
  これらの因子は、反復的なLLM再計画を導くための 自然言語制約（例：「タイムステップ $t$ において位置 $(x, y)$ を回避せよ」または「フェーズ境界で同期せよ」）へと翻訳される。

5. 反復アルゴリズム

システムは以下のループで動作する：

1. LLMが初期計画を生成する。
2. 計画がソフトテンソルに符号化される。
3. CP分解が $R^*$ と残差 $\mathbf{E}$ を計算する。
4. 衝突が残差スコアによって局所化される。
5. タッカー因子が具体的な自然言語制約を生成する。
6. 制約が再計画のためにLLMにフィードバックされる。
7. 収束するか最大イテレーションに達するまで、このループを繰り返す。

主な貢献

1. テンソル定式化: 安定した多重線形分解を可能にする、結合計画のソフトな符号化。
2. 代数的な複雑度指標: $R^*=N$ が計画の独立性に必要十分であることを証明する、計算可能で代数的に根拠のある調整複雑度（$CC$）の初の指標。
3. ドメインに依存しない衝突検出: 明示的な衝突ルールを必要とせず、エージェント $\times$ タイムステップ $\times$ アクション空間において代数的に衝突を局所化する残差ベースの手法。
4. 解釈可能な構造抽出: エージェントの役割、時間的フェーズ、およびアクションクラスターを導出するためのタッカー分解の利用。
5. 反復的洗練アルゴリズム: マルチロボット配送タスクにおいて高い収束率を達成するフレームワーク。

実験結果

実験は、2から5体のエージェントを用いたグリッドワールド（5x5および6x6）におけるマルチロボット配送タスクに対して行われた。

• 収束率:
  • Easy (2エージェント): 100% 収束（平均 1.4 イテレーション）。
  • Medium (3エージェント): 80% 収束（平均 3.2 イテレーション）。
  • Hard (4エージェント): 60% 収束（平均 4.0 イテレーション）。
  • Very Hard (5エージェント): 20% 収束（高混雑による解決限界）。
• スケーリング則: 最小CPランクはエージェント数に対して線形にスケールする：$R^*(N) \approx 3.9 \cdot N + 0.5$ ($R^2 = 0.94$)。これは、指標が複雑度の予測因子として信頼できることを裏付けている。
• ベースライン比較: Tensor-Coordは、独立プランニング、ラウンドロビン方式の逐次プランニング、および単一LLMによる結合プロンプティングを大幅に上回った。特に中程度の複雑度のシナリオにおいて、反復的洗練を通じてゼロ衝突に到達できた唯一の手法であった。

意義と主張

本論文は、Tensor-CoordがLLMの自然言語による柔軟性と、マルチエージェント調整における厳格な要求事項との間の溝を埋めるものであると主張している。テンソルランクを用いた代数問題として調整を扱うことにより、本フレームワークは以下を実現する：

• 従来のLLMマルチエージェントシステムには存在しなかった、定量化可能な難易度尺度 ($CC$) の提供。
• ドメイン固有のルールに依存しない、原理に基づいた衝突検出メカニメント。これにより、多様な環境への適用が可能となる。
• 代数的分解が、標準的なプロンプティング戦略では解決できない複雑な調整失敗を、LLMを導いて解決できることを実証。

著者らは、本手法は扱いやすい問題に対しては高い成功率を達成するものの、制約の相互作用が非単調な収束を招く可能性のある、極めて混雑した環境（例：6x6グリッド上の5エージェント）においては課題に直面することを指摘している。今後の課題として、より多くのエージェント数に対する階層的分解や、最小限の衝突解決制約セットへの取り組みが提案されている。