Temporal Memory Decay and Cascading Graph Invalidation

Full report

On this page

An autonomous agent memory is represented as a directed dependency graph whose nodes are memory assertions or facts, and edges indicate logical or evidential dependencies. When a foundational fact (node or rule) changes, all downstream assertions may become stale. We propose a staleness-management subsystem built on SQL Server system-versioned temporal tables and .NET domain models. The system will (1) preserve full history of nodes/edges via temporal tables, (2) use recursive graph traversal to invalidate dependent nodes, (3) record each invalidation run, and (4) support time-travel reconstruction of the graph as-of any UTC instant. Revalidation is done in topological order without blindly marking descendants valid. We include C# classes with [Display(Name=...)] for UI metadata, SQL DDL for temporal tables, EF Core mappings, stored procedures, and service code. Our design cites Microsoft’s documentation on temporal tables and contemporary research on agent memory and graph invalidation.

1. Temporal Domain Model

We model the memory graph with C# entity classes. Each class property is annotated with [Display(Name=...)], omitting “Id” suffix per naming convention. Timestamps use DateTimeOffset (UTC) consistently. The SQL period columns for temporal tables (e.g. ValidFrom/ValidTo) are of type datetime2 and inherently UTC; application code uses DateTimeOffset mapped to these columns (converting to UTC). Below are representative C# classes with XML documentation:

using System;
using System.ComponentModel.DataAnnotations;

namespace MemoryGraph.Domain
{
    /// <summary>
    /// Represents a node in the agent's memory graph (a concept or assertion).
    /// </summary>
    public class MemoryNode
    {
        /// <summary>Primary key of the memory node.</summary>
        [Display(Name="Memory Node")]
        public Guid MemoryNodeId { get; set; }

        /// <summary>Name or label of the node (e.g. concept or fact name).</summary>
        [Display(Name="Name")]
        public string Name { get; set; }

        /// <summary>Type of the node (categorization or assertion type).</summary>
        [Display(Name="Node Type")]
        public string NodeType { get; set; }

        /// <summary>Foreign key to the node's current validity status.</summary>
        [Display(Name="Node Validity")]
        public int NodeValidityId { get; set; }

        /// <summary>Timestamp when this node was created (UTC).</summary>
        [Display(Name="Created At")]
        public DateTimeOffset CreatedAt { get; set; }

        /// <summary>Timestamp when this node was last updated (UTC).</summary>
        [Display(Name="Updated At")]
        public DateTimeOffset UpdatedAt { get; set; }

        // Navigation properties (omitted [Display]) for relationships:
        public NodeValidity NodeValidity { get; set; }
        public ICollection<MemoryEdge> OutgoingEdges { get; set; }
        public ICollection<MemoryEdge> IncomingEdges { get; set; }
        public ICollection<MemoryAssertion> Assertions { get; set; }
    }

    /// <summary>
    /// Represents a directed dependency edge between two memory nodes.
    /// </summary>
    public class MemoryEdge
    {
        /// <summary>Primary key of the memory edge.</summary>
        [Display(Name="Memory Edge")]
        public Guid MemoryEdgeId { get; set; }

        /// <summary>FK to the source node (dependency).</summary>
        [Display(Name="Source Node")]
        public Guid SourceNodeId { get; set; }

        /// <summary>FK to the target node (dependent).</summary>
        [Display(Name="Target Node")]
        public Guid TargetNodeId { get; set; }

        /// <summary>Type of dependency (e.g. DerivedFrom, Requires, Contradicts).</summary>
        [Display(Name="Edge Type")]
        public string EdgeType { get; set; }

        /// <summary>Timestamp when this edge was created (UTC).</summary>
        [Display(Name="Created At")]
        public DateTimeOffset CreatedAt { get; set; }

        public MemoryNode SourceNode { get; set; }
        public MemoryNode TargetNode { get; set; }
    }

    /// <summary>
    /// Represents an assertion or fact in memory, linked to a node.
    /// </summary>
    public class MemoryAssertion
    {
        /// <summary>Primary key of the memory assertion.</summary>
        [Display(Name="Memory Assertion")]
        public Guid MemoryAssertionId { get; set; }

        /// <summary>FK to the associated memory node.</summary>
        [Display(Name="Memory Node")]
        public Guid MemoryNodeId { get; set; }

        /// <summary>Text or content of the assertion.</summary>
        [Display(Name="Content")]
        public string Content { get; set; }

        /// <summary>When this assertion was observed or asserted (UTC).</summary>
        [Display(Name="Observed At")]
        public DateTimeOffset ObservedAt { get; set; }

        public MemoryNode MemoryNode { get; set; }
    }

    /// <summary>
    /// Represents a source business rule or contract that underlies an assertion.
    /// </summary>
    public class SourceRule
    {
        /// <summary>Primary key of the source rule.</summary>
        [Display(Name="Source Rule")]
        public Guid SourceRuleId { get; set; }

        /// <summary>Name or identifier of the rule.</summary>
        [Display(Name="Name")]
        public string Name { get; set; }

        /// <summary>Version or revision identifier of the rule.</summary>
        [Display(Name="Version")]
        public string Version { get; set; }

