Skip to content

Graph retrieval reads the whole graph on every call: proposal for adjacency, observation and name-token indexes #1450

Closed

Description

@david-waltermire

Summary

Graph retrieval reads the whole graph on every call. The cost grows with the graph, and it is already large. This proposes three small key-value indexes, maintained in persistGraphDelta like the existing name, edge-key and degree indexes, so that retrieval reads only the part of the graph it visits.

This is a design proposal. There is no code yet, and I would like maintainer input before writing any. It builds on #1445 (bounded provenance) and #1446 (skip graph reads at weight 0).

The problem, on current main

GraphRetrieval.searchByEntities, expandFromChunks and temporalQuery each start with kv.list(KV.graphNodes) and kv.list(KV.graphEdges). Then:

  • searchByEntities matches names by substring over every node.
  • expandFromChunks scans every node's sourceObservationIds for the chunk ids.
  • dijkstraTraversal walks the full edge array to find neighbors.

Whole-scope graph reads also remain in temporal-graph.ts, cascade.ts, mesh.ts, reflect.ts, snapshot.ts, graph-node.ts and mcp/server.ts.

Measured on one store, 2026-09-30, after compacting provenance with #1445:

Records Size Growth over 5 days
mem:graph:nodes 41,702 43 MB (about 1 KB each) +50% (from 27,718)
mem:graph:edges 59,536 57 MB (about 1 KB each) +48% (from 40,175)

So one retrieval call moves about 100 MB from the engine to the worker, and that grows by about 20 MB a day. Two limits make this fail, not just slow:

Parsing a 50 MB list also blocks the worker's event loop.

Proposal

Three indexes, all keyed so that each read is a small kv.get:

  1. Adjacency: mem:graph:adjacency, keyed by node id, holding the ids of incident edges.
    • Traversal becomes a bounded breadth-first walk: fetch a node's edge ids, then those edges, then the neighbor nodes.
    • Work is proportional to the nodes visited (at most maxDepth hops and maxResults), not to the graph.
  2. Observation to node: mem:graph:obs-nodes, keyed by observation id, holding node ids.
  3. Name tokens: mem:graph:name-token, keyed by lowercased name token, holding node ids.
    • searchByEntities resolves its entities to candidate nodes by token lookup, then applies the current substring test to that candidate set only.

Maintenance: persistGraphDelta already holds graph:persist and writes the name, edge-key and degree indexes. It would write these three in the same pass, with no new lock.

Backfill: a sliced walker over name-index and edge-key, the same shape as the compaction walker in #1445, so it never lists the graph either.

Tradeoffs and open questions

  • Name matching changes shape. Today nameLower.includes(entity) || entity.includes(nameLower) matches any substring. A token index finds candidates by whole tokens. Is token matching acceptable, or should partial matches (for example path fragments) keep a slower fallback?
  • Storage. The existing name index is 3 MB and edge-key is 5 MB on this store. I would expect the three new indexes to be of the same order, but I have not measured it.
  • Order of work. temporalQuery and the other list-based readers could move to the indexes separately. Retrieval is the hot path, so I would start there.

If this direction is welcome, I can send it as a PR after #1445, with the same test-first approach: a characterization test of current retrieval results, then the indexes, then a test that retrieval never calls kv.list on nodes or edges.

Activity

  1. rohitg00 commented on Oct 8, 2026

    @rohitg00
    Owner

    @david-waltermire partially addressed in v0.9.30: node and edge provenance is capped at 32 ids and compacted on first start. Gating structural extraction is not part of the release. https://github.com/rohitg00/agentmemory/releases/tag/v0.9.30

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions