1 Introduction↩︎

Multi-Agent Systems (MAS) extend the reasoning capabilities of large language models (LLMs) by orchestrating multiple specialized agents [1]–[3]. However, as these systems scale to include more agents and interaction steps, inference latency becomes a key bottleneck [4]. State-of-the-art agent systems already require 10–60 minutes per task in realistic settings such as computer-use [5] and autonomous research [6], making latency an important factor for practical deployment. In MAS, this challenge is amplified because end-to-end time depends on the structure of agent interactions, not only on per-agent computation.

Recent efforts in automated multi-agent orchestration have made significant progress in optimizing task performance and inference cost [7]–[13]. Yet these methods largely treat efficiency through additive objectives such as cost, whereas latency in MAS is a structured property of the execution graph. Specifically, end-to-end latency is governed by the critical execution path—the longest chain of operations—rather than the total cost across all operators. As illustrated in Figure 1, two execution graphs can achieve similar accuracy and cost, yet differ substantially in latency.

However, optimizing latency while preserving accuracy in MAS is non-trivial. First, latency is non-additive over the execution graph, so a uniform latency penalty yields noisy operator-level credit. Second, latency-driven optimization without an accuracy floor can degrade task performance unpredictably. Third, a graph fixed at training time cannot leverage execution-time evidence about whether further agent interactions remain worthwhile.

To address these challenges, we propose Latency-Aware Multi-agent System (LAMaS), a latency-aware orchestration framework for multi-agent systems. At training time, LAMaS addresses the first two challenges through constrained optimization with critical-path-aware credit assignment, which targets the latency penalty on bottleneck operators while an explicit accuracy floor is enforced via Lagrangian relaxation. At inference time, it addresses the third by complementing graph construction with execution control that monitors operator completions and eliminates redundant future agent interactions.

We evaluate LAMaS on four benchmarks (GSM8K [14], HumanEval [15], MATH [16], and MMLU-Pro [17]) against MAS baselines MaAS [7], GDesigner [9], and AgentDropout [8]. LAMaS achieves the best latency among these baselines while maintaining competitive or better accuracy, and its mechanisms transfer to other MAS with minimal changes.

Our contributions are as follows:

• We formulate latency-aware MAS orchestration as a constrained optimization that minimizes latency under an accuracy floor, solved via Lagrangian relaxation with critical-path-aware credit assignment.

• We introduce a lightweight execution-time controller that scores partial executions under the same Lagrangian objective and supports online elimination of redundant future agent interactions.

• We demonstrate that LAMaS achieves the best latency among MAS baselines across four benchmarks while maintaining competitive or better accuracy, and show that its core mechanisms transfer to other MAS with minimal changes.

2 Related Work↩︎

2.0.0.1 LLM-Based Multi-Agent Systems.

Multi-Agent Systems built on LLMs decompose complex problems into subtasks handled by specialized agents. Early frameworks such as CAMEL [1], AutoGen [2], and MetaGPT [3] demonstrated the potential of collaborative problem-solving through role-playing and structured communication. However, these approaches rely on static, hand-crafted topologies that are labor-intensive to design and difficult to adapt across tasks and difficulty levels.

2.0.0.2 Automated Multi-Agent Orchestration.

To overcome the rigidity of manual designs, recent work treats orchestration as a search or optimization problem. AnyMAC [12] and SeqCV [13] dynamically adjust chain length per query. Aflow [10] and EvoAgentX [11] search over execution topologies using evolutionary or flow-based methods. MaAS [7] models the search space as a probabilistic agentic supernet and trains an orchestrator via policy gradient. AgentPrune [18] prunes redundant communication messages to obtain more economical communication topologies, while AgentDropout [8] dynamically eliminates redundant agents and communication to improve token efficiency. GDesigner [9] uses graph neural networks to architect communication topologies. These methods primarily optimize task performance, token efficiency, or inference cost. In contrast, latency is a graph-level systems objective whose bottlenecks are concentrated on the critical execution path, making it difficult to optimize with uniform additive rewards alone. Orthogonally, systems-level latency management methods such as Kairos [4] optimize serving, batching, or runtime scheduling, complementary to our focus on learning latency-aware orchestration policies.

3 Methodology↩︎

3.1 Problem Setting↩︎