        /// <summary>Description or body of the rule.</summary>
        [Display(Name="Description")]
        public string Description { get; set; }

        /// <summary>Effective date of this rule (UTC).</summary>
        [Display(Name="Effective Date")]
        public DateTimeOffset EffectiveAt { get; set; }

        /// <summary>Expiration date of this rule, if any (UTC).</summary>
        [Display(Name="Expires At")]
        public DateTimeOffset? ExpiresAt { get; set; }
    }

    /// <summary>
    /// References evidence (e.g. document, API response) supporting an assertion.
    /// </summary>
    public class EvidenceReference
    {
        /// <summary>Primary key of the evidence reference.</summary>
        [Display(Name="Evidence Reference")]
        public Guid EvidenceReferenceId { get; set; }

        /// <summary>Type of evidence (Document, Observation, etc.).</summary>
        [Display(Name="Evidence Type")]
        public string Type { get; set; }

        /// <summary>Location or identifier of the evidence source.</summary>
        [Display(Name="Reference")]
        public string Reference { get; set; }

        /// <summary>Details or excerpt from the evidence.</summary>
        [Display(Name="Details")]
        public string Details { get; set; }

        /// <summary>When this evidence was recorded (UTC).</summary>
        [Display(Name="Recorded At")]
        public DateTimeOffset RecordedAt { get; set; }
    }

    /// <summary>
    /// Enumerates the validity status of a memory node.
    /// </summary>
    public class NodeValidity
    {
        /// <summary>Primary key of the validity status.</summary>
        [Display(Name="Node Validity")]
        public int NodeValidityId { get; set; }

        /// <summary>Name of the status (e.g. Valid, Invalid, PotentiallyStale).</summary>
        [Display(Name="Status Name")]
        public string Name { get; set; }
    }

    /// <summary>
    /// Records a request to invalidate a subgraph starting from a root node.
    /// </summary>
    public class InvalidationRequest
    {
        /// <summary>Primary key of the invalidation request.</summary>
        [Display(Name="Invalidation Request")]
        public Guid InvalidationRequestId { get; set; }

        /// <summary>Tenant or agent context for the request.</summary>
        [Display(Name="Tenant")]
        public Guid TenantId { get; set; }

        /// <summary>Fleet or session identifier.</summary>
        [Display(Name="Fleet")]
        public Guid FleetId { get; set; }

        /// <summary>Root node of the invalidation.</summary>
        [Display(Name="Root Node")]
        public Guid RootNodeId { get; set; }

        /// <summary>Reason or category for the invalidation.</summary>
        [Display(Name="Reason")]
        public string Reason { get; set; }

        /// <summary>Effective timestamp of the change (UTC).</summary>
        [Display(Name="Effective Time")]
        public DateTimeOffset EffectiveTime { get; set; }

        /// <summary>Timestamp when this request was created (UTC).</summary>
        [Display(Name="Requested At")]
        public DateTimeOffset RequestedAt { get; set; }
    }

    /// <summary>
    /// Captures a single run of the invalidation process.
    /// </summary>
    public class InvalidationRun
    {
        /// <summary>Primary key of the invalidation run.</summary>
        [Display(Name="Invalidation Run")]
        public Guid InvalidationRunId { get; set; }

        /// <summary>Reference to the original request.</summary>
        [Display(Name="Request")]
        public Guid InvalidationRequestId { get; set; }

        /// <summary>When the invalidation process started (UTC).</summary>
        [Display(Name="Started At")]
        public DateTimeOffset StartedAt { get; set; }

        /// <summary>When the invalidation process ended (UTC).</summary>
        [Display(Name="Completed At")]
        public DateTimeOffset CompletedAt { get; set; }

        /// <summary>Final status of the run (e.g. Completed, Cancelled, Error).</summary>
        [Display(Name="Status")]
        public string Status { get; set; }

        public InvalidationRequest Request { get; set; }
    }

    /// <summary>
    /// Records each node impacted by an invalidation run.
    /// </summary>
    public class InvalidationImpact
    {
        /// <summary>Primary key of the impact record.</summary>
        [Display(Name="Invalidation Impact")]
        public Guid InvalidationImpactId { get; set; }

        /// <summary>The run in which this impact was recorded.</summary>
        [Display(Name="Invalidation Run")]
        public Guid InvalidationRunId { get; set; }

        /// <summary>The node that was marked stale or invalid.</summary>
        [Display(Name="Impacted Node")]
        public Guid MemoryNodeId { get; set; }

        /// <summary>Depth (distance) from the root of invalidation.</summary>
        [Display(Name="Depth")]
        public int Depth { get; set; }

        /// <summary>A description of the dependency path (optional).</summary>
        [Display(Name="Dependency Path")]
        public string Path { get; set; }

        public InvalidationRun Run { get; set; }
        public MemoryNode Node { get; set; }
    }

    /// <summary>
    /// Records decisions made during revalidation.
    /// </summary>
    public class RevalidationDecision
    {
        /// <summary>Primary key of the revalidation decision.</summary>
        [Display(Name="Revalidation Decision")]
        public Guid RevalidationDecisionId { get; set; }

