Analyzing Information Sharing and Coordination in Multi-Agent Planning

Tianyue Ou, Saujas Vaduguru, Daniel FriedarXiv 2025 · DOI · arXiv

Abstract

Long-horizon planning tasks present a "complexity ceiling" for Large Language Models (LLMs) due to context bloat and rigid coordination. This paper introduces a multi-agent system (MAS) that utilizes a structured shared notebook for information grounding and a reflective orchestrator for dynamic task routing. On the TravelPlanner benchmark, this architecture achieved a 25% pass rate, a significant improvement over the 7.5% baseline of single-agent systems.

Introduction

As LLMs are increasingly deployed as autonomous agents, they frequently encounter failure modes in complex planning scenarios. The authors identify two primary issues: Context Bloat, where excessive tool output leads to hallucinations of non-existent entities, and Rigid Workflows, where fixed pipelines prevent the necessary backtracking required to resolve interdependent constraints (e.g., adjusting a flight to accommodate a specific restaurant budget).

Methodology

The proposed MAS architecture moves away from messy chat histories toward structured collaboration through specialized components.

The MAS architecture featuring a shared Notebook (N) and a reflective Orchestrator (D) to manage expert agents.

Key components include:

  • The Notebook ($N$): A shared "source of truth" where experts record distilled facts, filtering out noisy raw tool outputs to prevent the "telephone game" effect.
  • The Orchestrator ($D$): A dynamic agent that uses self-reflection to decide which expert to call next, allowing for non-linear planning and backtracking when constraints conflict.
  • Expert Specialization: Specialized agents for Transportation, Hotels, and Dining handle raw data, passing only relevant information to the notebook.
  • Plan-Refine Loop: A dedicated Plan Compiler generates the initial itinerary, which is then iteratively polished by a Plan Critic.

Experimental Results

The system was evaluated using the TravelPlanner benchmark, a sandbox containing roughly four million entries. The MAS, powered by Claude 4 Sonnet, reached a 25% pass rate, tripling the performance of single-agent baselines (7.5%).

Impact of the Shared Notebook

The implementation of the Notebook significantly mitigated the "hallucination cascade." By forcing agents to commit to structured facts, the system reduced entity-related errors by 18%.

Comparison of error rates across different planning categories with and without the shared notebook.

As shown in Figure 2, the notebook was particularly effective in reducing errors in high-density data categories like Flights and Accommodations, eliminating more than half of the errors related to flight numbers.

Coordination and Backtracking

The Orchestrator's ability to backtrack was vital. On average, the system revisited previous steps 0.6 times per task to resolve conflicts. While this increased coordination complexity—leading to a slightly lower "Delivery Rate" (task completion within step limits)—the quality and constraint satisfaction of the resulting plans were substantially higher.

Conclusion and Future Work

This research demonstrates that structured memory and dynamic orchestration are essential for scaling LLM agents to long-horizon tasks. While the MAS is more computationally expensive, it successfully breaks the complexity ceiling of single-agent systems. Future work will focus on improving the efficiency of the Orchestrator to prevent coordination loops and developing more robust conflict detection mechanisms for deeply coupled constraints.

Summary updated

Abstract

Multi-agent systems (MASs) have pushed the boundaries of large language model (LLM) agents in domains such as web research and software engineering. However, long-horizon, multi-constraint planning tasks involve conditioning on detailed information and satisfying complex interdependent constraints, which can pose a challenge for these systems. In this study, we construct an LLM-based MAS for a travel planning task which is representative of these challenges. We evaluate the impact of a notebook to facilitate information sharing, and evaluate an orchestrator agent to improve coordination in free form conversation between agents. We find that the notebook reduces errors due to hallucinated details by 18%, while an orchestrator directs the MAS to focus on and further reduce errors by up to 13.5% within focused sub-areas. Combining both mechanisms achieves a 25% final pass rate on the TravelPlanner benchmark, a 17.5% absolute improvement over the single-agent baseline's 7.5% pass rate. These results highlight the potential of structured information sharing and reflective orchestration as key components in MASs for long horizon planning with LLMs.
BibTeX
@misc{ou2025analyzing,
  author = {Tianyue Ou and Saujas Vaduguru and Daniel Fried},
  title = {{Analyzing Information Sharing and Coordination in Multi-Agent Planning}},
  year = {2025},
  eprint = {2508.12981},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2508.12981},
}
Figure