Self-Evolving Agents as Dynamic Graph Transformation: A Survey and New Perspective
A survey that reframes self-evolving AI agents as ever-changing graphs you can track and roll back
This survey looks at LLM-based agents that keep updating their memories, tools, skills, workflows, and relationships with other agents over time. The authors model an agent's entire state as a dynamic graph of typed nodes and edges, and treat every state change as a rule-based graph edit (rewrite). Building on this, they classify 46 existing works into four evolution patterns, map nine dynamic-graph-learning techniques onto agent-evolution needs, and propose five evaluation/governance methods plus six open challenges.
METAL MEDIA explanatory visual
A survey that reframes self-evolving AI agents as ever-changing graphs you can track and roll back
- 01Agent memories, tools, skills, workflows, and inter-agent relations are represented as typed nodes and edges, with state changes modeled as rule-constrained graph rewrites (insertion, deletion, feature update, merge) following the double-pushout (DPO) formalism
- 0246 existing self-evolving-agent works are organized into four graph-transformation patterns: node/feature evolution, edge/topology evolution, subgraph activation, and cross-component co-evolution
- 03Nine dynamic-graph-learning method families are mapped onto nine agent-evolution capabilities such as prediction, activation, generation, diagnosis, rollback, and governance, positioning graph-learning research as reusable infrastructure for agents
- 04Five graph-aware evaluation and governance protocols are proposed: leakage-free temporal evaluation, privacy/deletion checking, safety monitoring, rollback analysis, and audit
- 05Six open challenges are outlined, covering observability of evolving state, tracing memory influence, validating tool dependency graphs, checking skill usability at scale, predicting workflow rewrite cascades, and governing unsafe propagation paths in multi-agent systems
What they did
- Agent memories, tools, skills, workflows, and inter-agent relations are represented as typed nodes and edges, with state changes modeled as rule-constrained graph rewrites (insertion, deletion, feature update, merge) following the double-pushout (DPO) formalism
- 46 existing self-evolving-agent works are organized into four graph-transformation patterns: node/feature evolution, edge/topology evolution, subgraph activation, and cross-component co-evolution
- Nine dynamic-graph-learning method families are mapped onto nine agent-evolution capabilities such as prediction, activation, generation, diagnosis, rollback, and governance, positioning graph-learning research as reusable infrastructure for agents
- Five graph-aware evaluation and governance protocols are proposed: leakage-free temporal evaluation, privacy/deletion checking, safety monitoring, rollback analysis, and audit
- Six open challenges are outlined, covering observability of evolving state, tracing memory influence, validating tool dependency graphs, checking skill usability at scale, predicting workflow rewrite cascades, and governing unsafe propagation paths in multi-agent systems
| Mechanism | Trigger | Rewrite | Scope | Persistence | Examples |
|---|---|---|---|---|---|
| A.1 Node and feature evolution | |||||
| Memory update | New evidence | Insert/Merge/FeatureUpdate | Memory graph | Long | Zep [116], TiMem [69] |
| Skill update | Trajectory/feedback | Insert; FeatureUpdate | Skill graph | Long | SkillOps [109] |
| A.2 Edge and topology evolution | |||||
| Workflow rewrite | Task change | Link/Unlink/Rewire | Workflow graph | Medium | AFlow [193], DynTaskMAS [176] |
| Communication pruning | Redundant messages | Unlink/Rewire | Communication graph | Medium | AgentPrune [184], AgentDropout [149] |
| Topology routing | Round context | Link/Rewire | Communication graph | Medium | GTD [43] |
| A.3 Read-only subgraph activation | |||||
| Team activation | Query/round | Activate | Agent graph | Temporary | DyLAN [86], DyTopo [89] |
| A.4 Cross-component co-evolution | |||||
| Workflow→team | Expertise change | Rewire+cascade | Workflow-Agent graph | Medium | MetaGen [147], TacoMAS [165] |
| Safety propagation | Unsafe trace | FeatureUpdate + cascade | Trace graph | Medium | GUARDIAN [209], SentinelAgent [45] |
| Family | Representative methods | Agent capability | Required adaptation | Naive failure modes |
|---|---|---|---|---|
| Representation learning on evolving graphs | ||||
| B.1 CTDGs & DTDGs | TGN [118]; DyGFormer [177] | Update prediction; activation; cascades | Typed rewrite events; temporal negatives | Temporal leakage; unstable embeddings |
| B.2 DyTAGs | MoMent [169]; CROSS [198] | Text-aware memory and skill activation | Selective re-encoding; text–time alignment | Stale text embeddings |
| Generative modeling of temporal structure | ||||
| B.3 DyG generation | TG-GAN [194]; TIGGER [40] | Workflow and topology synthesis | Typed schema constraints; valid decoding | Invalid tools or communication links |
| Learning under streams and temporal shift | ||||
| B.4 Continual learning | LTF [78]; PI-GNN [195] | Durable skill and memory encoders | Context-aware replay; update isolation | Rare skills are forgotten |
| B.5 OOD | DIDA [200]; SILD [201] | Robust activation and update | Splits by time, tool, and user cohort | Deployment drift is hidden |
| B.6 TKG reasoning | xERTE [42]; RE-Net [53] | Temporal memory reasoning | Text evidence with timestamped provenance | Language evidence is ignored |
| Diagnosis, removal, and explanation on dynamic graphs | ||||
| B.7 Anomaly detection | AddGraph [205]; TADDY [84] | Unsafe-rewrite and drift detection | Calibration on benign evolution bursts | Normal adaptation is flagged |
| B.8 DyG unlearning | GradientTransformation [190]; CallosumNet [39] | Deletion, rollback, influence removal | Versioned provenance; shared-state isolation | Rollback damages shared skills |
| B.9 T-GNN explanation | T-GNNExplainer [160]; Causal Explanation [204] | Audit and attribution | Event-level explanations over rewrite traces | Triggering events are missed |
Why it matters
As agents increasingly rewrite their own memories, tools, and workflows autonomously, failing to track what changed, when, and why makes it hard to diagnose errors or safety incidents after the fact. This survey offers a shared structural language for recording and auditing such changes, giving researchers and practitioners a concrete framework for building more traceable and governable self-evolving agents.
Terms in this paper
- dynamic graph · a graph structure whose nodes, edges, and attributes keep changing over time
- node/edge · basic graph elements representing entities and the relationships between them
- double-pushout (DPO) rewriting · a formal method for graph editing that specifies what pattern to find, what to keep, and what to replace it with
- subgraph activation · temporarily selecting a relevant portion of a stored graph for a task without permanently changing the graph
- rollback · reverting a system to a previous state after an unwanted or harmful change
Figures we cannot republish
- Figure 1: Positioning of this survey relative to existing LLM-agent, graph-agent, and dynamic-graph surveys.
- Figure 3: Dynamic graph learning as agent-evolution infrastructure. It includes nine DGL families and nine agent-evolution tasks over agent-graph streams, showing how dynamic graph methods can be adapted as reusable support for self-evolving agents.
Original abstract (English)
Large language model (LLM)-based agents are increasingly becoming self-evolving systems that persist across interactions, maintain memories, use tools, acquire skills, refine workflows, and coordinate with other agents. These capabilities make agent states structural and dynamic: entities, relations, attributes, dependencies, and execution structures change with new evidence, feedback, and environmental conditions. Existing graph-agent surveys typically treat graphs as support structures for agent functions rather than as evolving substrates, while self-evolving-agent surveys focus on agent-level mechanisms and rarely discuss graph topology evolution. Thus, the coupling between evolving agent state and dynamic graph topology remains underexplored. This survey connects these two research lines by framing \textit{agent evolution as dynamic graph transformation}. We model agent state as a dynamic graph, where memories, tools, skills, workflows, and inter-agent relations are represented as typed nodes, edges, and subgraphs updated through schema-constrained rewrites. Based on this formulation, we organize existing dynamic-graph-based methods for self-evolving agents into four taxonomies: node/feature evolution, edge/topology evolution, subgraph activation, and cross-component co-evolution. Building on this taxonomy, we propose dynamic graph learning as reusable infrastructure for self-evolving agents and map nine dynamic-graph-learning subfields to agent-evolution capabilities, discussing their adaptations and possible failure modes. Finally, we discuss five types of graph-aware evaluation and governance protocols from a dynamic-graph perspective, which complement end-task evaluation. The goal is to provide a compact structural lens for designing and governing self-evolving agents.
Read on arXivLatest papers
- SWE-bench Science: Can Coding Agents Resolve Engineering Tasks in Science?AI coding agents were tested on fixing real scientific software, and even the best one failed more than half the time
- FlashPrefill V2: Block-Sparse Prefill Attention for Long-Context LLM ServingMaking sparse attention fast enough and accurate enough for real LLM serving, not just papers
- PolicyGuide: From Guarding One Action to Guiding the Whole Workflow for Policy-Compliant LLM AgentsMaking customer-service AI agents follow the whole procedure, not just avoid one bad action
- EXIMO: VLM Guided Exploration of VLA PoliciesTeaching a robot new chores without human teleoperation, by letting a chatty AI supervise it
- EnvHarness: Awakening Static Worlds for Agent LearningInstead of building new training worlds from scratch, this work adds a plug-in layer that reshapes existing ones around each agent's actual weaknesses
- Bounded Sovereignty and the Control Tax: Pricing AI Oversight When the Deployer Does Not Own the ModelCompanies that rent AI instead of owning it can only do half of AI safety oversight
- PersonalBench: Measuring the Authorship Gap in LLM PersonalizationAI can be prompted to write 'like someone,' but its own voice never fully disappears
- Automated Summarization of Financial News Using Large Language Models and Retrieval-Augmented Generation: An Early Empirical Study (Fall 2023)Testing AI summaries of stock news, the simple approach beat the trendy retrieval-based one