PaperlayerView exact revision on arXiv

Source-linked AI summary

DynTaskMAS: A Dynamic Task Graph-driven Framework for Asynchronous and Parallel LLM-based Multi-Agent Systems

Junwei Yu, Yepeng Ding, Hiroyuki Sato

arXiv:2503.07675v2cs.MAcs.AIcs.DC

TL;DR

LLM-based multi-agent systems often lack sophisticated mechanisms for parallel execution and dynamic task management, while complex tasks strain decomposition, resource allocation, and context sharing. DynTaskMAS combines dynamic task-graph decomposition, asynchronous parallel execution, semantic-aware context management, and adaptive workflow management. DynTaskMAS reduces execution time by 21-33%, increases resource utilization by 35.4%, and achieves near-linear throughput scaling up to 16 concurrent agents.

  • Problem

    LLM-based multi-agent systems often lack sophisticated mechanisms for parallel execution and dynamic task management, while complex tasks strain decomposition, resource allocation, and context sharing.

    Source: §I · p. 1, A. Planning with LLMs · p. 2

  • Method

    DynTaskMAS combines dynamic task-graph decomposition, asynchronous parallel execution, semantic-aware context management, and adaptive workflow management.

    Source: §I · p. 1, §III · p. 3, A. Dynamic Task Graph Generator · p. 3

  • Results

    DynTaskMAS reduces execution time by 21-33%, increases resource utilization by 35.4%, and achieves near-linear throughput scaling up to 16 concurrent agents.

    Source: §I · p. 2

  • Takeaways & Limitations

    The framework establishes a foundation for scalable, high-performance LLM-based multi-agent systems handling complex, dynamic tasks efficiently.

    Source: §V · p. 8

Abstract

from arXiv · show

The emergence of Large Language Models (LLMs) in Multi-Agent Systems (MAS) has opened new possibilities for artificial intelligence, yet current implementations face significant challenges in resource management, task coordination, and system efficiency. While existing frameworks demonstrate the potential of LLM-based agents in collaborative problem-solving, they often lack sophisticated mechanisms for parallel execution and dynamic task management. This paper introduces DynTaskMAS, a novel framework that orchestrates asynchronous and parallel operations in LLM-based MAS through dynamic task graphs. The framework features four key innovations: (1) a Dynamic Task Graph Generator that intelligently decomposes complex tasks while maintaining logical dependencies, (2) an Asynchronous Parallel Execution Engine that optimizes resource utilization through efficient task scheduling, (3) a Semantic-Aware Context Management System that enables efficient information sharing among agents, and (4) an Adaptive Workflow Manager that dynamically optimizes system performance. Experimental evaluations demonstrate that DynTaskMAS achieves significant improvements over traditional approaches: a 21-33% reduction in execution time across task complexities (with higher gains for more complex tasks), a 35.4% improvement in resource utilization (from 65% to 88%), and near-linear throughput scaling up to 16 concurrent agents (3.47X improvement for 4X agents). Our framework establishes a foundation for building scalable, high-performance LLM-based multi-agent systems capable of handling complex, dynamic tasks efficiently.

I. INTRODUCTION

LLM-based multi-agent systems offer collaborative reasoning but remain limited by rigid task flows, underused parallelism, and difficult context management. DynTaskMAS addresses these gaps with dynamic task orchestration and asynchronous execution, targeting greater operational efficiency.

I. INTRODUCTION

  • Existing LLM-based multi-agent systems often use simplified topologies and straightforward task flows that do not match multifaceted, dynamic real-world demands.Source: §I · p. 1
  • Complex tasks increase the difficulty of coherent decomposition, efficient parallel processing, and context management across interacting agents.Source: §I · p. 1
  • DynTaskMAS introduces a dynamic task graph-driven framework for asynchronous and parallel LLM-based multi-agent systems.The framework is proposed to address limitations in task coordination, resource allocation, and execution efficiency.Source: §I · p. 1
  • The framework contributes principles for decomposition with semantic coherence and causal dependencies, abstractions for asynchronous agent interactions, and systematic semantic-aware context management.These contributions aim to balance information sharing with computational efficiency while preserving language-model reasoning capabilities.Source: §I · pp. 1–2

