Executive Summary

Full report

On this page

We design a deterministic graph-edit subsystem for LLM agents that transforms failed execution trajectories into successful ones by converting each trajectory into a directed Action Decision Graph (ADG), aligning failed and successful graphs, and emitting a sequence of graph-edit operations. This offline approach replaces expensive online LLM reflection loops with algorithmic exactness. In our design:

• Trajectories (sequences of observations, states, actions, outcomes) are modeled in C# with immutable, strongly-typed entities (e.g. AgentTrajectory, TrajectoryStep).
• Each trajectory is converted into an Action Decision Graph (nodes = normalized actions, edges = triggering observations). We reuse nodes for identical actions and represent repeated invalid actions as parallel edges from the same state.
• Failed and successful ADGs for the same task are aligned via an optimal-transport solver (e.g. Fused Gromov–Wasserstein). This yields a common subgraph (correct workflow) and a graph edit path (sequence of node/edge add/delete/relabel operations) that deterministically corrects the failure.
• We define a GraphEditPlan containing ordered operations (Add/Delete/Relabel Node/Edge). Tie-breaking is deterministic (e.g. lexicographic by node name) and the solver is seeded for reproducibility.
• A CQRS/MediatR command handler loads two trajectory records (failed & successful), builds their ADGs, invokes the graph-alignment calculator, validates the plan by reapplying it, persists the plan, and publishes an event. All timestamps use UTC DateTimeOffset and optimistic concurrency (SQL rowversion) ensures consistency.
• Persistence uses EF Core mappings with appropriate indices and constraints: for example, a unique index on (FailedTrajectoryId, SuccessfulTrajectoryId) enforces idempotency. Large objects (graph structures, solver matrices) are stored as JSON in nvarchar(max) columns or external storage to avoid relational bloat.
• Validation and Testing: xUnit tests cover node reuse, invalid-action loops, stable graph-hashing, idempotent command handling, and edit-plan verification by actually transforming a copy of the failed graph and comparing to the success graph.
• Operations: A background worker service (e.g. Azure Function or .NET Hosted Service) processes commands from a queue, with retries, dead-letter handling, metrics, and tracing. Versioning and audit trails track graph-schema and solver versions, and normalization changes trigger reprocessing of affected tasks.

This architecture leverages recent research in Experience Memory Graphs and graph matching, combining DDD/CQRS patterns with formal graph-alignment techniques to achieve one-shot error correction in agent workflows.

Definitions and Assumptions

• Agent Trajectory: An ordered sequence of interactions by an autonomous agent. Each step is a tuple (Observation, Action, ActionResult), ending in a terminal success/failure outcome. We assume trajectories are immutable records stored in a database (e.g. JSON or relational tables).
• NormalizedAction / NormalizedObservation: Value objects derived from raw action/observation texts. A NormalizedAction contains fields like ActionType, TargetObject, Destination, Tool, and any relevant Arguments; it also retains the original raw text. Similarly, NormalizedObservation abstracts state context (e.g. inventory lists) into canonical form. These are normalized (case-invariant, sorted arguments, fixed precision) to ensure identical semantics map to equal values (see Deterministic Normalization below).
• Action Decision Graph (ADG): A directed graph representing a trajectory. Each node is a normalized action; each edge is the normalized observation/state preceding that action. We include a virtual INIT node for the initial state. Identical actions reuse one node (accumulating multiple incoming observation-edges). Consecutive invalid actions (those that produce no state change) are all drawn as parallel edges from the same valid state node, avoiding long spurious chains.
• Graph Edit Plan: A sequence of edit operations (add/delete node, relabel node, add/delete edge) that transforms one ADG into another. We treat this as an aggregate with an ordered list of GraphEditOperation value objects. Each operation is detailed (e.g. which node to add/delete, with what label or connections). Operation ordering is deterministic (e.g. sort by operation type and node identifier) to ensure consistency.
• Graph Alignment Result: Intermediate result from the solver containing a node-matching between two ADGs, alignment cost, solver diagnostics (version, seed), and metrics. This is used to derive the final GraphEditPlan.

We assume a common task identifier links a failed and successful trajectory. All processing is offline (training phase) – no LLM calls occur during graph building or alignment. We target .NET 8/9, SQL Server, and use UTC DateTimeOffset for all timestamps. Int32 is avoided in T-SQL types (we use int for SQL Server) and in any TypeScript interfaces (use number).

Related Work

The Experience Memory Graph (EMG) paradigm aligns failed and successful agent trajectories via graph matching. EMG builds ADGs and extracts common subgraphs (correct parts) and graph edit paths (correction instructions) deterministically, replacing iterative LLM reflection. Our design is directly inspired by this: we convert trajectories to ADGs and compute the shortest edit path offline as in EMG, then store the results for reuse.

