Mosaic: Runtime-Efficient Multi-Agent Embodied Planning

Source: arXiv:2607.09603 · Published 2026-07-10 · By Kunjal Panchal, Saayan Mitra, Sunav Choudhary, Victor Bursztyn, Somdeb Sarkhel, Hui Guan

TL;DR

The paper addresses the high runtime latency problem in large-language-model (LLM)-based multi-agent embodied planning. Conventional approaches suffer from frequent failed actions caused by inaccurate state tracking under partial observability and inefficient coordination that triggers conflicting or redundant behaviors. The authors propose MOSAIC, a framework that integrates an agent-centric semantic memory for lightweight, relative-coordinate spatial state tracking and an Integer Linear Programming (ILP) based optimization for action selection to enforce multi-agent coordination constraints. MOSAIC’s memory encodes agent-relative object positions updated each step, enabling robust spatial reasoning without costly global mapping. The ILP resolves LLM-proposed candidate actions into globally feasible joint actions, avoiding physical conflicts and balancing workload. Evaluated on AI2-THOR and a search-and-rescue (SAR) domain, MOSAIC achieves up to 32% faster overall execution, 30–33% fewer LLM calls, 25–31% fewer physical steps, and 4–10% higher success rates compared to recent strong baselines. These results demonstrate that combining efficient, cross-agent spatial memory with constraint-guided coordination can substantially reduce failures and improve runtime efficiency in multi-agent embodied tasks.

Key findings

• MOSAIC reduces failed actions by 7–12 percentage points, lowering failure rates from up to 47% to approximately 35%.
• Execution speedup of 27–32% relative to state-of-the-art multi-agent embodied planners on AI2-THOR and SAR tasks.
• LLM calls per episode decrease by 30–33%, significantly cutting language model inference overhead.
• Multi-agent coordination via ILP reduces redundant exploration, leading to 25–31% fewer physical agent steps per episode.
• Task success rates improve by 4–10 percentage points under a fixed planning-step budget.
• Agent-centric Semantic Memory enables accurate spatial state tracking using relative coordinates updated via geometric transformations.
• ILP framework enforces action feasibility constraints such as collision avoidance and resource exclusivity at action-level granularity.
• MOSAIC scales effectively: speedups remain 1.25–1.30× with five agents, and performance maintains 70–90% under simulated sensor noise.

Threat model

The assumed adversary corresponds to environmental uncertainties causing partial observability and stochastic execution failures; no malicious attackers or agents are modeled. The system does not consider intentional adversarial manipulation of observations or communications between agents. The main threat addressed is performance degradation from failed actions due to inaccurate state tracking and poor coordination under realistic sensing and execution noise.

Methodology — deep read

The authors model the multi-agent embodied planning problem as a Partially Observable Markov Decision Process (POMDP) with joint discrete actions for N agents, operating under partial observability without explicit transition or reward models. The goal is to execute a sequence of joint actions fulfilling a natural language instruction efficiently. The MOSAIC framework integrates into a centralized LLM-based architecture with three distinct modules: (1) LLM-PLANNER decomposes high-level instructions into subtasks; (2) LLM-ACTOR generates candidate actions per agent for each subtask at every planning step; (3) LLM-VERIFIER identifies completed subtasks post execution, enabling adaptive replanning.

To address inaccurate state tracking, MOSAIC introduces Agent-centric Semantic Memory (ASM) which stores positional data of task-relevant objects relative to each agent’s position and orientation rather than absolute coordinates. Objects outside an agent’s field of view have positions updated via geometric transformations from other agents’ memory, supporting transfer across perspectives. Distances and orientations are continuous internally, but semantic tiers like 'just ahead' or 'far left' are provided to the LLM only as discretized prompts to facilitate reasoning without losing precision. This yields lightweight, accurate spatial representation that updates every planning step, correcting for sensor noise and agent motion.

For coordination, MOSAIC employs an Integer Linear Programming (ILP) formulation to select exactly one feasible action per agent from LLM-generated candidates at each planning step. The ILP enforces constraints: action eligibility (precondition checks), unique per-agent actions, multi-agent subtask staffing, exclusive resource usage, and collision/interference avoidance. A cost function balances penalties on repeating failure-prone or inefficient actions and workload imbalance across agents, thereby optimizing runtime efficiency. The ILP runs at every planning step to dynamically adapt joint action assignments to evolving environmental and team states.

MOSAIC limits ILP complexity by pruning candidate actions per agent. It runs on top of LLMs including GPT-4o, Claude Sonnet 4.5, or Gemini 3 Flash. Visual perception in AI2-THOR uses CLIP ViT-B/32 to correlate images and subtasks.

Experiments use households tasks in AI2-THOR (36 multi-agent tasks; up to 5 agents; partial observability; 1.5m sensor range; 90º FOV) and the SAR text-grid environment (search and rescue with fires and resource management). Baselines include single-call LLM outputting all agent actions (ACT, Chain-of-Thought, REACT) and multi-call systems with task decomposition (SMARTLLM, COELA, LLAMAR). Evaluation metrics assess success rate, transport rate of subtasks, coverage of relevant objects, failure rates, workload balance, physical steps, runtime, and LLM call count.