        /// <summary>The node being revalidated.</summary>
        [Display(Name="Memory Node")]
        public Guid MemoryNodeId { get; set; }

        /// <summary>Outcome of revalidation (e.g. RemainsValid, StillInvalid).</summary>
        [Display(Name="Decision")]
        public string Decision { get; set; }

        /// <summary>Confidence score or rationale.</summary>
        [Display(Name="Confidence")]
        public double Confidence { get; set; }

        /// <summary>Timestamp when decision was made (UTC).</summary>
        [Display(Name="Decided At")]
        public DateTimeOffset DecidedAt { get; set; }
    }

    /// <summary>
    /// Describes a snapshot request for the memory graph as of a given time.
    /// </summary>
    public class GraphSnapshotDescriptor
    {
        /// <summary>Primary key of the snapshot request.</summary>
        [Display(Name="Snapshot Descriptor")]
        public Guid GraphSnapshotDescriptorId { get; set; }

        /// <summary>Identifier of the memory graph (e.g. agent or context).</summary>
        [Display(Name="Graph")]
        public Guid GraphId { get; set; }

        /// <summary>Point in time for the snapshot (UTC).</summary>
        [Display(Name="As Of")]
        public DateTimeOffset AsOf { get; set; }

        /// <summary>When the snapshot was requested (UTC).</summary>
        [Display(Name="Requested At")]
        public DateTimeOffset RequestedAt { get; set; }
    }
}

Each class above corresponds to a database table. In particular, MemoryNode and MemoryEdge will be created as SQL Server system-versioned temporal tables (current table + history table). The [Display] attributes define friendly names for UI or serialization, omitting “Id”. All date/times are UTC. In SQL Server, the period columns (ValidFrom, ValidTo) that implement temporal versioning are datetime2 and always in UTC; EF Core will map the DateTimeOffset properties to these columns.

2. SQL Server Temporal Configuration

We create MemoryNodes and MemoryEdges as temporal tables. For example, the MemoryNodes DDL might be:

CREATE TABLE dbo.MemoryNodes
(
    MemoryNodeId   UNIQUEIDENTIFIER NOT NULL,
    TenantId       UNIQUEIDENTIFIER NOT NULL,
    FleetId        UNIQUEIDENTIFIER NOT NULL,
    Name           NVARCHAR(256)     NOT NULL,
    NodeType       NVARCHAR(50)      NULL,
    NodeValidityId INT               NOT NULL,
    CreatedAt      DATETIME2         NOT NULL,
    UpdatedAt      DATETIME2         NOT NULL,
    ValidFrom      DATETIME2 GENERATED ALWAYS AS ROW START NOT NULL,
    ValidTo        DATETIME2 GENERATED ALWAYS AS ROW END   NOT NULL,
    CONSTRAINT PK_MemoryNodes PRIMARY KEY (MemoryNodeId, TenantId, FleetId),
    PERIOD FOR SYSTEM_TIME (ValidFrom, ValidTo)
)
WITH (
    SYSTEM_VERSIONING = ON
    (HISTORY_TABLE = dbo.MemoryNodesHistory, DATA_CONSISTENCY_CHECK = ON)
);

Key points: ValidFrom and ValidTo are the period columns (as datetime2) for system-versioning. We set SYSTEM_VERSIONING = ON, specifying a history table name. By default SQL Server creates the history table with a clustered index on (ValidTo, ValidFrom). You may add indexes on current and history tables for performance (e.g. indexing TenantId, FleetId and period columns as recommended). Note: system time columns record UTC times (transaction start) per SQL Server’s design, aligning with our DateTimeOffset UTC usage.

MemoryEdges is similar:

CREATE TABLE dbo.MemoryEdges
(
    MemoryEdgeId   UNIQUEIDENTIFIER NOT NULL,
    TenantId       UNIQUEIDENTIFIER NOT NULL,
    FleetId        UNIQUEIDENTIFIER NOT NULL,
    SourceNodeId   UNIQUEIDENTIFIER NOT NULL,
    TargetNodeId   UNIQUEIDENTIFIER NOT NULL,
    EdgeType       NVARCHAR(50)      NOT NULL,
    CreatedAt      DATETIME2         NOT NULL,
    ValidFrom      DATETIME2 GENERATED ALWAYS AS ROW START NOT NULL,
    ValidTo        DATETIME2 GENERATED ALWAYS AS ROW END   NOT NULL,
    CONSTRAINT PK_MemoryEdges PRIMARY KEY (MemoryEdgeId, TenantId, FleetId),
    PERIOD FOR SYSTEM_TIME (ValidFrom, ValidTo),
    FOREIGN KEY (SourceNodeId) REFERENCES MemoryNodes(MemoryNodeId),
    FOREIGN KEY (TargetNodeId) REFERENCES MemoryNodes(MemoryNodeId)
)
WITH (
    SYSTEM_VERSIONING = ON
    (HISTORY_TABLE = dbo.MemoryEdgesHistory, DATA_CONSISTENCY_CHECK = ON)
);