Graph edit distance (GED) is NP-hard in general. Recent work (e.g. FGWAlign by Tang et al. 2025) uses optimal transport (Fused Gromov–Wasserstein) to compute approximate GED. FGWAlign handles node labels and edge structures jointly and offers good performance for graphs up to thousands of nodes. We adopt a similar solver, leveraging directed graphs with edge labels (extensions in FGWAlign).

In the database domain, storing semi-structured graph data can use JSON columns or varbinary to avoid row explosion. EF Core 7+ even supports mapping owned aggregates to JSON in SQL Server. We will use nvarchar(max) JSON columns for large graph structures or solver artifacts, and ensure indices and concurrency tokens per EF Core best practices.

Domain Model and Invariants

We define C# domain classes with strong typing and deterministic behavior. Key types include:

/// <summary>
/// Represents a complete agent trajectory (sequence of steps and final outcome).
/// Immutable once created.
/// </summary>
public class AgentTrajectory
{
    [Key]
    public Guid Id { get; init; }

    [Display(Name="Task Query")]
    public string Query { get; init; }  // e.g. instruction text

    [Display(Name="Steps")]
    public IReadOnlyList<TrajectoryStep> Steps { get; init; }

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

    [Display(Name="Timestamp")]
    public DateTimeOffset CreatedUtc { get; init; }  // UTC creation time
}

/// <summary>
/// Represents a single step in the trajectory: observation, action, and result.
/// </summary>
public class TrajectoryStep
{
    [Display(Name="Step Number")]
    public int StepNumber { get; init; }

    [Display(Name="Observation")]
    public string ObservationText { get; init; }

    [Display(Name="Action")]
    public string ActionText { get; init; }

    [Display(Name="ActionResult")]
    public string ActionResultText { get; init; }
}

Each TrajectoryStep is immutable and ordered by StepNumber. We assume inputs (observations, action texts) are consistent and well-formed. Malformed trajectories (missing initial state or null actions) are rejected or quarantined at the builder stage.

For normalized values (used as graph node/edge labels):

/// <summary>
/// Normalized representation of an action (type, target, destination, tool, etc.).
/// Value object: equality by content.
/// </summary>
public record NormalizedAction
{
    [Display(Name="Action Type")]
    public string ActionType { get; init; }

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

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

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

    [Display(Name="Arguments")]
    public IReadOnlyList<string> Arguments { get; init; }

    [Display(Name="Raw Text")]
    public string RawText { get; init; }
    // Override equality (record does structural compare).
}

/// <summary>
/// Normalized representation of an observation/environment state.
/// Value object: equality by content.
/// </summary>
public record NormalizedObservation
{
    [Display(Name="State Features")]
    public IDictionary<string,string> Features { get; init; }  // e.g., "location"->"kitchen"

    [Display(Name="Raw Text")]
    public string RawText { get; init; }
}

Normalization is deterministic: e.g. string fields are converted to a canonical case (e.g. lowercase with ToLowerInvariant()), argument lists are sorted if order is semantically irrelevant, numeric values formatted to fixed precision, and missing/optional fields omitted or set to defaults consistently. We may use [JsonProperty(Order = n)] or manual sorting to enforce property order in serialization if needed. Schema versions are tracked in a global version number; changing the normalization logic increments the version and triggers reprocessing.

The ADG classes:

/// <summary>
/// Represents the decision graph of an agent trajectory.
/// Contains nodes (actions) and edges (observations).
/// </summary>
public class ActionDecisionGraph
{
    [Key]
    public Guid Id { get; init; }

    [Display(Name="Nodes")]
    public HashSet<ActionDecisionNode> Nodes { get; init; } = new();

    [Display(Name="Edges")]
    public HashSet<ActionDecisionEdge> Edges { get; init; } = new();

    [Display(Name="Schema Version")]
    public int SchemaVersion { get; init; }  // version of normalization/graph scheme

    /// <summary>
    /// Generates a stable hash of the graph by sorting nodes and edges by label.
    /// Used for equality checks and caching.
    /// </summary>
    public string ComputeCanonicalHash() { /* ... */ }
}

/// <summary>
/// A node in the ADG, representing a normalized action.
/// </summary>
public class ActionDecisionNode
{
    [Key]
    public Guid Id { get; init; }

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

    public override bool Equals(object? obj) => obj is ActionDecisionNode other && Action == other.Action;
    public override int GetHashCode() => Action.GetHashCode();
}

/// <summary>
/// An edge in the ADG, representing the observation preceding an action.
/// </summary>
public class ActionDecisionEdge
{
    [Key]
    public Guid Id { get; init; }

    [Display(Name="From Node")]
    public Guid FromNodeId { get; init; }
    [Display(Name="To Node")]
    public Guid ToNodeId { get; init; }

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

    public override bool Equals(object? obj) =>
        obj is ActionDecisionEdge other
        && FromNodeId == other.FromNodeId
        && ToNodeId == other.ToNodeId
        && Observation == other.Observation;
    public override int GetHashCode() => HashCode.Combine(FromNodeId, ToNodeId, Observation);
}

