Graphs as Agent Memory: Why Vectors Alone Are Not Enough

The Failure Mode Nobody Talks About

Ask an LLM-powered agent: "Which services will break if we remove the orders.created queue?" Feed it a vector store built from your architecture documents, runbooks, and Confluence pages. You will get a confident, well-written paragraph. It will probably name two or three services. It will almost certainly be incomplete, and the agent has no way to know that.

This is the core limitation of treating an embedding store as your agent's memory. Vector search performs approximate nearest-neighbor (ANN) retrieval. It finds chunks that are semantically similar to the query. It cannot follow a chain. The question above needs a multi-hop traversal: find every service with a CONSUMES edge to orders.created, then follow the CALLS edges into those services to find the callers that depend on them, and so on. An ANN index cannot express that walk, because it has no edges to follow.

Here is how the two answers differ on a small example:

• Vector result: "The billing-service and fulfillment-api both process order events. Removing the queue may cause downstream processing delays." Plausible, and incomplete. The audit-logger, which consumes every queue in the namespace, is missing because its documentation never mentions orders.created by name.
• Graph traversal result: audit-logger, billing-service, fulfillment-api, and reporting-job, a weekly job that calls billing-service. Four services, because the edges exist. The C# code later in this article returns exactly this list against a real NebulaGraph instance.

This article looks at knowledge graphs as structured agent memory. If you have not read the Graph-Native Data Structures series on this site, that is a good place to start, because the traversal mechanics here build on it.

What Belongs Where

Before writing a single line of schema, decide what should live in the graph and what should stay in the embedding store. The two are complementary, not competing.

Put in the graph:

• Explicit entity to entity relationships, ServiceA CALLS ServiceB, ServiceB CONSUMES QueueC
• Multi-hop dependency chains that need to be walked, not recalled
• Temporal fact evolution: when a dependency was added, removed, or changed
• Contradiction resolution: when Service B no longer consumes Queue C, you retire the edge with a timestamp rather than leaving two conflicting embedding chunks that both rank highly on the same query

Keep in the embedding store:

• Unstructured prose: runbooks, incident reports, architecture decision records
• Fuzzy semantic recall: "what did we decide about retry logic?"
• Cold-start lookup before the graph is populated

A vector store plus a knowledge graph is a common pattern in agent memory frameworks. Zep builds its memory on Graphiti, a temporal knowledge graph that it searches together with embeddings, and Mem0 (which raised $24M in seed and Series A funding in October 2025) offers a graph memory option next to its vector store. The split also helps the graph itself: traversals slow down around very high-degree vertices, so letting the embedding store take the unstructured text keeps the graph to typed, queryable relationships.

Modeling the Dependency Graph in NebulaGraph

NebulaGraph 3.8.0 (Apache 2.0, released May 2024) is the latest open-source release. It is a distributed system, with metad, storaged and graphd processes, and it is not embeddable. Even in development, plan for Docker Compose.

One schema constraint catches people coming from other graph databases: by default, every vertex must carry at least one tag. NebulaGraph 3.8.0 can store vertices without tags, but only after you set --graph_use_vertex_key=true on every Graph service and --use_vertex_key=true on every Storage service.

NebulaGraph supports both native nGQL and openCypher-compatible syntax. Do not mix them in one composite statement, because the behaviour is undefined. The schema below is plain nGQL, and the traversal uses the openCypher-style MATCH.

nGQL Schema

# Run in NebulaGraph Console or Studio. nGQL comments start with # or //, not --
CREATE SPACE IF NOT EXISTS infra_memory(
  vid_type = FIXED_STRING(128),
  partition_num = 10,
  replica_factor = 1
);
USE infra_memory;
 
# Tags (vertex types)
CREATE TAG IF NOT EXISTS Service(
  name     string NOT NULL,
  language string,
  team     string
);
 
CREATE TAG IF NOT EXISTS Queue(
  name      string NOT NULL,
  broker    string DEFAULT "rabbitmq",
  durable   bool   DEFAULT true
);
 
CREATE TAG IF NOT EXISTS Database(
  name   string NOT NULL,
  engine string
);
 
