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

AI summary

Overview

Research area: Multi-agent systems (cs.MA), specifically heterogeneous reasoning with large language models — routing and coordination of specialist LLM agents across multiple subject domains.

Technical level: Advanced. The paper assumes familiarity with graph neural networks, message passing, LLM routing, mixture-of-experts and mixture-of-agents paradigms.

Scope: The paper proposes S-DAG, a framework that builds a subject-level directed acyclic graph with a Graph Neural Network and uses it to assign and coordinate subject-specialist LLMs on multi-subject questions, evaluated on curated subsets of MMLU-Pro, GPQA and MedMCQA.

What This Paper Is About

Most LLM routing and mixture-of-experts systems decide which model to use at the level of a task or a single coarse domain label, which is too blunt when one question genuinely requires several subject areas at once. S-DAG instead asks a more granular question: which subjects does this specific question need, how do those subjects depend on one another, and which expert model should answer each one? The goal is to achieve both higher accuracy and lower cost than single-best-model selection or existing multi-agent debate and skill-level mixture-of-experts baselines.

Key Contributions

1. Subject-level problem framing. The authors state they are the first to study heterogeneous reasoning where a single complex problem covers multiple subject knowledge, and they introduce S-DAG as a framework that decomposes a question into subject-specific components with graph-structured multi-agent collaboration.
2. A trained GNN that generates the S-DAG. Rather than prompting an LLM to produce subject structure (which the paper says is noisy and inconsistent), a BERT encoder plus a Graph Neural Network predicts relevant subject nodes and directed edges jointly, using a multi-task binary cross-entropy loss over node and edge labels.
3. Subject-aware subject-to-LLM matching. Each model in the pool receives a normalized subject capability profile built from a 200-question profiling set with weighted relevance scores, and each subject node in the S-DAG is assigned to the highest-scoring model.
4. Curated multi-subject benchmarks. The authors manually select interdisciplinary samples from MMLU-Pro, GPQA and MedMCQA, releasing training and test splits along with a 200-sample profiling set, and report comparisons against single-model, routing and multi-agent baselines.

Main Findings

• Highest average accuracy among the compared methods that do not rely on larger or proprietary models: S-DAG reaches 59.73% average accuracy, ahead of Symbolic-MoE (57.53%), MAD (56.39%), GraphRouter (56.03%), MoE (54.56%) and Self-Refine (54.44%). Per benchmark it scores 50.98 ± 0.19 on MMLU-Pro, 49.82 ± 0.24 on GPQA and 78.38 ± 0.35 on MedMCQA.
• Competitive with much larger monolithic models, but not uniformly better: S-DAG's 59.73% average is above GPT-4o-mini (58.52%) but below Qwen2.5 72B (60.08%) and Llama3.3 70B (60.04%). It is higher than both on GPQA, lower than both on MMLU-Pro, and lower than Qwen2.5 72B (80.44%) and GPT-4o-mini (78.82%) on MedMCQA.
• Graph structure matters more than unrestricted communication: The fully connected graph variant scores 57.29% average with 38.45s inference time and 8.2 LLM calls, versus S-DAG's 59.73% at 15.02s and 4.1 calls.
• Both the GNN and the capability profile are necessary: With random model assignment, the system scores 41.12% without GNN coordination and 42.19% with it. Removing the GNN but keeping profiled model selection gives 53.51%, still below the full S-DAG's 59.73%.
• The GNN is claimed to beat LLM-generated structure: The paper argues that a purely LLM-generated S-DAG yields significantly lower accuracy than the GNN-based one, attributing this to noisy and inconsistent LLM outputs.
• Sparse directionality beats over-communication: Because the fully connected variant allows unrestricted bidirectional exchange among all subject nodes, it produces redundant information flow and higher latency; the sparse, hierarchical S-DAG streamlines reasoning instead.

Methodology in Plain English

The framework runs in two stages.