We consider a query-dependent multi-agent system (MAS) that dynamically composes a set of agentic operators to solve an input problem. An agentic operator is the basic execution unit, representing a composite agent invocation that may involve multiple LLM calls and external tool usage. Given a query \(x\), the orchestrator constructs an execution graph \(\mathcal{G} = (\mathcal{V}, \mathcal{E})\), a directed acyclic graph (DAG) where each node \(o \in \mathcal{V}\) is an operator invocation. The edge set \(\mathcal{E}\) is induced by operator I/O flow: an edge \((o_i, o_j) \in \mathcal{E}\) exists when the output produced by \(o_i\) is used as input by \(o_j\) during execution.

We define the critical path as the longest path in \(\mathcal{G}\) measured by execution time: \[T = \max_{p \in \text{Paths}(\mathcal{G})} \sum_{o \in p} t(o),\] where \(t(o)\) denotes the execution time of operator \(o\), and \(\text{Paths}(\mathcal{G})\) denotes all source-to-sink paths in \(\mathcal{G}\). The critical path determines the end-to-end latency: operators off the critical path do not affect wall-clock time. In contrast, the total execution cost accumulates additively across all operators: \(C = \sum_{o \in \mathcal{V}} c(o)\). Latency and cost therefore diverge.

Our goal is to learn an orchestrator that preserves task accuracy while minimizing end-to-end latency.

3.2 Orchestrator Architecture↩︎

LAMaS represents the orchestrator as a policy network over an agentic supernet—a probabilistic DAG over a fixed set of candidate operators \(\mathcal{O}\) (a formulation also adopted by [7]). The latency-aware training and credit assignment introduced below are agnostic to the specific architectural choice and apply to any orchestrator that produces a differentiable distribution over execution graphs. The orchestrator constructs \(\mathcal{G}\) by sampling operators step-by-step, with the generation probability factorized as: \[P_\theta(\mathcal{G}|x) = \prod_{\ell=1}^{L} \pi_\theta(\mathcal{V}_\ell \mid x, \mathcal{G}_{1:\ell-1}),\] where \(\mathcal{V}_\ell \subseteq \mathcal{O}\) is the operator subset selected at step \(\ell\). The network produces a query-aware operator-level policy via softmax over activation logits; we denote the resulting probability of operator \(o\) by \(s_o := p_\theta(o \mid x, \mathcal{G}_{1:\ell-1})\). Operators are sampled from this policy sequentially without replacement until their cumulative probability first exceeds a threshold \(\tau\): \[\mathcal{V}_\ell = \bigl\{o_1, \ldots, o_k\bigr\}, \quad k = \min\!\Bigl\{j : \textstyle\sum_{i=1}^{j} s_{o_i} > \tau\Bigr\},\] enabling the architecture to dynamically adjust width and depth per query.

3.3 Training-Time Constrained Optimization↩︎

Existing multi-agent orchestration methods typically combine accuracy and cost into a single weighted reward (e.g., \(R = S - \lambda_c C\)). However, as discussed in Section 1, latency and cost are structurally different objectives. Because latency is governed by the critical path, uniform penalties provide weak operator-level attribution; without an explicit accuracy floor, latency-driven optimization can degrade task performance; and a graph fixed at training time cannot leverage execution-time evidence. LAMaS addresses these via critical-path-aware credit assignment, an accuracy floor enforced by Lagrangian relaxation, and a lightweight execution-time controller. We therefore formulate MAS orchestration as a constrained optimization: \[\min_\theta \; \mathbb{E}\!\left[\lambda_t T + \lambda_c C\right], \quad \text{s.t.} \quad \mathbb{E}[S] \geq S_0,\] where \(S \in \{0,1\}\) is the task score, \(C\) is the execution cost in USD per query, \(T\) is the end-to-end wall-clock latency in seconds per query, and \(\lambda_t\), \(\lambda_c\) are fixed weights controlling the relative importance of latency and cost. Here, \(S_0\) is a fixed target accuracy floor on \(\mathbb{E}[S]\), rather than a per-instance requirement, and in practice is set to the architecture’s reference accuracy (see the appendix for sensitivity to different floors).

The accuracy floor \(S_0\) acts as a “do-no-harm” constraint: LAMaS reduces latency without falling below the reference accuracy of the underlying architecture. In our main experiments, \(S_0\) is set to the validation accuracy of the same orchestrator trained with \(\lambda_t=0\); we analyze sensitivity to \(S_0\) in the appendix. We solve the constrained problem via Lagrangian relaxation with an adaptive dual variable: \[\label{eq:lagrangian} R = \lambda_S \frac{S}{S_0} - \lambda_t T - \lambda_c C,\tag{1}\] where \(\lambda_S\) is the dual variable updated via projected gradient ascent: \[\label{eq:dual95update} \lambda_S \leftarrow \max\!\left(0,\; \lambda_S + \eta \left(1 - \frac{\bar{S}}{S_0}\right)\right),\tag{2}\] where \(\bar{S}\) denotes the batch-averaged accuracy and \(\eta\) is the dual learning rate. When accuracy drops below \(S_0\), \(\lambda_S\) automatically increases to prioritize correctness; when accuracy is satisfied, \(\lambda_S\) decreases to allow more aggressive latency reduction. Empirically, this adaptive coupling keeps accuracy fluctuating near \(S_0\) throughout training while latency contracts steadily to its converged value, supporting the “do-no-harm” interpretation of the constraint and removing the need to hand-tune a fixed accuracy–latency trade-off weight. Appendix 8.3 visualizes this behavior on GSM8K and MMLU-Pro: latency decays steadily over training while accuracy oscillates around \(S_0\) and \(\lambda_S\) adapts in response.

3.4 Critical-Path-Aware Credit Assignment↩︎

End-to-end latency is determined by the critical path. Applying the latency penalty uniformly to all operators creates a mismatch in operator-level credit assignment: operators that have little or no influence on \(T\) receive the same gradient as bottleneck operators on the critical path. We therefore use a soft bottleneck-aware weighting that preserves full penalty on the realized critical path while assigning attenuated latency credit to operators on near-critical paths.

For each operator \(o\) in the realized execution graph \(\mathcal{G}\), let \(\ell(o)\) denote the latency of the longest path passing through \(o\), and define the path-criticality weight \[\label{eq:cp95weight} w(o) \;=\; \frac{\ell(o)}{T} \;\in\; [0, 1].\tag{3}\] By construction \(w(o) = 1\) exactly when \(o\) lies on the critical path, \(w(o) \approx 1\) for operators on near-critical paths, and \(w(o) \ll 1\) for operators whose longest containing path is far below \(T\). We assign operator-level rewards as \[\label{eq:credit} R(o) \;=\; \lambda_S \frac{S}{S_0} \;-\; \lambda_t \, w(o) \, T \;-\; \lambda_c C,\tag{4}\] so each operator receives a fraction \(w(o)\) of the global latency penalty \(-\lambda_t T\): critical-path operators are penalized in full, near-critical operators receive a smoothly attenuated share, and operators with negligible \(w(o)\) get effectively no latency signal. This biases the gradient toward bottleneck operators while preserving softer latency attribution for near-critical paths; the values \(\ell(o)\), and hence \(w(o)\), are obtained alongside the critical path itself via a single forward/backward pass over \(\mathcal{G}\).

3.5 Learning Objective↩︎

The orchestrator is trained with policy gradient optimization. Let \(\xi\) denote the trajectory of operator selections; the loss is \[\label{eq:policy95loss} \mathcal{L}(\theta) = - \mathbb{E}_{\xi \sim \pi_\theta} \left[ \sum_{\ell=1}^{L} \sum_{o \in \mathcal{V}_\ell} R(o) \log p_\theta(o \mid x, \mathcal{G}_{1:\ell-1}) \right].\tag{5}\] To reduce variance, we normalize rewards using exponential moving averages (EMA). Specifically, we maintain running estimates \(\hat{\mu}\) and \(\hat{\sigma}^2\) of the mean and variance of \(R(o)\) with momentum 0.95, and normalize each reward as \((R(o) - \hat{\mu}) / \hat{\sigma}\) before computing the policy gradient; this is more stable than per-batch normalization for small batch sizes.

3.6 Inference-Time Execution Control↩︎

The orchestrator commits to the full execution graph based solely on the query \(x\), but each operator completion reveals new information—output content, emerging answer consensus, and elapsed time—unavailable at construction time. LAMaS therefore augments graph construction with an execution-time controller, implemented as a lightweight learned module. This controller can be viewed as performing an online elimination of redundant future agent interactions: at each operator completion, it evaluates whether the current partial execution should be retained or whether additional agent interactions remain worthwhile, by predicting the control advantage—how much better (or worse) the current partial execution would be compared to running all operators: \[\label{eq:control} \Delta_k = R_k - R_N,\tag{6}\] where \(R_k\) is the Lagrangian reward (Eq. 1 ) evaluated at the \(k\)-th operator completion and \(R_N\) is the reward under full execution. \(\Delta_k > 0\) means the current partial execution is preferable because it preserves accuracy while reducing latency; \(\Delta_k < 0\) means additional agent interactions remain beneficial.

