HNSW distance compression vs. progressive graph search: matched-recall results on six 1M-scale datasets

[lyang24]

I have been exploring how HNSW should trade memory for single-query throughput when the target is approximately 0.95 recall@10. The comparison includes Faiss HNSW storage codecs, RaBitQ navigation with optional reranking, and graph algorithms that use progressive projections or specialized quantized layouts.

The main question is not “which codec has the smallest code?” in isolation. It is:

At a matched recall target, how much query throughput do we obtain, and what is the complete persistent index footprint?

Benchmark contract

Item	Setting
CPU	AWS x86_64, Intel Xeon Platinum 8488C (Sapphire Rapids)
Faiss build	AVX512 optimized CPU build
Search concurrency	One search thread, pinned to one CPU
Query workload	1,000 queries, top-10
Timing	At least one warmup; median of 3–7 timed runs
Recall	Set intersection recall@10 against exact ground truth
Common Faiss graph	M=32, efConstruction=200, built using FP32 distances
Graph isolation	FP32, SQ4, SQ8, and Faiss RaBitQ variants reuse the same exact graph
Memory	Complete persistent graph + vector/code payload, reported as bytes/vector
Point selection	Representative measured point at or immediately above R@10 = 0.95; no interpolation or fitted values

The reference RaBitQ implementation, PAG, and SymphonyQG build their own graphs. They are therefore whole-algorithm/system comparisons, while the Faiss codec rows isolate the effect of the search-time distance representation on a common graph.

Datasets

Dataset	Base vectors	Dimensions	Metric	Queries	Notes
DEEP-prefix-1M	1,000,000	96	inner product	1,000	Prefix of DEEP image embeddings
GloVe-100	1,183,514	100	normalized inner product	1,000	ANN-Benchmarks angular dataset
SIFT1M	1,000,000	128	L2	1,000	Standard SIFT1M
Cohere-medium-1M	1,000,000	768	inner product	1,000	VectorDBBench data; this is 768d, not 769d
GIST1M	1,000,000	960	L2	1,000	Standard GIST1M
OpenAI-DBpedia	999,000	1,536	inner product	1,000	Exact GT recomputed for the 999K prefix

What each row means

Method	Graph	Navigation distance	Final scoring	Important detail
HNSW FP32	Shared Faiss FP32 graph	FP32	FP32	Accuracy and memory baseline
HNSW SQ4/SQ8	Same shared graph	Faiss scalar quantizer	Same quantized score	Isolates storage/distance approximation
Faiss RaBitQ1 direct	Same shared graph	1-bit RaBitQ estimate	Same estimate	Fast sign-only path; no error-bound refinement
Faiss RaBitQ4 direct	Same shared graph	1-bit estimate plus staged multi-bit refinement	RaBitQ estimate	No original FP32 vectors after finalization
RQ1/RQ4 + SQ4/SQ8 refine	Same shared graph	RaBitQ	Rerank k_factor × k candidates with SQ4/SQ8	Includes both RaBitQ and refine payloads
Reference RaBitQ4	Its own M=32 graph	Reference RaBitQ search	Reference RaBitQ estimate	FHT-Kac rotation, 16 centroids; RaBitQ-Library
Panorama	Faiss HNSW graph	Progressive bounds	Progressive full score	L2-only, so it is only shown for GIST
PAG	Its own alpha-pruned graph	Progressive projection bounds	Progressive score	efConstruction=1000; PAG
SymphonyQG	Its own M=32 graph	Specialized quantized graph search	Internal quantized score	FHT-Kac rotation; implementation from RaBitQ-Library

Main result chart

Each cell is recall@10 / QPS / bytes per vector.

• †: the method did not reach 0.95; the highest measured recall point is shown.
• ≈: closest available discrete point.
• *: k_factor=1, so the additional SQ4 payload did not perform meaningful reranking.
• —: unsupported or not measured.

