💬 NLP

Improving the Efficiency of Language Agent Teams with Adaptive Task Graphs

The paper introduces LATTE, a framework that coordinates large language model teams through a shared, evolving task graph to dynamically balance structural consistency with adaptability, thereby reducing resource consumption and coordination failures while maintaining or improving accuracy compared to existing static or unstructured approaches.

Original authors: Elizabeth Mieczkowski, Alexander Ku, Tiwalayo Eisape, Dilip Arumugam, John Matters, Katherine M. Collins, Ilia Sucholutsky, Thomas L. Griffiths

Published 2026-05-08

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Elizabeth Mieczkowski, Alexander Ku, Tiwalayo Eisape, Dilip Arumugam, John Matters, Katherine M. Collins, Ilia Sucholutsky, Thomas L. Griffiths

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a team of incredibly smart, but slightly chaotic, robots trying to build a complex machine together. Some robots are great at planning, others at building, and some at checking the work. The problem is: how do you get them to work together without stepping on each other's toes, wasting time, or building the wrong parts?

This paper introduces a new way to organize these robot teams called LATTE (Language Agent Teams for Task Evolution).

The Problem: Two Bad Extremes

The authors say current ways of organizing AI teams fall into two traps:

The Rigid Factory: Imagine a strict assembly line where every robot has a fixed job and a fixed order. Robot A must do step 1, then Robot B must do step 2.
- The issue: If Robot A makes a mistake or if the instructions change halfway through, the whole line breaks. The robots can't adapt. If Robot A is slow, everyone waits.
The Wild West: Imagine a group of robots in a room with no rules. They all shout out ideas and start building whatever they want.
- The issue: They end up fighting over the same tools, building the same part twice, or overwriting each other's work. It's chaotic and wastes a lot of energy.

The Solution: A Living Map (The "Adaptive Task Graph")

LATTE solves this by giving the team a shared, living map (called a "Dynamic Coordination Graph"). Think of this map like a whiteboard that the whole team can see and update in real-time.

Here is how it works using a simple analogy:

The Team: You have a Lead (the project manager) and several Workers (the builders).
The Map: Instead of a fixed checklist, the map shows tasks as dots connected by lines.
- Dots (Nodes): These are small jobs (e.g., "fix the code," "analyze the data").
- Lines (Edges): These show dependencies (e.g., "You can't paint the wall until the drywall is fixed").
- The Frontier: This is the edge of the map where all the "ready to go" jobs are.

How LATTE Runs the Show

The magic of LATTE is in how the team interacts with this map:

The Lead Draws the Map: At the start, the Lead looks at the big goal and draws the initial map.
Workers Claim Jobs: Instead of waiting for the Lead to hand out every single task, if a worker finishes their job and sees an empty "ready" spot on the map, they can claim it themselves. This is like a worker saying, "I'm free, I'll grab that next job," rather than waiting for a boss to tell them what to do.
Discovering New Jobs: As workers do their jobs, they might realize, "Oh, I need to do this other thing first that we didn't think of." They can add a new dot to the map immediately.
The Lead as a Safety Net: The Lead watches the map. If a worker gets stuck (like a robot spinning its wheels), the Lead can release that job and give it to someone else. If a job looks risky, the Lead can add a "verification" step to double-check the work.

Why This is Better (The Results)

The authors tested LATTE against the "Rigid Factory" and the "Wild West" methods on tasks like debugging code, analyzing data, and building software libraries.

Less Waste: Because the map prevents two workers from trying to fix the same file at the same time, they wasted way less time and computer power (tokens).
Faster: By letting workers grab jobs as soon as they are ready (instead of waiting for a boss), the team finished tasks much faster.
Smarter: The team could adapt when things went wrong. If a plan failed, they could redraw the map on the fly.
Better Quality: The team made fewer mistakes and produced more accurate results than the other methods.

The Big Takeaway