The controller is a small MLP that takes execution-state features as input and predicts \(\hat{\Delta}_k\): \[\hat{\Delta}_k = \text{Controller}_\phi\!\left(\frac{n_{\text{completed}}}{n_{\text{total}}},\; \frac{\max\_\text{agree}}{n_{\text{completed}}},\; \text{Compress}(q)\right),\] where the first two features capture execution progress and answer consensus, and \(\text{Compress}(q)\) is a learned low-dimensional projection of the query embedding for difficulty awareness. We define consensus via task-specific semantic equivalence of the current operator outputs: for GSM8K and MATH, we extract the boxed answer (or, if absent, the final numeric answer) and compare exact matches; for MMLU-Pro, we extract the predicted option letter and compare exact matches; for HumanEval, we regard two outputs as agreeing if they induce the same pass/fail outcomes on the test cases available during execution (i.e., the same execution feedback used by the Test operator). The predicted advantage is converted to a selection score via: \[p(\text{select current}) = \sigma(\hat{\Delta}_k / \sigma_\Delta),\] where \(\sigma_\Delta = \text{std}(\{\Delta_k \mid \Delta_k > 0\})\) is computed from training data. At inference time, we sample the retain/eliminate decision from this Bernoulli score at each decision point.

3.6.0.1 Controller training.

The execution controller is trained after the orchestrator converges, using execution traces collected by running the frozen orchestrator on the training set. For each query, all operators are executed to completion, and \(\Delta_k\) is computed for every decision point \(k\). The controller is trained via MSE regression: \(\min_\phi \mathbb{E}[(\hat{\Delta}_k - \Delta_k)^2]\). Since \(R_k\) uses the same Lagrangian reward as the orchestrator, the controller inherits the orchestrator’s latency-aware objective under the same accuracy floor—in particular, the dual variable \(\lambda_S\) encodes how difficult accuracy is to maintain, automatically calibrating the controller’s aggressiveness.

The full training and inference procedure is summarized in Appendix 8.5 (Algorithm 5). Phase 1 trains the orchestrator with Lagrangian-constrained policy gradient and critical-path credit assignment. Phase 2 trains the execution controller on traces from the frozen orchestrator to predict the control advantage.

4 Experiments↩︎

4.1 Experimental Setup↩︎

4.1.0.1 Benchmarks & Tasks.

We evaluate our method on four benchmarks spanning three task categories. For HumanEval, GSM8K, and MATH, we follow the same training and evaluation splits as MaAS [7]; for MMLU-Pro [17], we construct our own stratified train/test split from the official test set. Detailed split statistics are provided in Appendix 7.3. For code generation, we use HumanEval, which measures functional correctness of Python programs generated from natural language descriptions. For mathematical reasoning, we use GSM8K and MATH, which consist of grade-school and competition-level math problems requiring multi-step reasoning. For knowledge reasoning, we use MMLU-Pro, which covers diverse professional-level questions requiring multi-step reasoning.

4.1.0.2 Baselines.

We compare against two categories of baselines: (i) non-MAS prompting strategies—Generate (direct single-step answer), CoT [19], and SC [20]; and (ii) learned MAS orchestrators—GDesigner [9], AgentDropout [8], and MaAS [7]. Detailed per-baseline configurations are provided in Appendix 7.4.

4.1.0.3 Evaluation Metrics.

We evaluate all methods using three metrics: task performance, API cost, and latency. For task performance, we report pass@1 on HumanEval, and accuracy on GSM8K, MATH, and MMLU-Pro. API cost is measured as the average per-query monetary cost (in units of \(\times 10^{-4}\) USD) incurred by LLM API calls. For latency, we directly measure the end-to-end wall-clock execution time, reported as the average latency per query (in seconds). All methods in Tables 1–3 that use API-served backbones are evaluated under the same API provider and execution runtime, without response caching, and latency is averaged over 3 independent runs. The end-to-end latency is determined by the critical execution path as defined in Section 3.1. We also report CP Tokens, the average number of output tokens generated along the critical execution path, as a complementary structural indicator of critical-path workload.

4.1.0.4 Implementation Details.

We use the closed-source LLM gpt-4o-mini-0718 [21]. The latency penalty is set to \(\lambda_t=0.005\), the activation threshold to \(\tau=0.3\), and the supernet has \(L=4\) layers; we report sensitivity to each of these in the appendix. The target accuracy floor \(S_0\) is set to the validation accuracy of the same orchestrator trained without latency optimization (i.e., \(\lambda_t=0\)), so the constraint measures whether latency reduction is achieved while maintaining the reference accuracy level of the underlying architecture. Remaining training hyperparameters are listed in Appendix 7.2. All results are averaged over 3 independent runs.