Method	DEEP-96	GloVe-100	SIFT-128	Cohere-768	GIST-960	OpenAI-1536
HNSW FP32	0.9509 / 7,960 / 656	0.9509 / 811 / 672	0.9524 / 6,545 / 784	0.9519 / 2,673 / 3,344	0.9519 / 440 / 4,112	0.9507 / 1,343 / 6,416
HNSW SQ4	0.6709† / 676 / 320	0.7105† / 154 / 322	0.8275† / 1,203 / 336	0.8682† / 689 / 656	0.6669† / 157 / 752	0.9415† / 327 / 1,040
HNSW SQ8	0.9513 / 8,068 / 368	0.9506 / 220 / 372	0.9501 / 9,360 / 400	0.9502 / 2,519 / 1,040	0.9500 / 450 / 1,232	0.9518 / 1,973 / 1,808
Faiss RaBitQ1 direct	0.2801† / 10,600 / 292	0.2880† / 2,146 / 293	0.1841† / 14,044 / 296	0.7614† / 1,199 / 376	0.2537† / 849 / 400	0.8201† / 364 / 472
Faiss RaBitQ4 direct	0.8482† / 698 / 340	0.8390† / 204 / 343	0.7986† / 444 / 356	0.9517 / 1,291 / 676	0.8202† / 325 / 772	0.9511 / 1,569 / 1,060
Reference RaBitQ4	0.8768† / 622 / 360	0.8488† / 144 / 360	0.8890† / 598 / 360	0.9500 / 4,636 / 680	0.9307† / 249 / 776	0.9498≈ / 3,855 / 1,064
RQ1 + SQ4 refine	0.6699† / 1,218 / 340	0.6849† / 405 / 343	0.8231† / 559 / 360	0.8671† / 1,386 / 760	0.6539† / 382 / 880	0.9433† / 338 / 1,240
RQ4 + SQ4 refine	0.8367† / 3,729 / 388	0.8320† / 369 / 393	0.8343† / 4,431 / 420	0.9517* / 1,255 / 1,060	0.8158† / 394 / 1,252	0.9511* / 1,592 / 1,828
RQ1 + SQ8 refine	0.9508 / 1,445 / 388	0.9550 / 97 / 393	0.9510 / 1,013 / 424	0.9504 / 4,192 / 1,144	0.9539 / 70.5 / 1,360	0.9514 / 3,141 / 2,008
RQ4 + SQ8 refine	0.9509 / 3,613 / 436	0.9505 / 358 / 443	0.9508 / 4,630 / 484	0.9509 / 3,398 / 1,444	0.9515 / 342 / 1,732	0.9506 / 2,351 / 2,596
Panorama	—	—	—	—	0.9584 / 280 / 4,148	—
PAG	0.9501 / 29,383 / 1,017	0.9516 / 3,565 / 1,137	0.9584 / 19,592 / 1,103	0.9670 / 10,791 / 3,868	0.9489≈ / 3,837 / 4,947	0.9522 / 7,411 / 7,098
SymphonyQG	0.9505 / 26,530 / 1,280	0.9508 / 1,250 / 1,296	0.9523 / 28,222 / 1,408	0.9500 / 22,210 / 6,528	0.9518 / 3,116 / 8,064	0.9513 / 10,380 / 12,672

Selected search parameters

Cells contain efSearch; refine rows contain efSearch / k_factor.

Method	DEEP	GloVe	SIFT	Cohere	GIST	OpenAI
HNSW FP32	40	352	40	40	208	32
HNSW SQ8	64	528	44	48	272	34
Reference RaBitQ4	1,024†	2,048†	1,024†	128	2,048†	80≈
RQ1 + SQ8 refine	192 / 72	1,280 / 768	256 / 128	60 / 8	1,280 / 1,024	36 / 3
RQ4 + SQ8 refine	64 / 3	576 / 3	48 / 3.5	48 / 1.5	384 / 12	34 / 1.5
PAG	40	272	56	40	80≈	32
SymphonyQG	80	1,536	80	58	320	64