A. Planning with LLMs

  • Prior LLM-planning research has advanced planning and reasoning but has largely overlooked real-time GPU resource allocation and asynchronous parallel execution in multi-agent systems.Source: A. Planning with LLMs · p. 2

B. Multi-Agent System

Prior LLM-based multi-agent systems support collaborative planning, role specialization, communication, and memory, but leave parallel and serial processing challenges unresolved. DynTaskMAS combines dynamic task decomposition, asynchronous execution, semantic context sharing, and adaptive workflow management.

B. Multi-Agent System

  • Existing systems such as AutoGPT, MetaGPT, Camel, and Generative Agents explore iterative planning, role specialization, communication, knowledge sharing, and adaptive memory.Source: B. Multi-Agent System · p. 2
  • These multi-agent approaches have not yet provided superior solutions for parallel and serial processing challenges.Source: B. Multi-Agent System · p. 3

III. DYNTASKMAS

  • DynTaskMAS decomposes incoming tasks into a dynamically updated DAG, executes dependent subtasks concurrently, shares semantically relevant context, and adapts workflows using real-time metrics.Its four components are DTGG, APEE, SACMS, and AWM.Source: §III · p. 3
  • The modular architecture uses central coordination to support coherent operation, scalability, and integration of additional agents or task types.Source: §III · p. 3

A. Dynamic Task Graph Generator

The Dynamic Task Graph Generator decomposes complex tasks into subtasks, represents dependencies in a weighted DAG, and updates the graph as information or requirements change. Its design also distinguishes genuine reflection cycles from linear refinement sequences and limits reflection iterations.

A. Dynamic Task Graph Generator

  • DTGG recursively decomposes complex tasks into subtasks until a predefined granularity level is reached, representing dependencies as a directed acyclic graph.Source: A. Dynamic Task Graph Generator · p. 3
  • The graph G = (V, E, W) uses vertices for subtasks, edges for dependencies, and positive edge weights for scheduling-related costs.Source: A. Dynamic Task Graph Generator · p. 3
  • Edge weights combine estimated computational complexity and context-transfer information through W(vi, vj) = α · C(vj) + β · I(vi, vj).C denotes subtask complexity, I denotes SACMS-managed context-transfer time, and α and β balance the two factors.Source: A. Dynamic Task Graph Generator · p. 3
  • The recommended coefficients normalize computation and context-transfer contributions using α = 1/Tc and β = 1/Tt.The normalization is intended to make both factors contribute proportionally to scheduling decisions.Source: A. Dynamic Task Graph Generator · p. 3
  • DTGG distinguishes genuine reflection cycles from apparent cycles created by iterative refinement, treating the latter as linear sequences with hierarchical dependencies.Source: A. Dynamic Task Graph Generator · p. 3
  • Reflection terminates when quality reaches a threshold, the iteration limit N is reached, or improvement falls below ε; the graph is updated as new information and task progress arrive.The stated maximum iteration threshold is typically N ≤3.Source: A. Dynamic Task Graph Generator · p. 3

B. Asynchronous Parallel Execution Engine

The Asynchronous Parallel Execution Engine schedules and executes interdependent tasks across LLM agents by combining dependency-aware prioritization, queue management, load balancing, and asynchronous communication.

B. Asynchronous Parallel Execution Engine

  • Dependency-aware scheduling and load balancing maximize parallelism while respecting task relationships across multiple LLM-based agents.The engine uses the dynamic task graph, scheduling algorithms, and load balancing to improve efficiency for complex interdependent tasks.Source: B. Asynchronous Parallel Execution… · pp. 4–5
  • The Task Scheduler prioritizes tasks using dependencies, estimated computational complexity, and system load.It operates on the current weighted task graph and computes priorities for each task.Source: B. Asynchronous Parallel Execution… · p. 4
  • The Execution Queue Manager maintains a priority queue of ready-to-execute tasks and updates it as system conditions change.Ready tasks are identified from the graph and enqueued according to scheduler output.Source: B. Asynchronous Parallel Execution… · p. 4
  • Agent pooling and load balancing distribute tasks according to priorities, agent capabilities, and current workload.The Agent Pool Manager tracks agent status and capabilities, while the Load Balancer selects suitable assignments.Source: B. Asynchronous Parallel Execution… · p. 4
  • Event-driven asynchronous communication handles task assignments, completion notifications, availability updates, failures, and result collection.The non-blocking handler is intended to maintain high throughput and responsiveness.Source: B. Asynchronous Parallel Execution… · p. 5