4.2 Result Analysis↩︎

We analyze the results from three perspectives: evaluated learning-based MAS baselines, the full set of baselines, and component-wise ablations.

4.2.0.1 Comparison with evaluated learning-based MAS baselines.

Table 1 shows that LAMaS consistently reduces end-to-end latency by 55.6–75.6% relative to the strongest evaluated learning-based MAS baselines while maintaining competitive or better accuracy. The reduction co-occurs with substantially lower CP Tokens (e.g., \(622\) vs.\(2501\) on GSM8K), indicating that the orchestrator produces graphs with shorter critical paths under the latency objective; the inference-time controller further trims execution once a confident answer emerges.

4.2.0.2 Comparison with baselines.

Non-MAS methods (Generate, CoT, SC) remain faster because of their simplicity but consistently underperform in task accuracy, especially on harder benchmarks. Among MAS methods, GDesigner and AgentDropout incur substantially higher latency without corresponding accuracy gains, whereas LAMaS achieves the lowest latency across all four benchmarks while maintaining comparable accuracy. Across MAS methods and benchmarks, CP Tokens are strongly correlated with measured wall-clock latency (Appendix 8.1), providing complementary evidence that LAMaS reduces critical-path workload together with end-to-end latency.

4.3 Ablation Study↩︎

We study four variants of LAMaS: removing CP credit assignment, removing the inference-time controller, removing the latency objective, and a naive “add latency to the reward” baseline. w/o CP Credit forces the latency penalty to apply uniformly to all operators rather than weighting it by path criticality; w/o controller removes the execution controller entirely and relies solely on training-time optimization; w/o latency obj. sets \(\lambda_t=0\), training the orchestrator without any latency objective; naive lat. only keeps only a bare uniform latency term in the training objective, with no \(S_0\) accuracy floor, no CP-aware credit assignment, and no inference controller—the simplest “add latency to the reward” baseline.

Table 2 shows consistent trends across all four benchmarks. Removing the controller preserves accuracy within 0.38 pp but increases latency by 16.5–21.1% and cost by 16.0–25.2%, confirming the importance of inference-time execution control. Removing CP credit assignment also degrades all three metrics, supporting path-criticality-weighted latency attribution rather than a uniform penalty over all operators. Removing the latency objective entirely (\(\lambda_t{=}0\)) leaves accuracy essentially unchanged (within \(\pm 0.25\) pp of LAMaS) but inflates latency by 24–70% and cost by 19–35%, confirming that the constrained latency objective reshapes the execution graph for efficiency while maintaining the reference accuracy level of the underlying architecture. Finally, the naive lat. only variant drops accuracy by 1.30–5.34 pp relative to LAMaS while yielding only 2–11% latency savings over \(\lambda_t{=}0\) and no cost reduction, showing that simply adding a latency term provides only limited gains. Taken together, these ablations show that LAMaS combines path-selective latency pressure with an explicit accuracy floor and execution-time control rather than simply shrinking computation.

4.4 Transferability and Generality of LAMaS Mechanisms↩︎

The full LAMaS pipeline—the training-time graph optimization, the critical-path credit assignment, and the inference-time execution controller—is not tied to a specific orchestrator architecture. To verify its broader applicability, we integrate the entire pipeline into two other learning-based MAS methods, GDesigner [9] and AgentDropout [8], without redesigning their original orchestration frameworks.

Across all four benchmarks and both architectures, integrating the full LAMaS pipeline consistently reduces latency by 27–39% while preserving or slightly improving accuracy within typical 3-run noise. These results confirm that latency-aware graph optimization together with inference-time execution control transfers effectively to other learning-based MAS architectures. The reductions are smaller than in the LAMaS-native setting (Table 1), consistent with the fact that GDesigner and AgentDropout retain their original orchestration policies: the LAMaS pipeline contributes the latency-aware credit signal and inference-time control rather than replacing their graph construction. Together with Appendix 10, this suggests that the LAMaS pipeline remains effective beyond a single orchestration architecture and extends to the additional backbone and serving configurations we evaluate. Appendix 8.4 further shows that the orchestrator can still reasonably select an operator not exposed during training.

5 Conclusion↩︎

This paper addresses a key limitation of existing multi-agent orchestration methods: optimizing accuracy and cost alone does not reliably control execution latency. We propose LAMaS, which treats latency as an explicit optimization objective at two levels: training-time graph optimization with critical-path credit assignment, and inference-time adaptive execution control via a lightweight learned controller. Experiments across four benchmarks demonstrate that LAMaS achieves the best latency among evaluated learning-based MAS baselines, reducing end-to-end latency by over 50% while maintaining competitive or better accuracy, and the full pipeline transfers to other MAS architectures with consistent latency reductions.

