Skip to content

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

Description

@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.

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

Metadata

Metadata

Assignees

No one assigned

    Labels

    enhancementNew feature or request

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions