Neo4j vector similarity search is O(N) brute-force; HNSW support was added in #859 then removed in #894

[xiaoyaner0201]

Neo4j vector similarity search is O(N) brute-force; HNSW support was added in #859 then removed in #894

Summary

On the Neo4j backend, every vector similarity search computes vector.similarity.cosine() against every matching node/edge in the graph. There is no vector index, and build_indices_and_constraints() never creates one.

On a modest graph (48,647 Entity nodes / 76,264 RELATES_TO edges, 2560-dim embeddings) this makes a single edge_similarity_search take ~41 seconds. Recreating the same query against a manually-created Neo4j HNSW index returns the identical top-20 result set in ~82 ms — a ~500x difference.

Neo4j has supported native vector indexes and db.index.vector.queryRelationships / queryNodes since 5.18. Graphiti currently does not use them on the Neo4j path.

Current behavior

graphiti_core/graph_queries.py (line numbers from 993e081, current main):

def get_vector_cosine_func_query(vec1, vec2, provider: GraphProvider) -> str:   # L155
    if provider == GraphProvider.FALKORDB:
        return f'(2 - vec.cosineDistance({vec1}, vecf32({vec2})))/2'
    if provider == GraphProvider.KUZU:
        return f'array_cosine_similarity({vec1}, {vec2})'
    return f'vector.similarity.cosine({vec1}, {vec2})'                          # L163  ← Neo4j

This helper is called from 11 sites in graphiti_core/search/search_utils.py, including the three primary search entry points:

Line	Function
413	edge_similarity_search
748	node_similarity_search
1137	community_similarity_search
1280, 1327, 1490, 1528, 1677, 1716	hybrid / combined search paths

Neo4jDriver.build_indices_and_constraints() creates range and fulltext indexes only:

range_indices: list[LiteralString] = get_range_indices(self.provider)
fulltext_indices: list[LiteralString] = get_fulltext_indices(self.provider)
index_queries: list[LiteralString] = range_indices + fulltext_indices

A repo-wide search confirms the gap on current main:

• db.index.vector → 0 hits
• CREATE VECTOR INDEX → 1 hit, in examples/ecommerce/runner.ipynb only

This was implemented once and then removed

This is not a feature that was never attempted:

• use hnsw indexes #859 "use hnsw indexes" (merged 2025-08-25) introduced a USE_HNSW env flag, a CREATE VECTOR INDEX ... OPTIONS { indexConfig: { \vector.dimensions`: 1024, `vector.similarity_function`: 'cosine' }}statement, and aGraphProvider.NEO4J and USE_HNSWbranch innode_similarity_searchusingCALL db.index.vector.queryNodes(...)`.
• cleanup #894 "cleanup" (1f5a1b8, 2025-09-05) removed USE_HNSW along with the associated branches.

USE_HNSW has 0 occurrences on current main.

I could not find a recorded rationale for the removal, so this issue is written as a question as much as a report: was the HNSW path dropped intentionally (e.g. hardcoded 1024 dimensions, per-group index naming, recall concerns), or did it fall out as collateral during cleanup? The answer determines whether a re-introduction is welcome and what shape it should take.

Reproduction / measurements

Environment:

• graphiti-core 0.29.2 (behavior verified verbatim against 993e081 on main)
• Neo4j 5.26.26 Community, heap 8G, pagecache 8G
• 48,647 Entity nodes, 76,264 RELATES_TO edges, fact_embedding dimension 2560
• No other workload on the database (the Graphiti MCP server was stopped for the benchmark; with it running, concurrent brute-force scans saturated ~29 CPU-equivalents and made all timings unusable)

All queries issued over the HTTP transaction endpoint. Baseline RETURN 1 measured at 149–162 ms; subtract that from the numbers below.

A — current behavior (brute-force):

WITH [x IN range(1,2560) | rand()] AS v
MATCH (n:Entity)-[e:RELATES_TO]->(m:Entity)
WHERE e.group_id IN ['<group>']
WITH DISTINCT e, n, m, vector.similarity.cosine(e.fact_embedding, v) AS score
WHERE score > 0.0
RETURN e.uuid AS uuid, n.uuid AS src, m.uuid AS dst, score
ORDER BY score DESC LIMIT 20

→ 45208 ms / 42723 ms / 41014 ms

B — same result via HNSW index:

CREATE VECTOR INDEX edge_fact_embedding_hnsw IF NOT EXISTS
FOR ()-[e:RELATES_TO]-() ON (e.fact_embedding)
OPTIONS {indexConfig: {`vector.dimensions`: 2560, `vector.similarity_function`: 'cosine'}}

WITH [x IN range(1,2560) | rand()] AS v
CALL db.index.vector.queryRelationships('edge_fact_embedding_hnsw', 60, v)
YIELD relationship AS e, score
WHERE e.group_id IN ['<group>']
RETURN e.uuid AS uuid, startNode(e).uuid AS src, endNode(e).uuid AS dst, score
ORDER BY score DESC LIMIT 20

→ 1456 ms (cold) / 390 ms / 232 ms

Index build took ~5 minutes for 76,264 edges and reached state=ONLINE, populationPercent=100.0.

