Paper deep dive
DIG to Heal: Scaling General-purpose Agent Collaboration via Explainable Dynamic Decision Paths
Hanqing Yang, Hyungwoo Lee, Yuhang Yao, Zhiwei Liu, Kay Liu, Jingdi Chen, Carlee Joe-Wong
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 91%
Last extracted: 7/20/2026, 6:22:36 AM
Summary
The paper introduces the Dynamic Interaction Graph (DIG), a framework for modeling and analyzing emergent collaboration in general-purpose multi-agent LLM systems. DIG captures agent activations and interactions as a time-evolving causal network, enabling the observation, explanation, and correction of collaboration-induced errors without predefined roles or workflows. The authors propose topological failure characterization and a structure-driven system healing mechanism to improve efficiency and reduce errors in autonomous multi-agent cooperation.
Entities (5)
Relation Signals (5)
Dynamic Interaction Graph → models → Emergent Collaboration
confidence 95% · DIG captures emergent collaboration as a time-evolving causal network of agent activations and interactions.
LLM Agents → participatein → Emergent Collaboration
confidence 94% · multi-agent systems composed of general-purpose LLM agents that solve problems through emergent collaboration
Graph Rewrite Operators → evolve → Dynamic Interaction Graph
confidence 92% · The DIG evolves through local graph rewrite operators induced by agent activations.
Dynamic Interaction Graph → enables → System Healing
confidence 90% · DIG makes emergent collaboration observable and explainable... enabling real-time identification, explanation, and correction of collaboration-induced error patterns
Dynamic Interaction Graph → detects → Collaboration-induced Error Patterns
confidence 89% · DIG makes emergent collaboration observable and explainable... enabling real-time identification... of collaboration-induced error patterns
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:The increasingly popular agentic AI paradigm promises to harness the power of multiple, general-purpose large language model (LLM) agents to collaboratively complete complex tasks. While many agentic AI systems reduce complexity through predefined workflows or fixed agent roles, the ideal is to support truly autonomous agents capable of emergent collaboration across many interacting agents. Yet in practice, such unstructured interactions often lead to redundant work and cascading failures that are difficult to interpret or correct. In this work, we study multi-agent systems composed of general-purpose LLM agents that solve problems through emergent collaboration, without relying on predefined roles, control flows, or communication constraints. We introduce the Dynamic Interaction Graph (DIG), which captures emergent collaboration as a time-evolving causal network of agent activations and interactions. DIG makes emergent collaboration observable and explainable for the first time, enabling real-time identification, explanation, and correction of collaboration-induced error patterns directly from agents' collaboration paths. Thus, DIG fills a critical gap in understanding how general LLM agents solve problems together in truly agentic multi-agent systems. The project webpage can be found at: this https URL.
Tags
Links
- Source: https://arxiv.org/abs/2603.00309v2
- Canonical: https://arxiv.org/abs/2603.00309v2
Trouble viewing inline? Open PDF directly →
Full Text
66,098 characters extracted from source content.
Expand or collapse full text
DIG to Heal: Scaling General-purpose Agent Collaboration via Explainable Dynamic Decision Paths Hanqing Yang CMU &Hyungwoo Lee CMU &Yuhang Yao Zoom Zhiwei Liu Salesforce &Kay Liu Amazon &Jingdi Chen UArizona Carlee Joe-Wong CMU Contact: hanqing3@andrew.cmu.edu. CMU: Carnegie Mellon University; UArizona: University of Arizona. Abstract The increasingly popular agentic AI paradigm promises to harness the power of multiple, general-purpose large language model (LLM) agents to collaboratively complete complex tasks. While many agentic AI systems reduce complexity through predefined workflows or fixed agent roles, the ideal is to support truly autonomous agents capable of emergent collaboration across many interacting agents. Yet in practice, such unstructured interactions often lead to redundant work and cascading failures that are difficult to interpret or correct. In this work, we study multi-agent systems composed of general-purpose LLM agents that solve problems through emergent collaboration, without relying on predefined roles, control flows, or communication constraints. We introduce the Dynamic Interaction Graph (DIG), which captures emergent collaboration as a time-evolving causal network of agent activations and interactions. DIG makes emergent collaboration observable and explainable for the first time, enabling real-time identification, explanation, and correction of collaboration-induced error patterns directly from agents’ collaboration paths. Thus, DIG fills a critical gap in understanding how general LLM agents solve problems together in truly agentic multi-agent systems. The project webpage can be found at: https://happyeureka.github.io/dig. 1 Introduction Large Language Models (LLMs) are increasingly used as general decision-making units due to their broad world knowledge, flexible reasoning abilities, and capacity to interact with external tools and memory. This has led to the emergence of LLM agents, which extend LLMs with persistent state, tool access, and environment interaction, enabling them to act autonomously in complex tasks. Recently, significant attention has been devoted to LLM-powered multi-agent systems (Chen et al., 2026; Yang et al., 2025), where multiple agents collaborate on tasks such as research, software engineering, robotics, simulation, and question answering (Durante et al., 2024; He et al., 2025). Despite the potential of allowing LLM agents to act autonomously, in practice unstructured agent collaboration often leads to task failure. Thus, many multi-agent systems utilize predefined workflows, with fixed roles, task decompositions, tool usage patterns, and message routing policies, in order to stabilize performance (Li et al., 2024). However, such designs are often domain-specific and fundamentally constrain how agents interact. In contrast, as illustrated in Fig. 2, we study LLM-powered multi-agent systems composed of general-purpose LLM agents that operate without predefined roles, control flow, or communication constraints. In such systems, coordination, task decomposition, and problem-solving strategies must arise implicitly from local agent decisions and interactions, resembling how human teams dynamically coordinate and adapt to solve evolving tasks. Our goal is to evaluate such cooperative intelligence in general-purpose LLM agents by illuminating the causes of collaboration failures so as to enable more resilient autonomous multi-agent systems. Figure 1: Cooperative problem solving with general-purpose agents. A pool of autonomous agents works on a shared task without predefined roles, control flow, or communication constraints, each operating independently and non-deterministically and interacting through emergent cooperative strategies. We make emergent cooperation analyzable by modeling agent interaction in a protocol-agnostic manner. Figure 2: Dynamic Interaction Graph (DIG) and local graph rewrite operators. (1-2) Bipartite graph structure with agent activation nodes (circles) and event nodes (rectangles). (3) Canonical edge rewrite operators. (4) Raw DIG induced by an execution trace, including all generation and delivery edges. (5) Cleaned DIG after removing non-productive edges corresponding to non-productive interactions, exposing the underlying interaction structure. The Challenges of Emergent Cooperation. Allowing agents to autonomously interact introduces substantial challenges. Each agent receives information, from other agents and the environment, at arbitrary times while acting concurrently with others. Local agent decisions can thus easily push global execution away from intended behavior, producing redundant work, stalled progress, or cascading failures that are difficult to diagnose or recover from. Simply increasing the number of agents does not guarantee improved performance (Kim et al., 2025); instead, interaction complexity grows combinatorially, leading to even more interdependent outputs that may cause task failures or redundancies. Unlike traditional distributed systems, multi-LLM agent systems are stochastic, heterogeneous, and message-driven, making tracing, debugging, and recovery particularly challenging. Existing approaches typically rely on centralized monitors (Gandhi et al., 2025; Zhang et al., 2025a), guard agents (Yu et al., 2025), or post hoc failure attribution based on execution logs or curated error datasets (Kong et al., 2025; Zhang et al., 2025b). These methods either assume fixed workflows, operate after failures have already occurred, or require large amounts of annotated data, and therefore do not directly address how cooperation emerges or fails during execution. Our Perspective: Analyzing Agent Interactions. In this work, we argue that understanding and improving general multi-agent systems requires treating collaboration itself as the primary object of analysis. Rather than focusing on individual agents or final outcomes, we model the system in terms of its interaction structure. We introduce the Dynamic Interaction Graph (DIG) (Fig. 2), a time-evolving directed graph that formalizes agent activations and interaction events as a causal network. This abstraction makes emergent collaboration observable and explainable, enabling real-time tracing, structural analysis, and reasoning about how cooperative behavior forms, propagates, and fails. Building on DIG, we establish a topological characterization of emergent collaboration, which maps interaction graph structures to distinct classes of collaboration-induced error patterns. This result provides a model-agnostic categorization of failure modes, enabling early failure detection at the level of collaboration structure rather than individual agent outputs. This structural perspective is designed to be compatible with existing failure detection and attribution methods, e.g., as proposed by Cemri et al. (2025). Rather than replacing them, it provides an error detection and guarding layer, where topology-level signals can be integrated into semantic, behavioral, and learning-based detectors. The DIG framework further supports reasoning about effective agent utilization, revealing when agents contribute meaningful progress versus introducing redundancy, inefficiency, or instability. Together, these capabilities provide a unified and explainable foundation for understanding and debugging truly agentic multi-LLM systems, where cooperation emerges dynamically from agents. Our main contributions are: (1) Interaction Modeling. We formalize the interaction structure and cooperative problem-solving process of general LLM agents with DIG, a dynamic directed acyclic graph (DAG) representation that captures both sequential and parallel dependencies, as well as temporal ordering, in unconstrained multi-agent systems. (2) Topological Failure Characterization. We establish a mapping from the DIG topology to collaboration-induced error types, yielding a high-level, model-agnostic categorization of failure modes that supports explainable and hierarchical error detection and can be naturally integrated with existing error detection and attribution methods. (3) General-Agent Execution Traces. We evaluate DIG on two scalable and verifiable evaluation tasks, allowing us to introduce the first dataset of execution traces that capture the behavior and interaction patterns of general-purpose agents operating without predefined roles or control flow. (4) Structure-Driven System Healing. We propose an automatic system healing mechanism driven by observed agent behavior and interaction structure, enabling early detection and correction of collaboration-induced failures during execution. In experiments, we find that this mechanism yields improved efficiency and fewer errors, particularly on difficult tasks with many agents. After reviewing related work in Section 2, we formalize agent interactions (Section 3) and DIG’s construction (Section 4). We then explain how DIG enables failure monitoring and healing (Section 5) and describe the design (Section 6) and results (Section 7) of our evaluation, concluding in Section 8. 2 Related Work LLM-powered Multi-agent Systems. Recent frameworks such as LangGraph (16), AutoGen (Wu et al., 2023), and AgentVerse (Chen et al., 2023) enable multi-agent collaboration through structured workflows and orchestration policies, with applications including research assistants, software engineering, robotics, and simulation (Chen et al., 2026). While effective for specific domains, these systems rely on predefined roles, control flow, and communication structures (Yan et al., 2025), providing limited insight into emergent cooperation in unconstrained, general-agent systems. Agent Interaction Modeling. Our interaction model is related to classical abstractions such as stochastic computation graphs (SCGs) (Schulman et al., 2016), Petri nets (Peterson, 1977), the Actor model (Agha, 1986), description logics (Baader et al., 2008; Antoniou and Harmelen, 2009), and process algebras (Fokkink, 2013; De Nicola, 2014). These formalisms model computation, concurrency, or system properties, but are not designed to preserve the asynchronous, non-deterministic, natural-language interaction paths generated by LLM agents without fixed protocols in real time, so as to enable failure interventions. In contrast, DIG provides lightweight interaction model tailored to emergent cooperation in multi-LLM systems. Please see Appendix F for further comparisons. Failure Characterization in Multi-agent Systems. Recent taxonomies show that multi-agent LLM systems frequently fail due to specification errors, misalignment, and verification breakdowns, with local failures often cascading into system-wide issues (Cemri et al., 2025). Prior work addresses these failures through post hoc attribution (Kong et al., 2025; Zhang et al., 2025b), centralized monitors or guard agents (Yu et al., 2025; Gandhi et al., 2025; Zhang et al., 2025a), and runtime supervision mechanisms (Wang et al., 2025; Lin et al., 2025), as well as graph-based monitoring and defense (Wu et al., 2025). While effective in specific settings, these approaches are typically coupled to fixed agent architectures or orchestration patterns, rely on curated error datasets, and diagnose failures at the level of individual agents or final outcomes. By contrast, our work provides a lightweight, framework-agnostic trace that captures interactions among general agents, enabling systematic and explainable error attribution and scaling naturally to massively parallel multi-agent systems. 3 Problem Formulation: Cooperative Problem Solving with General Agents We consider cooperative problem solving in systems of multiple general-purpose agents that interact asynchronously via message passing. As illustrated in Fig. 2, agent collaboration and task decomposition thus emerge solely from local agent decisions. System Model. A cooperative multi-agent system is characterized by the tuple =(,ℰ,,ℤ),S=(A,E,P,Z), where =a1,…,aNA=\a_1,…,a_N\ is a finite set of agents, ℰE is the set of interaction events, P denotes problem instance to be solved, ℤZ denotes the discrete logical time domain. P is encoded as an initial event e0∈ℰe_0 , delivered at t=0t=0 to an initial subset of agents 0⊆A_0 . Execution terminates when a terminal event e∞e_∞ is generated. Logical time t∈ℤt advances whenever an interaction occurs, including agent activation or event delivery. It induces a causal ordering over interactions but may not correspond to wall-clock time. Each agent a∈a (omitting the index i in aia_i for notational simplicity) is modeled as an autonomous decision-making unit that operates asynchronously and has no predefined role or control flow. Thus, we abstract away agent internals and model only observable interaction behavior via a non-deterministic transformation on events: fa:Ia⟶Oa,Ia,Oa⊆ℰ.f_a:I_a O_a, I_a,\,O_a . (1) Each agent a maintains a local event buffer Ba(t)⊆ℰB_a(t) . Let activate(t,a)∈0,1activate(t,a)∈\0,1\ indicate whether agent a is activated at time t. An idle agent is activated when its buffer changes: activate(t,a)=1ifBa(t)≠Ba(t−1)andactivate(t−1,a)=0.activate(t,a)=1 B_a(t)≠ B_a(t-1)\ and\ activate(t-1,a)=0. A buffer can change in two cases: the agent receives a new event, or the agent processes an existing event and removes it from the buffer. For example, an event may specify a computational task, i.e., sorting a list, which the agent performs after activation. Agents interact through events e, defined as e=(pe,πe)∈ℰ,πe(t)↦(Rt(e),πe′),Rt(e)⊆,e=(p_e, _e) , _e(t) (R_t(e), _e ), R_t(e) , (2) where pep_e is the event payload and πe _e is its delivery policy. At logical time t, πe _e determines the recipient set Rt(e)R_t(e) and updates itself to πe′ _e . The event is then appended to the buffers of agents in Rt(e)R_t(e). If πe′ _e is empty, the event expires. For example, pep_e may be the result of a computation completed by agent a, and πe _e may immediately deliver the result pep_e to all agents a′≠a ≠ a. Tracking Agent Dynamics. The coupled dynamics of agent transformations (1) and policy-driven event delivery (2) jointly define a stochastic execution process over logical time. We record this process as an execution trace T and define the system-level diagnosis problem Φ as: =(at,et,t)t∈ℤ,Φ:→ℱ.T=\(a_t,e_t,t)\_t , :T . (3) Here, ata_t is the agent activated at time t, if any, and ete_t denotes the event generated or delivered at that time. The challenge is that asynchronous and non-deterministic execution makes failures hard to localize from the terminal output e∞e_∞ alone. Failures may arise from intermediate interaction structure, e.g., stalled activations, lost subproblems, duplicated work, or premature termination. Thus, Φ must infer ℱF, the space of failure signals and explanations, from observable interaction traces without access to agent internals or semantic task labels. We address this with the Dynamic Interaction Graph (DIG), a formal representation of agent interactions during cooperative problem solving. 4 Method: Dynamic Interaction Graph (DIG) We present DIG as a system-level representation and evaluation framework for cooperative problem solving in general multi-agent systems. Given an execution trace T, DIG transforms observed agent interactions into a labeled causal interaction graph Ψ() (T). This graph enables graph-level inference to detect failures, explain coordination dynamics, and derive interventions without requiring access to agent internals or semantic task labels. 4.1 DIG Definition DIG represents agent cooperation as a dynamic causal graph. At logical time t, DIG is defined as: G(t)=(A(t)∪E(t),ℰG(t)),G(t)=(V_A(t) _E(t),\,E_G(t)), (4) where A(t)V_A(t) is the set of activation nodes, E(t)V_E(t) is the set of event nodes, and ℰG(t)E_G(t) is the set of directed edges, as illustrated in Fig. 2 (1–2). The graph is bipartite: edges only connect activation nodes and event nodes. Each activation node represents one activation of agent av∈a_v over the interval τv=[tvstart,tvend] _v=[t_v^start,t_v^end]: v=(idv,av,τv).v=(id_v,a_v, _v). Each event node represents one interaction event together with its realized delivery times: eG=(e,τe),τe=(tegen,terecv(b)b∈R∞(e)).e_G=(e, _e), _e= (t_e^gen,\t_e^recv(b)\_b∈ R_∞(e) ). Edges. DIG has two edge types: (1) Generation edges (v→eG)∈ℰG(v→ e_G) _G when activation v generates event e, and (2) Delivery edges (eG→vb)∈ℰG(e_G→ v_b) _G when event e triggers activation vbv_b. Collectively, ℰGE_G defines a complete temporal causal trace of execution, on which all causal influence propagates. Illustration. Fig. 2(4–5) illustrate DIG. Circles denote activation nodes v∈Av _A, spanning [tvstart,tvend][t_v^start,t_v^end], and squares denote event nodes eG∈Ee_G _E at generation time tegent_e^gen. Edges from circles to squares represent generation (v→eG)(v→ e_G), while edges from squares to circles represent delivery (eG→vb)(e_G→ v_b). Fig. 2(4) shows the full real-time DIG, including transient edges (defined in Sec. 4.2), while Fig. 2(5) omits them. Together, they show how an execution trace T maps to a time-indexed bipartite causal graph G(t)G(t), where cooperation structure is encoded by nodes and directed edges. DIG makes cooperation dynamics and causal dependencies observable. 4.2 Interaction Primitives as Graph Rewrite Operators The DIG evolves through local graph rewrite operators induced by agent activations. When an agent a is activated at logical time t, the activation is represented by an activation node v∈A(t)v _A(t). Let Ba(t)B_a(t) denote the local event buffer of agent a at time t, and let Ia(t)⊆Ba(t)I_a(t)\; \;B_a(t) denote the subset of events selected by the agent during the activation. These events correspond exactly to the set of incoming delivery edges of the activation node: EGin(v)=(e,v)∈ℰG(t).E_G^in(v)\;=\;\(e,v) _G(t)\. (5) We further assign a causal fate to each incoming interaction edge by defining a system-level edge rewrite semantics through a mapping ϕv:EGin(v)⟶consume,delay,reroute,discard _v:E_G^in(v)\; \;\ consume, delay, reroute, discard\. This induces a local graph rewrite operator ℛv:G(t)⟶G(t+)R_v:G(t)\; \;G(t^+) that transforms the DIG by modifying, removing, or creating nodes and edges. We elaborate these operators next. Canonical Rewrite Operators. Let Oa(t)⊆ℰO_a(t) denote the new events generated by agent a during activation; these become newly created event nodes in the DIG. The standard interaction primitives induce the following canonical edge rewrite patterns: (1) Respond (R): The agent acts on all buffered events, Ia(t)=Ba(t)I_a(t)=B_a(t) and Ba(t+)=∅B_a(t^+)= , and labels all incoming edges as consumed, ϕv(e,v)=consume _v(e,v)= consume. The DIG is rewritten by removing all input events from the agent buffer and generating new event nodes, G(t+)=G(t)∖EGin(v)∪(v,e′)∣e′∈Oa(t).G(t^+)=G(t) E_G^in(v)\;∪\;\(v,e ) e ∈ O_a(t)\. (2) Wait (W): The agent preserves its buffer, Ba(t+)=Ba(t)B_a(t^+)=B_a(t), and labels all incoming edges as delayed, ϕv(e,v)=delay _v(e,v)= delay. No graph modification is applied: G(t+)=G(t)G(t^+)=G(t). (3) Reroute (R): The agent forwards selected events, Ba(t+)=Ba(t)∖Ia(t)B_a(t^+)=B_a(t) I_a(t), and labels their edges as rerouted, ϕv(e,v)=reroute _v(e,v)= reroute. Each such edge is redirected:(e,v)↦(e,v′).(e,v)\; \;(e,v ). (4) Discard (D): The agent drops selected events, Ba(t+)=Ba(t)∖Ia(t)B_a(t^+)=B_a(t) I_a(t), and labels the edges as discarded, ϕv(e,v)=discard _v(e,v)= discard. The edges are removed:(e,v)↦∅.(e,v)\; \; . (5) Submit (S): A terminal Respond with Oa(t)=e∞O_a(t)=\e_∞\, yielding G(t+)=G(t)∖EGin(v)∪(v,e∞).G(t^+)=G(t) E_G^in(v)\;∪\;\(v,e_∞)\. The overall system execution is the composition of local graph rewrites induced by activation nodes: G0→ℛv1G1→ℛv2⋯→ℛvTGT,G_0 R_v_1G_1 R_v_2·s R_v_TG_T, (6) where each ℛvt∈(R),(W),(RR),(D),(S)Rv_t∈(R),(W),(R),(D),(S) is determined by the edge labeling function ϕvtφv_t. Edge Attribution. We attribute each edge one of two attribution types: productive or non-productive (transient). Productive edges indicate interactions that advance the cooperative solution, while non-productive edges indicate interactions that do not advance it at the current step. Edges corresponding Wait (W) and Discard (D) are non-productive and drawn as dashed. For Reroute (R), the edge to the rerouting agent is non-productive and dashed, while the redirected edge to the final recipient is productive and solid. Fig. 2 (3–4) illustrate this distinction: solid lines denote productive edges, and dashed lines denote non-productive edges. Illustration. Cooperative multi-agent execution is thus a graph rewriting dynamical system. As illustrated in Fig. 2 (3), agents coordinate not through predefined roles or control flow, but by applying local edge-level rewrites to the DIG. Emergent cooperation structure, system-level behavior, and failure modes arise from the composition of these local edge-level rewrite operators, making DIG the effective state space of cooperative intelligence. 4.3 DIG as a Representation of Cooperative Intelligence In this section, we show that DIG representation G(t)t∈ℤ\G(t)\_t is not merely a visualization artifact, but an intermediate operational state space for system-level reasoning over cooperation. Thus, DIG provides the core representation of cooperative intelligence. DIG as a Labeled Causal Interaction Graph. For any logical time t, let G(t)=(A(t)∪E(t),ℰG(t),ϕt),G(t)= (V_A(t) _E(t),\,E_G(t),\, _t ), (7) where (A(t)∪E(t),ℰG(t))(V_A(t) _E(t),E_G(t)) is the directed bipartite causal topology defined in Sec. 4.1, and ϕt:ℰG(t)⟶consume,delay,reroute,discard _t:E_G(t) \ consume, delay, reroute, discard\ is the edge-action labeling induced by local rewrite operators (Sec. 4.2). Thus, each G(t)G(t) is a fully labeled causal interaction graph, encoding both who interacted with whom and how each interaction edge was operationally treated. This formalism characterizes cooperative behavior structurally. Given an execution trace T, we group together all traces that induce the same time-indexed labeled DIG: ()=′∣Ψ(′)≅Ψ()C(T)=\T (T ) (T)\. Here, ≅ denotes graph isomorphism that preserves bipartite node types, directed edges, and edge labels. Thus, cooperative behavior is characterized by observable interaction structure rather than agent internals. Equivalently, cooperation is encoded by the temporal evolution of DIG under the edge-level rewrite operators ϕt\ _t\, which specify how interactions are consumed, delayed, rerouted, or discarded. DIG as an Explainability Trace. The sequence G(t)t∈ℤ\G(t)\_t forms an explainability trace of cooperative intelligence. Any system-level behavior or failure signal f∈ℱf inferred from an execution trace T can be expressed as f=ℐ(G(t)t∈ℤ)=ℐ(ϕt(G(t))t∈ℤ)f=I(\G(t)\_t )=I(\ _t(G(t))\_t ) for some graph-level inference operator ℐI. Thus, explanations depend only on the labeled causal structure (A∪E,ℰG,ϕt)(V_A _E,E_G, _t) and not on unobservable agent internals. In this sense, DIG is not merely a representation of execution, but a causal explanation object for emergent multi-agent cooperation. Theorem 1 (Topological Inference Reduction). Fix a class C of cooperative multi-agent systems whose observable semantics are defined by asynchronous activations and event passing, as in Sec. 3. Let T be the space of observable execution traces, with ∈T denoting one trace, and let Ψ:→G(t)t∈ℤ :T→\G(t)\_t be the DIG construction operator. For any system-level functional Φ:→ℱ :T that depends only on observable interactions, equivalently, is invariant over traces with isomorphic DIGs, there exists a graph functional ℐ:G(t)t∈ℤ→ℱI:\G(t)\_t such that, for every trace ∈T , Φ()=ℐ(Ψ()) (T)=I( (T)). The proof of Theorem 1 is given in Appendix A. This result shows that all structurally observable system-level reasoning about cooperative intelligence reduces to inference over the DIG. Thus, diagnosis, explanation, and intervention are performed not on hidden agent internals, but on the topology and edge-action structure of the evolving causal interaction graph. 4.4 Problem-Solving in DIG We interpret cooperative problem solving as a structural transformation process over the DIG. Given an execution trace T and its induced DIG sequence G(t)t∈ℤ=Ψ()\G(t)\_t = (T), task progress is realized not through access to agent internals, but through the composition of local graph rewrite operators (Eq. (6)). Specifically, each activation node vt∈Av_t _A induces a rewrite ℛvtR_v_t through its edge-action operator ϕvt _v_t and output event set Oat(t)O_a_t(t). Each activation node v∈Av _A consumes an input set of events and produces an output set of events, as recorded by the incident edges in the DIG. Let Iv I_v =e∈E∣(e,v)∈ℰG,Ov =\\,e _E (e,v) _G\,\, O_v =e′∈E∣(v,e′)∈ℰG. =\\,e _E (v,e ) _G\,\. (8) denote the input events delivered to v and the output events generated by v, respectively. We interpret v:Iv↦Ovv:\;I_v\; \;O_v as a local problem-solving transformation. An activation is problem-generating if it expands the unresolved work, |Ov|>|Iv||O_v|>|I_v|, in which case each p∈Ovp∈ O_v is treated as a subproblem spawned from context IvI_v. It is problem-reducing if |Ov|≤|Iv||O_v|≤|I_v|, in which case each s∈Ovs∈ O_v is treated as a subsolution produced from context IvI_v. 5 Failure, Detection, and Healing Figure 3: Structural failure patterns in DIG, showing collaboration-invariant violations as interaction structure. The system defines errors not by agents’ Internal Reasoning, but by observable Interaction Primitives (actions taken by agents) and the corresponding DIG structures. Failure Taxonomy. Empirically, cooperative general agent systems exhibit failures that arise not from isolated reasoning mistakes within individual agents, but from breakdowns in interaction structure and execution dynamics. Fig. 3 summarizes the major classes of failures observed in our experiments. The taxonomy is defined in terms of observable execution structure, without access to agent internals or task semantics. We consider two classes of violated structural or temporal invariants: failures in preserving and exhausting work (Reachability and Coverage) and warnings indicating inefficient or risky handling of emitted work (Progress). In both classes, the detection method remains task- and domain-agnostic, as it operates on the interaction structure. Failure Detection and Healing. Whenever a new event e is generated at time t, the system temporarily blocks its delivery and evaluates the current G(t)G(t) for error patterns shown in Fig. 3. If a failure is detected, the system may heal it by (i) injecting new information into it before delivery, (i) injecting and rerouting it to a recipient set, or (i) creating a new event and delivering it to a recipient set. We broadly categorize failures into two types: (I) reachability and (I) progress failures. We detail the detection and healing procedure for each failure pattern below. (I) Reachability and Termination. All reachable work in the DIG should persist until consumed. The system should emit a single Submit event once all reachable work has been consumed. (1) Early termination (ET). Detection: A Submit event is generated despite unresolved reachable work. Formally, e∞∈VE(t)e_∞∈ V_E(t) and ∃e∈R(t)∃ e∈ R(t) without a directed path from e to e∞e_∞. Healing: apply (i) by injecting information about unresolved events and rerouting it to the agent that issued Submit. (2) Missing termination (MC). Detection: All reachable work is exhausted, but no Submit event is generated. Formally, R(t)=∅R(t)= and e∞∉VE(t)e_∞∉ V_E(t) for t exceeding a threshold. Healing: apply (i) by injecting information that all reachable work is exhausted. (3) Orphaned event (OE). Detection: An event is generated but has no recipients for longer than a reasonable time window. Formally, ∃e∈VE(t)∃ e∈ V_E(t), e≠e∞e≠ e_∞, such that its recipient set is empty, Rt(e)=∅R_t(e)= for longer than a reasonable time window. Healing: apply (i) by injecting status information and rerouting the event back to its generating agent. (4) Deadlock (DL). Detection: Reachable work remains, but no activation occurs within a reasonable time window. Formally, R(t)≠∅R(t)≠ while VA(t)=∅V_A(t)= for all t within a reasonable time window. Healing: apply (i) by creating a new event and broadcasting it to all agents to restart activity. (I) Progress. Generated events should be consumed downstream within a reasonable time; repeated deferral, rerouting, or redundant handling indicates risk. (1) Excessive rerouting (ER). Detection: An event is repeatedly Rerouted across activations without ever being Consumed. Formally, ∃e∈VE(t)∃ e∈ V_E(t) such that its delivery edges are rerouted more than a reasonable number of times. Healing: apply (i) by injecting information indicating repeated rerouting. (2) Cross-lineage aggregation (CLA). Detection: Events from different problem-generating activations are delivered to the same recipient agent. Formally, there exists v∈VA(t)v∈ V_A(t) and e≠e′∈Ive≠ e ∈ I_v such that there is no activation vgv_g whose generated events have a directed path to both e and e′e . Healing: apply (i) by injecting ancestry information into each event. (3) Repeated subproblem solving (RSP). Detection: Multiple problem-reducing activations Consume the same upstream event p. Formally, ∃p∈VE(t)∃ p∈ V_E(t) and problem-reducing activations v≠v′v≠ v such that p∈Iv∩Iv′p∈ I_v∩ I_v . Healing: apply (i) by injecting information on which part of the result may be repeated. Note that these depend entirely on agent interaction patterns as encoded in the DIG, allowing us to improve problem-solving without modifying agent internals or constraining their interactions. 6 Experiment Design Figure 4: Task structures. Left: Count Frequency (fully parallelizable), where tasks are decomposed into independent subtasks that can be processed and merged once completed. Right: Research Job (dependency-constrained), where tasks are organized into stages with inter-stage dependencies, and violations cause processing or merging failures. Open-ended, verifiable task-solving. We introduce a task-solving setting to evaluate how agent interactions modify task structure and how solving progress can be verified from those structural changes. Each agent i∈Ii∈ I has an integer capability ziz_i, and each task component g has an integer load ℓg _g, a state sg∈Unprocessed,Processeds_g∈\ Unprocessed, Processed\, and optional dependency constraints. There is no fixed structure for solving the task; it can be decomposed in different ways, assigned to different agents, or solved in different orders. When agents choose Respond during an activation, they may invoke tools. We provide three tools for changing task structures and states: Decompose, Process, and Merge. Decompose splits a task into assigned subtasks, Process marks a feasible task component as processed, and Merge combines processed and compatible components. Each decomposition, processing step, and merge then becomes a trackable task-structure change, making problem-solving structurally verifiable. Agent prompts and detailed tool semantics are provided in Appendices B and D. We penalize both incomplete and redundant task solving by measuring final task progress as: coverage=min(S,N)N,over=max(S−N,0)N,error=(1−coverage)+over,coverage= (S,N)N, = (S-N,0)N, =(1-coverage)+over, (9) where N is the target and S the submitted problem size. Setting Agents Load # Failure (↓ ) Error (↓ ) Time (↓ ) Homogeneous (1000) MAS-Only 4 4000 2.11±0.312.11± 0.31 0.083±0.1180.083± 0.118 13.0±9.113.0± 9.1 MAS+DIG 4 4000 2.60±1.802.60± 1.80 0.025±0.0750.025± 0.075 10.7±7.810.7± 7.8 Δ % +23%+23\% −70%-70\% −18%-18\% MAS-Only 4 8000 2.60±0.662.60± 0.66 0.688±0.0840.688± 0.084 14.3±8.414.3± 8.4 MAS+DIG 4 8000 9.10±1.459.10± 1.45 0.588±0.1380.588± 0.138 20.1±9.420.1± 9.4 Δ % +250%+250\% −15%-15\% +41%+41\% MAS-Only 6 6000 2.50±1.502.50± 1.50 0.100±0.2490.100± 0.249 9.2±1.09.2± 1.0 MAS+DIG 6 6000 2.60±1.802.60± 1.80 0.017±0.0500.017± 0.050 10.4±2.810.4± 2.8 Δ % +4%+4\% −83%-83\% +13%+13\% MAS-Only 6 12000 3.50±1.033.50± 1.03 0.850±0.0330.850± 0.033 19.4±12.719.4± 12.7 MAS+DIG 6 12000 8.80±0.988.80± 0.98 0.775±0.0650.775± 0.065 19.7±9.119.7± 9.1 Δ % +151%+151\% −9%-9\% +2%+2\% Heterogeneous ([…, 1000,100,10,1]) MAS-Only 4 1111 1.80±0.401.80± 0.40 0.000±0.0000.000± 0.000 8.9±0.98.9± 0.9 MAS+DIG 4 1111 2.50±1.862.50± 1.86 0.001±0.0030.001± 0.003 9.4±2.59.4± 2.5 Δ % +39%+39\% ≈0≈ 0 +6%+6\% MAS-Only 4 2222 2.60±0.802.60± 0.80 0.735±0.2660.735± 0.266 33.0±7.933.0± 7.9 MAS+DIG 4 2222 8.60±1.638.60± 1.63 0.533±0.3570.533± 0.357 42.9±8.642.9± 8.6 Δ % +231%+231\% −27%-27\% +30%+30\% MAS-Only 6 111111 2.10±0.302.10± 0.30 0.100±0.2680.100± 0.268 12.2±8.112.2± 8.1 MAS+DIG 6 111111 5.30±3.495.30± 3.49 0.092±0.2090.092± 0.209 16.8±9.416.8± 9.4 Δ % +152%+152\% −8%-8\% +38%+38\% MAS-Only 6 222222 2.70±1.102.70± 1.10 0.847±0.2790.847± 0.279 32.5±13.232.5± 13.2 MAS+DIG 6 222222 10.10±1.6410.10± 1.64 0.568±0.3720.568± 0.372 43.8±11.043.8± 11.0 Δ % +274%+274\% −33%-33\% +35%+35\% Table 1: CF with parallelizable tasks. Mean ± std (10 runs). Bold = better. Δ% \% = MAS+DIG vs. MAS-Only. Experiment Settings. We instantiate this setting with two task structures, shown in Fig. 4: (i) a fully parallelizable structure, implemented by Count Frequency (CF), where independent components can be processed in any order and merged after completion; (i) a dependency-constrained structure, implemented by Research Job (RJ), where components can be processed only after earlier stages are solved. We evaluate both homogeneous and heterogeneous agent teams: (i) in the homogeneous setting, all agents have the same capability, zi=1000z_i=1000; (i) in the heterogeneous setting, capabilities vary, e.g., zi∈1,10,100,1000z_i∈\1,10,100,1000\. We compare MAS-Only, which executes without DIG-based healing, with MAS+DIG, which detects and heals structural failures during execution. We further include MAS+LLM Judge, following prior work by Cemri et al. (2025), which invokes an LLM to diagnose failures using a predefined error taxonomy. Since this baseline is not designed for real-time monitoring, we adapt it by running the judge periodically every n activations using our error taxonomy (see Appendix C). We report final task error, detected errors, and running time, with statistical analysis in Appendix E. (a) MAS + DIG (3 agents) (b) MAS + LLM Judge Figure 5: With DIG (a), the timeline of agent activations, event propagation, and edge-level rewrites indicates stable coordination and successful task termination. Using an LLM as judge (b), the DIG trace reveals unstable coordination, excessive waiting and rerouting, and delayed interventions. 7 Experiment Results Setting # Failure (↓ ) Error (↓ ) Time (↓ ) Homogeneous (1000) MAS-Only 6.20±2.966.20± 2.96 0.50±0.300.50± 0.30 24.8±31.824.8± 31.8 MAS+DIG 8.40±1.698.40± 1.69 0.28±0.280.28± 0.28 17.9±2.217.9± 2.2 Δ % +35%+35\% −44%-44\% −28%-28\% Heterogeneous ([…, 1000,100,10,1]) MAS-Only 3.50±1.433.50± 1.43 0.55±0.150.55± 0.15 43.4±32.943.4± 32.9 MAS+DIG 8.70±1.858.70± 1.85 0.45±0.150.45± 0.15 68.6±26.768.6± 26.7 Δ % +149%+149\% −18%-18\% +58%+58\% Table 2: RJ with two problem sets, each containing two sequential stages. Stage load is 4000 in the homogeneous setting and 1111 in the heterogeneous setting; each experiment uses 4 agents. Mean ± std (10 runs). Bold = better. Δ% \% = MAS+DIG vs. MAS-Only. We first analyze DIG results on both Count Frequency and Research Job, and then present a 20-agent case study to demonstrate DIG’s scalability. Tab. 1 and 2 summarize the main results. Across both task structures, MAS+DIG reduces final error at the cost of detecting more failures and, in some settings, longer runtime. On Count Frequency (CF), DIG consistently improves final error in all settings, including an 83%83\% reduction in the homogeneous 6-agent load-6000 setting and a 33%33\% reduction in the heterogeneous 6-agent load-222222 setting. Errors mainly come from incomplete coverage and redundant work; DIG improves subtask coverage and prevents premature submission, even in settings with larger loads and more heterogeneous capabilities that create more possible execution paths. On Research Job (RJ), where errors are further complicated by dependency violations that cause failed processing and merging, DIG can detect these structural failures before they propagate to later stages, with 44%44\% and 18%18\% error reductions in the homogeneous and heterogeneous settings respectively. Figure 6: MAS + DIG (20 agents): Large-scale DIG showing structured task propagation, controlled rerouting, and stable convergence despite dense interactions and high concurrency. These gains come with a trade-off: DIG keeps the system active to repair failures, which may expose additional failures and increase runtime. MAS appears to have fewer detected errors and shorter runtime simply because it leaves failures unresolved and may submit incomplete solutions. The traces in Appendix G show the runtime traces and interaction patterns structurally: without DIG, interactions are more fragmented, with redundant work, rerouting, and unresolved events; with DIG, task propagation is more organized and termination is more stable. Compared with MAS+LLM Judge (Fig. 5(a) and 5(b)), DIG avoids expensive semantic judging and provides more targeted, real-time intervention during execution. The LLM Judge results also show that not all interventions are helpful: untargeted or delayed interventions can increase overhead and even worsen performance, while DIG’s structure-driven interventions are more directly tied to the observed failure patterns. Case Study with 20 Agents. We conduct a 20-agent case study on CF with load 100,000100,000 to test DIG under high interaction complexity. Without DIG-based healing, MAS fails to produce a result within 120 seconds; with DIG, the same 20-agent system produces a valid answer within 70 seconds using 92 calls. Fig. 6 shows the resulting DIG trace and activation timeline. Even with many agents operating in parallel, DIG detects interaction failures, including 1 missing completion error, 8 repeated-effort incidents, 2 dependency warnings, 1 orphaned event, and 4 early termination errors. These observations highlight that multi-agent collaboration is non-trivial: with more agents, the system becomes susceptible to interaction failures, making scalable reliability a central challenge. DIG can identify and heal such failures without assuming a fixed agent count, agent type, or problem domain. 8 Conclusion We introduce DIG, a Dynamic Interaction Graph framework for evaluating multi-agent collaboration. DIG models collaboration as a time-evolving causal network of agent activations and interactions, making collaborative dynamics observable and explainable. To the best of our knowledge, DIG is the first framework enabling real-time identification, interpretation, and correction of collaboration-induced error patterns directly from agents’ interaction paths. We view DIG as an open framework and welcome extensions to more agents and domains. Acknowledgments and Disclosure of Funding This work was supported in part by the Office of Naval Research under grant N000142412073 and the National Science Foundation under grants CNS-2533813 and CNS-2312761. References G. Agha (1986) Actors: a model of concurrent computation in distributed systems. MIT press. Cited by: §2. G. Antoniou and F. v. Harmelen (2009) Web ontology language: owl. In Handbook on ontologies, p. 91–110. Cited by: Appendix F, §2. A. Artale and E. Franconi (2000) A survey of temporal extensions of description logics. Annals of Mathematics and Artificial Intelligence 30 (1), p. 171–210. Cited by: Appendix F. F. Baader, I. Horrocks, and U. Sattler (2008) Description logics. Foundations of Artificial Intelligence 3, p. 135–179. Cited by: Appendix F, §2. M. Cemri, M. Z. Pan, S. Yang, L. A. Agrawal, B. Chopra, R. Tiwari, K. Keutzer, A. Parameswaran, D. Klein, K. Ramchandran, et al. (2025) Why do multi-agent llm systems fail?. arXiv preprint arXiv:2503.13657. Cited by: §1, §2, §6. J. Chen, H. Yang, Z. Liu, and C. Joe-Wong (2026) The five ws of multi-agent communication: who talks to whom, when, what, and why - a survey from MARL to emergent language and LLMs. Transactions on Machine Learning Research. Note: Survey Certification External Links: ISSN 2835-8856, Link Cited by: §1, §2. W. Chen, Y. Su, J. Zuo, C. Yang, C. Yuan, C. Qian, C. Chan, Y. Qin, Y. Lu, R. Xie, et al. (2023) Agentverse: facilitating multi-agent collaboration and exploring emergent behaviors in agents. arXiv preprint arXiv:2308.10848 2 (4), p. 5. Cited by: §2. R. De Nicola (2014) A gentle introduction to process algebras. Notes 7. Cited by: Appendix F, §2. Z. Durante, Q. Huang, N. Wake, R. Gong, J. S. Park, B. Sarkar, R. Taori, Y. Noda, D. Terzopoulos, Y. Choi, et al. (2024) Agent ai: surveying the horizons of multimodal interaction. arXiv preprint arXiv:2401.03568. Cited by: §1. W. Fokkink (2013) Introduction to process algebra. springer science & Business Media. Cited by: Appendix F, §2. S. Gandhi, J. Tsay, J. Ganhotra, K. Kate, and Y. Rizk (2025) When agents go astray: course-correcting swe agents with prms. arXiv preprint arXiv:2509.02360. Cited by: §1, §2. J. He, C. Treude, and D. Lo (2025) Llm-based multi-agent systems for software engineering: literature review, vision, and the road ahead. ACM Transactions on Software Engineering and Methodology 34 (5), p. 1–30. Cited by: §1. H. Hermanns, U. Herzog, and J. Katoen (2002) Process algebra for performance evaluation. Theoretical computer science 274 (1-2), p. 43–87. Cited by: Appendix F. Y. Kim, K. Gu, C. Park, C. Park, S. Schmidgall, A. A. Heydari, Y. Yan, Z. Zhang, Y. Zhuang, Y. Liu, et al. (2025) Towards a science of scaling agent systems. arXiv preprint arXiv:2512.08296. Cited by: §1. F. Kong, R. Zhang, H. Yin, G. Zhang, X. Zhang, Z. Chen, Z. Zhang, X. Zhang, S. Zhu, and X. Feng (2025) Aegis: automated error generation and attribution for multi-agent systems. arXiv preprint arXiv:2509.14295. Cited by: §1, §2. [16] LangGraph. Note: https://w.langchain.com/langgraph Cited by: §2. X. Li, S. Wang, S. Zeng, Y. Wu, and Y. Yang (2024) A survey on llm-based multi-agent systems: workflow, infrastructure, and challenges. Vicinagearth 1 (1), p. 9. Cited by: §1. F. Lin, S. Chen, R. Fang, H. Wang, and T. Lin (2025) Stop wasting your tokens: towards efficient runtime multi-agent systems. arXiv preprint arXiv:2510.26585. Cited by: §2. J. L. Peterson (1977) Petri nets. ACM Computing Surveys (CSUR) 9 (3), p. 223–252. Cited by: §2. J. Schulman, N. Heess, T. Weber, and P. Abbeel (2016) Gradient estimation using stochastic computation graphs. External Links: 1506.05254, Link Cited by: §2. Q. Wang, T. Wang, Z. Tang, Q. Li, N. Chen, J. Liang, and B. He (2025) MegaAgent: a large-scale autonomous llm-based multi-agent system without predefined sops. In Findings of the Association for Computational Linguistics: ACL 2025, p. 4998–5036. Cited by: §2. C. Wu, Z. Zhang, M. Xu, Z. Wei, and M. Sun (2025) Monitoring llm-based multi-agent systems against corruptions via node evaluation. arXiv preprint arXiv:2510.19420. Cited by: §2. Q. Wu, G. Bansal, J. Zhang, Y. Wu, S. Zhang, E. Zhu, B. Li, L. Jiang, X. Zhang, and C. Wang (2023) Autogen: enabling next-gen llm applications via multi-agent conversation framework. arXiv preprint arXiv:2308.08155. Cited by: §2. B. Yan, Z. Zhou, L. Zhang, L. Zhang, Z. Zhou, D. Miao, Z. Li, C. Li, and X. Zhang (2025) Beyond self-talk: a communication-centric survey of llm-based multi-agent systems. arXiv preprint arXiv:2502.14321. Cited by: §2. H. Yang, J. Chen, M. Siew, T. Lorido-Botran, and C. Joe-Wong (2025) LLM-powered decentralized generative agents with adaptive hierarchical knowledge graph for cooperative planning. External Links: 2502.05453, Link Cited by: §1. C. Yu, S. Lu, C. Zhuang, D. Wang, Q. Wu, Z. Li, R. Gan, C. Wang, S. Hou, G. Huang, W. Yan, L. Hong, A. Xue, Y. Wang, J. Gu, D. Tsai, and T. Lin (2025) AWorld: orchestrating the training recipe for agentic ai. External Links: 2508.20404, Link Cited by: §1, §2. G. Zhang, J. Wang, J. Chen, W. Zhou, K. Wang, and S. Yan (2025a) AgenTracer: who is inducing failure in the llm agentic systems?. arXiv preprint arXiv:2509.03312. Cited by: §1, §2. S. Zhang, M. Yin, J. Zhang, J. Liu, Z. Han, J. Zhang, B. Li, C. Wang, H. Wang, Y. Chen, et al. (2025b) Which agent causes task failures and when? on automated failure attribution of llm multi-agent systems. arXiv preprint arXiv:2505.00212. Cited by: §1, §2. Appendix A Theoretical Results A.1 Proof for Theorem. 1 Proof. Because Φ depends only on observable interactions, it is constant on each behavioral equivalence class induced by DIG isomorphism. Concretely, for any 1,2∈T_1,T_2 , Ψ(1)≅Ψ(2)⟹Φ(1)=Φ(2). (T_1) (T_2) (T_1)= (T_2). (10) Define ℐI on the range of Ψ by selecting any trace ∈T such that Ψ()=G(t)t∈ℤ (T)=\G(t)\_t and setting ℐ(G(t)t∈ℤ)≜Φ().I (\G(t)\_t ) (T). (11) This definition is well-defined: if another trace ′∈T satisfies Ψ(′)=G(t)t∈ℤ (T )=\G(t)\_t , then Ψ(′)≅Ψ() (T ) (T), so Eq. (10) gives Φ(′)=Φ() (T )= (T). Hence Eq. (11) does not depend on the chosen representative trace. Finally, for any trace ∈T , (ℐ∘Ψ)()=ℐ(Ψ())=Φ(),(I )(T)=I ( (T) )= (T), (12) where the second equality follows from Eq. (11). Therefore, Φ=ℐ∘Ψ =I . ∎ Appendix B General Agent Agent Instructions Template You are agent_name, an autonomous agent in a cooperative multiagent problem-solving system. GOAL: Work with your collaborators to solve the problem in the SHORTEST TIME (minimum stages) possible. Coordinate efficiently and avoid redundant work. PROBLEM CONTEXT problem_spec stage_progress AVAILABLE AGENTS: agent_list INPUT EVENT ACTIONS For each pending event, specify ONE action: ‘consume’ - Process this event. MUST produce output event(s) OR use a tool. If you consume, you MUST generate something (event or tool call). If you’re not ready to process it, use ‘wait’ instead. If you don’t want it, use ‘discard’ instead. ‘reroute’ - Forward to other agents. MUST specify reroute_to recipients. ‘discard’ - Drop permanently (for duplicates/irrelevant events). ‘wait’ - Keep in buffer for later (need more data first). HOW TO PICK ACTION FOR EACH EVENT For PROBLEM events (without raw data): CONSUME: you MUST use a tool (split_problem_at_high_level, use_skill, or get_raw_data_of_problem). REROUTE: forward to another agent if you’re busy. WAIT: keep for later if you have higher priority work. For SKILL RESULT events (info.skill is set): CONSUME: read info.skill_result, then merge with other partials or submit. WAIT: if you are expecting more partial results before merging. For RAW DATA events: CONSUME: compute solution and output a solution event; share your solution to others to speed up the process. WAIT: if you need more data first. For SOLUTION events: CONSUME: aggregate with other solutions you have. DISCARD: if it’s a duplicate of information you already have. WAIT: if you’re expecting more solutions to aggregate. AGGREGATION: When consuming multiple solution events, reduce redundancy and output ONE combined solution. SUBMIT: Set is_final_answer=True when your solution is complete or good enough. To submit after a merge: include yourself in merge recipients, then in the NEXT activation call use_skill(submit, result_event_id=<merged_event_id>) and set is_final_answer=True. NEVER call merge and submit in the same activation --- always two separate activations. HANDLING MULTIPLE INPUTS: Prioritize aggregation if you have multiple solutions. Stay focused on one task type per activation. EVENT TYPES ‘problem’ - A task to solve. Use use_skill(decompose/process) to handle it server-side. ‘skill result’ - Compact result from use_skill(process/merge). Check info.skill_result. Merge partials with use_skill(merge) or use use_skill(submit) when complete. ‘solution’ - Final answer. ONLY create via use_skill(submit) or is_final_answer=True. ‘process_error’ - Your process call was rejected because the problem exceeds your capacity. info.error_type = ‘capacity_exceeded’, info.problem_id = the problem you tried to process, info.problem_size = actual number of elements, info.agent_capacity = your maximum capacity. You MUST handle this event. Two options: (a) Decompose: use_skill(decompose, problem_id, assignments=AgentX: size1, AgentY: size2, ...) so each chunk size <= the recipient’s capacity. (b) Reroute: use_skill(decompose, problem_id, assignments=CapableAgent: full_size) to delegate the whole problem to one agent with sufficient capacity. ‘merge_error’ - Your merge call was rejected because one or more tasks have not been processed yet (no skill_result available). info.error_type = ‘unprocessed_tasks’, info.attempted_event_ids = the event IDs you passed to merge, info.unprocessed = list of (event_id, load) pairs for unprocessed tasks, info.message = human-readable description of what went wrong. You MUST handle this event. First process the unprocessed tasks: use_skill(process, problem_id) for each unprocessed task, then retry the merge once all tasks have skill_results. event_examples TOOLS If you consume a PROBLEM event without raw data, you MUST use a tool (split_problem_at_high_level, use_skill, or get_raw_data_of_problem). Prefer use_skill(decompose) over split_problem_at_high_level for automated splitting. Prefer use_skill(process) over get_raw_data_of_problem to avoid raw data in the prompt. Do NOT also create out_events for the same consumed PROBLEM. You MUST still create out_events for any other consumed inputs not handled by a tool (e.g., aggregated solution events). NEVER embed raw result data (counts, arrays, computed values) in out_events payloads. To share a result with another agent, include them in the recipients of use_skill(process) or use_skill(merge) --- the skill result event will be delivered to them directly. You can also reroute a received skill result event to additional agents. Other agents merge results using use_skill(merge, event_ids=[...]) with the event IDs. tools_description capability_explain OUTPUT FORMAT input_actions: REQUIRED. event_id, action, reroute_to (if rerouting) is_final_answer: Set to True when you want to SUBMIT a final solution. If you have a reasonable answer, submit it! tool_requests OR out_events (mutually exclusive) reasoning: observation, thought, action FINAL SUBMISSION payload must include: "type": "solution", "problem_id": "P", "solution": ... NO EMPTY ACTIVATIONS: You MUST use tools OR generate output events (or both). You cannot do neither. REASONING GUIDANCE Be compact. Include only important details needed to justify actions and help teammates. Appendix C LLM Judge Error Taxonomy for Cooperative Multi-Agent Systems This document defines a structural failure taxonomy for cooperative multi-agent systems in terms of observable interaction patterns in the Dynamic Interaction Graph (DIG), independent of agent internals or task semantics. Reachability and Termination (Failures) All reachable work in the DIG should persist until some activation consumes it. The system should emit a single Submit event, and only after all reachable work has been consumed. • Early termination (ET): a Submit event is generated while some reachable work remains unconsumed. • Missing termination (MC): all reachable work has been consumed, but no Submit event is generated within a reasonable time window. • Orphaned event (OE): an event is generated but becomes unreachable before any activation can consume it, either because it is discarded or because it is assigned invalid recipients. • Deadlock (DL): reachable work remains, but all activated agents wait indefinitely, making progress impossible. Progress (Warnings) Generated events should be consumed downstream within a reasonable time; repeated deferral, rerouting, or redundant handling indicates risk. • Excessive rerouting (ER): an event is repeatedly Rerouted across activations without any activation Consumeing it to generate downstream events. • Cross-lineage aggregation (CLA): an activation Consumes events from different lineages. • Repeated subproblem solving (RSP): multiple problem-reducing activations generate outputs whose coverage overlaps on the same upstream event. Intended Use • Monitoring emergent cooperation • Early failure detection • Structure-driven system healing • Explainable debugging of multi-agent executions LLM Judge System Prompt You are an expert system monitor for cooperative multi-agent systems. Your role is to analyze the Dynamic Interaction Graph (DIG) and detect structural errors based solely on observable interaction patterns. You do not have access to agent internals, reasoning traces, task semantics, or predefined workflows. All judgments must be derived from DIG topology, event lineage, and interaction primitives (CONSUME, DELAY, REROUTE, DISCARD, SUBMIT). Error Taxonomy file_input DIG Log file_input Your Task • Identify errors using the taxonomy above • Assess severity (critical/high/medium/low) • Recommend conservative interventions only when necessary • Provide clear reasoning for your decisions Intervention Methods • inject_system_message: Add guidance to existing event and optionally reroute to different agents • create_system_event: Create new intervention event with message to specific agents Intervention Methods • inject_info: Inject new information into the blocked event before delivery. • inject_and_reroute: Inject guidance into the blocked event and reroute it to a specified recipient set. • create_system_event: Create a new system-level event and deliver it to a specified recipient set. Principles • Intervene when error is clear and intervention helps • Prioritize FAILURES over RISKS • Provide actionable, specific recommendations • Respect agent autonomy where appropriate Appendix D Tool Semantics Agents may invoke tools only during Respond activations. We use three tools to modify task structures and states: Decompose(g,i:ℓii∈I),Process(g),Merge(gkk=1K). Decompose(g,\i: _i\_i∈ I), Process(g), Merge(\g_k\_k=1^K). Decompose. Decompose partitions task g into subtasks assigned to agents i, where ℓi _i is the load assigned to agent i. If the total assigned load exceeds the load of g, the decomposition fails. If the total assigned load is smaller, the unassigned remainder is generated as a new task and routed back to the source agent. Process. Process attempts to change a task component from Unprocessed to Processed. The call succeeds only if the acting agent has sufficient capability for the task load and all dependency constraints of the task component are satisfied. Merge. Merge combines multiple task components into a larger result. The call succeeds only if all input components are processed and structurally compatible. Otherwise, the merge fails and a failure message is returned to the source agent. Appendix E Significance Tests For each setting, we treat experiment runs as independent samples with and without DIG. We use one-sided Mann–Whitney U tests to evaluate each metric separately, under the hypotheses that DIG leads to lower task error, higher detected errors, and longer runtime. We further use MANOVA to test the joint effect on all three metrics. Table 3 reports our results. Overall, DIG consistently yields significantly higher detected errors in most settings (p<0.05p<0.05), indicating improved failure visibility. Improvements in task error are observed in some settings but not uniformly. This suggests that while DIG reliably exposes structural failures, local interventions are not always sufficient to fully resolve them, highlighting the need for more advanced healing strategies. We also observe that MANOVA shows significant effects in more complex settings, indicating that DIG has more potential under higher interaction complexity. Table 3: Significance test results comparing runs with and without DIG. Values report one-sided Mann–Whitney U test p-values for individual metrics and MANOVA p-values for the joint effect across all three metrics. Asterisks indicate significance at p<0.05p<0.05. Domain Setting Detected Errors Task Error Runtime MANOVA (p) (p) (p) (p) CF 4-agent homo 4000 0.531 0.124 0.988 0.069 CF 4-agent homo 8000 0.000∗ 0.037∗ 0.001∗ 0.000∗ CF 4-agent hetero 1111 0.178 0.864 0.715 0.712 CF 4-agent hetero 2222 0.000∗ 0.038∗ 0.007∗ 0.000∗ CF 6-agent homo 6000 0.500 0.271 0.121 0.488 CF 6-agent homo 12000 0.000∗ 0.004∗ 0.032∗ 0.000∗ CF 6-agent hetero 111111 0.020∗ 0.867 0.052 0.064 CF 6-agent hetero 222222 0.000∗ 0.061 0.013∗ 0.000∗ Research homo 1000 0.021∗ 0.066 0.009∗ 0.041∗ Research hetero 1111 0.000∗ 0.096 0.013∗ 0.000∗ Appendix F Detailed Comparison with Description Logics and Process Algebras Description Logics (DLs). DLs model entities as persistent nodes and relationships as directed edges within a well-specified schema, enabling strong decidability guarantees but at the cost of expressiveness for interaction modeling (Baader et al., 2008). Since entities are often collapsed into a single persistent node, DLs do not naturally capture interaction histories or evolving interaction structure. While some DL-based frameworks, such as OWL (Antoniou and Harmelen, 2009) or temporal DLs (Artale and Franconi, 2000), allow modeling evolving properties or actions, the object of analysis is typically state change rather than the evolving interactions themselves. In DIG, agent activations appear as distinct, time-stamped nodes, and interactions are mediated through event nodes with explicit causal dependencies. Relationships in DIG are dynamically induced by agents through events during execution. By preserving activations separately, DIG tracks how events are transformed, divided, delayed, rerouted, or consumed across agents, ensuring that failure patterns such as repeated rerouting, orphaned events, or cross-lineage aggregation remain distinguishable and can be detected and, ideally, corrected in real time as agents interact. Process Algebras (PAs). PAs model concurrent systems and verify their properties (De Nicola, 2014), and they have been applied to performance evaluation of stochastic systems Hermanns et al. (2002). Many classical approaches rely on interleaving semantics, representing concurrency as nondeterministic sequential patterns, and typically assume predefined communication primitives Fokkink (2013). While PAs excel at verifying protocols, they often abstract internal agent-to-agent transitions as silent actions, treating structurally different interaction paths as equivalent if they produce the same observable outcomes. To analyze LLM cooperative problem solving, understanding how a task changes is critical. Instead of verifying predefined protocols, DIG observes and constructs the true interaction structure as it dynamically unfolds. While abstracting away internal node decisions, DIG explicitly preserves inter-node interactions, treating the task as an evolving entity whose lifecycle is captured by the interaction structure. By tracking how interactions propagate and by using edge labels to distinguish productive from non-productive interactions, DIG enables reasoning about task progress and structural inefficiencies, such as effective decomposition versus redundant work or excessive rerouting. Notably, graph rewrite operators allow dynamic modifications to how previously generated events are handled, such as rerouting. Compared to PAs or DLs, DIG is more expressive for modeling the sequential, time-evolving nature of stochastic and emergent interactions in unconstrained LLM agents at runtime. Because relationships in DIG are dynamically generated rather than defined within a fixed schema or protocol, DIG prioritizes reasoning over evolving interaction structure rather than formal decidability or protocol guarantees. We view DLs and PAs as complementary to our setting, as they may help define and reason about additional structural invariants on top of DIG. Appendix G Example traces Figure 7: Count Frequency example (Homogeneous_4000, 4 agents). The problem is within the group’s capability. Agent 1 decomposes the task for parallel execution, but due to asynchrony and partial observability, agents may ignore subtasks, reroute unnecessarily, or duplicate work. These stochastic behaviors make cooperation brittle, which DIG captures and helps diagnose. Figure 8: Count Frequency example (Homogeneous_8000, 4 agents, w/o DIG). The problem exceeds the group’s capability. Agents continue to decompose tasks, resulting in a more complex structure of problem-solving and interaction. Figure 9: Count Frequency example (Homogeneous_8000, 4 agents, w/ DIG). DIG mitigates early termination and redundant work, improving the cooperation structure and overall performance. Figure 10: Count Frequency example (Heterogeneous_2222, 4 agents, w/o DIG). The problem exceeds group capability. Agents decompose tasks based on downstream capacity, leading to uneven interaction patterns. Figure 11: Count Frequency example (Heterogeneous_2222, 4 agents, w/ DIG). DIG monitors interactions and intervenes in real time, improving coordination despite increased complexity. Figure 12: Research domain (Heterogeneous_1111, 4 agents, w/o DIG). Agents initially operate on the same stage and progressively move forward. However, due to the more complex task structure, errors are more likely: agents may merge incompatible results, violate dependencies, or terminate early under partial observability. Figure 13: Research domain (Heterogeneous_1111, 4 agents, w/ DIG). DIG monitors interaction structure and detects violations of graph-level invariants, improving coordination even in complex task settings.