Experience-Memory Graph Subsystem Design

Full report

On this page

We design a deterministic Action Decision Graph (ADG) subsystem to convert agent trajectories into structured graphs, align failed vs. successful trajectories, and compute a minimal graph edit path of operations to correct failures. In EMG (Experience Memory Graph) this process is done offline rather than by runtime LLM reflection. For each task, we convert both a failed exploration trajectory and its successful expert trajectory into directed Action Decision Graphs, match them to extract the common “success” subgraph and the shortest edit path (additions, deletions, relabels) to transform the failed graph into the successful one. This yields a deterministic correction plan (e.g. which actions to retain, remove or replace under specific observations) without any online trial-and-error loop.

Graphs and Edit Distance

We build Action Decision Graphs (ADGs) whose nodes represent normalized actions and whose directed edges carry the normalized observation/state that preceded that action. Identical normalized actions reuse the same node (so the same action type under different conditions converges into one node). Consecutive invalid actions under the same state (e.g. “nothing happens” observations) are represented as parallel edges from that state node, not as a long chain, effectively grouping repeated failures under the same context. This ensures compact graphs that capture decision patterns.

A graph edit path is a sequence of edit operations (node/edge additions, deletions, or relabelings) that transforms one graph into another. Graph Edit Distance (GED) measures the cost of this transformation: e.g., adding or deleting an edge, adding or deleting an isolated node, or relabeling a node or edge. Since exact GED is NP-hard, we use optimal-transport alignment (e.g. Fused Gromov-Wasserstein) to find a near-optimal node matching, then derive the edit operations from structural differences. In practice, FGWAlign efficiently finds a soft alignment for graphs of a few dozen nodes. We then discretize this into a one-to-one node mapping (via linear assignment) and compare the two graphs. Algorithm 2 retains edges present with matching labels (the common subgraph), while Algorithm 3 collects all mismatched or unmatched nodes/edges to emit edit operations (Add/Delete/Relabel).

C# Domain Model

We define a strongly-typed C# domain model. Key aggregates include AgentTrajectory, ActionDecisionGraph, and GraphEditPlan. Value objects include NormalizedAction and NormalizedObservation. Entities include steps, graph nodes, edges, and edit operations. Each public property is annotated with [Display(Name="...")], omitting “Id/ID/Identifier” suffix from the name. For example:

using System;
using System.Collections.Generic;
using System.ComponentModel.DataAnnotations;

public class AgentTrajectory
{
    [Display(Name = "Task")]
    public string TaskId { get; set; }

    [Display(Name = "Trajectory Steps")]
    public List<TrajectoryStep> Steps { get; set; } = new();

    [Display(Name = "Success")]
    public bool Success { get; set; }
}

• AgentTrajectory: aggregate root for a single execution. It holds a TaskId, a list of TrajectoryStep, and a final Success flag. Invariant: Steps is non-empty and ordered.

public class TrajectoryStep
{
    [Display(Name = "Step Index")]
    public int StepIndex { get; set; }

    [Display(Name = "Observation")]
    public NormalizedObservation Observation { get; set; }

    [Display(Name = "Action")]
    public NormalizedAction Action { get; set; }

    [Display(Name = "Result")]
    public string ActionResult { get; set; }
}

• TrajectoryStep: represents one step with the pre-action observation/state, the executed action, and the result.

public class NormalizedAction : IEquatable<NormalizedAction>
{
    [Display(Name = "Action Type")]
    public string Type { get; set; }

    [Display(Name = "Target Object")]
    public string Target { get; set; }

    [Display(Name = "Destination")]
    public string Destination { get; set; }

    [Display(Name = "Tool")]
    public string Tool { get; set; }

    [Display(Name = "Arguments")]
    public Dictionary<string, string> Arguments { get; set; } = new();

    public override bool Equals(object obj) => Equals(obj as NormalizedAction);
    public bool Equals(NormalizedAction other) =>
        other != null &&
        Type.Equals(other.Type, StringComparison.OrdinalIgnoreCase) &&
        Target.Equals(other.Target, StringComparison.OrdinalIgnoreCase) &&
        Destination.Equals(other.Destination, StringComparison.OrdinalIgnoreCase) &&
        Tool.Equals(other.Tool, StringComparison.OrdinalIgnoreCase) &&
        Arguments.SequenceEqual(other.Arguments);
    public override int GetHashCode() => HashCode.Combine(
        Type.ToLowerInvariant(), Target.ToLowerInvariant(),
        Destination.ToLowerInvariant(), Tool.ToLowerInvariant(),
        String.Join("|", Arguments.OrderBy(kv => kv.Key).Select(kv => kv.Key + "=" + kv.Value)));
}

