Comparison with HNSW #

HNSW (Hierarchical Navigable Small World) is one of the widely used libraries implementing Hierarchical Navigable Small World graphs, and forms the basis for most commercial offerings such as Milvus, Qdrant, etc. It’s widely adopted in recommendation systems, search engines, and as a core component in other vector databases due to its excellent speed-recall trade-off.

Query Time vs. Recall@10 Comparison #

Query Time vs Recall Graph

Detailed Comparison (SIFT1M, k=10) #

Performance Metrics #

Library	Geometric Mean QPS	Median QPS	QPS@95%	Weighted Avg QPS	AUC Value	AUC Normalized
PatANN	182,526.33	190,849.94	357,320.88	223,090.29	83,919.87	223,090.29
HNSWLib	20,503.97	24,161.21	53,226.40	32,429.12	21,098.06	32,429.12

Recall at Different QPS Levels #

Library	Recall@10,000 QPS	Recall@50,000 QPS	Recall@100,000 QPS	Recall@200,000 QPS
PatANN	0.99991	0.99991	0.99991	0.99944
HNSWLib	0.99624	0.68671	-	-

Algorithm Parameters #

Library	Points	Min K	Max K	K Range	Min Epsilon	Max Epsilon	Median Epsilon
PatANN	280	0.62374	0.99991	0.37617	0.72420	1	0.99718
HNSWLib	140	0.34913	0.99972	0.65059	0.41219	0.99998	0.96344

Key Findings #

PatANN demonstrates significantly better performance compared to HNSW implementations, with approximately 8.9x higher geometric mean QPS and 6.9x higher weighted average QPS. While HNSW maintains excellent recall (99.6%) at lower QPS levels (10,000), it experiences substantial degradation at higher throughput, dropping to 68.7% at 50,000 QPS and unable to maintain performance at higher QPS levels.

The graph-based approach of HNSW offers good precision but comes with scalability limitations compared to PatANN’s pattern-aware partitioning. HNSWLib requires careful tuning of the graph construction parameters (M and ef_construction) to balance build time, index size, and query performance, whereas PatANN offers more consistent performance across varying workloads with less parameter sensitivity.