An interaction graph that makes emergent cooperation observable and enables structure-driven detection and healing for general-purpose LLM agent teams.
DIG represents emergent LLM-agent collaboration. Emergent means nothing is predefined: no protocol, workflow, role structure, or communication constraints. DIG records whatever actually happens at run time.
A pool of autonomous LLM agents works on a shared task, each operating independently and non-deterministically. Coordination and decomposition emerge from local decisions, so unstructured interactions can produce redundant work and cascading failures.
We introduce the Dynamic Interaction Graph (DIG) - a time-evolving graph of events flowing between agents and activations where agents consume inputs and produce outputs. DIG is LLM-agnostic, environment-agnostic, and framework-agnostic: it can monitor an existing agent framework or provide its own event delivery layer.
We consider cooperative problem solving in systems of multiple general-purpose agents that interact asynchronously via message passing, with no predefined roles, workflow, or communication protocols. DIG records the collaboration that emerges as one observable graph, rather than assuming the structure in advance.
System model $\mathcal{S} = (\mathcal{A}, \mathcal{E}, \mathcal{P}, \mathbb{Z})$: a set of agents $\mathcal{A}=\{a_1,\dots,a_N\}$, interaction events $\mathcal{E}$, problem instance $\mathcal{P}$ (encoded as an initial event $e_0$ delivered at $t=0$), and discrete logical time $\mathbb{Z}$. Execution terminates when a terminal event $e_\infty$ is generated.
Agents are modeled as autonomous decision-making units with no predefined role. We abstract away agent internals and model only observable interaction behavior: $f_a : I_a \to O_a$, where $I_a, O_a \subseteq \mathcal{E}$. Each agent maintains a local event buffer $B_a(t)$; activation occurs when the buffer changes while the agent is idle.
Events $e = (p_e, \pi_e)$ are the things that flow between agents: messages, subproblems, results, code snippets, or file artifacts. Each event carries a payload $p_e$ and a delivery policy $\pi_e$ that determines recipients $R_t(e) \subseteq \mathcal{A}$ at each logical time. For example, a user request "Implement a sorting algorithm" is delivered as an initial event $e_0$; an agent responding with code produces a new event carrying that code to downstream agents. The event expires when $\pi_e'$ is empty.
Execution trace $\mathcal{T} = \{(a_t, e_t, t)\}_{t \in \mathbb{Z}}$ records the activated agent and generated/delivered event at each logical time step.
Failures may arise from intermediate interaction structure - stalled activations, lost subproblems, duplicated work, or premature termination. We study the inference problem: given only an observable trace $\mathcal{T}$, infer a diagnosis $\Phi : \mathcal{T} \to \mathcal{F}$ operating solely on observable interaction structure, without access to agent internals or payload semantics.
DIG represents execution as a bipartite directed graph $G(t) = (\mathcal{V}_A(t) \cup \mathcal{V}_E(t),\, \mathcal{E}_G(t))$ with two node types: activation nodes $v \in \mathcal{V}_A$ (agent activations at logical time $t$) and event nodes $e \in \mathcal{V}_E$ (messages, artifacts, system events). Edges capture generation and delivery relationships.
The DIG evolves through local graph rewrite operators induced by agent activations. When agent $a$ is activated at time $t$, let $B_a(t)$ be its event buffer and $I_a(t) \subseteq B_a(t)$ the selected inputs. These correspond to incoming edges $E_G^{\mathrm{in}}(v) = \{(e,v) \in \mathcal{E}_G(t)\}$. A global edge rewrite semantics $\phi_v : E_G^{\mathrm{in}}(v) \to \{\texttt{consume}, \texttt{delay}, \texttt{reroute}, \texttt{discard}\}$ assigns an action label to each edge, inducing a local rewrite $\mathcal{R}_v : G(t) \to G(t^+)$.
Canonical Rewrite Operators
| Respond (R) | $I_a(t)=B_a(t)$; all edges labeled consume; input events removed from buffer, output edges $\{(v,e') \mid e' \in O_a(t)\}$ added. |
| Wait (W) | $B_a(t^+)=B_a(t)$; all edges labeled delay; no graph modification, $G(t^+)=G(t)$. |
| Reroute (RR) | Selected edges labeled reroute; each edge redirected $(e,v) \mapsto (e,v')$ to a new recipient. |
| Discard (D) | Selected edges labeled discard; edges removed $(e,v) \mapsto \emptyset$. |
| Submit (S) | Terminal Respond with $O_a(t)=\{e_\infty\}$; produces the final terminal event node. |
Global Execution Semantics. The overall system execution is the composition of local graph rewrite operators induced by activation nodes:
$$G_0 \xrightarrow{\mathcal{R}_{v_1}} G_1 \xrightarrow{\mathcal{R}_{v_2}} \cdots \xrightarrow{\mathcal{R}_{v_T}} G_T$$
where each $\mathcal{R}_{v_t} \in \{R,\, W,\, RR,\, D,\, S\}$ is determined by the edge-action labeling function $\phi_{v_t}$. The resulting trace $G_T$ is the DIG used for failure detection, diagnosis, and healing.
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. The taxonomy is defined in terms of observable execution structure, without access to agent internals, task semantics, or predefined workflows. We consider two distinct 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). This separation enables precise monitoring, diagnosis, and intervention. Detection remains task- and domain-agnostic, as it operates on interaction structure alone.
Detection and Healing. Whenever a new event $e$ is generated at time $t$, DIG temporarily blocks its delivery and evaluates the current interaction graph $G(t)$ for structural error patterns. When a failure is detected, the system may (i) inject new information into the event before delivery, (ii) inject and reroute it to a corrected recipient set, or (iii) create a new event and deliver it to a recipient set to heal from the failure.
| Failure Category | Failure pattern | Detection & Healing |
|---|---|---|
|
Reachability and Coverage
All reachable work should persist until consumed. 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. Formally, $e_\infty \in V_E(t)$ and $\exists\, e \in R(t)$ with no directed path from $e$ to $e_\infty$. |
Detection: Submit generated despite unresolved reachable work. Healing (ii): Inject information about unresolved events; reroute Submit back to the issuing agent. |
| Missing termination (MC): all reachable work has been consumed, but no Submit event is generated within a reasonable time window. Formally, $R(t)=\emptyset$ and $e_\infty \notin V_E(t)$ past a threshold. |
Detection: Reachable set exhausted with no Submit. Healing (i): Inject a signal that all reachable work is exhausted. |
|
| Orphaned event (OE): an event is generated but has no recipients for longer than a reasonable time window. Formally, $\exists\, e \in V_E(t),\, e \neq e_\infty$ with $R_t(e)=\emptyset$. |
Detection: Generated event with empty recipient set past timeout. Healing (ii): Inject status information; reroute the event back to its generating agent. |
|
| Deadlock (DL): reachable work remains but no activation occurs within a reasonable window. Formally, $R(t)\neq\emptyset$ while $V_A(t)=\emptyset$ across a time window. |
Detection: Pending work with no active agent past timeout. Healing (iii): Create a new event and broadcast to all agents to restart activity. |
|
|
Progress
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 being Consumed. Formally, $\exists\, e \in V_E(t)$ whose delivery edges are rerouted more than a reasonable threshold. |
Detection: Reroute count on an event exceeds threshold. Healing (i): Inject information indicating repeated rerouting into the event. |
| Cross-lineage aggregation (CLA): events from different problem-generating activations are delivered to the same recipient. Formally, $\exists\, v \in V_A(t)$ and $e \neq e' \in I_v$ with no common generating activation ancestor. |
Detection: Inputs to an activation span multiple unrelated lineages. Healing (i): Inject ancestry information into each event. |
|
| Repeated subproblem solving (RSP): multiple problem-reducing activations consume the same upstream event $p$. Formally, $\exists\, p \in V_E(t)$ and problem-reducing activations $v \neq v'$ with $p \in I_v \cap I_{v'}$. |
Detection: Same upstream event consumed by multiple reducers. Healing (i): Inject information on which part of the result may be repeated. |
We evaluate DIG on two verifiable task structures with agent capability constraints: Count Frequency (CF), a fully parallelizable task, and Research Job (RJ), a dependency-constrained task with staged processing and merging. Results report detected structural failures, final task error, and runtime, with mean +/- standard deviation over 10 runs. We compare MAS-Only with MAS+DIG, and use MAS+LLM Judge as a qualitative baseline for real-time intervention overhead.
DIG consistently reduces final error across CF settings. Although CF is parallelizable, each agent has a capability limit, so larger loads must be decomposed and assigned across agents. The improvement is largest when coordination is harder: more agents, larger loads, or heterogeneous capabilities create more opportunities for incomplete coverage, redundant work, and premature submission.
| Setting | Method | Agents | Load | # Failure | Error | Time (s) |
|---|---|---|---|---|---|---|
| Homogeneous agents, capability 1000 | ||||||
| MAS-Only | 4 | 4000 | 2.11 +/- 0.31 | 0.083 +/- 0.118 | 13.0 +/- 9.1 | |
| Error -70% | MAS+DIG | 4 | 4000 | 2.60 +/- 1.80 | 0.025 +/- 0.075 | 10.7 +/- 7.8 |
| MAS-Only | 4 | 8000 | 2.60 +/- 0.66 | 0.688 +/- 0.084 | 14.3 +/- 8.4 | |
| Error -15% | MAS+DIG | 4 | 8000 | 9.10 +/- 1.45 | 0.588 +/- 0.138 | 20.1 +/- 9.4 |
| MAS-Only | 6 | 6000 | 2.50 +/- 1.50 | 0.100 +/- 0.249 | 9.2 +/- 1.0 | |
| Error -83% | MAS+DIG | 6 | 6000 | 2.60 +/- 1.80 | 0.017 +/- 0.050 | 10.4 +/- 2.8 |
| MAS-Only | 6 | 12000 | 3.50 +/- 1.03 | 0.850 +/- 0.033 | 19.4 +/- 12.7 | |
| Error -9% | MAS+DIG | 6 | 12000 | 8.80 +/- 0.98 | 0.775 +/- 0.065 | 19.7 +/- 9.1 |
| Heterogeneous agents, capabilities [..., 1000, 100, 10, 1] | ||||||
| MAS-Only | 4 | 1111 | 1.80 +/- 0.40 | 0.000 +/- 0.000 | 8.9 +/- 0.9 | |
| Error approx. 0 | MAS+DIG | 4 | 1111 | 2.50 +/- 1.86 | 0.001 +/- 0.003 | 9.4 +/- 2.5 |
| MAS-Only | 4 | 2222 | 2.60 +/- 0.80 | 0.735 +/- 0.266 | 33.0 +/- 7.9 | |
| Error -27% | MAS+DIG | 4 | 2222 | 8.60 +/- 1.63 | 0.533 +/- 0.357 | 42.9 +/- 8.6 |
| MAS-Only | 6 | 111111 | 2.10 +/- 0.30 | 0.100 +/- 0.268 | 12.2 +/- 8.1 | |
| Error -8% | MAS+DIG | 6 | 111111 | 5.30 +/- 3.49 | 0.092 +/- 0.209 | 16.8 +/- 9.4 |
| MAS-Only | 6 | 222222 | 2.70 +/- 1.10 | 0.847 +/- 0.279 | 32.5 +/- 13.2 | |
| Error -33% | MAS+DIG | 6 | 222222 | 10.10 +/- 1.64 | 0.568 +/- 0.372 | 43.8 +/- 11.0 |
RJ adds staged dependencies on top of capability constraints, so errors can arise from invalid processing, invalid merging, overloaded assignment, and dependency violations. DIG catches these structural failures before they propagate to later stages.
| Setting | Method | # Failure | Error | Time (s) |
|---|---|---|---|---|
| Homogeneous agents, stage load 4000 | ||||
| MAS-Only | 6.20 +/- 2.96 | 0.50 +/- 0.30 | 24.8 +/- 31.8 | |
| Error -44% | MAS+DIG | 8.40 +/- 1.69 | 0.28 +/- 0.28 | 17.9 +/- 2.2 |
| Heterogeneous agents, stage load 1111 | ||||
| MAS-Only | 3.50 +/- 1.43 | 0.55 +/- 0.15 | 43.4 +/- 32.9 | |
| Error -18% | MAS+DIG | 8.70 +/- 1.85 | 0.45 +/- 0.15 | 68.6 +/- 26.7 |
The apparent increase in detected failures is expected: DIG keeps execution active long enough to expose and repair failures that MAS-Only may leave unresolved. Runtime can increase for the same reason, although RJ homogeneous runs show that structure-driven repair can also reduce wall-clock time by preventing wasted work.
Case study: 20-agent scale. On CF with load 100,000, MAS-Only fails to produce a result within 120 s. With DIG, the same 20-agent system produces a valid answer within 70 s using 92 calls. During the run, DIG detects 1 missing completion error, 8 repeated-effort incidents, 2 dependency warnings, 1 orphaned event, and 4 early termination errors. This highlights that adding agents alone does not guarantee reliable collaboration; the interaction structure itself needs real-time monitoring and repair.
@article{yang2026dig,
title = {DIG to Heal: Scaling General-purpose Agent Collaboration via Explainable Dynamic Decision Paths},
author = {Yang, Hanqing and Lee, Hyungwoo and Yao, Yuhang and Liu, Zhiwei and Liu, Kay and Chen, Jingdi and Joe-Wong, Carlee},
journal = {arXiv preprint arXiv:2603.00309},
year = {2026}
}