On average over three episodes per task, MOSAIC consistently outperforms all baselines: highest success and transport rates, lowest failure rates (~0.35 vs 0.39–0.51), and improved workload balance. Runtime accelerations of 27–32% and 30–33% fewer LLM calls demonstrate reduced language reasoning overhead. In multi-agent scaling, MOSAIC maintains consistent gains in speed and success with 5 agents and under sensor noise scenarios, showing robustness. Ablations verify ASM and ILP contributions independently boost performance. Code, exact seeds, and complete reproducibility details are not specified, but baselines use public simulators AI2-THOR and SAR.

Technical innovations

• Agent-centric Semantic Memory encoding relative distances and orientations to task-relevant objects updated via geometric transformations allowing lightweight, precise state tracking under partial observability.
• Integer Linear Programming framework selecting one joint action per agent from multiple LLM-generated candidates enforcing feasibility constraints (collision avoidance, resource exclusivity, multi-agent subtasks) and optimizing execution cost.
• Fine-grained, action-level ILP coordination per planning step, adapting dynamically to environment and agent states versus prior coarse-grained episode-level task assignments.
• Semantic tier abstraction converting continuous spatial metrics into discretized semantic prompts exclusively for LLM reasoning interface while preserving internal numerical precision.

Datasets

• AI2-THOR — 36 multi-agent household tasks — publicly available photo-realistic 3D simulator
• SAR (Search and Rescue) — simulated discrete 2D grid emergency response tasks — MIT text-based simulator

Baselines vs proposed

• ACT (single LLM call): failure rate = 0.39–0.47 vs MOSAIC ~0.35; success rate improved by 4–10 percentage points
• Chain-of-Thought (COT): similar failure and success values as ACT; MOSAIC substantially better failure reduction
• REACT (reasoning & acting): failure rate 0.39–0.47 vs MOSAIC lower by up to 12 points
• SMARTLLM (multi-call with Python plans): failure rates 0.46–0.51 vs MOSAIC lower; MOSAIC 27–32% faster execution
• COELA (decentralized multi-call): failure rates 0.46–0.51 AI2-THOR; MOSAIC consistently outperforms in speed and success
• LLAMAR (plan-act-verify baseline): MOSAIC achieves 30–33% fewer LLM calls, 25–31% fewer steps, and up to 10% higher success

Figures from the paper

Figures are reproduced from the source paper for academic discussion. Original copyright: the paper authors. See arXiv:2607.09603.

Fig 2: Overview of MOSAIC. Agent-centric semantic memory (ASM) maintains task-relevant spatial context across timesteps under

Fig 2 (page 5).

Fig 3 (page 5).

Limitations

• Only evaluated in simulation environments AI2-THOR and SAR without real-world robotics deployment or continuous control.
• Assumes reliable localizations, with no direct low-level sensor drift handling; robustness tested only with synthetic spatial noise.
• LLM models are commercial black-boxes (GPT-4o, Claude Sonnet, Gemini 3 Flash) limiting reproducibility and isolating architectural effects from language model improvements.
• No detailed adversarial evaluation or tests under deliberate agent failures or deceptive inputs.
• Scalability of ILP to much larger teams or richer action spaces discussed but not empirically demonstrated beyond five agents.
• Unclear if framework supports dynamically joining/leaving agents or heterogeneous agent capabilities without retraining or redesign.

Open questions / follow-ons

• Can agent-centric semantic memory be integrated with learned spatial representations to handle more complex geometry and 3D manipulation tasks?
• How does MOSAIC perform when agents have heterogeneous capabilities or dynamically changing team membership?
• What are the practical limits of ILP scalability and can hierarchical or decentralized optimization methods jointly extend this approach?
• Can this framework be extended to explicitly model and mitigate adversarial or deceptive agent behaviors in multi-agent embodied settings?

Why it matters for bot defense

For bot-defense engineers interested in embodied multi-agent systems, MOSAIC’s approach highlights key challenges and solutions in runtime-efficient coordination. The agent-centric semantic memory exemplifies how relative, lightweight spatial representations can reduce planning errors under partial observability — analogous to state tracking challenges in coordinating distributed bots or CAPTCHA solvers interacting across changing environments. The ILP-based coordination illustrates how formal constraint enforcement can prevent conflicting instructions and resource contention among multiple automated agents acting concurrently.

While CAPTCHA challenges typically do not involve multi-agent embodied navigation, the principles of optimizing large language model calls and enforcing fine-grained joint action consistency apply broadly. MOSAIC suggests that combining model-driven candidate generation with symbolic runtime coordination can reduce latency and failure rates in complex multi-agent task execution. Practitioners may consider similar hybrid approaches to orchestrate LLM-guided bot behaviors in CAPTCHA solving or defense contexts, trading off inference overhead with constraint optimization for reliability.

Cite

@article{arxiv2607_09603,
  title={ Mosaic: Runtime-Efficient Multi-Agent Embodied Planning },
  author={ Kunjal Panchal and Saayan Mitra and Sunav Choudhary and Victor Bursztyn and Somdeb Sarkhel and Hui Guan },
  journal={arXiv preprint arXiv:2607.09603},
  year={ 2026 },
  url={https://arxiv.org/abs/2607.09603}
}

Read the full paper

• arXiv:2607.09603 (abstract)
• arXiv:2607.09603 (PDF)