Each ActionDecisionNode is uniquely identified by its normalized action. Duplicate actions reuse the same node (ensuring one node has multiple incoming edges if the action occurred in different contexts). ActionDecisionEdge equality is based on (From,To,Observation); parallel edges (same from/to with identical observation) are deduplicated by the set.

For graph edits:

/// <summary>
/// Base class for graph edit operations (abstract).
/// </summary>
public abstract class GraphEditOperation
{
    [Display(Name="Operation Type")]
    public abstract string Type { get; }
}

/// <summary>
/// Adds a new action node (and connecting edges) to the graph.
/// </summary>
public class AddNodeOperation : GraphEditOperation
{
    [Display(Name="Action")]
    public NormalizedAction NewAction { get; init; }
    [Display(Name="Incoming Observation")]
    public NormalizedObservation Observation { get; init; }
    public override string Type => "AddNode";
}

/// <summary>
/// Deletes an existing action node from the graph.
/// </summary>
public class DeleteNodeOperation : GraphEditOperation
{
    [Display(Name="Action")]
    public NormalizedAction TargetAction { get; init; }
    public override string Type => "DeleteNode";
}

/// <summary>
/// Relabels an action node (changing it to another action).
/// </summary>
public class RelabelNodeOperation : GraphEditOperation
{
    [Display(Name="Old Action")]
    public NormalizedAction OldAction { get; init; }
    [Display(Name="New Action")]
    public NormalizedAction NewAction { get; init; }
    public override string Type => "RelabelNode";
}

/// <summary>
/// Adds a new edge (observation context) between two nodes.
/// </summary>
public class AddEdgeOperation : GraphEditOperation
{
    [Display(Name="From Action")]
    public NormalizedAction FromAction { get; init; }
    [Display(Name="To Action")]
    public NormalizedAction ToAction { get; init; }
    [Display(Name="Observation")]
    public NormalizedObservation Observation { get; init; }
    public override string Type => "AddEdge";
}

/// <summary>
/// Deletes an existing edge between two nodes.
/// </summary>
public class DeleteEdgeOperation : GraphEditOperation
{
    [Display(Name="From Action")]
    public NormalizedAction FromAction { get; init; }
    [Display(Name="To Action")]
    public NormalizedAction ToAction { get; init; }
    [Display(Name="Observation")]
    public NormalizedObservation Observation { get; init; }
    public override string Type => "DeleteEdge";
}

Each operation includes enough context to apply it unambiguously. For example, AddNodeOperation knows the action to add and its incoming observation; RelabelNodeOperation specifies the old and new actions. The operations form an ordered list in the plan, which is applied sequentially.

The GraphEditPlan aggregate:

/// <summary>
/// Represents a full edit plan transforming one graph into another.
/// </summary>
public class GraphEditPlan
{
    [Key]
    public Guid Id { get; init; }

    [Display(Name="Failed Trajectory")]
    public Guid FailedTrajectoryId { get; init; }

    [Display(Name="Successful Trajectory")]
    public Guid SuccessfulTrajectoryId { get; init; }

    [Display(Name="Operations")]
    public IReadOnlyList<GraphEditOperation> Operations { get; init; }

    [Display(Name="Solver Version")]
    public string SolverVersion { get; init; }  // e.g. "FGWAlign v1.2"

    [Display(Name="Seed")]
    public int? Seed { get; init; }  // RNG seed for reproducibility

    [Display(Name="Cost")]
    public double TotalCost { get; init; }  // sum of operation costs

    [Display(Name="CreatedUtc")]
    public DateTimeOffset CreatedUtc { get; init; }

    [Timestamp]
    public byte[] RowVersion { get; set; }  // for optimistic concurrency
}

• Identifiers: Entities have a [Key] Id (GUID). Value objects (NormalizedAction, NormalizedObservation) use structural equality.
• Invariants:
• The list Operations is non-empty only if the graphs differ; applying the plan to the failed ADG must yield (isomorphic to) the successful ADG.
• The sequence is deterministic: for equal inputs, the same sequence should be produced. We sort operations by a canonical rule to break ties (e.g. lexicographically by action name) if the solver yields multiple valid sequences of equal cost.
• Deterministic Serialization: We will store or compare graphs using a canonical JSON form: e.g. sort nodes by their action tuple, sort edges similarly. This ensures that graph equality or hashing is consistent across runs. System.Text.Json or Newtonsoft can be configured to maintain property order or we explicitly sort collections. Text fields (action names, objects) are normalized to a fixed case and trimmed, so case differences do not alter identity.

In summary, our domain model captures the needed concepts with clear invariants (node reuse, no duplicate edges, consistent labeling) and uses .NET value-equality semantics. We include [Display(Name="…")] on each public property, deriving the display name from the property name without suffixes, as required. All non-obvious methods (like ComputeCanonicalHash) will have XML documentation in code.

