Research map / Multi-agent systems and games / LLM agents

Mosaic: Runtime-Efficient Multi-Agent Embodied Planning

ICML 2026 · Multi-agent systems and games › LLM agents · approach: Robust and efficient agent execution · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Mosaic adds an agent-centric relative-coordinate semantic memory and an ILP-based per-step action selector over LLM action candidates to cut failed actions, runtime, and LLM calls in multi-agent embodied planning.

Problem

LLM-based multi-agent embodied planning is impractically slow, largely because failed actions cause replanning, redundant exploration, and stalls, stemming from inaccurate state tracking under partial observability and poor action-level coordination.

Approach

Store task-relevant objects in each agent's relative (distance, orientation) frame, transform between agents' frames for cross-agent reasoning, and select one feasible action per agent at every step via an ILP with feasibility, staffing, exclusivity, and collision constraints plus a penalty/load-balance cost.

Key results

• On AI2-THOR, LLaMAR + Mosaic improves success from 0.59 to 0.69 while cutting runtime 26.9% (757.9s to 554.1s), LLM calls 33.3%, and agent steps 31.0%.
• On SAR, LLaMAR + Mosaic reduces runtime by 31.9% (333.8s to 227.4s) and failure rate from 0.16 to 0.09 with success 0.55 to 0.59.
• ILP overhead accounts for only 1.3-1.9% of total runtime when scaling from 3 to 8 agents in SAR.

Measured effects reported in the paper

Surprising findings

• Replacing short-term memory with ASM alone gives only 1-3 points of success gain on single-call baselines, while the largest boost comes from multi-call task decomposition.
• ASM alone increases token usage by 11.5-13.4% for ReAct, a modest overhead offset by gains in success and steps.

Limitations

• Assumes reliable localization; raw sensor drift is handled outside the planning scope.
• ILP scalability relies on action pruning (K=3) and agent pruning is only proposed for larger teams, not evaluated.
• Evaluated only on AI2-THOR and a text-based SAR grid simulator with three episodes per task.

Experimental setup

Datasets: AI2-THOR SAR

Benchmarks: AI2-THOR SAR

Metrics: success rate transport rate coverage balance failure rate runtime LLM calls agent steps prompt tokens

Baselines: Act CoT ReAct SmartLLM CoELA LLaMAR

Builds on: LLaMAR ReAct Chain-of-Thought CLIP

Closest papers by meaning

• From Assumptions to Actions: Turning LLM Reasoning into Uncertainty-Aware Planning for Embodied Agents (ICLR 2026 · similarity 0.88)
• Embodied Task Planning via Graph-Informed Action Generation with Large Language Models (ICML 2026 · similarity 0.88)
• Collaborative Tree Search for Enhancing Embodied Multi-Agent Collaboration (CVPR 2025 · similarity 0.87)
• Agentic Plan Caching: Test-Time Memory for Fast and Cost-Efficient LLM Agents (NeurIPS 2025 · similarity 0.87)
• Concurrent Planning and Execution in Lifelong Multi-Agent Path Finding with Delay Probabilities (AAAI 2025 · similarity 0.87)
• Optimus-1: Hybrid Multimodal Memory Empowered Agents Excel in Long-Horizon Tasks (NeurIPS 2024 · similarity 0.87)