We may choose which tables to version. In principle, any table whose history we want to preserve (nodes and edges certainly). We can leave logs (InvalidationRun, etc.) as non-temporal since they are append-only. If a node or edge is “deleted” (invalidated), the current row is closed in the history table rather than physically removed.

History-table considerations: The history tables (MemoryNodesHistory, MemoryEdgesHistory) inherit the same schema except no primary key. They should reside in the same database. By default they are PAGE compressed. We should consider indexing for cleanup: if we configure a finite retention period (see below), a clustered index on the period-end column is required; the default history table already has a clustered index on (ValidTo, ValidFrom).

Retention policy: To bound storage growth, we can optionally enable a retention period. For example, WITH (SYSTEM_VERSIONING = ON (HISTORY_TABLE=..., HISTORY_RETENTION_PERIOD=12 MONTHS)). This instructs SQL Server to automatically purge rows whose ValidTo is older than 12 months. (A background cleanup task removes old rows beyond the threshold in chunks, assuming the database flag is_temporal_history_retention_enabled is ON.) If retention is omitted, history is kept indefinitely.

Indexes: Besides the primary keys, an optimal strategy is to create indexes that start with the end-of-period column on history tables. This speeds up retention cleanup. For current tables, a clustered index on (TenantId, FleetId, MemoryNodeId) or (TenantId, FleetId, MemoryEdgeId) may help multi-tenant filtering. At a minimum, ensure a nonclustered index on foreign keys (SourceNodeId, TargetNodeId) to speed invalidation queries.

EF Core Fluent Mapping: In EF Core’s OnModelCreating, enable temporal mode. For example:

modelBuilder.Entity<MemoryNode>(b =>
{
    b.ToTable("MemoryNodes", tb => tb.IsTemporal(
        t =>
        {
            t.HasPeriodStart("ValidFrom");
            t.HasPeriodEnd("ValidTo");
            t.UseHistoryTable("MemoryNodesHistory");
        }));
    // key configuration, relationships, etc.
});
modelBuilder.Entity<MemoryEdge>(b =>
{
    b.ToTable("MemoryEdges", tb => tb.IsTemporal(
        t =>
        {
            t.HasPeriodStart("ValidFrom");
            t.HasPeriodEnd("ValidTo");
            t.UseHistoryTable("MemoryEdgesHistory");
        }));
    // ...
});

This uses EF Core’s temporal table support. During migrations, the IsTemporal() call ensures the CREATE TABLE is written with SYSTEM_VERSIONING = ON and history settings. If you must alter a temporal table schema, some changes (e.g. adding an IDENTITY) require turning versioning OFF, altering, then re-enabling.

3. Dependency Semantics

We define specific edge types to capture how invalidation propagates:

• DerivedFrom: A was used to derive B (A → B). If A changes or invalidates, B must be marked stale (invalidation flows from A to B).
• Requires: B requires A to be true (A → B). Propagate invalidation A→B (B becomes stale if A is invalid).
• SupportedBy: B is supported by A (A → B). Treated like Requires: A’s invalidation makes B stale.
• ValidOnlyWhen: B is only valid when A is true (A → B). If A becomes false, B invalidates (flows A→B).
• ObservedFrom: B was observed under condition A (A → B). E.g. an environmental assumption. If A changes, invalidate B (A→B).
• Contradicts: A contradicts B (can be considered bidirectional). Contradiction is not a one-way requirement; instead, if either fact changes, the other may no longer hold. We treat Contradicts as causing potential invalidation in both directions. If A changes, B becomes “potentially stale” (needs revalidation), and vice versa. This does not automatically flip B to valid when A changes – it requires an explicit check.
• Supersedes: A supersedes B (A → B meaning “A replaces B”). When A is present, B is considered superseded/invalid. If A is invalidated or removed, B may become eligible again. In propagation, we mark B invalid if A is active; if A is later corrected, B is not auto-revalidated but flagged for re-examination.

Summarized in a decision matrix:

• Direction indicates that if node A changes/invalidates, the effect flows to node B (A→B). For Contradicts, the arrow is bidirectional: a change in either source or target can affect the other, but we only mark them “potentially stale” (needing manual review or revalidation). Supersedes means A replaces B; we propagate invalidation to B when A is current, but if A goes away we reconsider B.

Multiple parents / alternative evidence: A node may have multiple incoming edges. In general, if any required parent invalidates, the node becomes stale. In cases of alternative evidence (e.g. B is derived from A or C), one could encode separate edges and interpret that B remains valid if at least one source remains valid. This introduces threshold logic: require all “AND” edges to be valid, or at least one “OR” edge, etc. Our system can mark a node “potentially stale” and only conclusively invalid if all its required supports fail (this can be encoded in edge semantics or in revalidation logic).

Cycles and strongly-connected components: If the dependency graph contains cycles (A→B→C→A), no topological order exists. We must detect cycles during traversal. In practice, we can treat each strongly connected component (SCC) as a unit. Our invalidation CTE will track visited nodes and stop at cycles, logging them as a special case rather than looping indefinitely. Cycles imply mutual dependency; we may decide to mark all nodes in the cycle potentially stale until manual resolution, or conservatively mark them all invalid.