Graph Construction (IActionDecisionGraphBuilder)

We define an interface to build an ADG from a trajectory:

public interface IActionDecisionGraphBuilder
{
    /// <summary>
    /// Builds an ActionDecisionGraph from a sequence of trajectory steps.
    /// This process is deterministic and idempotent for the same input.
    /// </summary>
    /// <param name="steps">Ordered trajectory steps to convert.</param>
    /// <returns>Constructed ActionDecisionGraph.</returns>
    public ActionDecisionGraph Build(IReadOnlyList<TrajectoryStep> steps);
}

Its implementation follows the design in EMG:

1. Initialization: Create a new ActionDecisionGraph. Add a virtual "INIT" node representing the start. Set currentStateNode = INIT.
2. Action Reuse Dictionary: Maintain a Dictionary<NormalizedAction, ActionDecisionNode> to reuse nodes.
3. Scan Trajectory: For each TrajectoryStep step in order:

• Compute a NormalizedAction from step.ActionText and a NormalizedObservation from step.ObservationText, applying deterministic rules (case, trimming, etc.).
• If step.ActionResultText indicates the action was invalid (e.g. "nothing happens"), we do not update the state. Instead, add an edge parallel from currentStateNode back to currentStateNode (or to a special "failure marker") with the same observation. This models multiple invalid attempts from the same decision point.
• If the action is valid (state changes), do:
• If the action tuple exists in the dictionary, reuse the existing targetNode. Else create a new ActionDecisionNode and add it to the graph and dictionary.
• Add an ActionDecisionEdge from currentStateNode to targetNode labeled with the normalized observation.
• Set currentStateNode = targetNode.

1. Label Assignment: Once nodes/edges are created, assign each distinct action tuple an integer label, and each distinct observation string an integer label. Identical actions/observations get the same label. (These labels are used by the solver but can be stored or re-derived as needed.)

1. Finalization: Compute and store a canonical hash of the graph (e.g. by serializing nodes and edges sorted) to detect duplicates or for caching.

This algorithm runs in linear time O(T) for T steps, since each step is processed once and dictionary lookups are O(1) average. We ensure idempotence: feeding the same trajectory yields an identical graph (same nodes/edges set), and repeated calls do not create duplicates. Malformed input (null fields, inconsistent step numbers) triggers an exception or returns a special error graph.

Complexity: Scanning T steps yields up to N unique nodes (actions) and E≈T edges. Using hash sets/dictionaries yields roughly O(T) time. Hashing or comparing graphs is O(N log N + E log E) if we sort by labels. Given typical trajectories (tens of steps), performance is negligible.

Graph Edit-Path Abstraction (IGraphEditPlanCalculator)

We define a service interface to compute the edit plan between two ADGs:

public interface IGraphEditPlanCalculator
{
    /// <summary>
    /// Calculates a deterministic graph edit plan that transforms <paramref name="failedGraph"/>
    /// into <paramref name="successfulGraph"/>.
    /// </summary>
    /// <param name="failedGraph">The graph from the failed trajectory.</param>
    /// <param name="successfulGraph">The graph from the successful trajectory.</param>
    /// <param name="cancellationToken">Token to cancel long-running computation.</param>
    /// <returns>A GraphEditPlan containing the edit operations and metadata.</returns>
    Task<GraphEditPlan> CalculateEditPlanAsync(
        ActionDecisionGraph failedGraph,
        ActionDecisionGraph successfulGraph,
        CancellationToken cancellationToken);
}

Design considerations:

• Deterministic Ordering: If multiple optimal edit sequences exist, we impose a fixed tie-breaking (e.g. sort operations by type then by action name) to ensure the same plan is produced each time.
• Cost Model: We assign uniform unit costs to add/delete/relabel operations for simplicity (this yields the shortest path in edit space), but the model is pluggable. Costs are recorded in GraphEditPlan.TotalCost.
• Solver Version & Seed: The resulting GraphEditPlan records the solver version (e.g. FGWAlign v1.x) and the RNG seed used. We fix a seed (or use a hash of the input graphs as seed) so that repeated calls are reproducible.
• Cancellation & Timeouts: The method accepts a CancellationToken. If the solver does not finish before a configured timeout, we throw a controlled exception (caught by the handler) or return a failure plan which can be retried. We track if an execution timed out in logs/metrics.
• Idempotency: Given the same inputs and version, the plan must be identical. We can detect repeated requests (same failed/success pair) via the unique index in the database, so the handler will skip recomputation if a plan already exists.
• Validation: As a sanity check, after computing the plan, we apply it to a clone of the failed graph and ensure we reach the successful graph (or isomorphic version). If not, we discard the plan and log an error. This guards against solver bugs or mismatches (treating the solver output as untrusted until validated).
• Quality Metrics: The plan includes basic confidence (e.g. soft alignment score) and metrics (e.g. number of matched nodes). Optionally, if the solver can estimate ambiguity (multiple near-optimal solutions), we can flag low confidence.

