💻 computer science

Learning Latency-Aware Orchestration for Multi-Agent Systems

This paper introduces LAMaS, a novel orchestration framework that reduces end-to-end latency in multi-agent systems by over 50% while maintaining accuracy through a two-level approach combining critical-path-aware training and an adaptive inference-time controller.

Original authors: Xi Shi, Mengxin Zheng, Qian Lou

Published 2026-07-16

📖 5 min read🧠 Deep dive

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 you are the conductor of a massive, high-tech orchestra where every musician is a super-smart robot brain. In the world of artificial intelligence, these robot brains are called "agents," and when they work together, they can solve incredibly hard puzzles, write complex code, or even do your homework. This field is known as Multi-Agent Systems. The idea is simple: one robot might be great at math, another at reading, and a third at checking facts. If they pass notes back and forth, they can tackle problems that stump a single robot. But here's the catch: every time they pass a note, it takes time. If the orchestra has to pass notes in a long, winding line, the music takes forever to start. In the real world, waiting 10 to 60 minutes for a computer to finish a task is like waiting for a slow internet connection to load a single cat video—it's frustrating and makes the technology hard to use.

For a long time, scientists trying to fix this have focused on two things: making sure the robots get the right answer (accuracy) and making sure they don't spend too much money on electricity or computer time (cost). They treated the robots like a grocery bill, trying to keep the total price low. But this paper points out a funny flaw in that thinking: just because you buy fewer items doesn't mean you get to the checkout line faster. If you have a long line of people, the total time you wait depends on the slowest person in the longest line, not on how many people are in the store total. In computer terms, this is called the "critical path." You could cut the cost in half by removing a few side conversations, but if the main conversation chain is still long and winding, the wait time stays the same. The big question this paper asks is: How do we teach these robot teams to finish their work faster without making them dumber or more expensive?

Enter LAMaS (Latency-Aware Multi-agent System), a new framework proposed by researchers Xi Shi, Mengxin Zheng, and Qian Lou from the University of Central Florida. Think of LAMaS as a super-organized stage manager for our robot orchestra. Instead of just counting how many notes the musicians play (cost), LAMaS watches the clock and figures out exactly which notes are causing the delay.

The researchers found that previous methods were like a teacher who scolds the whole class for being late, even if only one student was dawdling. LAMaS is smarter. It uses a special training method to identify the "bottleneck"—the specific chain of robots that is holding up the whole show. It gives extra credit (or rather, extra focus) to the robots on that slow chain, teaching them to be more efficient, while letting the other robots relax. This is called "critical-path-aware credit assignment." It's like telling the runner in the slowest lane to sprint, rather than yelling at everyone in the stadium.

But there's a second trick. Sometimes, even the best plan can't predict the future. What if the robots figure out the answer halfway through the show? A rigid plan would force them to finish the whole script anyway, wasting time. LAMaS adds a "lightweight controller," which acts like a sharp-eyed director sitting in the wings. As the robots perform, this director watches the progress. If the robots have already agreed on the answer and are just repeating themselves, the director shouts "Cut!" and stops the unnecessary future interactions. This happens in real-time, trimming the fat off the performance as it unfolds.

The team tested this new system on four different types of tough challenges: math problems, coding tasks, competition-level math, and complex knowledge questions. The results were impressive. Compared to other smart robot teams, LAMaS didn't just get the answers right; it got them over 50% faster. In some cases, it cut the waiting time from over a minute down to just a few seconds, all while keeping the accuracy just as high (or even better) than the slower methods.

The researchers also showed that this isn't a one-trick pony. They took the LAMaS stage manager and director and plugged them into other existing robot team systems. Even without rebuilding those systems from scratch, the new methods made them faster, proving that this approach is flexible and can be used to speed up many different kinds of AI teams.

In short, this paper suggests that to make AI faster, we need to stop looking at the whole team's total effort and start focusing on the specific bottlenecks that cause delays, while also having a smart supervisor ready to stop the show the moment the job is done. It's a shift from simply counting the cost of doing the work to actually managing the time it takes, making these powerful robot teams much more practical for the real world.

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

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 approaches 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. Optimizing total cost does not reliably reduce the critical path length.
Credit Assignment Noise: Naive latency penalties applied uniformly to all operators fail to distinguish between bottleneck operators on the critical path and non-critical operators, leading to noisy gradient signals.
Accuracy-Latency Trade-off: Optimizing for latency without constraints can degrade task accuracy unpredictably.
Static Limitations: Graphs committed at training time cannot leverage runtime evidence (e.g., early consensus on an answer) to eliminate redundant future interactions.