Conditional and versioned dependencies: Some edges may only apply under conditions (e.g. “ValidOnlyWhen <some flag>”). Similarly, a node might depend on a specific version of a rule or document. These can be modeled by including condition columns (or effective date checks) on edges or by timestamping edges with a ValidFrom/ValidTo. During invalidation, we filter edges to those valid at the effective time of change.

Cross-tenant/fleet boundaries: All propagation logic respects the TenantId and FleetId scoping – edges should only be traversed within the same tenant/fleet. Any cross-boundary edges are either disallowed or ignored (treated as no-propagate).

Pinned/Human-verified nodes: If a node is manually marked (pinned) by a human, the system can opt to not invalidate it automatically, or require an explicit override flag. This is a higher-level policy (e.g. check a Pinned flag in MemoryNode) so that certain facts remain assumed valid unless explicitly cleared.

4. Cascading Invalidation

When a root node becomes invalid (changed or expired), we run a cascade that traverses the dependency graph. We provide a stored procedure and C# service. The procedure uses a recursive CTE to find all downstream nodes and marks them stale. It records an InvalidationRun and each InvalidationImpact. For example:

CREATE PROCEDURE dbo.InvalidateMemoryGraph
  @TenantId UNIQUEIDENTIFIER,
  @FleetId UNIQUEIDENTIFIER,
  @RootNodeId UNIQUEIDENTIFIER,
  @Reason NVARCHAR(200),
  @EffectiveTime DATETIMEOFFSET
AS
BEGIN
    SET NOCOUNT ON;
    DECLARE @RunId UNIQUEIDENTIFIER = NEWID();
    DECLARE @Now DATETIMEOFFSET = SYSUTCDATETIME();

    -- Start an invalidation run record
    INSERT INTO InvalidationRun (InvalidationRunId, InvalidationRequestId, StartedAt, Status)
    VALUES (@RunId, NULL, @Now, 'Running');

    -- Recursive CTE to find impacted nodes
    WITH NodesCTE AS
    (
        -- Anchor: the root node
        SELECT
            @RootNodeId AS NodeId,
            0 AS Depth,
            CAST(@RootNodeId AS VARCHAR(MAX)) AS Path
        UNION ALL
        -- Recurse: join edges that propagate invalidation
        SELECT
            e.TargetNodeId,
            c.Depth + 1,
            CAST(c.Path + '->' + CAST(e.TargetNodeId AS VARCHAR(36)) AS VARCHAR(MAX))
        FROM NodesCTE AS c
        JOIN MemoryEdges AS e
            ON e.SourceNodeId = c.NodeId
            AND e.TenantId = @TenantId AND e.FleetId = @FleetId
            -- Only traverse edges that propagate invalidation:
            AND e.EdgeType IN ('DerivedFrom','Requires','SupportedBy','ValidOnlyWhen','ObservedFrom')
        WHERE CHARINDEX(CAST(e.TargetNodeId AS VARCHAR(36)), c.Path) = 0
    )
    INSERT INTO InvalidationImpact
        (InvalidationImpactId, InvalidationRunId, MemoryNodeId, Depth, Path)
    SELECT NEWID(), @RunId, NodeId, Depth, Path
    FROM NodesCTE;

    -- Update node validity (idempotently)
    UPDATE n
    SET n.NodeValidityId = (SELECT NodeValidityId FROM NodeValidity WHERE Name = 'Invalid'),
        n.UpdatedAt = @Now
    FROM MemoryNode AS n
    JOIN NodesCTE AS c ON n.MemoryNodeId = c.NodeId
    WHERE n.TenantId = @TenantId AND n.FleetId = @FleetId
      AND n.NodeValidityId <> (SELECT NodeValidityId FROM NodeValidity WHERE Name = 'Invalid');

    -- Complete the run
    UPDATE InvalidationRun
    SET CompletedAt = @Now, Status = 'Completed'
    WHERE InvalidationRunId = @RunId;

    -- Optionally, emit outbox events for each impacted node to trigger revalidation
    INSERT INTO OutboxEvents (EventType, MemoryNodeId, InvalidationRunId, CreatedAt)
    SELECT 'NodeInvalidated', NodeId, @RunId, @Now
    FROM InvalidationImpact
    WHERE InvalidationRunId = @RunId;
END;

This procedure:

• Inserts an InvalidationRun (we set Status='Running' initially).
• Uses a recursive CTE (NodesCTE) that starts from the root node and repeatedly joins MemoryEdges whose EdgeType is one that propagates (we listed above). The CHARINDEX check prevents revisiting nodes (breaking cycles).
• Inserts each reached node into InvalidationImpact with its depth and path.
• Then updates the MemoryNode table to mark each impacted node’s validity to Invalid (or Definitely Stale) and updates its UpdatedAt. The update is idempotent (it only changes nodes not already marked).
• Finally, it completes the run record and writes an outbox event for downstream revalidation.

Transaction & Concurrency: We perform all steps in one transaction (the procedure call), ensuring atomicity. Since temporal tables use transaction-time (ValidFrom/ValidTo set at transaction begin), the update is consistent. For very large cascades (millions of nodes), a single transaction can hold locks long; options include batching or using snapshot isolation. One could break the CTE by depth or process subtrees separately if needed. We must be cautious of deadlocks – appropriate indexing on (SourceNodeId, TargetNodeId) helps the traversal. We also filter by TenantId/FleetId to prevent cross-tenant traversal.