C. Semantic-Aware Context Management System

The Semantic-Aware Context Management System distributes relevant contextual information among agents through semantic analysis, hierarchical storage, relevance filtering, and consistency-preserving updates.

C. Semantic-Aware Context Management System

  • SACMS manages and distributes contextual information so LLM agents can access relevant data during task execution.Its architecture combines semantic analysis, distributed storage, and adaptive mechanisms for context-aware operation.Source: C. Semantic-Aware Context Management… · pp. 5–6
  • The Context Repository stores context in a distributed hierarchical structure organized as a forest of domain-specific trees.Each context tree contains nodes, edges, and a root node, while nodes store data and semantic labels.Source: C. Semantic-Aware Context Management… · p. 5
  • Context updates are distributed to agents whose semantic tags exceed a relevance threshold, while query retrieval uses semantic matching and cosine similarity.The system filters results using both relevance and access-control constraints.Source: C. Semantic-Aware Context Management… · p. 5
  • The Semantic Analyzer extracts tags, entities, and relationships to construct a semantic graph for querying and reasoning.The resulting representation supports semantic matching across distributed context data.Source: C. Semantic-Aware Context Management… · p. 5
  • The Update Handler integrates new context through a two-phase commit protocol and synchronizes the semantic index after updates.Atomic integration preserves semantic relationships, query consistency, and ACID properties while minimizing query latency.Source: C. Semantic-Aware Context Management… · p. 6

D. Adaptive Workflow Manager (AWM)

The Adaptive Workflow Manager continuously adjusts workflows and resource allocation using real-time performance metrics, workflow state, and changing task or resource conditions.

D. Adaptive Workflow Manager (AWM)

  • The Adaptive Workflow Manager dynamically adjusts workflows based on real-time performance metrics and environmental changes.It adapts to evolving task requirements and resource availability to support system performance.Source: D. Adaptive Workflow Manager (AWM) · p. 6
  • The Performance Monitor tracks throughput, latency, agent utilization, and task completion metrics for data-driven optimization.These measurements provide the state information used by adaptive workflow decisions.Source: D. Adaptive Workflow Manager (AWM) · p. 6
  • Workflow optimization generates candidate configurations and selects the configuration minimizing an objective function evaluated on current system metrics.The iterative procedure compares candidates against the current workflow and retains the best-scoring option.Source: D. Adaptive Workflow Manager (AWM) · p. 6
  • Resource allocation uses a greedy strategy that prioritizes immediate efficiency while adapting to current performance and predicted future demand.The allocation update is represented as R(t) = R(t) + ∆R(t).Source: D. Adaptive Workflow Manager (AWM) · p. 6
  • The allocation strategy balances agent load while prioritizing critical tasks through priority weights and current utilization.The formulation accounts for each agent’s priority weight and current load.Source: D. Adaptive Workflow Manager (AWM) · p. 6
  • In the travel-planning comparison, DynTaskMAS completed execution in 3.7s versus 4.7s for serial execution.The experiment used seven specialized agents for distinct travel-planning subtasks.Source: Figure 3 · p. 7

IV. EXPERIMENTAL RESULTS

The experimental evaluation deployed DynTaskMAS with TensorRT-LLM on NVIDIA RTX 3090 GPUs, using Llama-3.1-8B as the foundation model for all agents.

IV. EXPERIMENTAL RESULTS

  • The evaluation used TensorRT-LLM on NVIDIA RTX 3090 GPUs with Llama-3.1-8B serving as the foundation model for every agent.These deployment settings define the reported experimental environment.Source: §IV · p. 7

A. Experimental Setup

Experiments used a four-GPU RTX 3090 cluster with an AMD EPYC processor and 512GB memory, running INT8 quantization with batch size 32 and sequence length 2048.

A. Experimental Setup

  • Experiments ran on four NVIDIA RTX 3090 GPUs with an AMD EPYC 7763 64-Core Processor and 512GB DDR4 memory.Source: A. Experimental Setup · p. 7
  • The software stack used Ubuntu 22.04 LTS, CUDA 12.1, and TensorRT-LLM 0.7.1 with INT8 quantization, batch size 32, and sequence length 2048.Source: A. Experimental Setup · p. 7

B. Performance Evaluation

DynTaskMAS reduced execution time more as task complexity increased and scaled near-linearly through 16 agents, while showing diminishing returns at 32 agents.

B. Performance Evaluation

  • 21.3%, 27.6%, and 33.0% execution-time reductions occurred for simple, medium, and complex tasks, respectively, versus traditional processing.Simple tasks decreased from 4.7s to 3.7s; the gain increased with task complexity.Source: B. Performance Evaluation · p. 7, Table I · p. 7
  • DynTaskMAS’s increasing efficiency gains reflect DTGG parallelization, reduced redundant context transfers through SACMS, and higher GPU utilization from APEE scheduling.Source: B. Performance Evaluation · p. 7
  • Performance variability was ±0.2–0.5s, with relative variability decreasing as task complexity increased.The passage attributes this pattern to more deterministic management across larger task graphs.Source: B. Performance Evaluation · p. 7
  • Throughput scaled near-linearly to 16 agents, rising from 12.3 tasks/s with 4 agents to 42.7 tasks/s with 16 agents, a 3.47× improvement.Scaling efficiency was approximately 87% in the moderate agent range.Source: B. Performance Evaluation · pp. 7–8, Table II · p. 7
  • At 32 agents, throughput reached 76.4 tasks/s but showed diminishing returns, corresponding to a 6.21× improvement for an 8× increase in agents.The reported causes were shared-resource contention in SACMS and increased APEE scheduling and load-balancing overhead.Source: B. Performance Evaluation · p. 8

C. Case Study

A seven-agent travel-planning case study compared serial execution with DynTaskMAS using INT8 quantization and continuous batching. DynTaskMAS reduced execution time and increased GPU utilization.

C. Case Study

  • The travel-planning system used seven specialized agents covering preferences, destinations, transportation, and accommodations.Source: C. Case Study · p. 8
  • DynTaskMAS reduced overall execution time by 21%, from 4.7s to 3.7s, compared with serial processing.The evaluation used INT8 quantization, continuous batching, batch size 32, and sequence length 2048.Source: C. Case Study · p. 8
  • GPU utilization increased by 35% under DynTaskMAS, alongside efficient parallel execution, dynamic memory management, and streamlined context sharing.The results were reported as demonstrating effectiveness for complex, dynamic tasks while identifying areas for future optimization.Source: C. Case Study · p. 8

V. CONCLUSION

DynTaskMAS combines dynamic task graphs, asynchronous parallel execution, semantic-aware context management, and adaptive workflow management to improve LLM-based multi-agent coordination and resource use. The reported results include larger execution-time gains for more complex tasks, improved resource utilization, and scalable throughput.

V. CONCLUSION

  • DynTaskMAS integrates Dynamic Task Graph Generation, Asynchronous Parallel Execution, Semantic-Aware Context Management, and Adaptive Workflow Management.The architecture distributes computational resources while maintaining task coherence and reducing computational redundancy.Source: §V · p. 8
  • 21.3% to 33.0% execution-time improvements, a 35.4% resource-utilization increase from 65% to 88%, and 3.47× throughput improvement were reported.The execution-time range covers simple through complex tasks, while the throughput result concerns 16 concurrent agents.Source: §V · p. 8
  • The paper presents DynTaskMAS as a systematic approach for scalable, high-performance LLM-based multi-agent systems balancing resource optimization with task coordination.Source: §V · p. 8
Loading 2503.07675v2…