The paper argues that you don't need a strict boss to control every move, nor do you need to let everyone run wild. The sweet spot is a shared, evolving plan that the team builds together.

Think of it like a group of hikers navigating a mountain.

Rigid: One person holds a map and says, "Step left, then right, then left." If they hit a rock, the whole group stops.
Wild: Everyone runs in different directions, shouting, and eventually they lose each other.
LATTE: They have a shared GPS map. The leader updates the route, but if a hiker sees a better path or a blocked trail, they can update the map for everyone. If someone gets stuck, the group can quickly reroute them. Everyone knows where they are going, but they can adapt to the terrain as they go.

The result is a team that is efficient, doesn't waste resources, and can handle complex, changing problems much better than before.

Technical Summary: Improving the Efficiency of Language Agent Teams with Adaptive Task Graphs

Problem Statement

Large Language Model (LLM) teams are increasingly deployed to solve complex collaborative tasks, yet existing coordination architectures face a fundamental tension between structure and adaptability. Current approaches typically occupy one of two extremes:

Highly Structured Systems: Frameworks like MetaGPT or Leader-Worker hierarchies rely on fixed roles, pre-specified pipelines, or static task decompositions assigned a priori. While these ensure consistency, they lack the flexibility to adapt when new dependencies emerge, workloads shift, or agents fail. They often suffer from bottlenecks, single points of failure (e.g., Lead hallucinations), and inefficiencies when the initial plan is suboptimal.
Fully Unstructured/Decentralized Systems: These allow agents to operate autonomously, fostering adaptability. However, they frequently suffer from error propagation, inter-agent conflicts (e.g., file overwrites), redundant outputs, and super-linear communication overhead. Without coordination scaffolding, agents often overwrite each other's work or fail to detect when sequential dependencies are violated.

The core challenge is designing a coordination mechanism that maintains global consistency and efficiency while preserving the capacity for dynamic, context-sensitive adaptation inherent to LLMs.

Methodology: LATTE Framework

The authors propose LATTE (Language Agent Teams for Task Evolution), a formal orchestration framework inspired by distributed systems protocols. LATTE enables a team of agents to collaboratively construct, maintain, and adapt a shared Dynamic Coordination Graph during execution.

Core Architecture

Agent Roles: The team consists of a Lead ( $\ell$ $ℓ$ ) and a set of Workers ( $W$ $W$ ).
- The Lead maintains global visibility of the coordination graph and controls operators with graph-wide consequences (e.g., assigning tasks, verifying outputs, releasing stalled tasks).
- Workers execute assigned subtasks and possess local visibility. They can propose structural changes (e.g., discovering new subtasks) and claim available work.
Dynamic Coordination Graph ( $G_t$ ): A directed acyclic graph (DAG) where:
- Nodes represent subtasks.
- Edges encode dependency constraints (a node cannot begin until its predecessors are complete).
- State ( $\lambda_t$ ): Each node is assigned an agent and a status from the set $\{pending, assigned, in\_progress, done, verified\}$ .
- Frontier ( $F_t$ ): The set of pending nodes with no unsatisfied dependencies. These represent the tasks immediately available for parallel execution.

Graph Mutation Operators

LATTE defines a set of explicit operators with preconditions and postconditions to mutate the graph, ensuring the DAG invariant is preserved:

DISCOVER: Adds a new pending node (subtask) with specified dependencies. Can be invoked by Lead or Workers.
ASSIGN: Lead assigns a pending node to a specific Worker.
CLAIM: A Worker proactively claims a node from the frontier ( $F_t$ ) if idle, mimicking work-stealing to reduce overhead.
COMPLETE: A Worker marks its assigned node as done.
RELEASE: Lead reassigns a stalled task (detected via heartbeat monitoring) back to the pending state.
CLOSE: Lead forces a node to completion without waiting for the Worker signal (used when tests pass but the agent is stuck).
VERIFY: Lead spawns a verification node for high-risk outputs, triggering a review before downstream tasks proceed.

Execution Protocol

