Support HNSW Search using GPUs

[premal]

Feature: GPU search backend for IndexHNSW — GpuIndexHNSW

Motivation

We need high-throughput vector search on a collection of 500M+ vectors. We evaluated both CPU HNSW and GPU CAGRA:

• CPU HNSW scales sub-linearly with node count — throughput plateaus at ~1,600 vec/s on 10 nodes, bottlenecked by DRAM bandwidth.
• GPU CAGRA (cuVS) returned 0% recall on our production workload (INT8_VECTOR, dim 384, COSINE, ~538M rows): R@1/R@5/R@10 = 0.000, 0/20 self-matches. It is not usable for us as it stands. Here's the related cuvs issue - [BUG] CAGRA may miss exact self-match in IP self-query NVIDIA/cuvs#2102

Given that CAGRA is not viable at our scale, we implemented a GPU search backend for the classic IndexHNSW graph — GpuIndexHNSW — that takes a CPU-built faiss::IndexHNSW (Flat or ScalarQuantizer storage), uploads its graph + vectors to the device, and runs beam search on the GPU. This leverages GPU memory bandwidth (10–20× higher than CPU DRAM) while using the same HNSW graph the user already built — zero index rebuild cost.

Preliminary benchmarks

On an internal 538M-vector workload, we compared a 10-node CPU cluster (r8g.2xlarge) to an 8-node GPU cluster (g7e.2xlarge) using Milvus with the same HNSW index and comparable recall (GPU R@10 0.95–0.96).

CPU cluster (10 × r8g.2xlarge)

batch	P×W	conc	Throughput (vec/s)	p50 ms	p95 ms	p99 ms
256	4×1	4	1,276	798	864	940
256	4×4	16	1,406	2,477	4,465	4,875
256	8×1	8	1,328	1,578	1,662	2,496
256	8×4	32	1,460	4,935	7,038	7,960
512	4×1	4	1,449	1,401	1,513	1,548
512	4×4	16	1,539	4,569	8,037	8,496
512	8×1	8	1,464	2,783	3,054	3,103
512	8×4	32	1,509	9,178	15,463	17,352
1024	4×1	4	1,415	2,894	3,035	3,057
1024	4×4	16	1,540	10,095	15,191	16,365
1024	8×1	8	1,521	5,392	5,495	5,520
1024	8×4	32	1,601	18,448	24,680	30,206

GPU cluster (8 × g7e.2xlarge)

batch	P×W	conc	Throughput (vec/s)	p50 ms	p95 ms	p99 ms
256	4×1	4	17,937	48.9	137.3	152.7
512	4×1	4	20,134	88.5	187.8	201.8
1024	4×1	4	20,690	173.2	287.5	305.5
256	4×4	16	27,523	127.9	225.3	252.6
512	4×4	16	30,928	225.1	374.1	419.3
1024	4×4	16	30,769	421.1	646.5	737.7
256	8×1	8	23,739	79.1	153.0	173.6
512	8×1	8	28,436	133.2	233.2	250.2
1024	8×1	8	29,630	261.0	379.3	404.8
256	8×4	32	31,209	235.6	329.6	377.1
512	8×4	32	35,503	412.5	545.7	605.0
1024	8×4	32	39,152	661.7	906.2	996.6

Summary

	CPU (10 nodes)	GPU (8 nodes)	Improvement
Peak throughput	~1,600 vec/s	~39,000 vec/s	25×
p50 latency (batch=256, conc=4)	798 ms	49 ms	16×
p50 latency (batch=1024, conc=32)	18,448 ms	662 ms	28×

The CPU cluster plateaus at ~1,600 vec/s regardless of batch size or concurrency — DRAM-bandwidth-bound. The GPU cluster scales with concurrency up to ~39,000 vec/s. Latency improvements are even more dramatic: at the highest-concurrency configuration (batch=1024, 8×4), p50 drops from 18.4s to 662ms — 28× lower. Note that the GPU cluster uses 2 fewer nodes (8 vs 10), so the per-node improvement is even higher.

What we built

API (follows existing faiss GPU index conventions)

• GpuIndexHNSW(GpuResourcesProvider*, int dims, MetricType, GpuIndexHNSWConfig) — empty constructor, mirroring GpuIndexFlat.
• GpuIndexHNSW(GpuResourcesProvider*, const faiss::IndexHNSW*, GpuIndexHNSWConfig) — convenience constructor that calls copyFrom.
• copyFrom(const faiss::IndexHNSW*) — uploads a CPU-built index to the GPU.
• copyTo(faiss::IndexHNSW*) / index_gpu_to_cpu() — throw an explicit FaissException: the index is search-only (uploads a CPU-built graph; no reconstructable CPU copy is retained on the device).
• GpuCloner integration: index_cpu_to_gpu builds GpuIndexHNSW from IndexHNSWFlat / IndexHNSWSQ. IndexHNSWCagra is excluded (still routed to the cuVS branch).
• SWIG bindings (swigfaiss.swig): includes the header, ignores internal searchHost/searchHostInt8/setSearchParams methods.
• GpuAutoTune efSearch parameter sweep, mirroring the CPU IndexHNSW tuning path.

