MOSAIC Runtime-Efficient Multi-Agent Embodied Planning

Jul 16, 2026

LLM-based multi-agent embodied planning suffers from prohibitively high execution latency, driven primarily by failed actions. The failures originate from inaccurate state tracking under partial observability and inefficient coordination that yields redundant or conflicting behaviors. MOSAIC is a runtime-efficient planning framework that combines lightweight, accurate agent-centric semantic memory with relative-coordinate object representations and geometric transformations. Integer Linear Programming allocates feasible actions at every step, enforcing physical feasibility and inter-agent constraints. On AI2-THOR and search-and-rescue benchmarks, it delivers 27–32% faster execution, fewer LLM calls, fewer steps, and higher success rates, showing memory efficiency and constraint-guided coordination as key enablers.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages39

Reading Time1 h 38 min

Introduction

Problem: execution latency from failed actions

Key challenges: state tracking and coordination

MOSAIC: Runtime-Efficient Multi-Agent Embodied Planning Kunjal Panchal * 1 Saayan Mitra 2 Sunav Choudhary 2 Victor Bursztyn 2 Somdeb Sarkhel 2 Hui Guan 1 arXiv :2607 .09603v1 [ cs .MA] 10 Jul 2026 Abstract LLM-based multi-agent embodied planning remains impractical due to prohibitively high execution latency. We identify failed actions asthe dominant bottleneck, stemming from two core challenges: inaccurate state tracking under partial observability and inefficient coordination that produces redundant or conflicting actions. We introduce MOSAIC, a runtime-efficient multi-agent planning framework that addresses both challenges. MOSAIC maintains accurate yet lightweight state tracking through agent-centric semantic memory that stores objects in relative coordinates, enabling geometric transformations and coordination. It ensures efficient coordination through Integer Linear Programming that allocates actions at every planning step, enforcing physical feasibility and inter-agent coordination constraints. Across AI2-THOR and search-and-rescue benchmarks, MOSAIC achieves 27–32% faster execution, 30–33% fewer LLM calls, 25–31% fewer steps, and 4–10% points higher success rates. These results demonstrate that efficient memory and constraint-guided coordination are critical for scalable, low-latency multi-agent planning. 1. Introduction Many real-world embodied tasks such as collaborative search and rescue, household rearrangement, and environmental exploration require multiple agents (physical or simulated entities executing coordinated plans or policies) operating simultaneously in shared spaces (Liu et al., 2024 ; Qian et al., 2025 ; Skrynnik et al., 2024 ; Chen et al., 2024) . Leveraging multiple agents offers clear advantages: they can parallelize subtasks, cover larger areas, and recover from lo- ∗Partial work completed during an internship at Adobe. 1 College of Information and Computer Sciences, University of Massachusetts, Amherst 2Adobe, San Jose. Correspondence to: Kunjal Panchal <[kpanchal@umass.edu](kpanchal@umass.edu) >. Proceedings of the 43 rd International Conference on Machine Learning, Seoul, South Korea. PMLR 306, 2026 . Copyright 2026 by the author(s) . cal failures (Qian et al., 2025 ; Nayak et al., 2024), leading to faster and more robust task completion compared to singleagent systems. Recent works have explored the use of Large Language Models (LLMs) as planners in such multi-agent environments, demonstrating impressive inference-time generalization across unstructured tasks and domains (Zhang et al., 2025e ; Bai et al., 2025) . In this paradigm, LLMs generate action sequences for each agent, while the agents execute these planned actions in the environment. However, practical deployment of LLM-driven multi-agent planning remains limited due to prohibitively high latency, which include both physical action execution time and LLM inference overhead. For example, running a state-of-the-art multi-agent system (Nayak et al., 2024) to solve a simple embodied task such as “Turn off the faucet and light”requires approximately 7.2 minutes to complete. More complex tasks such as “Rescue two people from a fire-affected area” in a simplified simulation environment require 10.5 minutes to complete. We find that a substantial portion of the runtime is spent on failed actions during execution, which trigger replanning, recovery, or redundant exploration. Figure 1 illustrates a sequence of such failed actions in a rescue scenario: Agent B repeatedly fails to navigate to a person due to spatial reasoning errors (steps 1–2), then violates action preconditions by attempting to carry the person while holding debris (step 4), while Agent A remains idle waiting for coordination (steps 2–3, 5) . In our preliminary experiments on state-ofthe-art LLM-based multi-agent systems for embodied planning (Nayak et al., 2024 ; Zhang et al., 2023b), agents spent up to 16–51% of planning steps on failed actions, frequentl

FAQs

What is the main reason LLM-based multi-agent embodied planning is impractical in real deployments?

Prohibitively high execution latency. A substantial portion of runtime is spent on failed actions that trigger replanning, recovery, or redundant exploration.

Which two core challenges does MOSAIC address?

Accurate state tracking under partial observability and efficient multi-agent coordination that prevents redundant or conflicting actions.

How does MOSAIC improve performance during planning and execution?

It uses lightweight agent-centric semantic memory with relative coordinates for accurate state tracking and geometric transformations, and applies Integer Linear Programming at every step to allocate feasible actions while enforcing physical feasibility and coordination constraints.

Jul 16, 2026

Upload by Valentina