PAG search budgets are stage-quantized. For example, Cohere remains at 0.9473 through ef=39 and jumps to 0.9670 at ef=40; SIFT similarly jumps from 0.9394 to 0.9584. These points are reported as measured rather than interpolated.

Throughput and memory relative to SQ8

Dataset	PAG QPS	PAG memory	SymphonyQG QPS	SymphonyQG memory
DEEP	3.64×	2.76×	3.29×	3.48×
GloVe	16.20×	3.05×	5.68×	3.48×
SIFT	2.09×	2.76×	3.02×	3.52×
Cohere	4.28×	3.72×	8.82×	6.28×
GIST	8.53×	4.02×	6.93×	6.55×
OpenAI	3.76×	3.93×	5.26×	7.01×

Throughput and memory relative to unquantized HNSW FP32

The memory trade-off looks substantially different when the baseline is the
unquantized HNSW index rather than SQ8. This is particularly important for
high-dimensional vectors, where the FP32 payload already dominates the graph
overhead.

Dataset	PAG QPS	PAG memory	SymphonyQG QPS	SymphonyQG memory
DEEP	3.69×	1.55×	3.33×	1.95×
GloVe	4.40×	1.69×	1.54×	1.93×
SIFT	2.99×	1.41×	4.31×	1.80×
Cohere	4.04×	1.16×	8.31×	1.95×
GIST	8.72×	1.20×	7.08×	1.96×
OpenAI	5.52×	1.11×	7.73×	1.98×

Against HNSW FP32, PAG provides 2.99–8.72× the throughput for 1.11–1.69×
the memory. The trade-off is especially favorable on Cohere, GIST, and OpenAI:
PAG adds only 11–20% persistent memory while increasing throughput by
4.04–8.72×. SymphonyQG remains the higher-throughput option on several
datasets, but consistently approaches 2× the FP32 HNSW footprint.

Observations

1. Graph/projection algorithms change the throughput scale. PAG and SymphonyQG usually outperform codec-only HNSW changes by multiples, not single-digit percentages, but they spend substantially more memory.
2. Reference RaBitQ4 is a strong compact point on high-dimensional IP data. On Cohere it reaches 4,636 QPS at 680 B/vector, versus SQ8 at 2,519 QPS and 1,040 B/vector. OpenAI shows a similar compact Pareto point at 0.9498 recall.
3. Multi-bit staged navigation is not universally better than 1-bit navigation plus reranking. RQ4+SQ8 greatly reduces the required candidate multiplier on DEEP/GloVe/SIFT/GIST, but RQ1+SQ8 is faster on Cohere and OpenAI.
4. SQ4 is not an adequate final scorer at this recall target. It fails to recover 0.95 on almost every dataset. The two apparent RQ4+SQ4 successes use k_factor=1, so SQ4 adds memory without changing the direct RaBitQ ranking.
5. Quantization does not guarantee higher throughput. SQ8 beats FP32 on SIFT and is roughly tied on DEEP, but is slower on GloVe and slightly slower on Cohere. Dimension, metric, cache behavior, and decoding overhead all matter.
6. The best product point depends on the memory budget. A compact configuration should be compared around SQ8-sized memory; PAG/SymphonyQG represent a separate throughput-oriented profile.

Caveats

• These are single-thread results from one Sapphire Rapids host. They should be repeated on at least one other microarchitecture before making portable performance claims.
• PAG and SymphonyQG use their own graph construction and storage, so their results are not codec-only A/B tests.
• Build time and peak construction RSS are not normalized across external libraries and are therefore excluded from the main search table.
• Persistent bytes/vector do not include temporary process RSS or the source FP32 dataset used during construction.
• Panorama currently supports L2 only in this comparison.

[mnorris11]

@lyang24 were you able to compare to PiPNN?

We are planning to investigate both in Q4 starting in maybe a week or two.

[lyang24]

@lyang24 were you able to compare to PiPNN?

We are planning to investigate both in Q4 starting in maybe a week or two.

no yet will run some benches over the weekend