Tie-breaking Example: Suppose two nodes can be relabeled with equal cost. We break ties by lexicographically comparing the normalized action tuples (e.g. NormalizedAction.ToString() under ordinal comparison). This imposes a consistent order on operations.

In summary, the alignment interface encapsulates the solver and edit extraction. Internally we perform:

1. Compute an optimal soft assignment between nodes (e.g. FGW).
2. Discretize it to a hard matching (linear assignment).
3. Identify the common subgraph and list of edit operations as described in Appendix B of EMG.
4. Order and return the final GraphEditPlan.

CQRS Processing Pipeline

We use MediatR to implement a command-handler pattern. The command:

public class GenerateEditPlanCommand : IRequest
{
    [Display(Name="Failed Trajectory Id")]
    public Guid FailedTrajectoryId { get; init; }

    [Display(Name="Successful Trajectory Id")]
    public Guid SuccessfulTrajectoryId { get; init; }
}

Handler outline:

public class GenerateEditPlanHandler : IRequestHandler<GenerateEditPlanCommand>
{
    private readonly IAppDbContext _db;
    private readonly IActionDecisionGraphBuilder _graphBuilder;
    private readonly IGraphEditPlanCalculator _editPlanCalculator;
    private readonly IEventBus _eventBus;

    public GenerateEditPlanHandler(/* inject dependencies */) { ... }

    /// <summary>
    /// Handles the command by loading trajectories, building graphs, computing the edit plan,
    /// validating it, saving the result, and publishing an event.
    /// </summary>
    public async Task<Unit> Handle(GenerateEditPlanCommand cmd, CancellationToken ct)
    {
        // Load immutable trajectories (Idempotent read-only).
        var failedTraj = await _db.AgentTrajectories
            .Include(t => t.Steps)
            .SingleOrDefaultAsync(t => t.Id == cmd.FailedTrajectoryId, ct);
        var successTraj = await _db.AgentTrajectories
            .Include(t => t.Steps)
            .SingleOrDefaultAsync(t => t.Id == cmd.SuccessfulTrajectoryId, ct);

        if (failedTraj == null || successTraj == null)
            throw new InvalidOperationException("Trajectory not found.");

        // Build graphs (outside of any transaction to avoid long locks).
        var failedGraph = _graphBuilder.Build(failedTraj.Steps);
        var successGraph = _graphBuilder.Build(successTraj.Steps);

        // Check if a plan already exists (idempotency).
        bool planExists = await _db.GraphEditPlans
            .AnyAsync(p => p.FailedTrajectoryId == cmd.FailedTrajectoryId
                        && p.SuccessfulTrajectoryId == cmd.SuccessfulTrajectoryId, ct);
        if (planExists)
            return Unit.Value;  // Already processed.

        // Compute edit plan (may be long-running).
        GraphEditPlan plan;
        try
        {
            plan = await _editPlanCalculator.CalculateEditPlanAsync(failedGraph, successGraph, ct);
        }
        catch (Exception ex) when (ct.IsCancellationRequested)
        {
            // Log and optionally rethrow or handle as timeout.
            throw new OperationCanceledException("Edit plan calculation cancelled", ex);
        }

        // Validate the plan by applying it.
        ValidatePlan(failedGraph, successGraph, plan);

        // Persist the plan and provenance in one transaction.
        using var tx = await _db.Database.BeginTransactionAsync(ct);
        _db.GraphEditPlans.Add(plan);
        await _db.SaveChangesAsync(ct);
        await tx.CommitAsync(ct);

        // Publish an event (out-of-transaction, via eventual consistency).
        await _eventBus.PublishAsync(new GraphEditPlanCreatedEvent(plan.Id, cmd.FailedTrajectoryId, cmd.SuccessfulTrajectoryId), ct);

        return Unit.Value;
    }

    private void ValidatePlan(ActionDecisionGraph failed, ActionDecisionGraph success, GraphEditPlan plan)
    {
        // Apply operations to a copy of 'failed' and ensure it matches 'success'.
        var copy = failed.DeepCopy();
        foreach (var op in plan.Operations)
            ApplyOperation(copy, op);
        if (!copy.Equals(success))
            throw new InvalidOperationException("Validation failed: edit plan does not produce target graph.");
    }

    // ... (ApplyOperation details omitted for brevity) ...
}

Transaction Boundaries: We separate graph construction/alignment (pure in-memory computation) from the database transaction. Trajectory loading is read-only; building graphs and calling the solver happens outside any transaction scope to avoid long locks. Only the final save of the GraphEditPlan is wrapped in a transaction (to ensure atomic write and event publication). This follows the Outbox pattern: the event is published after the DB commit, ensuring consistency.

