Research map / Multi-agent systems and games / LLM agents

Optimize Once, Execute Fast: Latency-Aware Multi-Agent Workflow Learning for Recurrent Queries

NeurIPS 2026 · Multi-agent systems and games › LLM agents · approach: LLM multi-agent decision making

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes LAWA, a latency-aware framework that learns multi-agent workflows by makespan-guided beam search over theoretically grounded graph edits (parallel rewiring, node removal), guided by a learned GNN evaluator and a DPO-trained graph generator.

Problem

LLM-based multi-agent workflows are usually optimized only for task accuracy, ignoring end-to-end execution latency (makespan), which accumulates when workflows are reused for recurrent queries.

Approach

Defines latency-aware workflow generation and uses critical-path-guided graph edits (parallel rewiring and node removal) with proven reachability preservation and non-increasing makespan, combined with a learned graph evaluator that filters edits to keep task performance and a graph generator that initializes chain workflows from scratch.

Key results

• LAWA achieves the lowest wall-clock makespan on six of seven benchmarks, e.g., 6.18s on SVAMP vs 8.12s for LAMaS, and best average makespan rank (1.14).
• LAWA attains best average accuracy rank (1.79), e.g., 83.46% on AQuA and 77.77% on MMLU, while being competitive on other benchmarks.
• As a plug-in, LAWA reduces makespan of baseline workflows (e.g., -8.6s on MMLU from Random Chain) with non-negative mean accuracy changes in reported runs.

Surprising findings

• Random Chain initializations, when optimized by LAWA, show large makespan reductions with accuracy gains on several benchmarks, suggesting the chain structure is not a limiting starting point.
• Removing DPO training of the graph generator hurts accuracy more than removing SFT on the reported benchmarks.

Limitations

• Makespan model assumes full parallelism; limited-executor behavior only reported in an appendix table.
• Evaluator-based filtering relies on performance predictions from graphs built on a small training subset; perturbation robustness only tested up to alpha=0.2.
• Reported accuracy differences are often within standard deviations, so the claim of no degradation is statistical rather than strict.

Experimental setup

Datasets: MBPP HumanEval GSM8K MATH500 SVAMP AQuA MMLU

Benchmarks: MBPP HumanEval AQuA GSM8K MATH500 SVAMP MMLU

Metrics: wall-clock makespan (s) accuracy average rank total token consumption

Baselines: DyLAN G-Designer AgentDropout AgentPrune BiRouter AFlow LAMaS Random Chain Random Graph 3-Round Discussion

Builds on: DPO AFlow G-Designer AgentPrune LAMaS

Closest papers by meaning

• Flow: Modularized Agentic Workflow Automation (ICLR 2025 · similarity 0.90)
• GraphFlow: A Graph-Based Workflow Management for Efficient LLM-Agent Serving (ICML 2026 · similarity 0.90)
• Benchmarking Agentic Workflow Generation (ICLR 2025 · similarity 0.89)
• WorkflowLLM: Enhancing Workflow Orchestration Capability of Large Language Models (ICLR 2025 · similarity 0.89)
• AFlow: Automating Agentic Workflow Generation (ICLR 2025 · similarity 0.88)
• KVFlow: Efficient Prefix Caching for Accelerating LLM-Based Multi-Agent Workflows (NeurIPS 2025 · similarity 0.88)