Stage 1 — build the subject graph. Every subject is first placed as a node in a fully connected directed graph. A BERT encoder turns the question into a vector, and each subject node is initialized by combining its own embedding with the question embedding through a small MLP. Several layers of directional message passing let nodes exchange information, after which two predictors output a relevance score per subject and a dependency score per directed edge. The result is a pruned graph, the S-DAG, where a directed edge from subject A to subject B means A is supporting knowledge for B. Training supervision comes from a subject LLM (qwen-turbo-0919) run three times per question, keeping only subjects that appear consistently; subjects below a weight threshold such as 0.1 are dropped, and those above the average (for example 1/4 = 0.25 when four subjects are present) become dominant subjects while the rest act as supporting nodes. Edge loss is masked when both endpoints are irrelevant subjects, so the model is not penalized for ignoring unrelated domains.

Stage 2 — pick and coordinate agents. Each LLM in a pool of 14 domain experts (roughly 7B to 13B parameters, such as DeepseekMath for mathematics and BioMistral for biology) is scored on 200 profiling questions. A model that answers a question weighted math 0.5, physics 0.3, biology 0.2 correctly earns +0.5, +0.3 and +0.2 in those subjects respectively. Scores are normalized so each model's subject scores sum to 1, and for each subject node the model with the highest score is chosen. Agents then communicate only along the S-DAG's edges: an agent's output plus the original question become the prompt for the downstream agent, so information flows from supporting subjects to dominant ones. Experiments used A100 GPUs with 40 GB memory, decoding temperature 0.7, a 4096-token maximum output length, the Adam optimizer, a fixed seed, and results averaged over three trials with standard deviations reported.

Why This Matters

Impact on research. The paper shifts the granularity of model selection from the task or domain level down to the subject level, and it argues that subject-to-subject dependency, not just subject identity, should determine how expert agents talk to one another. It also releases curated multi-subject splits of standard benchmarks, giving the community a harder evaluation setting where a question averages 3.5 to 4.4 distinct subjects.

Real-world applications:

• Clinical decision support, where a case may blend medicine, biology, chemistry and health knowledge (the MedMCQA setting covers 21 medical subdomains).
• Scientific and engineering analysis, where a single question spans graduate-level physics, chemistry and mathematics (the GPQA setting).
• Cross-disciplinary professional advisory, for example work that mixes economics, law, business and history, which is what the MMLU-Pro curation targets.
• Cost-sensitive deployment of open-weight models, where a pool of 7B–13B specialists is coordinated instead of calling a single large proprietary model.

Industry relevance. The efficiency numbers are the practical draw: 4.1 LLM calls and 15.02s per question versus 8.2 calls and 38.45s for the fully connected alternative, with accuracy still above naive routing and debate baselines. That is a direct argument about latency and inference spend in production agent pipelines.

Future Directions

• Better ground-truth subject structure. Supervision currently comes from a single subject LLM run three times with a consistency filter; stronger or human-verified annotations could test whether the claimed advantage of the GNN over LLM-generated graphs holds at larger scale.
• Scaling the design choices. The paper does not report a systematic sweep over the number of subject nodes, the relevance and dominance thresholds, or the GNN depth, so sensitivity to these settings remains open.
• Extending beyond three benchmarks. The evaluation is limited to MMLU-Pro, GPQA and MedMCQA; whether S-DAG generalizes to other multi-subject domains and to more than 14 expert models is not established.
• Adaptive agent pools. Capability profiles are built once from 200 profiling questions and normalized per model; whether these profiles should be refreshed, personalized, or made uncertainty-aware during inference is left unaddressed.

Target Audience

Researchers and practitioners working on LLM routing, mixture-of-experts, and multi-agent orchestration who need an evaluation setup for questions that intentionally cross subject boundaries. It is also relevant to applied teams that must balance accuracy against latency and API cost when composing several small specialist models instead of one large generalist. Readers without background in graph neural networks or multi-agent prompting will need to consult the cited prior work on mixture-of-agents, GraphRouter and Symbolic-MoE first.

Authors’ 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.