Graph conversion (copyFrom)

Converts faiss::HNSW (CSR neighbors/offsets/levels) into a GPU-friendly layout:

• Layer 0: dense flat array (row-major, padded to max_degree0), uploaded as uint32_t.
• Upper layers: sparse per-layer node lists with their own neighbor arrays.
• Entry point validated (rejects malformed/sentinel entry points before GPU dereference).

Storage (native low-precision, not decode-to-fp32)

Storage type	Device layout	Bytes/elem	Distance kernel
IndexHNSWFlat (fp32)	native fp32	4	fp32 accumulation
IndexHNSWSQ QT_8bit_direct_signed	native int8	1	DP4A (int8×int8 → int32)
IndexHNSWSQ QT_fp16	native fp16	2	per-element __half2float → fp32 accumulation
IndexHNSWSQ QT_bf16	native bf16	2	per-element __bfloat162float → fp32 accumulation
Other SQ types (e.g. QT_8bit, QT_4bit)	decoded to fp32	4	fp32 accumulation

Keeping vectors in their native low-precision layout on the device (rather than decoding to fp32 at upload) preserves the VRAM advantage — critical at 500M+ vector scale. The search kernel up-converts each element to fp32 inside the distance computation for accumulation, but the resident dataset stays compact.

Search kernel

• Parallel beam search: one CUDA block per query; warp-cooperative distance computation for bandwidth efficiency.
• Metrics: METRIC_L2 and METRIC_INNER_PRODUCT. Cosine follows the standard faiss idiom (L2-normalize vectors → build IP index) — no separate metric, no inverse-norm state.
• Filtered search: the kernel consumes a BitsetView (delete / TTL / partition filters) with CPU-HNSW-parity semantics:
  • Filtered rows are excluded from results but still traversed as graph waypoints (preserving recall).
  • Two-tier beam: valid result beam + invalid (filtered) frontier, with an alpha-gated admission rate that adapts to the filter ratio.
  • Brute-force fallback at high filter ratios (≥93% filtered or k ≥ 50% of live rows), matching CPU HNSW thresholds.
• Distance-sign convention matches faiss: IP/cosine returns larger-is-better; L2 returns smaller-is-better. The kernel negates internally (min-heap) and flips on copy-out.
• Per-query top-k with valid-id/sentinel handling.

Tests (TestGpuIndexHNSW.cpp)

CPU-parity recall gates against brute-force IndexFlat ground truth:

Test	Metric	Storage	Recall bar
Flat_L2	L2	fp32	0.90
Flat_IP	IP	fp32	0.90
Flat_Cosine	IP (normalized)	fp32	0.90
SQ_Int8_L2	L2	int8 (direct_signed)	0.70
SQ_Fp16_L2	L2	fp16	0.88
SQ_Fp16_Cosine	IP (normalized)	fp16	0.85
SQ_Bf16_Cosine	IP (normalized)	bf16	0.80
CopyToThrows	—	—	verifies search-only contract
RejectsUnsupportedMetric	—	—	verifies metric validation

Design decisions

1. Search-only (no copyTo): The GPU index uploads a CPU-built graph and does not retain a reconstructable CPU copy. This matches the use case (build on CPU, search on GPU) and avoids duplicating the graph in host RAM. copyTo / index_gpu_to_cpu throw immediately with a clear message.

2. Cosine = normalize + IP: Following the rest of faiss/gpu, cosine is not a distinct metric. The caller L2-normalizes vectors before building an IP index. No per-row inverse-norm buffer is uploaded.

3. Native precision storage: Rather than decoding SQ codes to fp32 at upload time (which would cost 4 B/elem regardless of the source type), the kernel stores int8/fp16/bf16 in their native layout and up-converts per element during distance computation. This mirrors the existing INT8 precedent in faiss/gpu and preserves the VRAM advantage.

4. IndexHNSWCagra excluded from cloner: CAGRA has its own GPU path via cuVS. The cloner routes IndexHNSWFlat/IndexHNSWSQ to GpuIndexHNSW and leaves IndexHNSWCagra untouched.

Files