Concurrency: We enforce idempotency at the DB level with a unique index on (FailedTrajectoryId, SuccessfulTrajectoryId). If two handlers race, one will succeed in insert and the other will get a unique-key violation (caught and ignored, as the plan already exists).

Provenance: We record SolverVersion, Seed, and CreatedUtc in the plan for traceability.

Persistence (EF Core & SQL)

We use EF Core code-first mappings and migrations to define tables. Highlights:

modelBuilder.Entity<GraphEditPlan>(entity =>
{
    entity.HasKey(p => p.Id);
    entity.Property(p => p.CreatedUtc)
          .HasConversion(v => v.ToUniversalTime(), v => DateTime.SpecifyKind(v, DateTimeKind.Utc));
    entity.Property(p => p.SolverVersion).IsRequired();
    entity.Property(p => p.Seed);
    entity.Property(p => p.TotalCost);
    entity.Property(p => p.RowVersion)
          .IsRowVersion()
          .IsConcurrencyToken();

    // Unique index for idempotency (one plan per trajectory-pair).
    entity.HasIndex(p => new { p.FailedTrajectoryId, p.SuccessfulTrajectoryId })
          .IsUnique();
});

• Tables:
• AgentTrajectories(Id PK, Query, IsSuccess, CreatedUtc, ...) with related TrajectorySteps(StepId, TrajectoryId FK, StepNumber, ObservationText, ActionText, ActionResultText). Steps are an owned collection or separate entity.
• ActionDecisionGraphs (if we choose to persist graphs) would store nodes/edges, but we treat ADGs as ephemeral. If needed, we could have a table ActionDecisionNodes(GraphId, ActionText, ...) with graph ID and labels, etc. For now, we skip persisting ADGs to limit storage (we rebuild as needed).
• GraphEditPlans(Id PK, FailedTrajectoryId FK, SuccessfulTrajectoryId FK, SolverVersion, Seed, TotalCost, CreatedUtc, RowVersion) as above.
• GraphEditOperations(OperationId PK, PlanId FK, OperationOrder, Discriminator, [fields per op]). We use TPH (table-per-hierarchy) or separate tables for ops. For simplicity, we store all ops in one table with a Discriminator (AddNode, DeleteNode, etc) and columns for each op type’s fields.

• Indexes/Constraints:
• Unique constraint on (FailedTrajectoryId, SuccessfulTrajectoryId) to prevent duplicates.
• Foreign keys from operations to plan, and from plan to trajectories.
• Timestamp column RowVersion on GraphEditPlan for optimistic concurrency.

