CORAL: Dynamic Multi-Agent Coordination Without Predefined Workflows

Research Overview

If you have built a multi-agent system, you know the black box problem. Your web agent fails to retrieve data, but you do not know why. Was the page unavailable? Did it retrieve partial data? Did it misinterpret the query entirely? The workflow marks the subtask as "failed" and triggers replanning, but you still have no insight into what actually happened. You are debugging a state machine that cannot explain itself.

Most multi-agent frameworks treat coordination as a workflow engineering problem. Systems like OWL, MetaGPT, and AutoAgent require developers to predefine task states and routing rules. The result is a fragile state machine: you enumerate every anticipated failure mode, write routing logic for each, and hope nothing falls through the cracks. When something does, the system either fails silently or triggers expensive replanning that re-executes work already completed.

CORAL takes a different approach. Instead of predefined workflows, it uses an "information flow orchestrator" that monitors task progress and coordinates agents dynamically through natural language. Think of it as replacing the state machine with an auditable checklist. The orchestrator does not follow a decision tree. It observes what agents produce, evaluates whether results meet the actual requirements, and explains its coordination decisions in natural language. When something goes wrong, you can read the orchestrator's reasoning to understand why.

Key results

The performance gap appears when worker agents use weaker models. Weaker models produce more partial results and edge cases. Workflow-based systems cannot handle these gracefully because their predefined states do not account for every failure mode. The information flow orchestrator detects and corrects these issues in real time.

The Workflow Problem

Consider a concrete example from the GAIA benchmark. The task: "Find all U.S. Survivor winners through August 2023, including their names and birth dates."

A web agent retrieves all 46 winner names successfully. But for several winners, birth dates are not available on the pages it accessed. The agent returns results with some birth dates marked as "unknown."

In a workflow-based system like OWL, the subtask is not explicitly marked as "failed" because names were retrieved. The workflow proceeds to the next step, which now operates on incomplete data. Downstream agents compute statistics or filter results based on birth dates, producing wrong answers.

In CORAL, the information flow orchestrator reviews the web agent's output. It notices that several entries lack birth dates, which violates the implicit success criteria of the original query. The orchestrator explicitly identifies this mismatch and instructs the web agent to search specifically for the missing birth dates before proceeding.

Before vs After: A Real Edge Case

Here is how a standard workflow agent and CORAL handle the same partial data scenario:

The orchestrator catches the partial completion because it continuously evaluates results against the original requirements, not just the subtask definition.

Why workflows struggle

The fundamental issue is that real-world tasks have a continuous state space, but workflows discretize this into a finite set of predefined states. Complex tasks inevitably encounter states that fall between the cracks.

Architecture

CORAL organizes agents around a central information flow orchestrator that coordinates all communication.

A useful analogy: the orchestrator is like a Product Manager who coordinates a team of developers. The PM does not write code themselves. Instead, they review deliverables, check if they meet requirements, provide clarifying feedback, and occasionally reassign tasks when someone is stuck. The developers (agents) do the actual work; the PM (orchestrator) ensures the pieces fit together correctly.

Components

Information Flow Orchestrator. The central agent that receives tasks, monitors progress, and coordinates other agents. It maintains a complete history of all inter-agent communication and decides when to dispatch tasks, request clarification, or submit final answers.

Specialized Agents. Domain-specific agents handle particular capabilities:

• Planner: Decomposes complex tasks into subtasks
• Web Agent: Searches and retrieves information from the web
• Document Agent: Processes files, PDFs, and structured data
• Reasoning & Coding Agent: Performs calculations and writes code

A2A Communication Toolkit. A minimal API that enables natural language communication between agents. All coordination happens through this toolkit rather than hardcoded function calls.

Communication flow

1. Task arrives at the information flow orchestrator
2. Orchestrator evaluates task complexity and dispatches to appropriate agent(s)
3. Agent executes and returns results via A2A toolkit
4. Orchestrator evaluates results against task requirements
5. If requirements met: proceed to next step or submit answer
6. If not met: refine instructions, substitute agents, or escalate to planner

The orchestrator maintains a message history that captures all interactions. This history provides context for evaluating whether accumulated results satisfy the original task.

A2A Communication

The A2A (Agent-to-Agent) communication toolkit is intentionally minimal. It provides two operations:

# Agent waits for a message from another agent
wait_for_mention(agent_id) -> message
 
# Agent sends a message to another agent
send_messages(sender_id, recipient_id, content)

Asymmetric Communication: A Critical Design Choice

CORAL enforces a hub-and-spoke pattern: all agents communicate exclusively with the information flow orchestrator. Agents cannot message each other directly. This asymmetric constraint is not a limitation; it is a deliberate architectural decision that prevents coordination chaos.

What an infinite loop looks like:

1. Planner (to Web Agent): "I need the list of AI papers to create a summary."
2. Web Agent (to Planner): "Please specify which papers you want me to search for."
3. Planner (to Web Agent): "I asked you to provide the list of papers."
4. Web Agent (to Planner): "I cannot search without knowing what to search for."
5. (Loop continues indefinitely, consuming tokens until timeout)

With hub-and-spoke, this cannot happen. The orchestrator receives each message and can break the deadlock: "Web Agent, search arXiv for 'multi-agent LLM coordination' papers from 2024-2025."

Think of it this way: too many cooks in the kitchen leads to chaos. The orchestrator acts as the head chef who coordinates all communication. Agents report to the orchestrator, not to each other. This keeps the system predictable and debuggable.

Message structure

Messages are natural language with implicit structure:

Inquiry: "Based on the search results, do we have complete birth date information for all 46 Survivor winners?"

Instruction: "Search specifically for the birth dates of Richard Hatch, Tina Wesson, and Ethan Zohn. Focus on their Wikipedia pages."

Response: "Found birth dates: Richard Hatch (April 8, 1961), Tina Wesson (December 26, 1961), Ethan Zohn (November 12, 1973)."

The orchestrator interprets these messages using the same LLM capabilities that power the agents themselves.

Emergent Coordination Patterns

Through case-level analysis of GAIA benchmark executions, the authors identified four distinct coordination patterns that emerge from the orchestrator's behavior. These patterns are not programmed explicitly. They arise from the orchestrator's continuous monitoring and adaptive decision-making.

Pattern 1: Direct Agent Dispatch

For simple, non-decomposable tasks, the orchestrator skips planning entirely. It directly assigns the task to an appropriate agent.

Example: "What is the capital of France?" The orchestrator dispatches directly to the web agent without invoking the planner. This avoids unnecessary decomposition overhead.

Benefit: Reduces token consumption and avoids the failure modes that excessive decomposition can introduce.

Pattern 2: Planner-Mediated Decomposition

For complex tasks that benefit from explicit structure, the orchestrator consults the planner to decompose the task into subtasks.

Example: "Compare the GDP growth rates of G7 countries over the past decade and identify which country had the most consistent growth."

The orchestrator recognizes this requires multiple data retrieval steps followed by analysis. It asks the planner to create a structured decomposition.

Benefit: Provides explicit task structure when beneficial, while remaining compatible with traditional workflow patterns.

Pattern 3: Instruction Refinement

When an agent struggles with a task, the orchestrator does not immediately escalate to replanning. Instead, it refines the original instruction and lets the same agent retry.

Example dialogue:

Web Agent: "Search results for 'Survivor winners birth dates' returned a list of 46 names but birth dates for only 40 winners. The remaining 6 entries show 'Date of birth: Unknown'."

Orchestrator: "The current results are incomplete. 6 winners lack birth dates: Richard Hatch, Tina Wesson, Ethan Zohn, Vecepia Towery, Brian Heidik, and Jenna Morasca. Please search specifically for each of these names on their Wikipedia pages and return the exact birth date strings (e.g., 'April 8, 1961')."

Web Agent: "Found: Richard Hatch (April 8, 1961), Tina Wesson (December 26, 1961), Ethan Zohn (November 12, 1973), Vecepia Towery (March 21, 1965), Brian Heidik (March 5, 1962), Jenna Morasca (February 15, 1981)."

Benefit: Maintains context continuity and avoids the token overhead of full replanning.

Pattern 4: Agent Substitution

When one agent cannot complete a task, the orchestrator reassigns it to a different agent without full replanning.

Example: The web agent cannot access a paywalled article. The orchestrator substitutes: "Document agent, can you process this PDF version instead?"

Benefit: Explores alternative execution paths without restarting the entire task.

Benchmark Results

CORAL was evaluated on the GAIA validation set (165 tasks) against OWL, a state-of-the-art workflow-based multi-agent system.

Homogeneous configuration (all agents use Grok 4.1 Fast)

With strong models everywhere, both systems achieve identical overall accuracy. CORAL performs slightly worse on simple tasks (Level 1) where the overhead of dynamic coordination provides no benefit. It performs better on medium-complexity tasks (Level 2) where edge cases are more common.

Heterogeneous configuration (main agents: Grok 4.1 Fast, workers: GPT-4.1 Mini)

When worker agents use weaker models, the performance gap becomes substantial. Weaker models produce more partial results, errors, and edge cases. OWL's predefined workflows cannot handle these gracefully. CORAL's orchestrator detects and corrects issues in real time.

Token consumption

With homogeneous models, CORAL uses slightly more tokens due to A2A communication overhead. With heterogeneous models, CORAL actually uses fewer tokens on complex tasks (over 0.6M tokens). This is because workflow-based systems trigger full replanning on failures, which re-executes completed subtasks. The orchestrator often resolves issues through instruction refinement without re-execution.

Edge Case Handling

The authors identified three strategies that the information flow orchestrator uses to handle edge cases that workflow systems miss.

Example of orchestrator reasoning:

When the web agent returns "The average age of Survivor winners is approximately 32 years," the orchestrator internally evaluates:

"The original task asked for 'the exact average age of all Survivor winners.' The response says 'approximately 32 years,' which indicates an estimate rather than a precise calculation. This does not satisfy the 'exact' requirement. I should ask the agent to compute the average using the actual birth dates rather than an approximation."

This reasoning happens automatically as part of the orchestrator's response generation. No explicit confidence scores or thresholds are needed.

Strategy 1: Dynamic Success Criteria

Scenario: Web agent retrieves Survivor winners but some birth dates are "unknown."

Workflow behavior: Subtask marked as success because names were retrieved. Downstream tasks proceed with incomplete data.

Orchestrator behavior: Detects that "unknown" entries violate the implicit requirement for complete birth date information. Explicitly refines success criteria and instructs the agent to search specifically for missing data.

Strategy 2: Semantic Assumption Auditing

Scenario: Task asks for albums released "before 1999." Agent returns albums from 1999.

Workflow behavior: Results passed through because the query structure was satisfied.

Orchestrator behavior: Audits the semantic assumption that "1999" satisfies "before 1999." Prunes invalid entries before they propagate to downstream tasks.

Strategy 3: Instruction Alignment Monitoring

Scenario: Task asks for reading rates in "words per day." Agent uses page counts as a proxy because word counts are unavailable.

Workflow behavior: Subtask marked as complete because a calculation was performed.

Orchestrator behavior: Detects the mismatch between requested metric and proxy used. Escalates to planner with specific instruction to retrieve actual word counts from external sources.

Implementation Blueprint

Business impact

The switch from workflow-based to information-flow coordination has measurable ROI:

These estimates are based on the GAIA benchmark results extrapolated to production workloads. Your mileage will vary based on task complexity and current failure rates.

Cost analysis: When to use CORAL

CORAL is not always the right choice. The orchestrator adds communication overhead that does not pay off for simple tasks.

Rule of thumb: If your agents fail more than 20% of the time on edge cases, switch to CORAL. If they fail less than 5%, the overhead is not worth it.

Recommended tech stack

Core data structures

The A2A toolkit requires two simple operations. Here is a minimal implementation:

class A2AToolkit:
    def __init__(self):
        self.messages = []
        self.waiting = {}  # agent_id -> Event
 
    def send_message(self, sender, recipient, content):
        """Send message; wakes up waiting recipient."""
        msg = {
            "from": sender,
            "to": recipient,
            "content": content,
            "ts": time.time()
        }
        self.messages.append(msg)
        # Wake up recipient if blocking
        if recipient in self.waiting:
            self.waiting[recipient].set()
 
    def wait_for_mention(self, agent_id, timeout=300):
        """Block until this agent receives a message.
 
        This is the key coordination primitive.
        Agents call this to wait for instructions
        from the orchestrator. Without it, agents
        would need to poll for new messages.
        """
        event = threading.Event()
        self.waiting[agent_id] = event
        event.wait(timeout=timeout)
        return self._get_latest(agent_id)

Orchestrator prompt structure

The information flow orchestrator requires a prompt that specifies:

1. Monitoring responsibility: Continuously evaluate whether agent outputs satisfy task requirements
2. Coordination authority: Dispatch tasks, refine instructions, substitute agents
3. Submission criteria: When accumulated results are sufficient to answer the original query

You are an information flow orchestrator. Your role is to:

1. MONITOR: Evaluate each agent response against the
   original task requirements. Check for:
   - Completeness (all requested data present?)
   - Accuracy (semantic assumptions correct?)
   - Alignment (methodology matches requirements?)

2. COORDINATE: Based on your evaluation:
   - If complete: proceed to next step or submit
   - If partial: refine instructions for same agent
   - If stuck: substitute with different agent
   - If complex: consult planner for decomposition

3. SUBMIT: When you have sufficient information to
   answer the original query with confidence.

Available agents: planner, web_agent, doc_agent, code_agent

Key parameters

Common pitfalls

Overly aggressive decomposition. The orchestrator may invoke the planner for simple tasks. Monitor task complexity and prefer direct dispatch for straightforward queries.

Infinite refinement loops. The orchestrator may keep refining instructions without progress. Implement a refinement counter and escalate to replanning after 2-3 attempts.

Context overflow. Full message history can exceed context limits on long tasks. Implement summarization for completed subtask threads.

Resources

• GitHub: github.com/Coral-Protocol/Beyond-Rule-Based-Workflows
• CORAL Protocol: coral.dev
• GAIA Benchmark: huggingface.co/datasets/gaia-benchmark/GAIA

Limitations

Single orchestrator bottleneck. All coordination flows through one agent. For highly parallel tasks, this could become a throughput constraint.

No learning from experience. The orchestrator does not improve over time. Each task starts fresh without memory of successful coordination patterns from previous tasks.

Communication overhead. A2A messaging adds tokens compared to direct function calls in workflow systems. This overhead is only justified for tasks complex enough to benefit from dynamic coordination.

Evaluation scope. Results are on GAIA only. Performance on domain-specific benchmarks (code generation, scientific reasoning) may differ.

Model dependence. The orchestrator's effectiveness depends heavily on the underlying LLM's ability to evaluate task completion and generate appropriate coordination messages.

The Bottom Line

Should you switch to CORAL?

Use this decision framework:

Audience-specific takeaways

For ML engineers: Start with the reference implementation and adapt the orchestrator prompt to your domain. Focus on the monitoring prompt (what constitutes "complete" results for your use case).

For engineering managers: The 8.5 pp improvement matters most with heterogeneous models. Budget 1-2 weeks for integration. The real savings come from eliminating ongoing workflow maintenance, not just accuracy gains.

For researchers: The four emergent patterns (direct dispatch, planner-mediated decomposition, instruction refinement, agent substitution) provide a taxonomy for analyzing dynamic coordination. Future work could explore learning these patterns rather than letting them emerge implicitly.

Paper: arXiv:2601.09883 Authors: Xinxing Ren, Quagmire Zang, Caelum Forder, Suman Deb, Ahsen Tahir, et al. (Coral Protocol, multiple universities) Original paper: arXiv ・ PDF ・ HTML