PaperlayerView exact revision on arXiv

Source-linked AI summary

DEALS: Decentralized Expertise-Aware Load Serving for Multi-Agent LLM Systems

Jingjuan Huang, Wenbin Wang, Yanchuan Yin, Alvaro Velasquez, Jia Liu

arXiv:2609.33768v1cs.LGcs.AIcs.MA

TL;DR

Concurrent heterogeneous tasks can strain MAS coordination, while centralized or costly routing approaches limit scalable task allocation. DEALS uses decentralized, expertise-aware routing and concurrent execution; experiments report competitive accuracy and higher throughput than state-of-the-art baselines.

  • Problem

    Serving concurrent heterogeneous tasks can imbalance workloads, while centralized coordination may limit scalability and trained routers or LLM-based selection add computational and coordination costs.

    Source: §1 · p. 2

  • Method

    DEALS routes tasks using local backlog and neighbor success-rate differences, coordinating task decomposition and concurrent execution without a central controller or separately trained router.

    Source: §1 · p. 2, §3.3 · p. 5

  • Results

    DEALS achieves the highest average accuracy among compared methods and 4.7× to 22.7× of baseline-method throughput across homogeneous and heterogeneous agent pools.

    Source: §1 · p. 2

  • Takeaways & Limitations

    Experiments indicate that incorporating quality information is particularly useful in heterogeneous pools, and DEALS achieves competitive accuracy with higher workload throughput than state-of-the-art baselines.

    Source: §5 · p. 9

    Evaluation covers complete graphs with three, five, and seven agents across three LLM families; other topologies, more challenging benchmarks, and broader LLM families remain future work.

    Source: B LIMITATIONS · p. 14

Abstract

from arXiv · show

Multi-agent systems (MAS) have recently emerged as an effective approach for coordinating large language model (LLM)-based agents to solve complex tasks through structured interactions. In practice, MASs often handle a stream of heterogeneous and complex tasks, requiring agents to decompose each task and then self-organize and self-evolve to adapt to incoming tasks while sharing execution resources. However, most early approaches to MASs rely on centralized controllers or fixed coordination patterns, which can limit scalability or adaptability. In contrast, existing decentralized and dynamic MASs often require training dedicated routers or invoking LLMs for agent selection, resulting in substantial computational costs and coordination overhead. To address these challenges and enable efficient task-level self-organization and self-evolution for task- and workload-level collaboration, we propose Decentralized Expertise-Aware Load Serving (DEALS), a decentralized and low-complexity framework that enables agents to self-organize and dynamically route concurrent tasks for processing. Specifically, each agent maintains local queues of incoming tasks, and its router decides whether to process a task locally or forward it to a neighbor based on differences in backlog and success rate. Meanwhile, executors process independent tasks concurrently within and across agents, and partially solved tasks can be resumed by other agents. Experiments show that DEALS not only improves performance along multiple dimensions (e.g., answer accuracy and task throughput) in both homogeneous and heterogeneous agent pools, but also balances agent expertise and workload in a self-organized manner, enabling effective decentralized coordination.

1 INTRODUCTION

DEALS addresses the challenge of serving heterogeneous concurrent tasks without centralized coordination or costly routing. Agents route tasks using local backlog and task-specific success-rate differences, while coordinating task decomposition and concurrent execution.

1 INTRODUCTION

  • Earlier MAS work used centralized controllers or fixed patterns, while later collaboration designs remained static or focused on individual tasks; reinforcement learning could bring training costs and stability issues.The authors identify decentralized routing and private memories as more recent self-organization approaches.Source: §1 · p. 1
  • Concurrent heterogeneous workloads can imbalance agent workloads, degrading throughput and increasing latency, while centralized coordination can become a scalability bottleneck and single point of failure.Other routing approaches may also require separately trained routers or LLM inference for agent selection, adding training, inference, and coordination costs.Source: §1 · p. 2
  • The paper asks whether a self-organizing, self-evolving MAS can use low-complexity decentralized routing to solve concurrent tasks with high accuracy and low latency.MASs coordinate multiple LLM agents through structured interactions to solve complex tasks.Source: §1 · pp. 1–2
  • The framework coordinates local routing, task decomposition, and concurrent execution to support self-organized collaboration within tasks and resource allocation across the workload.Independent tasks can execute concurrently within and across agents.Source: §1 · p. 2
  • DEALS routes tasks locally or to neighbors using queue backlog and task-specific success-rate differences, without additional LLM calls or a separately trained routing model.Its local decisions use local state and direct-neighbor information.Source: §1 · p. 2
  • DEALS achieves the highest average accuracy among compared methods and 4.7× to 22.7× of baseline-method throughput.The evaluation covers homogeneous and heterogeneous agent pools.Source: §1 · p. 2

2 RELATED WORK

