💻 computer science

Learning Latency-Aware Orchestration for Multi-Agent Systems

The paper introduces LAMaS, a novel framework that reduces end-to-end latency in multi-agent systems by learning latency-aware execution graphs with critical-path credit assignment during training and employing a lightweight adaptive controller to eliminate redundant interactions during inference, achieving over 50% latency reduction while maintaining task accuracy.

Original authors: Xi Shi, Mengxin Zheng, Qian Lou

Published 2026-08-14

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Xi Shi, Mengxin Zheng, Qian Lou

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 a team of brilliant, specialized robots working together to solve a complex puzzle. This is the world of Multi-Agent Systems (MAS), where powerful AI "brains" (called Large Language Models) are broken down into smaller, focused helpers. One robot might be great at math, another at coding, and a third at checking facts. By passing notes and ideas back and forth, they can tackle problems a single robot couldn't solve alone. However, there's a catch: every time these robots talk to each other, it takes time. If they have to pass a note ten times to get an answer, the whole process drags on, sometimes taking 10 to 60 minutes just to finish a single task. In the real world, waiting that long is a dealbreaker.

For a while, scientists tried to make these teams faster by simply cutting costs or making the robots smarter. But they realized that making the team "cheaper" doesn't always make it "faster." Think of it like a relay race: if you have a team of ten runners, the total time isn't just the sum of everyone's running speed; it's determined by the slowest, longest chain of runners passing the baton. If you cut the number of runners but leave the slowest chain untouched, the race time doesn't improve. The big question became: How do we redesign the team's workflow to shave off time without losing the accuracy of the final answer?

This is exactly what the researchers at the University of Central Florida tackled in their new paper, introducing a system called LAMaS (Latency-Aware Multi-agent System). They found that the old way of optimizing these AI teams was like trying to fix a traffic jam by telling every car to drive faster, even if the bottleneck was a single narrow bridge. Instead, LAMaS acts like a smart traffic controller that knows exactly which part of the route is the "critical path"—the longest chain of steps that determines the total time.

The paper proposes a two-part strategy to fix the speed issue. First, during the "training" phase (where the system learns how to work), LAMaS uses a special scoring method. Instead of punishing every robot equally for taking too long, it focuses its "scolding" only on the robots that are part of the critical path—the ones holding up the whole team. It also sets a strict rule: no matter how fast they get, they cannot drop below a certain level of accuracy. It's like telling a race team, "You can run as fast as you want, but you must still finish the race correctly."

Second, and perhaps more cleverly, LAMaS adds a "lightweight controller" that watches the race in real-time. Even if the team planned to run ten laps, this controller might notice after lap three that the team has already figured out the answer. It then has the power to say, "Stop! We don't need the other seven laps," and cut the rest of the work short. This happens dynamically as the task unfolds, rather than being a fixed plan made in advance.

When the researchers tested this on four different challenging benchmarks—ranging from solving grade-school math problems to writing code and answering complex knowledge questions—they found that LAMaS was a game-changer. Compared to other advanced AI team systems, LAMaS reduced the total waiting time by over 50% (in some cases cutting it by as much as 75%) while keeping the accuracy just as high, or even better. For example, on a math benchmark called GSM8K, their system finished in about 11.73 seconds with 93.65% accuracy, whereas other top systems took over 48 seconds for similar accuracy.

The paper suggests that this approach isn't just a one-time fix for one specific system; when they tried plugging the LAMaS method into other existing AI team designs, it consistently made them faster without breaking them. The authors show that by focusing on the "bottleneck" steps and allowing the system to stop early when it's confident, we can build AI teams that are not only smart but also lightning-fast, making them much more practical for real-world use.

=== SUMMARY ===

Technical Summary: Learning Latency-Aware Orchestration for Multi-Agent Systems (LAMaS)

1. Problem Statement

Multi-Agent Systems (MAS) enhance the reasoning capabilities of Large Language Models (LLMs) by orchestrating multiple specialized agents. However, as these systems scale, inference latency has become a critical bottleneck, often requiring 10–60 minutes per task in realistic scenarios.

Existing orchestration methods primarily optimize for task performance and inference cost (token usage). The authors argue that these objectives are insufficient for latency reduction because:

Structural Mismatch: End-to-end latency is governed by the critical execution path (the longest chain of dependencies), not the total additive cost of all operators. Reducing total cost does not necessarily shorten the critical path.
Credit Assignment Noise: Simple latency optimization applies uniform penalties, failing to distinguish between operators on the critical path (bottlenecks) and those on non-critical paths.
Accuracy-Latency Trade-off: Optimizing for latency without constraints can degrade task accuracy unpredictably.
Static Limitations: Graphs fixed at training time cannot leverage runtime evidence (e.g., early consensus on an answer) to eliminate redundant future interactions.

2. Methodology: LAMaS Framework

The authors propose Latency-Aware Multi-agent System (LAMaS), a framework that addresses latency at two distinct levels: training-time graph optimization and inference-time execution control.

A. Training-Time: Constrained Optimization with Critical-Path Awareness

LAMaS formulates orchestration as a constrained optimization problem:
$\min_{\theta} \mathbb{E}[\lambda_t T + \lambda_c C] \quad \text{s.t.} \quad \mathbb{E}[S] \geq S_0$
Where $T$ is latency, $C$ is cost, $S$ is task accuracy, and $S_0$ is a target accuracy floor.

Lagrangian Relaxation: The constraint is solved via an adaptive dual variable ( $\lambda_S$ ) updated via projected gradient ascent. This ensures the system reduces latency only if it does not fall below the reference accuracy ( $S_0$ ) of the underlying architecture.
Critical-Path-Aware Credit Assignment: To address the structural mismatch, LAMaS assigns operator-level rewards based on path criticality.
- For an operator $o$ , the weight $w(o)$ is defined as the ratio of the longest path passing through $o$ to the total critical path length ( $T$ ).
- Operators on the critical path ( $w(o)=1$ ) receive the full latency penalty.
- Operators on near-critical paths receive attenuated penalties, while those on non-critical paths receive negligible signals. This directs gradient updates toward bottleneck operators.

B. Inference-Time: Adaptive Execution Control

Recognizing that a training-time graph cannot exploit runtime evidence, LAMaS introduces a lightweight execution controller.

Function: At each operator completion, the controller evaluates whether the current partial execution is sufficient or if further agent interactions are beneficial.
Mechanism: It predicts a "control advantage" ( $\Delta_k$ ), estimating the difference in Lagrangian reward between stopping now versus running the full graph.
Decision: If $\Delta_k > 0$ , the system terminates early, eliminating redundant future interactions. The controller is trained via MSE regression on traces collected from the frozen orchestrator, using features such as execution progress, answer consensus (semantic equivalence of outputs), and query difficulty.

3. Key Contributions

Formulation: The authors formulate latency-aware MAS orchestration as a constrained optimization problem that minimizes latency under an accuracy floor, solved via Lagrangian relaxation.
Credit Assignment: They introduce a critical-path-aware credit assignment mechanism that weights latency penalties by path criticality, ensuring gradients focus on bottleneck operators.
Runtime Control: They propose a lightweight inference-time controller that scores partial executions and adaptively eliminates redundant agent interactions based on runtime evidence.
Modularity: The framework is designed to be modular, allowing the core mechanisms to transfer to other learning-based MAS architectures with minimal changes.

4. Experimental Results

LAMaS was evaluated on four benchmarks: GSM8K, HumanEval, MATH, and MMLU-Pro, against baselines including non-MAS strategies (CoT, SC) and learned MAS orchestrators (MaAS, GDesigner, AgentDropout).

Latency Reduction: LAMaS achieved the best latency among all evaluated learning-based MAS baselines, reducing end-to-end latency by 55.6% to 75.6% compared to the strongest baselines (e.g., reducing latency from 48.11s to 11.73s on GSM8K).
Accuracy Preservation: Despite significant latency reductions, LAMaS maintained competitive or better accuracy compared to baselines (e.g., 93.65% vs. 93.36% on GSM8K).
Cost Efficiency: The method also reduced API costs significantly (e.g., from 31.52 to 7.71 units on GSM8K) due to fewer operator invocations.
Ablation Studies:
- Removing the inference-time controller increased latency by 16.5–21.1%.
- Removing critical-path credit assignment degraded all metrics, confirming the necessity of path-weighted penalties.
- A "simple" latency-only approach (without accuracy floors or critical-path weighting) resulted in significant accuracy drops with minimal latency gains.
Transferability: When integrated into other architectures (GDesigner and AgentDropout), the LAMaS pipeline consistently reduced latency by 27–39% while preserving accuracy, demonstrating its generality.

5. Significance and Claims

The paper claims that LAMaS addresses a fundamental gap in multi-agent orchestration: the inability of existing cost- or performance-focused methods to reliably control execution latency.

Structural Insight: The work highlights that latency is a graph-level property determined by the critical path, requiring specialized credit assignment rather than uniform additive rewards.
Practical Deployment: By reducing latency by over 50% without sacrificing accuracy, LAMaS makes complex multi-agent reasoning more viable for practical, real-time deployment.
Do-No-Harm Constraint: The use of an explicit accuracy floor ( $S_0$ ) ensures that latency optimization does not come at the expense of task performance, a common failure mode in unconstrained optimization.
Generalizability: The framework's ability to transfer to other MAS architectures suggests that latency-aware orchestration is a universal requirement for scalable agent systems, independent of the specific underlying policy network.