Research: semantic hierarchy for HNSW — centrality-biased levels, zoom-out retrieval, RAPTOR-style summary trees

# Research: semantic hierarchy for HNSW — centrality-biased level assignment, zoom-out retrieval, RAPTOR-style summary trees

## Status: exploratory

Parts 1–3 of this series are incremental engineering on existing structures. This one is research-flavored: prototype, benchmark, report back — do not productionize without the numbers. It carries enough implementation detail that a capable model/engineer can build the prototype unassisted.

## Problem

RAG over a large corpus needs answers at multiple granularities. "What does this codebase do?" wants cluster-level summaries; "what does `searchLayer` return?" wants a specific chunk. Flat ANN retrieval only serves the second. Hierarchical-retrieval systems (RAPTOR, arXiv:2401.18059; Microsoft GraphRAG's community summaries, arXiv:2404.16130) solve the first by building a summary tree over the corpus — but they bolt it on outside the vector index.

HNSW already *has* a hierarchy — but a common misconception is that its upper layers are semantic. They are not: level assignment is random (exponential distribution, `MAX_LEVEL` 10 in `resources/indexes/HierarchicalNavigableSmallWorld.ts`), so upper-layer nodes are a uniform random sample whose only job is routing. Two questions follow:

1. Can level assignment be *biased* so upper layers become meaningful landmarks (cluster-central records) without hurting — or while improving — search recall/latency?
2. Should Harper offer a RAPTOR-style summary-table pattern on top, where the hierarchy nodes are LLM-generated summaries rather than promoted records?

These compose: (1) makes the index's own hierarchy browsable; (2) builds an explicit semantic tree using only existing Harper features (`@embed`, `@relationship`, HNSW). They can be evaluated independently.

## Thread A: centrality-biased level assignment

### Hypothesis

If upper-layer nodes are chosen by hubness/centrality in the layer-0 k-NN graph instead of randomly, the upper layers become coarse semantic representatives — enabling "zoom-out" retrieval — while routing quality holds or improves (hub nodes are, plausibly, *better* waypoints than random ones). The risk is real: randomness is load-bearing in the HNSW navigability analysis, and biased promotion could create traffic-jam hubs or leave sparse regions unreachable from the top. That's exactly what the benchmark must settle. Treat recall parity as the gate.

### Design sketch

- New index option: `@indexed(type: "HNSW", levelAssignment: "centrality")`, default `"random"` (no behavior change for existing indexes; changing the option is a structural change that triggers reindex, per the existing lifecycle in `resources/databases.ts:1307–1486`).
- Centrality can't be known at insert time, so bias is applied by a **periodic promotion pass**, not at insert:
1. New inserts get level 0 (or the standard random draw — prototype both).
2. A maintenance pass walks layer 0, computes a cheap centrality proxy per node — in-degree over the layer-0 adjacency lists is the obvious one (the lists are already persisted per node; no extra structure needed) — and reassigns levels so the level-ℓ population matches the standard exponential size schedule but is *selected* by centrality rank rather than randomly.
3. Promotion/demotion reuses the existing connection machinery (`addConnection`, bidirectional repair) — a promoted node needs edges built at its new levels; a demoted node needs its upper-level edges removed, mirroring the delete path's edge cleanup.
- Entry-point election logic (insert path lines ~271–278, delete re-election ~418–450) is unchanged — highest level wins; under centrality assignment that's now the most central record.
- The pass can run where reindexing already runs (async, tracked by `Table.indexingOperation`), triggered by a node-count growth threshold (e.g. every 2× growth) rather than per-write.

### Zoom-out retrieval

With meaningful upper layers (either assignment mode, but only useful under centrality):

```js
Docs.search({ sort: { attribute: 'embedding', target: v, level: 2 }, limit: 5 })
```

stops the descent at level 2 and returns level-≥2 nodes nearest the target — i.e. "the 5 most relevant *regions* of the corpus," each a real record that can serve as a cluster representative. Implementation: terminate the layer loop in `search()` (`HierarchicalNavigableSmallWorld.ts:709–718`) at `l = level` and return that layer's results; the result mapping (primaryKey + distance) is unchanged.

### Benchmark gate (the actual deliverable)

Extend `benchmarks/hnsw-search.js`:
- Recall@10 and latency: random vs. centrality assignment, at 100k and 1M vectors, with and without int8 quantization, including post-delete-churn graphs (build, delete 20%, re-insert).
- Maintenance-pass cost: wall time and write amplification per pass.
- Zoom-out quality: with a corpus that has known cluster labels, measure whether level-2+ representatives cover the clusters (purity / coverage vs. k-means centroids as the reference).

If recall drops more than ~1–2% or maintenance cost is pathological, write up the negative result and stop — thread B does not depend on thread A.

## Thread B: RAPTOR-style summary tree as a Harper pattern

No core index changes required — this is a modeling pattern plus (optionally) a maintenance job, and most of it is buildable today:

```graphql
type Chunk @table {
id: ID @primaryKey
text: String
embedding: [Float] @indexed(type: "HNSW") @embed(source: "text", model: "...")
summaryId: String @indexed
summary: Summary @relationship(from: "summaryId")
}
type Summary @table {
id: ID @primaryKey
text: String # LLM-generated summary of member chunks
level: Int @indexed # 1 = summarizes chunks, 2 = summarizes level-1 summaries, ...
embedding: [Float] @indexed(type: "HNSW") @embed(source: "text", model: "...")
parentId: String @indexed
parent: Summary @relationship(from: "parentId")
members: [Chunk] @relationship(to: "summaryId")
}
```

Build loop (a component / scheduled job, using `scope.models` for the summarization calls once available):
1. Cluster chunk embeddings (k-means is fine; GMM per the RAPTOR paper if soft assignment matters). If thread A lands, level-promoted nodes are free cluster seeds; otherwise sample-based k-means over the stored vectors.
2. LLM-summarize each cluster's member texts → insert `Summary` rows; `@embed` indexes them automatically.
3. Recurse on summary embeddings until one root or a size floor.
4. Incremental maintenance: dirty-flag clusters whose membership churns past a threshold; re-summarize those only.

Retrieval composes with the rest of the series: collapsed-tree retrieval (RAPTOR's best-performing mode) is just ANN over `Chunk ∪ Summary` — two searches merged, or one table if chunks and summaries share a table — and relationship expansion (series part 2) walks `members`/`parent` edges to assemble the context bundle around a hit.

**Deliverables for thread B:** a reference component (or skill/docs recipe) implementing the build loop, plus an evaluation on a public QA-over-corpus benchmark comparing flat ANN vs. collapsed-tree retrieval. Identify any core friction encountered (e.g. bulk vector export for clustering — is iterating records sufficient at 1M rows, or is a vector-scan API needed?) and file follow-ups.

## Acceptance

- [ ] Thread A prototype behind `levelAssignment: "centrality"` with the promotion pass; benchmark report (recall/latency/maintenance/zoom-out quality) posted to this issue with a ship / iterate / abandon recommendation.
- [ ] Zoom-out `level` query option implemented in the prototype branch.
- [ ] Thread B reference implementation + retrieval-quality evaluation posted; core-friction follow-ups filed.
- [ ] Neither thread regresses default-path behavior (`levelAssignment: "random"` untouched; summary tree is purely additive schema).

## Out of scope

- Productionizing either thread before the benchmark gates pass.
- Online/streaming centrality maintenance (per-write promotion) — periodic pass only.
- Cross-table or multi-index hierarchies.

## Series

Part 4 (research) of the hybrid graph/semantic retrieval sequence: #1241 (predicate-aware traversal) → #1242 (relationship expansion) → #1243 (conversational retrieval primitives) → this. Thread B benefits from #1242 for context assembly; thread A is independent.

---

🤖 Generated with [Claude Code](https://claude.com/claude-code)