S-DAG: A Subject-Based Directed Acyclic Graph for Multi-Agent Heterogeneous Reasoning

Jiangwen Dong, Zehui Lin, Wanyu Lin, Mingjin ZhangarXiv 2025 · DOI · arXiv

Introduction

Large Language Models (LLMs) have demonstrated remarkable capabilities across various domains. However, they frequently encounter limitations when faced with complex, multi-disciplinary reasoning tasks—such as medical entrance exams that require simultaneous mastery of biology, chemistry, and ethics. Current approaches to this problem generally fall into two categories: coarse-grained routing, which sends a query to a single "best" expert model, and Mixture-of-Agents (MoA), which involves unstructured debate or aggregation among multiple models.

Comparison of the S-DAG approach against traditional single-router methods.

As illustrated in Figure 1, traditional methods often fail to capture the nuanced interdependencies between subjects within a single question. The authors of S-DAG argue that effective reasoning requires fine-grained, subject-level coordination, focusing not just on agent selection but on the logical flow of information between specialized experts.

The S-DAG Framework

The S-DAG (Subject-Based Directed Acyclic Graph) framework introduces a structured approach to multi-agent collaboration through a two-stage process: question analysis and graph-based execution.

1. Question Analysis and DAG Generation

Rather than relying on inconsistent LLM self-prompting to determine task structure, S-DAG utilizes a trained Graph Neural Network (GNN). When a query is received, the GNN identifies the relevant subjects and predicts their dependencies. It constructs a Directed Acyclic Graph where nodes represent specific subjects and edges define the information flow. For instance, a "supporting" subject like Mathematics may be solved first to provide necessary context for a "dominant" subject like Physics.

2. Multi-Agent Collaboration and Execution

The system manages a pool of 14 specialized, lightweight LLMs (typically 7B to 13B parameters). By maintaining a "Capability Profile" for each model, S-DAG matches graph nodes to the most proficient experts. Supporting agents generate intermediate reasoning, which is passed as context to subsequent agents in the graph, eventually reaching the "Dominant Agent" for the final answer.

The end-to-end pipeline of S-DAG, from GNN-based graph generation to multi-agent information flow.

Experimental Setup and Datasets

To evaluate S-DAG, the researchers curated multi-subject subsets from three rigorous benchmarks where questions averaged between 3.5 and 4.4 distinct subjects:

  • MMLU-Pro: College-level multi-disciplinary subjects.
  • GPQA: Graduate-level science questions.
  • MedMCQA: Medical entrance examination queries.

Key Results and Insights

Performance and Efficiency

S-DAG achieved an average accuracy of 59.73% across the benchmarks, outperforming both the Symbolic-MoE baseline (57.53%) and the closed-source GPT-4o-mini (58.52%). Remarkably, this performance was achieved using a collection of small models, rivaling much larger generalist models like Qwen2.5-72B and Llama3.3-70B.

Beyond accuracy, S-DAG proved significantly more efficient than fully connected multi-agent setups. By restricting communication to the logical paths defined by the DAG, the system reduced LLM calls by 50% and cut inference time from 38.45 seconds to 15.02 seconds.

The Importance of Structure

A critical finding of the study is that "more communication" is not always better. Fully connected graphs, where every agent interacts with every other agent, often performed worse due to the introduction of reasoning loops and redundant "noise." The GNN-generated DAG acts as a traffic controller, ensuring that information flows only where it is logically required.

Conclusion and Future Work

S-DAG demonstrates that structured coordination can effectively compensate for raw parameter count in complex reasoning tasks. While the framework shows great promise, its performance remains dependent on the quality of the underlying expert pool. Future research will explore dynamic expert fetching and the implementation of safety safeguards for high-stakes applications like medical diagnosis, where error propagation must be strictly controlled.

Summary updated

Abstract

Large Language Models (LLMs) have achieved impressive performance in complex reasoning problems. Their effectiveness highly depends on the specific nature of the task, especially the required domain knowledge. Existing approaches, such as mixture-of-experts, typically operate at the task level; they are too coarse to effectively solve the heterogeneous problems involving multiple subjects. This work proposes a novel framework that performs fine-grained analysis at subject level equipped with a designated multi-agent collaboration strategy for addressing heterogeneous problem reasoning. Specifically, given an input query, we first employ a Graph Neural Network to identify the relevant subjects and infer their interdependencies to generate an \textit{Subject-based Directed Acyclic Graph} (S-DAG), where nodes represent subjects and edges encode information flow. Then we profile the LLM models by assigning each model a subject-specific expertise score, and select the top-performing one for matching corresponding subject of the S-DAG. Such subject-model matching enables graph-structured multi-agent collaboration where information flows from the starting model to the ending model over S-DAG. We curate and release multi-subject subsets of standard benchmarks (MMLU-Pro, GPQA, MedMCQA) to better reflect complex, real-world reasoning tasks. Extensive experiments show that our approach significantly outperforms existing task-level model selection and multi-agent collaboration baselines in accuracy and efficiency. These results highlight the effectiveness of subject-aware reasoning and structured collaboration in addressing complex and multi-subject problems.
BibTeX
@misc{dong2025s,
  author = {Jiangwen Dong and Zehui Lin and Wanyu Lin and Mingjin Zhang},
  title = {{S-DAG: A Subject-Based Directed Acyclic Graph for Multi-Agent Heterogeneous Reasoning}},
  year = {2025},
  eprint = {2511.06727},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2511.06727},
}
Figure