6 Limitations↩︎

LAMaS reduces orchestration latency; however, it does not mitigate broader risks inherited from the underlying LLMs and associated tools, including unsafe outputs, hallucinations, and social biases.

7 Experimental Setup Details↩︎

This section collects additional implementation and dataset details used for reproducibility.

7.1 Operator Set↩︎

Each operator corresponds to a predefined reasoning or execution primitive used to construct execution graphs. We briefly summarize their functionality below for completeness.

• Generate. A basic generator that directly produces text or code without additional reasoning or post-processing. It invokes the LLM once and is primarily used for simple generation tasks.

• GenerateCoT. A chain-of-thought generator that prompts the LLM to perform step-by-step reasoning. For mathematical tasks (e.g., MATH, GSM8K), it includes explicit reasoning exemplars, while for code tasks (e.g., HumanEval), it uses lightweight reasoning prompts. This operator invokes the LLM once.

• MultiGenerateCoT. A diversity-oriented CoT generator that produces multiple candidate solutions in parallel. It generates three independent chain-of-thought solutions, yielding a set of candidate responses for downstream aggregation.

• ScEnsemble. A self-consistency ensemble operator that selects the most consistent answer from multiple candidate solutions. All candidates are formatted as discrete options, and the LLM is prompted to select the most consistent one, following the self-consistency principle.

• SelfRefine. A refinement operator that analyzes an existing solution to identify errors or suboptimal reasoning and generates an improved version. This operator invokes the LLM once.

7.1.0.1 Task-Specific Operators.

We also employ task-specific operators for different benchmarks.

• CustomCodeGenerate (HumanEval). A lightweight code generator that produces candidate code solutions without execution or testing.

• Test (HumanEval). A test-driven refinement operator that executes generated code and iteratively improves it based on failure feedback. Upon failure, the operator generates a revised solution using reflective prompts and retries up to three times.

• Programmer (MATH/GSM8K). A code execution operator that generates Python programs, executes them in an isolated environment, and iteratively refines the code based on execution feedback.

7.2 Additional Implementation Details↩︎

We list the remaining training hyperparameters not detailed in Section 4.1. The cost weight is \(\lambda_c=3.0\), the dual learning rate is \(\eta=0.01\), the batch size is \(4\), and the orchestrator is trained for \(4\) repetitions over the training set. These values follow the supernet implementation conventions of MaAS [7].

Queries are encoded by a frozen all-MiniLM-L6-v2 SentenceTransformer; the resulting embedding is shared between the orchestrator’s policy network (Section 3.2) and the controller’s \(\text{Compress}(\cdot)\) projection (Section 3.6), and is not finetuned during training.

In the main experiments, we use gpt-4o-mini-0718 via the OpenAI API with temperature set to 1. Appendix 10 instead evaluates qwen3.5-flash (closed-source) via OpenRouter with Alibaba Cloud Int. selected as the provider, and qwen3.5-9b (open-weight) served locally through vLLM; the same temperature setting is used there as well.

Training the orchestrator and execution controller requires modest local compute but does not finetune the underlying LLM backbone. All training runs were executed on a Slurm cluster using a single NVIDIA H100 80GB GPU per run. The local qwen3.5-9b evaluation uses vLLM served on two NVIDIA B200 GPUs.

7.3 Dataset Split Statistics↩︎

We evaluate on four publicly available benchmarks: HumanEval [15], GSM8K [14], MATH [16], and MMLU-Pro [17]. Following common practice in workflow-automation work [7], [10], each benchmark is partitioned into training and test sets with a train:test ratio of 1:4. For MATH, we use a 605-problem subset of level-5 problems spanning four representative categories: Combinatorics & Probability, Number Theory, Pre-algebra, and Pre-calculus. For MMLU-Pro, we construct a stratified split from the official test set (seed 42), sampling proportionally per category with no overlap between train and test. Statistics are summarized in Table 4.

7.4 Baseline Setups↩︎

We provide the configurations for each baseline method below.

1. Generate. A single-pass direct-answer baseline that prompts the LLM once with the query and uses its output as the final answer, with no chain-of-thought scaffolding or post-processing.

2. CoT. Chain-of-Thought prompting [19] elicits step-by-step reasoning before the final answer; we use a standard zero-shot CoT prompt template.

3. SC. Self-Consistency [20]: to enhance robustness, we aggregate five CoT-generated solutions through an ensemble step over the candidate answers.