CREATE TAG IF NOT EXISTS Deployment(
  cluster     string NOT NULL,
  namespace   string,
  replicas    int    DEFAULT 1
);
 
# Edge types
CREATE EDGE IF NOT EXISTS CONSUMES(
  since    datetime,
  retired  datetime DEFAULT datetime("9999-12-31T00:00:00")
);
 
CREATE EDGE IF NOT EXISTS CALLS(
  protocol string DEFAULT "http",
  timeout_ms int DEFAULT 5000
);
 
CREATE EDGE IF NOT EXISTS DEPLOYED_TO(
  deployed_at datetime
);
 
CREATE EDGE IF NOT EXISTS READS_FROM();
CREATE EDGE IF NOT EXISTS WRITES_TO();

Tags and edge types are created asynchronously. NebulaGraph's documentation says to wait two heartbeat cycles, 20 seconds with the default heartbeat_interval_secs of 10, before inserting data that uses them, so a setup script should pause or retry between the schema and the first INSERT.

The retired field on CONSUMES is the contradiction-resolution mechanism. When a dependency is removed, you set retired to the current time rather than deleting the edge. History is preserved, and the traversal keeps only edges where retired > datetime(). Note that it has to be datetime(): in nGQL, now() returns an integer Unix timestamp, and comparing a datetime property with it matches nothing.

C# Client Wiring

The .NET client is NebulaNet (nebula-contrib/nebula-net, NuGet version 3.0.0, published March 2022, targeting netstandard2.1). NebulaGraph's documentation lists it only as a community-contributed client, with no support guarantee, and its README maps 3.0.0 to "3.x" without naming a minor version. The code below runs against 3.8.0. The official documentation describes thread-safe pools only for the Java and Go clients. NebulaNet hands out pooled sessions through NebulaPool; take one per query and release it, as the repository does.

The client sends plain statement strings and has no parameter binding, so every value that goes into a query has to be escaped. That is what Quote does. When a statement fails, ExecuteAsync throws a plain Exception whose message is the server's error followed by the full statement, so be careful about where those messages get logged.

using System.Text;
using Nebula.Common;
using NebulaNet;
 
public sealed class NebulaInfraRepository
{
    private readonly NebulaPool _pool;
 
    public NebulaInfraRepository(NebulaPool pool) => _pool = pool;
 
    /// <summary>
    /// Services with an active CONSUMES edge to the queue, plus the services
    /// that CALL those consumers. A two-hop walk that a vector index cannot do.
    /// </summary>
    public async Task<IReadOnlyList<string>> GetDependantsAsync(string queueId)
    {
        var data = await QueryAsync($"""
            USE infra_memory;
            MATCH (s:Service)-[c:CONSUMES]->(q:Queue)
            WHERE id(q) == {Quote(queueId)} AND c.retired > datetime()
            OPTIONAL MATCH (caller:Service)-[:CALLS]->(s)
            RETURN DISTINCT id(s) AS direct_consumer, id(caller) AS indirect_caller;
            """);
 
        var dependants = new SortedSet<string>(StringComparer.Ordinal);
        foreach (var row in data.Rows)
        {
            foreach (var value in row.Values)
            {
                // A service with no callers comes back with a null indirect_caller.
                if (value.SVal is not null) dependants.Add(Encoding.UTF8.GetString(value.SVal));
            }
        }
        return dependants.ToList();
    }
 
    /// <summary>
    /// Adds an active CONSUMES edge unless one already exists. Each edge gets its
    /// own rank, so retired edges stay in the graph as history.
    /// </summary>
    public async Task AddConsumesAsync(string serviceId, string queueId)
    {
        if ((await ActiveRanksAsync(serviceId, queueId)).Count > 0) return;
 
        var rank = DateTimeOffset.UtcNow.ToUnixTimeMilliseconds();
        await QueryAsync($"""
            USE infra_memory;
            INSERT EDGE CONSUMES(since, retired)
            VALUES {Quote(serviceId)}->{Quote(queueId)}@{rank}:(datetime(), datetime("9999-12-31T00:00:00"));
            """);
    }
 
    /// <summary>Retires every active CONSUMES edge from the service to the queue.</summary>
    public async Task RetireConsumesAsync(string serviceId, string queueId)
    {
        foreach (var rank in await ActiveRanksAsync(serviceId, queueId))
        {
            await QueryAsync($"""
                USE infra_memory;
                UPDATE EDGE ON CONSUMES {Quote(serviceId)}->{Quote(queueId)}@{rank}
                SET retired = datetime();
                """);
        }
    }
 
    private async Task<List<long>> ActiveRanksAsync(string serviceId, string queueId)
    {
        var data = await QueryAsync($"""
            USE infra_memory;
            GO FROM {Quote(serviceId)} OVER CONSUMES
            WHERE CONSUMES._dst == {Quote(queueId)} AND CONSUMES.retired > datetime()
            YIELD CONSUMES._rank AS r;
            """);
        return data.Rows.Select(row => row.Values[0].IVal).ToList();
    }
 
    private async Task<DataSet> QueryAsync(string ngql)
    {
        var session = await _pool.GetSessionAsync();
        try
        {
            // NebulaNet throws on any non-zero error code, so there is nothing to check here.
            var response = await session.ExecuteAsync(ngql);
            return response.Data ?? new DataSet { Rows = new List<Row>() };
        }
        finally
        {
            session.Release();
        }
    }
 
    // NebulaNet has no bound parameters, so every string literal is escaped here.
    private static string Quote(string value) =>
        "\"" + value.Replace("\\", "\\\\").Replace("\"", "\\\"") + "\"";
}

Calling AddConsumesAsync twice leaves one active edge, not two. Retiring an edge and adding it again leaves two edges: the retired one, which records when the dependency was dropped, and a new active one.

Register it in your DI container. AddNebulaGraph comes with NebulaNet and registers NebulaPool as a singleton:

builder.Services.AddNebulaGraph(config =>
{
    config.Ip = "127.0.0.1";
    config.Port = 9669;
    config.UserName = "root";
    config.Password = "nebula";
});
builder.Services.AddSingleton<NebulaInfraRepository>();

The Cost of Keeping the Graph Current

Here is the part that vendor demos skip. A fresh graph is empty. Something has to build it: extract entities and relationships from your architecture docs, Terraform outputs, and service manifests, resolve duplicates, and keep edges current as the system evolves. That extraction step is typically an LLM call, which means it is slow, costs tokens, and can hallucinate edges.

Entity resolution is genuinely hard. orders-created-queue, orders.created, and OrdersCreatedQueue may all refer to the same vertex. Unresolved, they fragment your graph and break traversals.

The practical approach for a codebase-and-infrastructure graph:

1. Seed from machine-readable sources first. Parse docker-compose.yml, Kubernetes service manifests, AsyncAPI specs, and OpenAPI documents. These give you high-confidence edges without LLM inference.
2. Use the LLM for prose sources only, runbooks, ADRs and incident post mortems. Accept lower confidence; flag edges with a source: llm property and a confidence score.
3. Run reconciliation on deploy. When a service is deployed, re-examine its manifest edges and retire anything that disappeared.

The third step has its own pitfalls, and Keep Your Knowledge Graph Current Without a Team walks through a reconciliation worker that does it.

Keep watching how many edges each vertex collects. If you start storing every log line as an edge, a handful of vertices end up with huge fan-out and traversals through them slow down. The embedding store absorbs that unstructured load; the graph stays focused on typed, queryable relationships.

Where This Is Heading

NebulaGraph Enterprise v5.2 (November 2025) added graph, vector and full-text retrieval in a single query, and NebulaGraph claims up to 100 times faster path queries along with wider ISO GQL support. That is the commercial edition. The open-source 3.8.0 used here is the version you can run today without a licence, and it has no built-in vector search, which is why the embedding store stays a separate system in this design.

In August 2025, Gartner predicted that up to 40% of enterprise applications would include task-specific AI agents by the end of 2026, up from less than 5% in 2025. Most of those agents will start with a pure vector store because it is fast and has no cold-start cost. The failure mode at the top of this article is what they will hit next. A knowledge graph does not replace the embedding store. It is the layer that answers the questions the embedding store cannot.

To see the two stores working together on one query, read Hybrid Vector + Graph Retrieval in C# for Agent Memory.