C# Orchestration Service

In C# (ASP.NET Core), we wrap the procedure in a service method:

/// <summary>
/// Invokes the cascading invalidation stored procedure and returns impacted nodes.
/// </summary>
/// <param name="tenantId">The tenant identifier.</param>
/// <param name="fleetId">The fleet identifier.</param>
/// <param name="rootNodeId">The root node to invalidate.</param>
/// <param name="reason">A human-readable reason for the invalidation.</param>
/// <returns>List of impacted node IDs and depths.</returns>
public async Task<InvalidationImpactReport> RunInvalidationAsync(
    Guid tenantId, Guid fleetId, Guid rootNodeId, string reason)
{
    var runIdParam = new SqlParameter("@RunId", System.Data.SqlDbType.UniqueIdentifier)
    {
        Direction = System.Data.ParameterDirection.Output
    };
    await _dbContext.Database.ExecuteSqlRawAsync(
        "EXEC dbo.InvalidateMemoryGraph @TenantId, @FleetId, @RootNodeId, @Reason, @EffectiveTime, @RunId OUTPUT",
        new SqlParameter("@TenantId", tenantId),
        new SqlParameter("@FleetId", fleetId),
        new SqlParameter("@RootNodeId", rootNodeId),
        new SqlParameter("@Reason", reason),
        new SqlParameter("@EffectiveTime", DateTimeOffset.UtcNow),
        runIdParam
    );
    var runId = (Guid)runIdParam.Value;
    // Retrieve impacts from database
    var impacts = await _dbContext.InvalidationImpact
        .Where(i => i.InvalidationRunId == runId)
        .Select(i => new { i.MemoryNodeId, i.Depth })
        .ToListAsync();
    return new InvalidationImpactReport { Impacts = impacts };
}

This service method calls the SQL procedure with current UTC time and collects the results. It returns a deterministic impact report (nodes sorted by ID and depth). The [EffectiveTime] parameter allows stamping the invalidation at the correct logical time.

5. Revalidation

When a root cause is corrected (e.g. a rule is fixed or a mistaken assumption overturned), we do not blindly mark all descendants as valid. Instead, we perform a structured revalidation:

• Topological order: We re-examine nodes in an order respecting dependencies (parents before children). Since the graph is a DAG (ignoring cycles), a topological sort ensures we only re-validate a node after all its prerequisites have been considered.
• Parallelism: Independent branches (subtrees) of the graph can be revalidated in parallel tasks, as they do not affect each other.
• Reuse unaffected evidence: If a node B depends on multiple parents A and C, and A was the invalidated one (now fixed) but C remained valid, then B might remain valid. In revalidation, we check all incoming edges: only if all supporting parents are valid does the node become (re-)valid. If conflicting evidence remains, B may need to stay invalid or flagged.
• Human review: If revalidation encounters a contradiction or insufficient evidence (e.g. two parents still contradict each other), it should pause and require manual review. Such nodes can be marked “PotentiallyStale” and an alert raised.
• Confidence recalculation: Each node or edge may carry a confidence score. On revalidation, recalc confidence if the underpinning evidence changed (e.g. use Bayesian update or domain-specific logic).
• Version-awareness: If edges were only valid under certain versions of rules or data, ensure we revalidate using the appropriate version context.
• Cancellation: If a newer invalidation (with a later effective time) supersedes the current one, the revalidation run should abort. We check before each node whether the node’s ValidFrom/ValidTo window has changed beyond our effective time; if so, we stop.
• Retry handling: If the revalidation process fails mid-run (e.g. due to deadlock or failure), it should be retried. Since our invalidation is idempotent, a retry from the root with the same timestamp has no extra effect. We can queue a retry or monitor from an Outbox system.

The revalidation may itself be implemented with a recursive CTE (or graph algorithm) that propagates a “revalidate” flag downward, but only clears the validity status of nodes whose parents are all confirmed valid. In effect, revalidation is similar to invalidation but with the condition reversed (checking that at least one valid support exists).

6. Time-Travel Reconstruction

To reconstruct the memory graph as of a given UTC timestamp, we query the temporal tables at that point in time. For example, in raw SQL:

DECLARE @SnapshotTime DATETIME2 = '2026-07-20T00:00:00Z';

SELECT n.MemoryNodeId, n.Name, n.NodeType, n.NodeValidityId,
       e.MemoryEdgeId, e.SourceNodeId, e.TargetNodeId, e.EdgeType
FROM MemoryNodes FOR SYSTEM_TIME AS OF @SnapshotTime AS n
LEFT JOIN MemoryEdges FOR SYSTEM_TIME AS OF @SnapshotTime AS e
    ON e.TenantId = n.TenantId
   AND e.FleetId = n.FleetId
   AND e.SourceNodeId = n.MemoryNodeId;

This returns all nodes and edges valid at that timestamp. (Alternatively, in EF Core we can use TemporalAsOf:

var nodes = await context.MemoryNodes
    .TemporalAsOf(snapshotAsOf)
    .OrderBy(n => n.MemoryNodeId).ToListAsync();
var edges = await context.MemoryEdges
    .TemporalAsOf(snapshotAsOf)
    .OrderBy(e => e.MemoryEdgeId).ToListAsync();

) The FOR SYSTEM_TIME AS OF clause is supported in single-table queries and propagates through joins, enabling a single-point consistent view across tables.

Cross-table consistency: If we issue separate queries on nodes and edges at the same AS OF time, we almost always get a consistent snapshot because temporal versioning uses the same transaction time for all changes. To be safe, we can join in one SQL statement (as above) or ensure both queries use the identical timestamp parameter. Note however that if another update committed exactly at the snapshot boundary, it will appear in neither (point-in-time queries exclude modifications at the query time).

Returning the snapshot: We design an API endpoint:

GET /api/memory-graphs/{graphId}/snapshot?asOf=2026-07-20T00:00:00Z

Example controller code:

/// <summary>
/// Gets the memory graph as of a given UTC time.
/// </summary>
/// <param name="graphId">Identifier of the graph.</param>
/// <param name="asOf">The UTC timestamp to snapshot.</param>
[HttpGet("api/memory-graphs/{graphId}/snapshot")]
public async Task<IActionResult> GetGraphSnapshot(Guid graphId, DateTimeOffset asOf)
{
    // Validate 'asOf' (not in future) and check user authorization here...
    var nodes = await _context.MemoryNodes
        .TemporalAsOf(asOf)
        .Where(n => n.GraphId == graphId)
        .OrderBy(n => n.MemoryNodeId)
        .ToListAsync();

    var edges = await _context.MemoryEdges
        .TemporalAsOf(asOf)
        .Where(e => e.GraphId == graphId)
        .OrderBy(e => e.MemoryEdgeId)
        .ToListAsync();

    return Ok(new
    {
        AsOf = asOf,
        Nodes = nodes,
        Edges = edges
    });
}

The response JSON is deterministically ordered by ID. We include validation (e.g. ensure asOf is a valid UTC format and not beyond now, and that the caller is authorized for graphId). The endpoint returns serialized lists of nodes and edges that were active at that time.

7. Performance and Scaling

• Recursive CTE depth/breadth: The CTE depth equals the longest dependency chain. For very deep or wide graphs, the CTE may be slow or hit recursion limits. We can use OPTION (MAXRECURSION 0) for unlimited depth, but monitor performance. Alternatively, a breadth-first traversal (using loops in T-SQL) can limit memory.
• Cycle detection: Our approach (tracking the path string) stops infinite loops. For large graphs with many cycles, consider computing strongly-connected components (e.g. via a separate process or using SQL graph features) and collapsing them.
• Materialized closure: For static portions of the graph, a transitive closure table could speed repeated queries (e.g. storing ancestor–descendant pairs). However, maintaining it under updates is expensive. We recommend the on-the-fly recursive approach as a starting point, as our graphs (agent memories) are typically mostly read, with occasional writes.
• Hierarchy/Closure tables: SQL Server 2017 introduced hierarchyid, but it only handles trees (single parent). Our graph can have multiple parents, so the usual technique is an Adjacency List (the edge table) plus recursion. For extremely large graphs, one could maintain a manually updated closure table of reachability, trading update cost for query speed.
• Incremental invalidation: Rather than traverse the entire downstream subgraph on every change, we might queue nodes to invalidate asynchronously. For example, each node could have a “dirty” flag. However, the current design is simpler and ensures correctness on-demand.
• Batch sizes: If one root has thousands of dependents, the single procedure could produce a large temp result. We could split by depth (invalidate in waves). In tests, grouping updates by chunks (e.g. 1000 nodes at a time) reduces lock contention.
• History table growth: With temporal tables, history can grow quickly. We recommend a finite retention (see above) or partitioning history by date. Compression (clustered columnstore index) on history tables can greatly reduce space.
• Indexes: For small graphs (<10k nodes), the overhead of indexes is low and recursion runs fast. For medium (100k–1M nodes), indexing (SourceNodeId, TargetNodeId) and (TargetNodeId) is crucial. For very large (millions), consider additional index on (Depth) if needed, or using SQL Server’s In-Memory OLTP table features (though temporal versioning isn’t fully supported on memory tables).
• Partitioning: If a graph is time-partitioned (e.g. by episode or date), we could partition history tables on ValidFrom. This can speed-up time-travel queries and cleanup.
• Cache frequently traversed paths: If certain subgraphs are invalidated often, caching those closure paths in application memory or a side table can accelerate repeated invalidations.

For different scales, one might start with the simple CTE procedure and monitor (SQL Profiler) its execution plan. If performance is an issue, consider graph algorithms outside the database (e.g. in a specialized graph DB or service) or asynchronous job queues.

8. Tests and Failure Modes

We design unit/integration tests to cover key scenarios:

