perf(vector/search): HNSW prefetch is one-hop; no lookahead via beam-search

[mosuka]

Round-3 perf push sub-issue (tracked under umbrella #536).

[M] HNSW prefetch is one-hop; no lookahead via beam-search

• Where: laurus/src/vector/index/hnsw/searcher.rs:597-637 (prefetch_neighbor) emits
  _mm_prefetch / prfm per 64 bytes for the current pop's neighbours
  (419-487). Once those are consumed and the next candidate is popped from the heap, we
  wait for graph.get_neighbors and only then prefetch — adding a memory round-trip per
  hop.
• Current behavior: Single-hop prefetch. The heap pop / neighbour load is a serial
  dependency chain.
• Why it might be a bottleneck / risk: For mmap-backed or out-of-L3 graphs,
  neighbour-list loads dominate. Beam-search HNSW / DiskANN traversals overlap two or more
  hops.
• Reference precedent: DiskANN / Vamana beam-search; Qdrant mmap graph "lookahead";
  hnswlib setEf with prefetch_distance.
• Suggested direction: Peek the next heap top before popping; prefetch its neighbour
  pointers (need to expose HnswGraph.nodes[idx][0].as_ptr() or inline SmallVec); then
  pop and consume. Two-hop pipeline.
• Risk / scope: Medium. Requires exposing graph data layout.

Task list

• Investigation & plan (see comment below)
• Add a speculative prefetch_lookahead closure (peeks candidates.peek(), prefetches its neighbors' vector data)
• Wire it into both the bookkeeping and pristine ef_search branches
• New benchmark exercising an eager-loaded, large corpus (existing HNSW benches default to mmap, where prefetch is currently disabled entirely — see investigation comment)
• New regression test proving search results are bit-for-bit unchanged with the lookahead added
• Full verification (fmt/clippy, cargo test -p laurus, existing HNSW tests unchanged)
• Follow-up issue filed for OnDemand (mmap/lazy) storage having no prefetch at all — perf(vector/search): OnDemand (mmap/lazy) vector storage has no prefetch at all #1148
• PR opened (perf(vector/search): speculative two-hop prefetch lookahead in HNSW search #1149)

---

ID: VS-13 — see ~/.claude/tasks/laurus/20260523_perf_round3_audit/task_list.md for the full Round-3 issue list.

[mosuka]

Investigation

Read HnswSearcher::search_graph (laurus/src/vector/index/hnsw/searcher.rs) in full,
plus OrdinalHnswGraph (graph.rs) and VectorStorage::OnDemand::get (storage.rs), to
understand exactly what "prefetching a neighbor list" means in this codebase's actual data
layout before designing a fix.

The issue's framing doesn't quite match this codebase's architecture

• The query-time graph (OrdinalHnswGraph, graph.rs) is a different type from the
  build-time HnswGraph/ConcurrentHnswGraph the issue's suggested-direction text refers
  to. Its adjacency lists (nodes: Vec<Vec<Vec<u32>>>) are always fully materialized into
  RAM when the reader loads a segment — never mmap'd. So "the graph" itself is never
  cold/paged; graph.neighbors(ord, level) is an O(1), always-resident slice lookup.
• What can be mmap'd/lazily-loaded is the vector data a neighbor ordinal points to
  (VectorStorage::OnDemand). That's exactly what the existing one-hop prefetch already
  targets (prefetch_ord, prefetching a neighbor's vector bytes, not its adjacency entry).

A bigger finding: the literal target regime has zero prefetch today, not one-hop

VectorStorage::OnDemand (mmap/lazy loading — the "mmap-backed... graphs" case this issue
names as the motivating scenario) gets no prefetch at all, one-hop or otherwise:

• HnswIndexReader::field_prefetch_index returns an empty HashMap unconditionally for
  OnDemand (reader.rs:892).
• OnDemand never has a QuantizedVectorPool, so the SQ-based sq_prefetch path is also
  never populated.
• search_graph's prefetch_enabled = sq_prefetch.is_some() || field_prefetch.is_some()
  is therefore false for OnDemand, and both prefetch passes are skipped entirely.

Digging into why: VectorStorage::OnDemand::get() (storage.rs:233+) doesn't hold a raw
memory address to prefetch at all — it goes through StorageInput::seek + a read call, an
I/O abstraction, not a pointer into resident memory. The existing _mm_prefetch/prfm
mechanism (cache-line hints against a known address) doesn't apply to that access pattern
without a much deeper change (e.g. exposing a raw address only when the underlying
Storage happens to be mmap-backed, plus an OS-level madvise hook, or an async
speculative-read scheme) — a different, larger problem than "extend one-hop to two-hop."

Prefetch today only fires for the two fully RAM-resident storage modes: OwnedQuantized
(int8 SQ, eager) and legacy Owned (f32, eager). Two-hop lookahead is only technically
meaningful for these two.

The heap and closure shape

candidates: BinaryHeap<Candidate> — std::collections::BinaryHeap::peek() is O(1) and
non-destructive, confirmed usable exactly as the issue's suggested direction assumes
(peek before pop). The existing prefetch_ord closure takes ord: u32 as an explicit
parameter rather than capturing "the current neighbor" — because visited: BitVec is
mutated (.set()) elsewhere in the same loop, and a closure capturing &visited for its
whole lifetime would conflict with those later &mut accesses. A new lookahead closure
needs the same shape: candidates/visited passed as explicit parameters, not captured.

Benchmark gap

Every existing HNSW query benchmark in vector_search_bench.rs defaults to
use_mmap = true (OnDemand), which per the above means prefetch is already disabled
in all of them — including the one that would be the natural before/after gate for this
change. Only bench_hnsw_graph_search_sparse_ids forces eager loading, but at a fixed
10,000-vector corpus small enough to plausibly fit in L3. No existing benchmark combines
"prefetch actually enabled" with "corpus large enough to be out-of-L3."

Plan

1. Add a prefetch_lookahead closure next to the existing prefetch_ord: peeks
   candidates.peek() (the heap's state as of the end of the previous iteration — this
   iteration hasn't pushed anything yet, so it's a speculative guess, not a guarantee, of
   what pops next) and issues the same prefetch hints for its neighbors, overlapping that
   fetch with the current iteration's own neighbor processing. Takes candidates/visited
   as explicit parameters for the borrow reason above.
2. Call it (gated by the existing prefetch_enabled) in both the bookkeeping and pristine
   ef_search branches, right after each iteration's early-exit checks and before the
   current candidate's own neighbor processing.
3. This is provably side-effect-free on search results — a wrong guess just touches cache
   lines that may or may not be used, never changes candidates/found/visited state.
   Verification is a results-identical regression test plus reliance on the existing
   correctness suite, not a traditional break-it-and-see-the-test-fail mutation check (see
   local implementation notes for why that doesn't fit this kind of change).
4. Add a new benchmark that forces eager loading at a large corpus size, since none of the
   existing ones can show this change's effect at all.
5. File a follow-up issue for OnDemand's complete lack of prefetch — the actual "mmap /
   out-of-L3" regime this issue names — since fixing that needs a different mechanism
   entirely and is a substantially bigger, more architecturally novel change than this
   issue's two-hop-lookahead scope.

Task list tracked in the issue description.