Recall check. Using a real edge's fact_embedding as the query vector, top-20 from A and top-20 from B were compared as sets:

brute-force returned: 20
HNSW returned:        20
intersection:         20
only in brute-force:  (none)
only in HNSW:         (none)

This is a single seed, so it is evidence rather than proof — HNSW is approximate by construction and a broader recall sweep would be needed to characterize it properly. Over-fetching (limit * 3) before post-filtering is what makes the group filter safe here, matching the approach in #1335.

Why this matters beyond raw latency

The cost is not paid once per user query. While the Graphiti MCP server was running normally, SHOW TRANSACTIONS consistently showed 5+ concurrent brute-force scans, each already 2+ minutes elapsed, with Neo4j pinned at multiple thousand percent CPU. Stopping the MCP server dropped Neo4j to 0.85% CPU. On the Neo4j path the cost scales with graph size × concurrency, so it degrades exactly as a memory graph becomes worth having.

Related work

• feat(falkordb): Use HNSW vector index procedures for similarity search #1335 (open since 2026-03-20) — feat(falkordb): Use HNSW vector index procedures for similarity search. Same root cause, FalkorDB driver. Reports 6-8 s per query on 3072-dim embeddings.
• perf: add FalkorDB HNSW vector indices and fix O(n) fulltext re-match #1287 (closed, unmerged) — perf: add FalkorDB HNSW vector indices and fix O(n) fulltext re-match. Reports 12-65 s per search.

Both target FalkorDB. Neo4j — the default backend in the README quickstart — has no equivalent open work that I could find, despite having had a partial implementation in-tree a year ago.

Proposed direction

Assuming the removal in #894 was not a deliberate rejection, a re-introduction would need to address the reasons the original was fragile:

1. Create HNSW vector indexes in Neo4jDriver.build_indices_and_constraints() — on Entity.name_embedding, RELATES_TO.fact_embedding, and Community.name_embedding. Dimension must be derived from the configured embedder rather than hardcoded (use hnsw indexes #859 hardcoded 1024; this deployment uses 2560).
2. Route Neo4j similarity searches through db.index.vector.queryNodes / queryRelationships with over-fetch + post-filter, so group_ids and SearchFilters semantics are preserved.
3. Keep the brute-force path available for exact-recall requirements and for graphs whose index has not been built, rather than reintroducing a bare env flag as the only control.

I have the benchmark harness and a fork set up, and I am happy to open a PR for the Neo4j path. Before writing it I would rather have maintainer input on two points, since they determine the shape of the change:

• Is a Neo4j HNSW path wanted at all, given cleanup #894 removed the previous one?
• Should index creation be automatic in build_indices_and_constraints(), or opt-in? Automatic creation on an existing large graph triggers a background population that is expensive once; opt-in avoids surprising existing deployments but leaves the default slow.

Happy to provide the full benchmark scripts, or to run a wider recall sweep across many seeds if that would help the decision.

[xiaoyaner0201]

Opened #1796 as a Draft with a concrete implementation for the Neo4j path, so the proposal is reviewable alongside the question above.

It takes the conservative branch on both open decisions — index creation is opt-in via Neo4jDriver(use_vector_index=True) rather than automatic, and the brute-force path is kept as a fallback rather than replaced. Scope is limited to edge_similarity_search; the node and community paths can follow once the approach is settled.

The Draft is not a claim that the direction is approved. If the removal in #894 was deliberate, I will close it.

[xiaoyaner0201]

Update on #1796 — the Draft now carries a substantially revised implementation.

The first revision post-filtered an over-fetched candidate set (limit * 3) when filters were present. That is a heuristic and can still return fewer results than the caller asked for, so it was removed. The index path is now used only for genuinely unfiltered searches; any group_id, SearchFilters, or endpoint-UUID filter falls back to the exact pre-filtered cosine query. Also added: bounded fallback when the index is missing/offline/populating/mismatched (real errors still propagate), a fail-fast dimension check, and the public Graphiti(use_vector_index=...) / GRAPHITI_NEO4J_USE_VECTOR_INDEX opt-in so MCP-style deployments that never construct Neo4jDriver directly can reach it. Neo4j's 4096-dimension index ceiling is now enforced only when the opt-in is active, so non-opt-in deployments with larger embedders are unaffected.

One thing worth separating from the HNSW question: on current main, in both search_utils.py and the Neo4j search_ops.py, the source_node_uuid / target_node_uuid filters are nested inside if group_ids is not None:. With group_ids=None both endpoint filters are silently dropped and the search returns unrelated edges. The PR de-indents them. That is a pre-existing bug, unrelated to vector indexing — happy to split it into its own PR if you would prefer.

Verification on the exact published tree: 60 focused tests, 107 related/adversarial, 411 passed / 11 skipped across the non-database suite, ruff and ruff format --check clean, pyright 0 errors. No live Neo4j was involved — every test is mock-based or asserts on generated Cypher, so the index path is verified in shape, not behaviour. The benchmark and single-seed recall figures in #1793 and the PR body remain hand-measured on a private deployment and are not reproducible from the repository.

Still Draft, still pending the question above: was the #894 removal deliberate? If a Neo4j HNSW path is not wanted, I will close this.