Methodology

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

1. Training-Time Constrained Optimization

LAMaS formulates orchestration as a constrained optimization problem: minimize latency and cost subject to an accuracy floor ( $S_0$ ).

Objective: $\min_{\theta} \mathbb{E}[\lambda_t T + \lambda_c C]$ s.t. $\mathbb{E}[S] \geq S_0$ .
Lagrangian Relaxation: The constraint is handled via an adaptive dual variable ( $\lambda_S$ ) updated via projected gradient ascent. This automatically balances the trade-off: if accuracy drops below $S_0$ , $\lambda_S$ increases to prioritize correctness; if accuracy is met, $\lambda_S$ decreases to allow aggressive latency reduction.
Critical-Path-Aware Credit Assignment: To address the non-additive nature of latency, LAMaS assigns operator-level rewards based on path criticality.
- For an operator $o$ , the weight $w(o) = \ell(o) / T$ is calculated, where $\ell(o)$ is the longest path passing through $o$ and $T$ is the total critical path length.
- Operators on the critical path receive a full latency penalty ( $w(o)=1$ ), while those on near-critical or non-critical paths receive attenuated penalties. This ensures gradients focus on bottleneck operators.

2. Inference-Time Execution Control

Since a training-time graph cannot adapt to runtime evidence, LAMaS introduces a lightweight execution controller.

Function: The controller monitors partial executions and predicts the control advantage ( $\Delta_k$ ), defined as the difference between the Lagrangian reward of the current partial execution and the reward of running the full graph.
Decision Logic: If $\Delta_k > 0$ , the current partial execution is preferred (it preserves accuracy while reducing latency), and the controller eliminates redundant future agent interactions.
Implementation: A small Multi-Layer Perceptron (MLP) predicts $\Delta_k$ using features such as execution progress, answer consensus (semantic equivalence of outputs), and query difficulty. The controller is trained via MSE regression on traces collected from the frozen orchestrator.

Key Contributions

Formulation: The authors formulate latency-aware MAS orchestration as a constrained optimization problem that minimizes latency under an explicit accuracy floor, solved via Lagrangian relaxation.
Credit Assignment Mechanism: They introduce a critical-path-aware credit assignment strategy that weights latency penalties by path criticality, ensuring optimization targets bottleneck operators rather than applying uniform noise.
Hybrid Control: They propose a lightweight execution-time controller that supports the online elimination of redundant agent interactions based on runtime consensus and progress, complementing the static graph construction.
Modularity: The framework is designed to be modular, transferring to other learning-based MAS architectures with minimal changes.

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 (GDesigner, AgentDropout, MaAS).

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% on GSM8K vs. 93.36% for MaAS).
Cost Efficiency: The method also reduced API costs significantly (e.g., 7.71 vs. 31.52 $\times 10^{-4}$ USD on GSM8K) by reducing the number of tokens on the critical path.
Ablation Studies: Removing the inference-time controller increased latency by 16–21%. Removing critical-path credit assignment degraded all metrics. A naive "add latency to reward" approach without the accuracy floor or critical-path weighting resulted in significant accuracy drops with minimal latency gains.
Transferability: When applied to other architectures (GDesigner and AgentDropout), the LAMaS pipeline consistently reduced latency by 27–39% while preserving accuracy, demonstrating its generality.

Significance and Claims

The paper claims that LAMaS addresses a fundamental gap in multi-agent orchestration: the inability of existing cost- and accuracy-focused methods to reliably control execution latency. By treating latency as a structured, graph-level property rather than an additive cost, and by decoupling training-time graph optimization from inference-time adaptive control, LAMaS achieves a "do-no-harm" reduction in latency. The authors emphasize that their approach does not merely shrink computation but intelligently targets the critical execution path and leverages runtime evidence to eliminate redundancy, offering a practical pathway for deploying faster, more efficient multi-agent systems without sacrificing reasoning quality.