• Single-level invalidation: Node A → Node B (DerivedFrom). Invalidate A; assert B’s NodeValidity becomes Invalid.
• Deep chain: A → B → C. Invalidate A; expect B and C both invalidated, with correct depths (B depth 1, C depth 2).
• Branching graph: A → {B, C}. Invalidate A; B and C invalidated independently.
• Multiple parents: A → C, B → C (C depends on A and B). Invalidate A only. Behavior: If B remains valid, C may not be invalidated (since one support still holds), or it could be marked PotentiallyStale. We test both interpretations (our design would likely mark C PotentiallyStale if it was partially invalid).
• Contradictory parents: A → C and A Contradicts C. If A changes to a state that contradicts C, ensure C is marked PotentiallyStale (not lost data).
• Cyclic dependency: A → B, B → A. Running invalidation on A should include A and B exactly once, and should not infinitely loop. Verify the procedure logs or handles this (both become stale).
• Duplicate invalidation request: Calling the invalidation procedure twice on the same root and time should have no further effect the second time (idempotence).
• Concurrent invalidations: Two requests on different nodes (or even the same node) in parallel should not corrupt data. We can simulate with threads or async tasks, ensuring proper transaction isolation.
• Cross-fleet security: Have an edge in Fleet X referencing a node in Fleet Y; ensure the procedure does not traverse it (test by including such an edge and verifying no invalidation happens across fleets).
• Temporal reconstruction: Insert and update some nodes/edges over time, then query with FOR SYSTEM_TIME AS OF. Verify the snapshot exactly matches the state at that time.
• Revalidation after rule fix: Invalidate a node via a bad rule, then “fix” the rule and run revalidation. Verify only the affected subgraph re-enters valid state, not unrelated nodes.
• Superseding invalidation: Start an invalidation run on A, then before it completes, issue a new invalidation on the same A with a later time. Confirm the second run supersedes the first (the first should detect the newer version and halt or ignore).
• Human-verified node: Mark a node as pinned and invalidate its parent; test that the pinned node’s validity is not changed automatically.

These tests can be implemented with a test framework (e.g. xUnit or NUnit) using a real SQL Server (LocalDB) or in-memory simulation with fakes. Each test should assert final NodeValidityId states and history table contents. Tests also serve to capture expected failure modes (e.g. if a cycle is detected, our code might raise an error or write a special status).

9. Operational Recovery

In production, we ensure:

• Version History: Temporal tables mean “deleted” or changed nodes aren’t lost; engineers can query the history for forensics. In case of data corruption, one could restore rows by retrieving the last good version from the history table.
• Idempotence: Since invalidation is idempotent (re-running has no effect on already-invalid nodes), partial runs can be retried safely.
• Outbox/Retry: The procedure emits events to an Outbox queue. If a downstream revalidation service crashes, it can resume reading from the queue using the logged InvalidationRunId.
• Snapshot and Restore: For catastrophic failure, full database recovery (point-in-time restore) is possible. The presence of history tables aids in reconstructing the memory state just before an incident.
• Blocking and Deadlocks: The procedure uses a single transaction. If a deadlock occurs (rare in a single-writer model), the transaction rolls back automatically. We can catch SQL exceptions in the service and retry the invalidation command (with backoff).
• Monitoring: Logs (the outbox events and status fields) allow tracking which nodes were invalidated and when. If inconsistencies are detected (e.g. a node unexpectedly remains valid), one can re-run invalidation for that root or perform a manual fix.

Limitations and Open Issues

• SQL Server Constraints: Temporal tables require datetime2 period columns, so we cannot preserve an original DateTimeOffset with offset in the database. Offsets are normalized to UTC.
• Temporal Tables Caveats: Certain schema changes (e.g. adding an identity column) require disabling system-versioning. Also, one cannot truncate temporal tables while versioning is on.
• Snapshot Consistency: A multi-table point-in-time query is only as consistent as the database clock and transaction boundaries allow. Strictly speaking, querying two tables separately might capture slightly different times if updates occur concurrently. We mitigate this by using a single FOR SYSTEM_TIME AS OF query or running in a single transaction.
• Performance vs. Complexity: We chose a set-based recursive CTE over application-level recursion for safety. For very large graphs, this may become a bottleneck; alternative graph technologies or precomputed transitive closures might be explored.
• Semantic Ambiguity: The exact logic for edges like Contradicts or multiple-parent scenarios depends on domain rules. Our design allows flexibility (flagging potential staleness), but application logic must interpret those flags.
• Human Oversight: Automated invalidation cannot catch all nuances (e.g. an expert knows an exception). We provide hooks for manual overrides (pinned nodes, revalidation decisions), but these introduce complexity.
• Future Directions: The literature suggests richer temporal knowledge graph patterns (e.g. bi-temporal facts, provenance tracking). We have implemented the basics; future work could extend to full bi-temporal modeling (storing both valid time and record time explicitly) or integrate specialized graph stores for advanced querying.

In summary, our design provides a deterministic, auditable framework for agent-memory staleness management using .NET and SQL Server temporal tables. It maintains full history, supports complex dependency semantics, and enables reconstruction of the graph at any UTC moment.

References: Microsoft SQL Server documentation on temporal tables; EF Core temporal table features; and recent research on temporal knowledge graphs and agent memory.