4. GDesigner. We use the official implementation of [9], which learns a graph neural network over operator embeddings to construct communication topologies. We retain the original training procedure and operator set defined in the released codebase, replacing only the LLM backbone with gpt-4o-mini-0718 for fair comparison.

5. AgentDropout. We follow the released implementation of [8], which dynamically prunes redundant agents and communication edges during execution. The dropout schedule and per-agent role assignments use the defaults from the official codebase.

6. MaAS. We use the agentic-supernet implementation of [7], training the orchestrator with the same supernet depth (\(L=4\)), operator set, and policy-gradient procedure as released. The original cost-only reward is used unchanged so that MaAS represents the cost-aware—but not latency-aware—learning baseline.

All MAS baselines are trained and evaluated under the same train/test partition (Appendix 7.3), the same backbone LLM (gpt-4o-mini-0718), and the same per-query latency/cost measurement protocol described in Section 4.1.

8 Additional Supporting Analyses↩︎

This section provides supplementary analyses supporting the main-paper interpretation of LAMaS.

8.1 Critical-Path Tokens as a Latency Proxy↩︎

The critical-path-aware credit assignment in Section 3.4 is motivated by the expectation that CP Tokens should co-vary with end-to-end wall-clock latency. To verify this empirically, we form one \((\text{CP Tokens}, \text{latency})\) pair for each MAS-method/benchmark cell in Table 1 and compute the pooled correlation across all 4 MAS methods \(\times\) 4 benchmarks (\(n=16\)). Both Pearson and Spearman correlations indicate a strong positive association, providing complementary evidence that reductions in CP Tokens align with reductions in end-to-end latency.

8.2 Comparison with Oracle Controller↩︎

To probe how close the learned execution controller is to an optimal stopping rule, we compare it against an oracle that has access to the true control advantage \(\Delta_k = R_k - R_N\) at each decision point and stops iff \(\Delta_k > 0\). We evaluate on HumanEval and MMLU-Pro from two complementary angles: decision-level agreement with the oracle (Table 6), and end-to-end performance when the learned controller is replaced by either the oracle or no controller (Table 7).

8.2.0.1 Decision-level agreement.

Table 6 reports decision accuracy together with precision, recall, and F1 for the positive (stop) class, treating the oracle’s \(\Delta_k > 0\) rule as ground truth. Across both benchmarks, the learned controller agrees with oracle decisions in 70.8–73.5% of cases. Precision exceeds recall on both benchmarks, indicating that the learned controller is conservative: it tends to continue execution when the oracle’s signal is borderline rather than making an over-aggressive elimination decision.

8.2.0.2 End-to-end performance.

Table 7 compares three controller settings: no controller, the learned controller, and the oracle. The learned controller closes most of the gap between no-controller execution and the oracle: on HumanEval it trails the oracle by 2.16 s in latency and 0.25 pp in accuracy, and on MMLU-Pro by 1.74 s and 0.46 pp. This indicates that the learned controller approaches oracle-level execution control despite operating only on the partial-execution features available at runtime.

8.3 Training Dynamics↩︎

Figure 3 shows the per-step batch-averaged accuracy \(\bar{S}_t\), end-to-end latency \(\bar{T}_t\), and dual variable \(\lambda_S\) over training, on GSM8K (264 optimizer steps) and MMLU-Pro (125 steps). Curves are smoothed with a trailing window of size 5 (size 3 for \(\lambda_S\), to preserve its responsiveness to per-step accuracy fluctuations).

Three trends are visible. (i) Latency decays monotonically from a high initial value to the LAMaS configuration reported in Table 2, confirming that latency is the actively optimized quantity. (ii) Accuracy oscillates around the floor \(S_0\) without a clear trend, since \(S_0\) is a constraint rather than an objective. (iii) The dual variable \(\lambda_S\) performs a small random walk near \(1.0\) in response to the per-step violation \(1-\bar{S}_t/S_0\). On the harder MMLU-Pro task, \(\lambda_S\) shows a more pronounced early rise (the constraint is tighter when accuracy is harder to maintain), then partially relaxes; on the easier GSM8K task, \(\lambda_S\) stays close to \(1.0\) throughout. These dynamics match the intended behavior of the dual update in Eq. 2 .

8.4 Compatibility with Unseen Operators↩︎

To probe whether the learned policy generalizes beyond the fixed training-time operator set, we insert an unseen operator (Debate) at inference time on HumanEval and inspect the orchestrator’s average selection probabilities. Figure 4 reports the average probability mass over the seven non-halt operators shown. The unseen Debate operator receives 14.8% probability mass, comparable to seen operators such as Generate (14.9%), ScEnsemble (15.1%), and Test (15.5%). This suggests that the learned policy can still reasonably select an unseen operator during architecture sampling, indicating some inductive flexibility beyond the exact operator set seen during training.