Prior MAS research has addressed collaboration structures, routing, and decentralized coordination, but the related work distinguishes these approaches from DEALS by their focus, information requirements, or allocation mechanism.

LLM-based Multi-Agent Systems

  • Prior MAS approaches structure collaboration through roles, workflows, debate, voting, or optimized computation graphs and workflows; debate and voting raise per-task cost (Guo et al., 2024; Qi et al., 2026; Li et al., 2023; Wu et al., 2023; Hong et al., 2024; Du et al., 2023; Li et al., 2024; Zhuge et al., 2024; Zhang et al., 2025c).AgentPrune reduces communication, while DyLAN and AgentVerse address team composition (Zhang et al., 2025b; Liu et al., 2023; Chen et al., 2024).Source: §2 · pp. 2–3

Centralized Routing for Task Allocation

Decentralized Coordination and Workload Allocation

  • Decentralized coordination has used trajectory memories, bidding, and queueing or backpressure; DEALS instead combines success-rate and backlog differences for local routing without extra LLM calls (Yang et al., 2026; Hao et al., 2026; Bhatt et al., 2025; Liu et al., 2026; Dai et al., 2025; Zhang et al., 2026).Some queueing-based guarantees rely on assumptions that simplify real-world system dynamics.Source: §2 · p. 3

3 THE PROPOSED DEALS FRAMEWORK

DEALS models a multi-agent system in which agents route typed tasks across a fixed directed graph while executing tasks locally. Its decentralized design combines workload and task-specific success-rate information for routing, supports concurrent execution and task splitting, and updates learned information during warm-up before testing.

3.1 PROBLEM STATEMENT AND SYSTEM MODEL

  • Each agent has FIFO queues by task type, a router, and an executor that can process up to its capacity concurrently.Tasks arrive at agents over time; execution can return a final answer or unfinished work for further processing.Source: §3.1 · p. 3

3.2 DECENTRALIZED ROUTING DESIGN IN DEALS

  • Routing combines backlog and task-specific success-rate differentials, using local state and direct-neighbor information to balance congestion against capability.The router forwards to a neighbor when its best score exceeds margin m; otherwise it retains the task locally, subject to hop and split limits.Source: §3.2 · pp. 3–5

3.3 THE EXECUTOR DESIGN IN DEALS

  • Agents use private memories of successful warm-up trajectories as demonstrations, while concurrent executor slots handle independent tasks across and within agents.An execution step can complete a task or split off a subproblem and return unfinished work to the local queue.Source: §3.3 · p. 5

3.4 OVERALL OPERATIONS OF DEALS

  • During warm-up, agents that execute or split tasks update success and failure counts and add their own successful trajectories to private memory; testing freezes these estimates and memories while backlogs continue changing.Dispatch admits a task from the longest typed queue when an execution slot is available, and admitted tasks progress in separate concurrent calls.Source: §3.2 · p. 4, §3.4 · pp. 5–6

4 EXPERIMENTAL RESULTS

The experiments compare DEALS with baselines on accuracy and throughput, then examine quality-weight routing, self-organized task allocation, and larger agent pools. They evaluate three benchmarks and homogeneous and heterogeneous configurations.

4.1 EXPERIMENTAL SETUP

  • The evaluation uses MATH, BBH, and MMLU-Pro with homogeneous and mixed-model pools, including five- and seven-agent variants.The larger heterogeneous pools combine Qwen, Mistral, and Llama agents.Source: §4.1 · p. 7

4.2 ACCURACY AND THROUGHPUT ANALYSIS

  • DEALS leads average accuracy in all four configurations and reaches 66.52% versus AgentNet's 57.76% in heterogeneous pools; throughput is 4.7×–22.7× AgentNet.Figure 3 compares completed tasks per test wall-clock minute.Source: §4.2 · p. 7, Figure 3 · p. 8

4.3 GUIDING SELF-ORGANIZATION THROUGH LOCAL ROUTING

  • At V = 0, final answers are distributed approximately evenly; at V = 80, Qwen produces about 99% on MATH and 64% on MMLU-Pro.These allocations arise from local routing rather than predefined task assignments.Source: §4.3 · p. 8
  • In heterogeneous pools, raising V from 0 to 80 improves accuracy on every dataset, including MATH from 44.29% to 73.57%; homogeneous accuracy varies less.Figure 4 compares final-answer share by agent and accuracy across pools and quality weights.Source: §4.3 · p. 8, Figure 4 · p. 9

4.4 EXPERTISE-AWARE ROUTING AT LARGER POOL SIZES

  • With V = 80, M5 and M7 reach 72.86% and 67.86% MATH accuracy, respectively, above the strongest single agent's 66.43%; backlog-only routing falls below it.Accuracy drops from M5 to M7 as M7 adds two weaker Llama agents, while homogeneous pools change little across V.Source: §4.4 · p. 9

5 CONCLUSION

DEALS coordinates concurrent task workloads using local backlog and success-rate differences. The experiments find quality information particularly useful in heterogeneous pools, alongside competitive accuracy and higher throughput than baselines.

5 CONCLUSION

  • The framework considers execution capacity together with task-solving capability when serving concurrent workloads.Local backlog and success-rate differentials guide routing while independent tasks proceed asynchronously.Source: §5 · p. 9
  • Incorporating quality information is particularly useful in heterogeneous pools.Source: §5 · p. 9
  • The experiments report competitive accuracy and higher workload throughput than state-of-the-art baselines.Source: §5 · p. 9

A IMPLEMENTATION DETAILS

The appendix specifies DEALS’s experimental serving, concurrency, routing, trajectory-retrieval, and warm-up/test settings; Table 3 lists implementation parameters.

A IMPLEMENTATION DETAILS

  • Each agent serves its backbone model through a private vLLM replica on a dedicated GPU, while a separate GPU hosts the retrieval encoder.Model calls use temperature 0, request seed 1, and a maximum of 2048 generated tokens.Source: A IMPLEMENTATION DETAILS · p. 13
  • Each agent uses nine worker slots; when one frees, the longest typed queue supplies the next task, with ties broken by task-type order.A task holds a slot while being routed or executed.Source: A IMPLEMENTATION DETAILS · p. 13
  • Routing evaluates every eligible direct neighbor except the task’s previous agent and forwards only if the best score exceeds 1; after three hops, the holder executes it.Ties go to the neighbor with the smallest index.Source: A IMPLEMENTATION DETAILS · p. 13
  • Trajectory relevance combines cosine similarity with an execution-time factor weighted by 0.2.Recorded time covers local trajectory execution, excluding action selection, preliminary-thought generation, and completion checks.Source: A IMPLEMENTATION DETAILS · p. 13
  • Retrieval returns up to three successful trajectories scoring at least 0.7 from each agent’s private memory, which holds at most 40 trajectories.If fewer than three qualify, all qualifying trajectories are returned.Source: A IMPLEMENTATION DETAILS · p. 13
  • Ingress probabilities are drawn per task type from a Dirichlet distribution with α = 0.7 and held fixed within each phase; testing freezes memories and success rates.Warm-up and testing use different ingress seeds, and warm-up verifies each finished task immediately.Source: A IMPLEMENTATION DETAILS · p. 13

B LIMITATIONS

The evaluation is scoped to complete graphs with three, five, or seven agents and three LLM families; the authors identify broader settings for future study.

B LIMITATIONS

  • Evaluation covers complete graphs, with other communication topologies such as chain, ring, and sparse graphs left for future study.The stated evaluation setting is complete graphs with three, five, and seven agents across three LLM families.Source: B LIMITATIONS · p. 14
  • The evaluation spans three LLM families; the authors identify a broader range of families as future work.Source: B LIMITATIONS · p. 14
  • The authors also identify more challenging benchmarks as a direction for future evaluation.Source: B LIMITATIONS · p. 14

C.1 QUALITY-WEIGHT SENSITIVITY AND FINAL-TASK ALLOCATION

This section describes accuracy sensitivity to the quality weight and per-agent completion counts for selected heterogeneous runs; Tables 4 and 5 preserve Figure 4’s numerical values.

C.1 QUALITY-WEIGHT SENSITIVITY AND FINAL-TASK ALLOCATION

  • Tables 4 and 5 preserve the exact numerical values used in Figure 4.Source: §C.1 · p. 14, Table 4 · p. 14, Table 5 · p. 14
  • Table 4 reports accuracy sensitivity to quality weight V and defines spread as the difference between the highest and lowest reported accuracy values.Bold marks the best result within each row.Source: Table 4 · p. 14
  • Table 5 reports each model-backed agent’s completed test-task count for the selected V = 0 and V = 80 runs from Table 4.Each count identifies the agent responsible for final task completion.Source: Table 5 · p. 14

D CASE STUDY

A BBH movie-recommendation example traces a task through one split and one forward: one agent describes reference films, and another completes the comparison and returns the reference answer.

D CASE STUDY

  • The example uses three Qwen2.5-7B-Instruct agents and V = 20, with one split followed by one forward and execution at a second agent.The task enters agent a2.Source: D CASE STUDY · p. 15
  • Agent a2 summarizes the reference films’ genres and themes, but the completion check marks the task incomplete because candidates remain un-compared.The partial output describes films rather than choosing a final answer.Source: D CASE STUDY · p. 15
  • The remaining work is forwarded to a3 with the partial descriptions; a3 compares candidates using those descriptions and retrieved demonstrations, selects The Fugitive, and returns the reference answer (A).Source: D CASE STUDY · p. 15
Loading 2609.33768v1…