• Data types: Use int (SQL int) for small numeric fields, nvarchar(max) for large text or JSON. All dates use datetimeoffset (mapping DateTimeOffset in C#). No INT32 type; in C# we use int (alias for System.Int32) and in SQL an int column.

• Storing Large Data: For large graphs or solver outputs (e.g. coupling matrices), we do not create a relational row per element. Instead:
• Graphs: If we needed to persist ADGs, we could store the adjacency as a JSON document in nvarchar(max) columns using EF Core’s JSON support. For example, GraphNodes and GraphEdges could be stored in JSON to avoid a huge normalized schema.
• Solver Artifacts: The coupling matrix (transport plan) can be large and sparse. We suggest storing it externally (e.g. in blob storage) and saving only a reference (URI or GUID) in the database. If stored in SQL, use a varbinary(max) or nvarchar(max) with compression.
• Node Features: (e.g. embeddings or textual summaries) can similarly be serialized to JSON columns. EF Core 7.0’s ToJson() mapping makes this easy. The example above shows storing an owned aggregate as JSON in Authors.Contact. We can adopt the same for any owned types.

• Optimistic Concurrency: We use a byte[] RowVersion with [Timestamp] on GraphEditPlan. EF Core will include this in the WHERE clause on update, throwing DbUpdateConcurrencyException if there’s a conflict. This is standard practice.

Tests

We provide comprehensive xUnit tests covering each requirement. Examples:

public class GraphBuilderTests
{
    [Fact]
    public void NodeReuse_MergesIdenticalActions()
    {
        // Two identical actions in different contexts produce one node.
        var steps = new List<TrajectoryStep>
        {
            new(... ActionText="move to kitchen", ...),
            new(... ActionText="pick apple", ...),
            new(... ActionText="move to kitchen", ...)  // same action text
        };
        var graph = graphBuilder.Build(steps);
        int nodeCount = graph.Nodes.Count(node => node.Action.ActionType == "move");
        Assert.Equal(1, nodeCount);  // reused node
    }

    [Fact]
    public void InvalidActionLoops_CreateParallelEdges()
    {
        // Several invalid actions from same state should not form a chain.
        var steps = new List<TrajectoryStep>
        {
            new(... ObservationText="state1", ActionText="drink water", ActionResultText="nothing happens"),
            new(... ObservationText="state1", ActionText="drink water", ActionResultText="nothing happens")
        };
        var graph = graphBuilder.Build(steps);
        var edges = graph.Edges
            .Where(e => e.FromNodeId == e.ToNodeId)
            .ToList();
        Assert.Equal(2, edges.Count);  // two parallel edges from INIT to INIT
    }

    [Fact]
    public void ComputeHash_IsStableAcrossRuns()
    {
        var steps = ... // some trajectory
        var g1 = graphBuilder.Build(steps);
        var g2 = graphBuilder.Build(steps);
        Assert.Equal(g1.ComputeCanonicalHash(), g2.ComputeCanonicalHash());
    }
}

public class EditPlanHandlerTests
{
    [Fact]
    public async Task Handler_IsIdempotent_WhenPlanAlreadyExists()
    {
        // Arrange two identical trajectory records.
        // Save a GraphEditPlan for them in the test DB.
        // Act: call handler twice.
        // Assert: second call does not throw and does not create a duplicate plan.
    }

    [Fact]
    public async Task PlanVerification_FailsIfPlanIncorrect()
    {
        // Arrange a fake edit plan that does not match the graphs.
        // Act: call ValidatePlan and expect exception.
    }

    [Fact]
    public async Task ConcurrencyConflict_RaisesException()
    {
        // Simulate two concurrent inserts on GraphEditPlan with same PK or trajectories.
        // EF Core should throw DbUpdateConcurrencyException for one.
    }
}

Additionally, we implement an Edit-Plan Verifier: a method that takes a copy of the failed graph and applies each GraphEditOperation in order, then compares to the successful graph. This independent check ensures correctness. Each test asserts exact ordering of operations (e.g. delete before add) and that no extra operations exist.

We also mock the graph-aligner to test the pipeline without the actual solver: for example, we inject a fake IGraphEditPlanCalculator that returns a known plan, and verify the handler saves it and publishes the event.

Operational Architecture

We envision an offline, asynchronous processing pipeline:

sequenceDiagram
    participant Agent as "LLM Agent / UI"
    participant CommandService as "CQRS Command Handler"
    participant TrajStore as "Trajectory Store (DB)"
    participant GraphBuilder
    participant Solver as "Graph Alignment Solver"
    participant PlanStore as "GraphEditPlan Store (DB)"
    participant EventBus as "Message Bus"
    Agent->>CommandService: Send GenerateEditPlan(failedId, successId)
    CommandService->>TrajStore: Load(failedId), Load(successId)
    CommandService->>GraphBuilder: Build ADGs
    GraphBuilder-->>CommandService: ADGs
    CommandService->>Solver: ComputeEditPlan(ADGs)
    Solver-->>CommandService: EditPlan
    CommandService->>CommandService: Validate plan
    CommandService->>PlanStore: Save(GraphEditPlan)
    CommandService->>EventBus: Publish(GraphEditPlanCreated)
    EventBus-->>Agent: Notify(edit plan available)

In deployment:

• Queueing: GenerateEditPlan commands are queued in a durable queue (e.g. Azure Service Bus or RabbitMQ). A background worker (a .NET Hosted Service) processes these commands sequentially or in parallel.
• Retry & Dead-Letter: If processing fails (e.g. network error, solver error), we retry with exponential backoff. After N failed attempts, the message goes to a dead-letter queue and an alert is raised. As one best practice notes, silent background failures can be devastating: we therefore log every exception and notify on dead-letter.
• Solver Isolation: The graph solver can be resource-intensive (and possibly written in Python/ML stack). We run it isolated (either in a separate process/container or via an asynchronous service). We pass a cancellation token and enforce a timeout. If the solver library supports GPU or async, we manage threads accordingly, but results (alignments) are returned deterministically given a fixed seed.
• Metrics & Tracing: Each step (build time, solve time, DB time) emits metrics (e.g. Prometheus counters/gauges). We instrument distributed traces (e.g. OpenTelemetry) across the service boundary (injection via DI) to correlate command lifecycle.
• Versioning and Audit: We tag each record with graph-schema and solver versions. If normalization changes, we trigger reprocessing of all stored trajectories to update memory graphs. All domain events and commands include version tags. Audit tables can log who/when a plan was computed.
• Mermaid Component Diagram: System components are illustrated below.

graph LR
    A[User/Agent Interface] -->|requests| B[API / CQRS Service]
    B --> C[(SQL DB)]
    B --> D[GraphBuilder Service]
    B --> E[GraphAlignment Service]
    B --> F[Event Bus]
    E -->|metadata| C
    F -->|EditPlanAvailable| G[LLM Agent Execution]

Complexity and Scalability

• Graph Build: O(T) time for T steps; small in practice. Uses O(N+E) memory for N unique actions, E edges. Deterministic hashing adds O(N log N) for sorting nodes. Memory footprint is modest (hundreds of nodes).
• Graph Alignment: Worst-case O(n³·|L|) time for FGW (n = #nodes, |L| = #edge labels). In experiments, n is “a few dozen” (e.g. <100), so this is a few million ops. On modern hardware, sub-second to few-second latency is typical. If tasks grow to thousands of steps, we would need to approximate (e.g. graph coarsening or use smaller subgraphs).
• Database: Storage scales with number of trajectories and plans. Each plan has O(p) rows (p = number of ops). Using JSON columns keeps rows small. Index on (FailedId,SuccessId) allows fast lookup for duplicates.
• Parallelism: The design allows multiple commands to be processed in parallel (by parallel workers) as long as they concern different trajectory pairs. Concurrency is controlled via the DB unique index.
• Bottlenecks: The solver is the heaviest component; we mitigate by caching recent graph builds and reusing plans if identical inputs reappear. We also keep graphs in-memory long enough to avoid redundant rebuilds.

Failure Modes and Security

• Failure: If graph-building or alignment throws (e.g. due to numerical issues), the handler logs the exception and the message is retried. After too many failures, it moves to dead-letter. We avoid losing data by never discarding the failed message without visibility.
• Concurrency: Optimistic concurrency (rowversion) prevents lost updates. If two workers try to insert the same plan, one will succeed and the other will get a DbUpdateConcurrencyException which we catch and handle (treat as “already done”).
• Invalid Plans: We verify each plan by simulation. If the solver output is incorrect (not reaching the target graph), we reject it and can optionally fall back to a simpler diff (e.g. only keep common subgraph) or flag for manual review.
• Data Sensitivity: Trajectories may contain user queries or private data. We treat them as sensitive: all storage is access-controlled, and any logging avoids storing raw text (only normalized labels). The graph search does not expose data beyond planned operations.
• Injection Attacks: We ensure all text is treated as data, never executed. The graph operations are applied in-memory, so there is no SQL injection.
• Audit: Every command and plan is logged with user/task ID. We can trace which plan originated from which trajectory pair.

Implementation Plan

1. Domain Model: Define C# classes with attributes and XML comments as above. Ensure deterministic JSON serialization settings (e.g. custom JsonSerializerOptions) for value objects. Unit-test equality of NormalizedAction and hashing.
2. Graph Builder: Implement IActionDecisionGraphBuilder.Build per algorithm described, including parallel edges logic. Write unit tests for node reuse and loops.
3. Graph Alignment Interface: Create IGraphEditPlanCalculator and a concrete FgwGraphEditPlanCalculator that wraps an FGW solver library (or stub for now). Ensure ability to inject a seed.
4. Edit Plan Extraction: Implement logic to derive GraphEditPlan from the solver’s node-matching (Algorithms 2 & 3 in EMG Appendix B).
5. Command Handler: Use MediatR to write GenerateEditPlanHandler. Ensure transaction management and event publishing.
6. EF Core Persistence: Create DbContext and entity configurations for AgentTrajectory, TrajectoryStep, GraphEditPlan, and GraphEditOperation. Add migrations to produce SQL tables and indices (including unique index and rowversion).
7. Tests: Write xUnit tests for graph construction, alignment (using a fake solver), handler idempotency, concurrency, timeout scenarios, and plan application. Include a test verifying the plan transform correctness (apply and compare).
8. Background Worker: Implement a hosted service that pulls commands from a queue and uses MediatR to send them. Configure retries and dead-letter (e.g. via Azure Functions retry policy or Polly).
9. Diagrams and Documentation: Add sequence/component diagrams (Mermaid) and a design document summarizing decisions and citing sources as needed.
10. Review Unresolved Issues: Note any open research questions (below) and plan for addressing them in future iterations.

Open Questions

• Solver Determinism: If FGWAlign uses random restarts, how to guarantee determinism? We mitigate by fixed seed, but future solver updates might change behavior. We should version the solver and record seeds.
• Edit-Operation Granularity: We assume atomic node/edge edits suffice. In rare cases, an optimal edge-swap might exist that our model splits into delete+add. We accept this limited model for now.
• Cross-Task Edits: The EMG framework also suggests building a global memory graph of tasks. Integrating cross-task insights (edges in the memory graph) is future work.
• Schema Evolution: Changing the normalization format (e.g. new fields in NormalizedAction) may invalidate old graphs. We must design a migration strategy: either recompute all graphs or maintain backward compatibility.
• Scale to Many Nodes: If tasks become much larger (hundreds of steps), FGW may become slow. Alternatives (e.g. simpler graph matching heuristics) could be explored.
• Evaluation Metrics: Defining a good cost model or confidence metric is non-trivial. We may need to experiment with weighted operations or incorporate domain knowledge (some actions might have higher significance).

Despite these open issues, the design uses proven techniques from recent literature and standard enterprise practices to achieve a deterministic, offline correction subsystem.