Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper introduces Tensor-Coord, a multilinear algebra framework that models the joint planning of multiple agents using a third-order tensor to mitigate coordination failures in multi-agent LLM scenarios. By employing Canonical Polyadic and Tucker decompositions, the authors derive a computable coordination complexity measure that quantifies the independence of plans and identifies conflict scores across agents. Experimental results demonstrate that Tensor-Coord achieves conflict-free planning in various multi-robot delivery tasks, showing high success rates and rapid convergence across different agent configurations.
Achieving 100% conflict-free plans for two agents within an average of 1.4 iterations reveals a new frontier in multi-agent coordination for LLMs.
Large language models (LLMs) remain limited in multi-agent planning because independently generated plans can create coordination failures such as spatial collisions, resource contention, and temporal deadlocks. We introduce Tensor-Coord, a multilinear algebra framework that represents the joint plan of N agents as a third-order tensor \(T \in R^{N \times H \times A}\) over agents, timesteps, and actions. Canonical Polyadic (CP) and Tucker decompositions are used to identify latent coordination structure. The minimal epsilon-approximate CP rank R* defines a computable coordination complexity measure, with \(CC(Pi)=(R*-N)/N\). We prove that R*=N is necessary and sufficient for plan independence. The residual \(E=T-T_{R*}\) defines a conflict score over agent pairs, timesteps, and actions, localizing failures without domain-specific rules. Tucker factors provide interpretable agent roles, temporal phases, and action clusters that are converted into natural language constraints for iterative LLM replanning. Experiments on multi-robot delivery tasks across Easy (2 agents, 5x5 grid), Medium (3 agents, 5x5 grid), and Hard (4 agents, 5x5 grid) settings show convergence to conflict-free plans in 100% of 2-agent cases within 1.4 iterations on average, 80% of 3-agent cases within 3.2 iterations, and 60% of 4-agent cases within 4.0 iterations. CP rank scaled approximately linearly as \(R*(N) = 3.9N + 0.5\), supporting its use as a predictor of coordination complexity.