• NormalizedAction: a value object capturing the action tuple. We enforce canonical equality (case-insensitive type/destination, sorted argument keys) for determinism. Similar approach applies to NormalizedObservation. Optional or missing fields (null/empty) are treated consistently (e.g. normalize to empty string). Numeric values in arguments should be formatted (e.g. ToString("G9")) to avoid floating-point inconsistencies.

public class NormalizedObservation
{
    [Display(Name = "State")]
    public string StateDescription { get; set; }
}

• NormalizedObservation: captures the agent’s observed state or environment features. Its StateDescription is canonicalized (e.g. lowercased, sorted elements if it’s a list) so identical observations get identical normalized representations.

public class ActionDecisionNode
{
    [Display(Name = "Action")]
    public NormalizedAction Action { get; set; }
    [Display(Name = "Label")]
    public int Label { get; set; }  // Assigned in graph-building
}
public class ActionDecisionEdge
{
    [Display(Name = "From Node")]
    public ActionDecisionNode From { get; set; }
    [Display(Name = "To Node")]
    public ActionDecisionNode To { get; set; }
    [Display(Name = "Observation")]
    public NormalizedObservation Observation { get; set; }
}
public class ActionDecisionGraph
{
    [Display(Name = "Query")]
    public string TaskQuery { get; set; }
    [Display(Name = "Final Reward")]
    public double Reward { get; set; }
    [Display(Name = "Nodes")]
    public List<ActionDecisionNode> Nodes { get; set; } = new();
    [Display(Name = "Edges")]
    public List<ActionDecisionEdge> Edges { get; set; } = new();

    /// <summary>
    /// Builds an action decision graph from a raw trajectory.
    /// </summary>
    /// <param name="trajectory">The raw agent trajectory.</param>
    /// <returns>A directed graph of normalized actions and observations.</returns>
    public static ActionDecisionGraph BuildFrom(AgentTrajectory trajectory)
    {
        // Implementation of Algorithm 1 (append nodes/edges with reuse/parallel logic)...
        throw new NotImplementedException();
    }
}

• ActionDecisionGraph: aggregate root with nodes and edges. Each node has a normalized action, each edge carries the observation that triggered the next action. We include a synthetic INIT node (label 0) for the starting observation. We assign each distinct action tuple a unique Label integer, and each distinct observation text an edge label, so that later graph matching can compare by label equality.

public abstract class GraphEditOperation
{
    [Display(Name = "Type")]
    public string OperationType { get; set; }
}
public class AddNodeOperation : GraphEditOperation
{
    [Display(Name = "Node To Add")]
    public ActionDecisionNode Node { get; set; }
}
public class DeleteNodeOperation : GraphEditOperation
{
    [Display(Name = "Node To Delete")]
    public ActionDecisionNode Node { get; set; }
}
public class RelabelNodeOperation : GraphEditOperation
{
    [Display(Name = "Node")]
    public ActionDecisionNode Node { get; set; }
    [Display(Name = "New Action")]
    public NormalizedAction NewAction { get; set; }
}
public class AddEdgeOperation : GraphEditOperation
{
    [Display(Name = "From Node")]
    public ActionDecisionNode From { get; set; }
    [Display(Name = "To Node")]
    public ActionDecisionNode To { get; set; }
    [Display(Name = "Observation")]
    public NormalizedObservation Observation { get; set; }
}
public class DeleteEdgeOperation : GraphEditOperation
{
    [Display(Name = "From Node")]
    public ActionDecisionNode From { get; set; }
    [Display(Name = "To Node")]
    public ActionDecisionNode To { get; set; }
}

• GraphEditOperation and derived types: represent edit actions to transform one graph into another. Each property has a display name (e.g. “Node To Add”). Operations include adding/deleting nodes and edges, and relabeling node actions. We treat each graph element (ActionDecisionNode or ActionDecisionEdge) as identifiable so operations can refer to specific items.

public class GraphEditPlan
{
    [Display(Name = "Operations")]
    public List<GraphEditOperation> Operations { get; set; } = new();

    /// <summary>
    /// Serializes the plan to a canonical JSON string.
    /// </summary>
    /// <returns>A deterministically ordered JSON representation.</returns>
    public string ToCanonicalJson()
    {
        // Example: use System.Text.Json with JsonSerializerOptions(PropertyNamingPolicy = null, WriteIndented = false, SortProperties = true)
        throw new NotImplementedException();
    }
}

• GraphEditPlan: an ordered list of edit operations. We ensure deterministic ordering (e.g. sort operations by type and node identifiers) and use canonical JSON (sorted properties) when serializing. This avoids variability due to dictionary order or default serialization quirks.

public class GraphAlignmentResult
{
    [Display(Name = "Node Mapping")]
    public Dictionary<int,int> NodeMapping { get; set; } = new();
    [Display(Name = "Score")]
    public double Score { get; set; }
}