8.5 Full Training and Inference Procedure↩︎

9 Sensitivity Analyses↩︎

This section reports the sensitivity of LAMaS to the main hyperparameters that control latency pressure, graph structure, and the accuracy floor.

9.1 Parameter Sensitivity Analysis↩︎

We analyze the sensitivity of LAMaS to four key hyperparameters: the latency penalty weight \(\lambda_t\), the activation threshold \(\tau\), the number of supernet layers \(L\), and the accuracy floor \(S_0\). We report results on HumanEval and MMLU-Pro, with the default configuration (\(\lambda_t{=}0.005\), \(\tau{=}0.3\), \(L{=}4\)) marked by \(\blacklozenge\).

9.1.0.1 Latency weight \(\lambda_t\).

Table 8 shows that increasing \(\lambda_t\) monotonically reduces latency, while accuracy varies only mildly across the sweep. On HumanEval, raising \(\lambda_t\) from 0 to 0.05 reduces latency from 35.62s to 11.29s with at most 2.0% accuracy change; the trend is consistent on MMLU-Pro. The \(\lambda_t{=}0\) setting (no latency objective during training) leaves accuracy near the LAMaS level but yields the largest latency, complementing the corresponding row in the ablation study (Table 2). Overall, \(\lambda_t\) provides smooth and predictable control over latency while keeping accuracy broadly stable.

9.1.0.2 Activation threshold \(\tau\).

Table 9 reveals that the threshold controls the width of the execution graph. A lower threshold (\(\tau{=}0.1\)) produces lean graphs with fewer operators per step, yielding the lowest latency but reduced accuracy. A higher threshold (\(\tau{=}0.4\)) activates more operators, improving accuracy through greater exploration together with increased latency. The default \(\tau{=}0.3\) provides a balanced setting across both benchmarks.

9.1.0.3 Number of layers \(L\).

Table 10 shows that increasing the number of supernet layers provides greater reasoning depth. On HumanEval, accuracy improves from 94.15% (\(L{=}2\)) to 95.93% (\(L{=}8\)), but latency increases from 12.85s to 25.54s due to the deeper critical path. The marginal accuracy gain diminishes beyond \(L{=}4\), while latency continues to grow, justifying the default choice of \(L{=}4\).

9.1.0.4 Accuracy floor \(S_0\).

Unlike \(\lambda_t\), \(\tau\), and \(L\), which control the latency penalty and graph structure, the accuracy floor \(S_0\) sets the target accuracy level used during training. Table 11 reports results across \(S_0 \in \{0.95, 1.00, 1.02, 1.05\} \cdot S_{\text{ref}}\), where \(S_{\text{ref}}\) denotes the orchestrator’s reference accuracy and the default deployment (\(S_0 = S_{\text{ref}}\)) is marked by \(\blacklozenge\). Tightening \(S_0\) towards \(S_{\text{ref}}\) enforces a stricter no-regression guarantee at the cost of more execution, while relaxing \(S_0\) allows LAMaS to push more aggressively for latency reduction with a small accuracy concession. The trend is monotonic on both benchmarks: on HumanEval, sweeping \(S_0\) from \(0.95\cdot S_{\text{ref}}\) to \(1.05\cdot S_{\text{ref}}\) moves accuracy from 94.66% to 96.18% while latency rises from 17.85s to 23.54s; the same direction holds on MMLU-Pro (65.40%\(\to\)​67.13%, 12.60s\(\to\)​16.51s). This confirms that varying \(S_0\) during training provides a smooth way to control how aggressively latency is reduced while maintaining different target accuracy floors.

10 Generalizability Across Backbones and Serving Setups↩︎

To assess whether LAMaS’s latency advantage transfers across different LLM backbones and serving setups, we replicate the comparison on two additional configurations: the closed-source flash variant qwen3.5-flash served through OpenRouter, and the open-weight qwen3.5-9b served locally with vLLM. Both are evaluated on HumanEval and MMLU-Pro against the strongest learning-based MAS baseline (MaAS) and LAMaS. As shown in Table 12, LAMaS reduces latency by about 60% on HumanEval and about 43% on MMLU-Pro across the two settings, while matching or slightly exceeding MaAS in accuracy. This confirms that LAMaS’s mechanisms transfer across distinct backbones and serving setups.

References↩︎