DIG-TAG: Representing Open-Ended Collaboration in LLM-Based Multi-Agent Systems Structurally

Collaboration Is More Than Environment State

Open-ended agent teams create and transform work while they act: they propose tasks, revise objectives, split and join subtasks, exchange evidence, and reorganize after failures. Environment state alone does not capture this collaborative state, while transcripts entangle it with surface language and incidental ordering.

DIG-TAG makes the consequential structure created by interaction a first-class object. Its two linked views preserve both the flow of information and the evolving identity, version history, and evidence of shared work.

DIG-TAG overview showing task activity, agent interactions, and shared environment aligned over time — **DIG-TAG at a glance.** The Task Activity Graph (top), Dynamic Interaction Graph (middle), and environment state (bottom) remain aligned through agent-issued tool calls and returned events.

The key separation: DIG records interaction flow; TAG records task flow. They share task actions and provenance, but TAG is not merely a causal subgraph of DIG. This factorization exposes structure useful for reconstruction, comparison, assessment, and optimization.

The DIG-TAG Collaboration Interface

A DIG-TAG instance combines a Dynamic Interaction Graph, a Task Activity Graph, the shared environment, and the available task, environment, and information tools. Persistent agent identities connect the views.

D

Dynamic Interaction Graph

A directed bipartite graph of information events and agent activations. It records input events, ordered tool-call occurrences, returned events, deliveries, timing, and routing dependencies.

T

Task Activity Graph

A versioned graph of task nodes, occurrence-identified task actions, and evidence attachments. It preserves task identity, specification, reported state, ancestry, frontier, and lifecycle.

Z

Shared Environment

The external world agents observe and change. Environment tools return fresh DIG events, allowing task declarations and evidence to remain connected to externally verifiable effects.

One realized execution, two relations

An activation is one invocation of an agent. Its input set is fixed at activation start, and its ordered calls may return new events. Repeated invocations and repeated calls remain distinct occurrences, so cycles, retries, concurrency, and dynamic routing are preserved rather than collapsed.

Task versions are immutable. Every update appends a version; evidence targets an exact version and does not silently carry forward. Provenance records where a claim came from, while validity remains a separate, domain-specific judgment.

View	What it answers
DIG	Who acted, what information reached them, which tools they called, and where outputs flowed.
TAG	What work exists, how it was revised or decomposed, which version is current, and what evidence supports it.
DIG + TAG	Who produced a task version, from which inputs, with what evidence and interaction context.

A Small Vocabulary for Evolving Work

TAG uses six structural task operations. Applications supply the meaning of goals, states, evaluation rules, and domain effects; the interface captures how work changes without fixing what the work must be.

OPEN

Create a fresh task identity and its initial version with status open.

EDIT

Append a version that revises the task specification while preserving reported state.

UPDATE

Append a version that changes reported state while preserving the task specification.

SPLIT

Decompose one version into multiple versions with distinct task identities.

JOIN

Integrate versions from distinct task identities into a single successor version.

CLOSE

Declare that an identity needs no further work; closure does not certify success.

Designed for honest histories. Transformations can use historical versions, concurrent edits create distinct tasks rather than overwriting one another, and closure never erases lineage or pretends a goal was satisfied.

What the Representation Makes Observable

From interaction trace to topology. Two rounds of hub-worker interaction produce seven activations across three agents and eight routed deliveries. Aggregating by agent identity yields three nodes and four directed edges, each with delivery count two; repeated interactions become weights while activation timing is omitted.

Seven collaboration patterns and their corresponding DIG execution records — **Collaboration patterns.** Sequential, hierarchical, supervisor, mesh, parallel fan-out/fan-in, cyclic, and dynamically instantiated worker structures all admit a common occurrence-level record.

From traces back to structure

DIG can encode any finite graph execution whose occurrences and relations are recorded. Aggregating activations by agent identity reconstructs realized interaction graphs; retaining occurrence-level records preserves repeated calls, parallel overlap, branch choices, and dynamically created workers.

From versions back to decisions

TAG reconstructs finite histories of task introduction, revision, decomposition, integration, and closure. Because task actions are attributed to DIG call occurrences, a query can follow a result through its version lineage to the responsible activation, its available context, and attached evidence.

Adaptive coordination

Compare interaction structures and routing patterns by task, phase, or agent group to inform recipient selection, review assignment, or revised decomposition.

Targeted verification & repair

Use failed checks, task lineage, information flow, and call attribution to identify what should be rechecked or revised.

Learning collaboration policies

Relate public context and call choices to observations, task effects, assessed outcomes, and costs to learn transferable policies.

Structural Validation

The paper evaluates whether DIG-TAG faithfully records known collaboration structures, recovers stochastic routing, reconstructs a long-horizon trace when supplied with perfect phase chunking, scales to larger teams, and transfers across distinct task domains. It also reports that directly optimizing over the collaborative state exposed by DIG-TAG improves grounded task completion over baselines across diverse environments.

525

Steps reconstructed across three perfectly chunked topology phases.

0.09

Maximum routing-frequency deviation after 600 steps in the eight-agent experiment.

50

Workers in the large supervisor topology used for the scale demonstration.

40

Agents in the hierarchical topology reconstructed from the execution record.

Routing probability recovery over a 600-step eight-agent trajectory — **Routing recovery.** Empirical transition frequencies converge toward the defined probabilities; the maximum absolute deviation falls from 0.70 after 10 steps to 0.09 after 600.

Aggregated DIG records for a 50-worker supervisor topology and a 40-agent hierarchy — **Scaling up.** A 50-worker supervisor topology and a 40-agent hierarchy aggregate into readable interaction structures while their occurrence-level records retain the underlying deliveries.

A 525-step interaction trace split at known boundaries into tree, cluster, and gated topology phases, with ground-truth and reconstructed routing matrices — **Long-horizon recovery with perfect chunking.** Given the true phase boundaries at steps 140 and 360, DIG-TAG reconstructs the tree, cluster, and gated routing structures from the corresponding chunks. The phase reconstructions recover 10/10, 14/14, and 8/9 edges; the missing gated edge never fires in the trace.

Reconstructing structure phase by phase

A single 525-step execution changes topology twice. With perfect chunking - the known boundaries supplied to the analysis - DIG-TAG aggregates the occurrence-level records inside each phase and recovers that phase's realized interaction graph and routing frequencies. Aggregating the full trace recovers 23 of 24 combined edges.

Scope of the result: the experiment evaluates reconstruction given correct segmentation; phase-boundary discovery is not part of this claim.

Aligned DIG-TAG records across survey, software, analysis, and proof domains — **Domain-agnostic records.** The same planner-worker-reviewer policy produces aligned interaction and task-activity records in survey, software, analysis, and proof tasks.

A general interface, not a prescribed workflow

Agents need not reason in graphs or reveal chain-of-thought. They may call task tools directly, or a wrapper or evaluated parser may emit equivalent typed effects from observable behavior. Unsuccessful, conflicting, and irrelevant behavior remains representable; cooperation and correctness are assessed downstream.

Back to top