File	Description
faiss/gpu/GpuIndexHNSW.h	Public API: constructors, copyFrom/copyTo, searchHost/searchHostInt8, setSearchParams
faiss/gpu/GpuIndexHNSW.cu	Implementation: copyFrom dispatch, search entry points, cloner integration
faiss/gpu/impl/GpuHnswTypes.h	Device index struct, search params, scratch pool, dataset type enum
faiss/gpu/impl/GpuHnswBuildCommon.cuh	Graph extraction, dataset upload (fp32/int8/fp16/bf16), scratch allocation
faiss/gpu/impl/GpuHnswBuildVanilla.cuh	from_index_hnsw_flat / from_index_hnsw_sq — vanilla faiss build path (no cppcontrib dependency)
faiss/gpu/impl/GpuHnswSearch.cuh	Search host wrapper: scratch setup, smem budget, launch logic
faiss/gpu/impl/GpuHnswSearchKernel.cuh	CUDA kernel: beam search, distance computation, two-tier filtered beam, copy-out
faiss/gpu/impl/GpuHnswBruteForce.cuh	Brute-force top-k fallback kernel for filtered search
faiss/gpu/GpuAutoTune.cpp	efSearch parameter sweep
faiss/gpu/GpuCloner.cpp	index_cpu_to_gpu routing for IndexHNSWFlat/IndexHNSWSQ
faiss/python/swigfaiss.swig	SWIG bindings (includes header, ignores internal methods)
faiss/gpu/test/TestGpuIndexHNSW.cpp	Recall gates, contract tests, metric validation

Hardware requirements

• NVIDIA GPU with compute capability 7.0+ (Volta or newer)
• CUDA 12.x+

Status

Implemented and validated at 500M+ vector scale on our cluster. We'd like to upstream this to faiss. Happy to adjust anything to fit the project's conventions.

GPU HNSW vs CPU HNSW — SIFT1M Benchmark Report

Overview

CPU-vs-GPU comparison of faiss HNSW search on the standard SIFT1M ANN benchmark. The same CPU-built HNSW graph is searched on the CPU and on the GPU (GpuIndexHNSW, reached via index_cpu_to_gpu); both traverse the identical graph, so this isolates the search-backend speedup at matched recall.

Reproducible with the in-tree script:

python benchs/bench_gpu_hnsw.py 10 hnsw
python benchs/bench_gpu_hnsw.py 10 hnsw_sq

Configuration

Dataset	SIFT1M — 1,000,000 base vectors, 128-d fp32, 10,000 queries, 100-NN ground truth
Index	HNSW32 (M=32, efConstruction=40)
Storage	fp32 (IndexHNSWFlat) and SQ8 (IndexHNSWSQ, QT_8bit)
k	10
GPU	NVIDIA L40S (SM 8.9, Ada Lovelace), 1 device
CUDA	12.8
CPU baseline	single-threaded IndexHNSW.search on the same graph

Results — HNSW Flat (fp32)

efSearch	CPU QPS	GPU QPS	Speedup	CPU R@1	GPU R@1	CPU R@10	GPU R@10
16	30,303	791,139	26.1×	0.9051	0.9208	0.8638	0.8862
32	18,457	683,167	37.0×	0.9543	0.9585	0.9380	0.9446
64	9,925	453,076	45.6×	0.9795	0.9798	0.9772	0.9785
128	5,457	271,413	49.7×	0.9876	0.9877	0.9929	0.9931
256	3,005	152,756	50.8×	0.9906	0.9906	0.9979	0.9980

Results — HNSW SQ8

efSearch	CPU QPS	GPU QPS	Speedup	CPU R@1	GPU R@1	CPU R@10	GPU R@10
16	12,244	813,370	66.4×	0.8953	0.9111	0.8585	0.8814
32	8,078	684,561	84.7×	0.9428	0.9454	0.9298	0.9367
64	5,379	451,904	84.0×	0.9659	0.9664	0.9683	0.9695
128	3,162	270,946	85.7×	0.9742	0.9742	0.9821	0.9822
256	1,798	152,694	85.0×	0.9771	0.9771	0.9866	0.9866

Findings

• Throughput: GPU delivers 26–51× the QPS of single-threaded CPU HNSW for fp32, and 66–86× for SQ8. SQ8's larger multiplier reflects the higher per-distance cost of quantized comparison on the CPU, which the GPU absorbs.
• Recall parity: GPU recall matches CPU to within <0.3% at every efSearch for both storage types (the two search the same graph; residual deltas are fp32 tie-breaking, not an algorithmic difference). At high efSearch the numbers are identical to 4 decimals.
• Operating point (fp32, efSearch=128): 271k QPS on GPU vs 5.5k on CPU (49.7×) at R@10 = 0.993.
• Storage tradeoff: SQ8 runs at ~1–2% lower recall than fp32 at matched efSearch, in exchange for 4× smaller vector storage.
• Measured on an L40S (SM 8.9); higher-memory-bandwidth GPUs would scale further.