Technical Summary: Tensor-Coord

Problem Statement

Large Language Models (LLMs) exhibit fundamental limitations in multi-agent planning, primarily due to a gap between generative fluency and structured reasoning. While LLMs can generate plausible individual plans, they lack the deterministic state tracking and systematic search capabilities required for coordinated action. When multiple agents plan independently, their plans often result in collective inconsistencies, such as spatial collisions, resource contention, and temporal deadlocks.

Existing coordination approaches fail to address this effectively:

• Joint Prompting: Concatenating all agent contexts exceeds practical context windows as the joint action space grows exponentially ($|A|^N$).
• Sequential Planning: Introduces ordering bias and cannot resolve circular dependencies.
• Classical Algorithms (e.g., Conflict-Based Search): Require formal domain specifications (PDDL) that negate the natural language flexibility of LLMs.

The core challenge is to detect and resolve coordination failures in LLM-generated joint plans without relying on domain-specific rules or formal state-space models.

Methodology: Tensor-Coord Framework

The paper introduces Tensor-Coord, a framework that encodes the joint plan of $N$ agents as a third-order tensor $\mathbf{T} \in \mathbb{R}^{N \times T \times A}$ (Agents $\times$ Timesteps $\times$ Actions) and applies multilinear algebra to discover latent coordination structures.

1. Soft Tensor Representation

To ensure numerical stability and full multilinear rank, the framework avoids hard binary encoding. Instead, it uses a 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]$$
where $\gamma$ is a confidence parameter (e.g., 0.8). This assigns high probability to the chosen action and distributes the remainder among other actions, preserving the dominant structure while preventing rank deficiency.

2. Canonical Polyadic (CP) Decomposition & Complexity Metric

The framework applies CP decomposition to factorize the tensor into a sum of rank-one components:
$$\mathcal{T} \approx \sum_{r=1}^{R} \lambda_r \cdot \mathbf{u}_r \otimes \mathbf{v}_r \otimes \mathbf{w}_r$$

• Theoretical Insight: If agents are independent, the tensor rank $R^*$ equals the number of agents $N$. If $R^* > N$, the excess rank represents inter-agent dependencies (coupling).
• Coordination Complexity Metric ($CC$): Defined as $CC(\Pi) = \frac{R^* - N}{N}$.
  • $CC(\Pi) = 0$ implies mutual independence (no conflicts possible).
  • $CC(\Pi) > 0$ implies statistical dependence and the necessity of coordination.

3. Residual-Based Conflict Detection

The decomposition residual $\mathbf{E} = \mathcal{T} - \mathcal{T}_{R^*}$ captures behavior unexplained by independent threads.

• Conflict Score: $CS(i, j, t) = \rho(i, t) \cdot \rho(j, t)$, where $\rho(i, t) = \|\mathbf{E}(i, t, :)\|_2$.
• Mechanism: High residuals in both agents $i$ and $j$ at the same timestep $t$ indicate a coordination failure (e.g., a collision) that the independent model cannot explain. This localizes conflicts algebraically without domain-specific rules.

4. Tucker Decomposition for Interpretability

To guide replanning, the framework uses Tucker decomposition ($\mathcal{T} \approx \mathcal{G} \times_1 \mathbf{U} \times_2 \mathbf{V} \times_3 \mathbf{W}$) to extract interpretable factors:

• $\mathbf{U}$ (Agent Roles): Clusters agents with similar coordination roles.
• $\mathbf{V}$ (Temporal Phases): Identifies critical coordination windows.
• $\mathbf{W}$ (Action Types): Groups functionally equivalent actions.
  These factors are translated into Natural Language Constraints (e.g., "AVOID position (x,y) at timestep t" or "SYNCHRONIZE at phase boundary") to guide iterative LLM replanning.

5. Iterative Algorithm

The system operates in a loop:

1. LLMs generate initial plans.
2. Plans are encoded into a soft tensor.
3. CP decomposition computes $R^*$ and the residual $\mathbf{E}$.
4. Conflicts are localized via the residual score.
5. Tucker factors generate specific natural language constraints.
6. Constraints are fed back to LLMs for replanning.
7. The loop repeats until convergence or max iterations.

Key Contributions

1. Tensor Formulation: A soft encoding of joint plans enabling stable multilinear decomposition.
2. Algebraic Complexity Metric: The first computable, algebraically-grounded measure of coordination complexity ($CC$), proving that $R^*=N$ is necessary and sufficient for plan independence.
3. Domain-Agnostic Conflict Detection: A residual-based method that algebraically localizes conflicts in the agent $\times$ timestep $\times$ action space without requiring explicit collision rules.
4. Interpretable Structure Extraction: Using Tucker decomposition to derive agent roles, temporal phases, and action clusters for generating actionable constraints.
5. Iterative Refinement Algorithm: A framework achieving high convergence rates on multi-robot delivery tasks.

Experimental Results

Experiments were conducted on multi-robot delivery tasks across grid worlds (5x5 and 6x6) with 2 to 5 agents.

• Convergence Rates:
  • Easy (2 agents): 100% convergence (avg. 1.4 iterations).
  • Medium (3 agents): 80% convergence (avg. 3.2 iterations).
  • Hard (4 agents): 60% convergence (avg. 4.0 iterations).
  • Very Hard (5 agents): 20% convergence (high congestion limits resolution).
• Scaling Law: The minimal CP rank scales linearly with agent count: $R^*(N) \approx 3.9 \cdot N + 0.5$ ($R^2 = 0.94$), confirming the metric's reliability as a complexity predictor.
• Baseline Comparison: Tensor-Coord significantly outperformed Independent Planning, Round-Robin sequential planning, and Single-LLM Joint prompting. It was the only method capable of reaching zero conflicts through iterative refinement, particularly in medium-complexity scenarios.

Significance and Claims

The paper claims that Tensor-Coord bridges the gap between the natural language flexibility of LLMs and the rigorous requirements of multi-agent coordination. By treating coordination as an algebraic problem of tensor rank, the framework:

• Provides a quantifiable measure of planning difficulty ($CC$) that was previously absent in LLM multi-agent systems.
• Offers a principled mechanism for conflict detection that does not rely on hand-crafted domain rules, making it applicable to diverse environments.
• Demonstrates that algebraic decomposition can effectively guide LLMs to resolve complex coordination failures that standard prompting strategies cannot.

The authors note that while the approach achieves high success rates on tractable problems, it faces challenges in highly congested environments (e.g., 5 agents on a 6x6 grid) where constraint interactions can lead to non-monotonic convergence. Future work is proposed to address hierarchical decomposition for larger agent counts and minimal conflict-resolving constraint sets.