• GraphAlignmentResult: contains the node-to-node matching found (e.g. mapping from indices in graph A to graph B) and an optional alignment score. We can use this to compute the edit path: unmatched indices imply deletes/inserts, and mismatched labels imply relabel operations.

Identifiers and Equality: Each node has a unique ID (or label) within its graph. Value objects (NormalizedAction/Observation) implement Equals/GetHashCode for content equality (case-insensitive, argument-sorted) to ensure deterministic matching. Entities (nodes/edges) compare by identity (unique label) once created.

Serialization: For interoperability or storage, we use a JSON serializer configured for canonical form (e.g. PropertyNameCaseInsensitive = false, SortProperties = true) so that equivalent objects serialize identically. This handles property ordering. Text fields are lowercased or standardized, optional fields are omitted or set to default values, and numeric precision is fixed, ensuring schema-version changes do not break older data (e.g. unknown new fields are ignored, defaults are handled predictably).

Deterministic Normalization

To guarantee that two semantically identical actions/observations produce the same normalized object, we enforce:

• Property ordering: In lists or dictionaries (e.g. action arguments), always sort by key before processing. For example, store action arguments in a SortedDictionary<string,string>.
• Text casing: Convert all string fields to a consistent case (e.g. lower-case) when normalizing. Punctuation and whitespace can be normalized (e.g. trimmed, single spacing).
• Optional values: Use default values or omit fields consistently. e.g. if Tool is null, normalize it to empty string. Missing optional fields should not change the tuple ordering.
• Numeric precision: For any numeric arguments, format using a fixed string format (double.ToString("G9") for 9 significant digits) so that 0.5 stays “0.5” and not “0.500000001”.
• Argument ordering: Define a canonical order (alphabetical by argument name) when comparing or serializing. This ensures that {"x":1,"y":2} and {"y":2,"x":1} yield the same normalized action.
• Schema changes: Maintain versioned normalization code. If the action schema evolves, write compatibility layers so older actions still normalize into the same form or map deprecated fields to new ones consistently.

By these rules, any given raw action or observation always maps to a unique NormalizedAction/NormalizedObservation value. We then assign labels deterministically (e.g. hash or ordered index) so that identical normalized tuples always produce identical node/edge labels.

Graph Alignment and Edit-Path Computation

For each task, we align a failed ADG (G) with its successful ADG (H). We use a Fused Gromov–Wasserstein (FGW) solver to find a soft correspondence between nodes based on action-label similarity and edge-structure similarity. FGW jointly optimizes matching of node labels (actions) and edge structures, solving a transport problem on graphs. We use the FGWAlign algorithm (Tang et al. 2025) which supports edge-labeled directed graphs and runs efficiently on small graphs.

Once we obtain the soft transport plan, we convert it to a hard matching (using linear assignment). Given this node mapping, we compare G and H:

• Common subgraph: Any edge (u→v) present in both G and H (with matching labels under the mapping) is kept. These edges/actions represent the correctly executed workflow.
• Edit operations: All nodes/edges in G that have no match in H become deletions, and all in H unmatched in G become additions. If a matched node has a different action label than its partner, we emit a relabel for that node. Similarly, unmatched edges yield add/delete edge ops.

The result is a shortest edit path (we sort operations deterministically, e.g. delete-nodes first, then relabels, then add-nodes, then edge ops, sorted by node IDs) that transforms G into H. This graph edit plan is the correction plan: for each edit (e.g. “delete node A”, “add node B”, “relabel node C to action X”), the agent knows exactly how to amend its failed trajectory. Unlike LLM-based reflection loops, this is a static, one-shot instruction sequence.

References and Provenance

Our design is grounded in recent literature on graph alignment and agent memory. The EMG framework itself has been proposed as a way to reformulate agent failure recovery as graph matching, extracting common subgraphs and graph edit paths between failed and successful trajectories. In particular, Wang et al. (KDD 2027) describe converting trajectories into ADGs and using FGW-based matching to compute deterministic correction plans. The FGWAlign approach (Tang et al. 2025) underlies our alignment algorithm, efficiently handling directed edge-labeled graphs. The fundamental operations (add/delete nodes/edges, relabel) follow the standard graph edit distance definition. All cited methods emphasize offline, reproducible computation rather than any call to an LLM at runtime.

Sources: Foundational definitions and methods are from Tang et al. (2025) on fused Gromov–Wasserstein alignment for graph edit distance and from Wang et al. (2027) on Experience Memory Graphs for agent error correction. These works detail the Action Decision Graph conversion, optimal transport alignment, and extraction of common subgraphs and edit paths, which directly inform this design.