SCHEMAS: Leveraging a Scalable Heterogeneous Graph for Query-Guided Reasoning in Multi-Agent Systems

Multi-agent systems have demonstrated strong problem-solving capabilities, yet real-world tasks often require complex interactions that involve retrieving external knowledge and calling tools. In such settings, interaction dependencies among query, agent, and tool entities are often encoded implicitly and transiently in dialogues and execution traces, without an explicit structure to systematically represent invocation conditions and collaboration pathways. In this paper, we propose SCHEMAS, a scalable and configurable heterogeneous graph framework for multi-agent systems that unifies four entity types: query, agent, tool, and distilled insight, explicitly capturing their typed interactions to enable query-guided reasoning and continual evolution. To improve performance on a new query, we propose a query-driven structured memory mechanism that constructs a memory subgraph by retrieving the most relevant query, agent, tool, and insight nodes from the heterogeneous graph. Based on the subgraph, we allocate the query to the most compatible agent by matching the query’s required capability profile to agent capability representations. After execution, we apply the dynamic update mechanism that writes back the new query and its trace to the heterogeneous graph, thereby enabling the progressive evolution of the multi-agent systems. Extensive experiments across eight main benchmarks spanning tool-use and memory-augmented interactive settings demonstrate that SCHEMAS delivers consistently strong performance, scales across diverse tool-use scenarios and interactive tasks, and does so with lower token usage than state-of-the-art baselines.