The execution proceeds in rounds:

Planning: The Lead initializes $G_0$ by decomposing the task.
Monitoring: Heartbeat checks identify stragglers (agents inactive for $H$ rounds).
Dispatching: Idle Workers claim tasks from $F_t$ ; the Lead assigns remaining tasks.
Parallel Execution: Selected agents execute their subtasks.
Graph Update: Agents propose mutations (DISCOVER, COMPLETE, CLAIM), which are serialized and merged by the Lead to update $G_t$ .

This hybrid model balances consistency (via the Lead's serialization of updates) with adaptability (via Workers' ability to discover tasks and claim work).

Key Contributions

Formal Orchestration Framework: LATTE introduces a rigorous execution protocol using dynamic task graphs with explicit graph mutation operators. This structure induces desirable runtime properties, such as maximal parallelism via frontier nodes.
Hybrid Centralized-Decentralized Model: The framework employs a two-tier model where Workers propose structural modifications and the Lead evaluates them. This is grounded in a probabilistic account of task decomposition (analogous to Metropolis-Hastings sampling), balancing local adaptability with global consistency.
Interpretability and Auditing: By externalizing coordination decisions into an evolving graph, LATTE makes team behavior observable. The authors introduce a suite of coordination metrics (overwrite rate, concurrent conflicts, wasted characters, idle rounds, straggler tail latency) to benchmark multi-agent systems beyond simple accuracy.
Empirical Validation: Extensive experiments demonstrate that LATTE outperforms existing frameworks in efficiency and accuracy.

Experimental Results

The authors evaluated LATTE against four baselines (MetaGPT, Leader-Worker, Decentralized, and a Static Graph ablation) across three tasks: Exploratory Data Analysis, Debugging, and Library Extension, using Claude Sonnet 4-6 and GPT-5.2.

Efficiency: LATTE achieved a mean token cost of 47.5% relative to the next-best method (Static Graph), reducing token usage by nearly half. It also reduced wall-clock time significantly compared to Leader-Worker and MetaGPT baselines.
Accuracy: LATTE achieved the highest overall task accuracy (79.7%), surpassing static graphs (57.6%), fixed pipelines (33.9%), and decentralized teams (73.9%).
Coordination Quality:
- Conflicts: LATTE reduced agent overwrites by 5.3x compared to Leader-Worker and 8.2x compared to decentralized teams.
- Wasted Output: Discarded characters were reduced from ~45k (Leader-Worker) to ~5k per trial.
- Communication: LATTE agents sent fewer messages (20.4 vs. 31.4–34.8) and exchanged leaner content.
- Stragglers: The heartbeat mechanism allowed LATTE to recover from stalled agents, reducing the 95th percentile completion time for nodes by 2.3x compared to static systems.
Dynamic Adaptation: Analysis showed that LATTE teams actively utilized the full range of graph operators, with "Discover" being the most frequent, confirming that teams expanded their coordination graphs as new requirements emerged during execution.

Significance and Claims

The paper argues that explicit coordination structures maintained by agents themselves are a viable path toward LLM teams that are simultaneously more efficient, interpretable, and adaptive.

Paradigm Shift: LATTE challenges the assumption that coordination structures must be imposed by a system architect a priori. Instead, it demonstrates that allowing agents to maintain and revise their own coordination structure online enables teams to adapt to evidence accumulated during execution.
Cost Reduction: By reducing token consumption, wall-clock time, and redundant communication, LATTE directly lowers the computational and financial costs associated with LLM teams.
Robustness: The framework provides mechanisms for fault tolerance (straggler recovery) and quality control (selective verification) that emerge naturally from the coordination protocol rather than being hard-coded.

The authors note limitations, including planning overhead for simple tasks, the current focus on domains with natural subtask boundaries (like coding), and the fixed team size used for benchmarking. They suggest future work could explore extending operators to less structured reasoning tasks and applying reinforcement learning to optimize graph construction and coordination protocols.