Vector search and ANN indexes quiz

Question 1

What does HNSW stand for, and what type of data structure does it use for approximate nearest neighbor search?

Accepted Answer

Hierarchical Navigable Small World — a multi-layer proximity graph

Answer

Hash-based Nearest Neighbor Search with Weighted layers — a tree structure

Answer

High-dimensional Nearest-neighbor Search with Wavelets — a wavelet index

Answer

Heuristic Node Search with Weight relaxation — a skip list

Question 2

For non-unit-length vectors, how do cosine similarity and dot product (inner product) differ in behavior, and when are they equivalent?

Accepted Answer

Cosine similarity normalizes by magnitude and measures angle; dot product is magnitude-sensitive; they are equivalent only for unit-normalized vectors

Answer

Dot product normalizes by magnitude; cosine does not; they are never equivalent

Answer

Both metrics are identical for all vector norms

Answer

Cosine similarity is always slower to compute because it requires a square-root normalization step

Question 3

What does the HNSW hyperparameter M control, and what is its primary trade-off?

Accepted Answer

Maximum number of bidirectional links per node per graph layer

Answer

Maximum number of candidates evaluated at query time (beam width)

Answer

Number of Voronoi cells in the IVF coarse quantizer

Answer

Number of hash tables used in the LSH index

Question 4

What is the functional difference between ef_construction and ef (ef_search) in HNSW, and can ef_search be tuned without rebuilding the index?

Accepted Answer

ef_construction governs build-time graph quality via candidate list size; ef governs query-time recall-latency tradeoff without requiring a rebuild

Answer

ef_construction controls query-time latency; ef controls build quality

Answer

ef_construction and ef are interchangeable aliases for the same parameter

Answer

ef_construction must always equal ef; changing one requires a full rebuild

Question 5

How does Product Quantization (PQ) compress vectors, and what is the Asymmetric Distance Computation (ADC) trick that makes it efficient at query time?

Accepted Answer

PQ splits vectors into m sub-spaces, quantizes each to k* centroids independently, and ADC precomputes sub-space distances per query as a lookup table to avoid decoding DB vectors

Answer

PQ applies a single global k-means to all dimensions and ADC caches the cluster centroids across queries

Answer

PQ uses random projections to reduce dimension and ADC computes dot products asymmetrically between queries and projected vectors

Answer

PQ stores full vectors with redundancy for error correction and ADC selects the nearest replica

Question 6

What does the nprobe parameter control in a FAISS IVF index, and how does it affect the recall-latency tradeoff?

Accepted Answer

Number of Voronoi cells (inverted lists) probed at query time; increasing it improves recall at the cost of higher latency

Answer

Number of HNSW layers traversed during search

Answer

Number of PQ sub-spaces in the product quantizer

Answer

Number of SIMD lanes used for distance computation on CPU

Question 7

What does Recall@10 = 0.95 mean in an ANN evaluation context, and why is Recall@k the standard metric rather than precision?

Accepted Answer

On average, 9.5 of the true 10 nearest neighbors appear in the index's top-10 results

Answer

95% of database vectors are scanned during each query

Answer

The index returns results within 95% of the true nearest neighbor distance

Answer

The 95th-percentile query latency is 10 milliseconds

Question 8

What is the theoretical average-case search complexity of HNSW, and how does the skip-list analogy explain it?

Accepted Answer

O(log n) — hierarchical skip-list structure enables long-range jumps at upper layers and local refinement at lower layers

Answer

O(n) — every node in the bottom layer must be visited for accurate search

Answer

O(d × log n) — one traversal step per dimension per graph layer

Answer

O(n^0.5) — analogous to kd-tree search in low dimensions

Question 9

When should IndexIVFPQ be preferred over IndexHNSWFlat in FAISS for large-scale production deployments?

Accepted Answer

When the dataset does not fit in RAM and per-vector memory footprint must be minimized (m bytes vs. ~4d bytes for HNSW)

Answer

When maximum recall at minimum latency is required regardless of memory usage

Answer

When the dataset is small (< 100k vectors) and build time dominates

Answer

When GPU acceleration is available; IVF-PQ maps to GPU GEMM primitives unlike HNSW

Question 10

How does DiskANN achieve billion-scale ANN search with under 64 GB RAM, and what is its key algorithmic innovation?

Accepted Answer

DiskANN keeps PQ-compressed codes in RAM for beam-search candidate filtering, then fetches full-precision vectors from SSD in 3-5 I/O rounds

Answer

DiskANN stores the entire graph on GPU HBM using tiled compression

Answer

DiskANN uses a distributed IVF where each node holds one Voronoi cell on local disk

Answer

DiskANN employs memory-mapped files and OS prefetching to transparently page graph edges from disk

Question 11

What is the key risk of post-filtering in ANN search with highly selective metadata filters, and what strategies mitigate it?

Accepted Answer

Post-filtering may return fewer than k valid results when the filter is highly selective, because matching vectors may not appear in the ANN shortlist

Answer

Post-filtering is always slower than pre-filtering because it requires two separate indexing stages

Answer

Post-filtering requires a separate inverted index, doubling storage cost regardless of filter selectivity

Answer

Post-filtering is only supported by IVF indexes and not by graph-based HNSW indexes

Question 12

What is binary quantization (BQ) of embeddings, what is its memory compression ratio vs. float32, and what inference optimization does it enable?

Accepted Answer

Binary quantization maps each dimension to one bit (32× memory compression over float32) and enables Hamming-distance search via POPCNT instructions

Answer

Binary quantization uses 2 bits per dimension, achieving 16× compression over float32

Answer

Binary quantization is a synonym for int8 scalar quantization, achieving 4× compression

Answer

Binary quantization clusters all vectors into two groups and stores a single cluster ID per vector

Question 13

What hash family does LSH use for cosine similarity, and how does the collision probability relate to the angle between two vectors?

Accepted Answer

Random hyperplane hashing — hash bit = sign(x · r) for random unit vector r; collision probability = 1 − angle(x,y)/π

Answer

MinHash — designed to estimate Jaccard coefficient between sets of tokens

Answer

SimHash — XOR of bit signatures derived from random weight vectors without a collision probability guarantee

Answer

Bit-sampling — randomly sampling bits from binary vector representations of integer IDs

Question 14

What is Matryoshka Representation Learning (MRL), and how does it reduce cost in production ANN retrieval pipelines?

Accepted Answer

MRL trains embeddings with a nested loss so any prefix of dimensions is a useful lower-dimensional embedding, enabling cheap coarse ANN followed by full-dimension re-ranking

Answer

MRL is a multi-resolution LSH technique that hashes at progressively shorter bit depths

Answer

MRL is a matrix factorization method for compressing the ANN index weight matrix offline

Answer

MRL refers to multi-retrieval-layer, a cascaded IVF hierarchy for billion-scale search

Question 15

How do systems like Qdrant and Weaviate combine dense vector ANN with sparse BM25/SPLADE retrieval in hybrid search, and what fusion strategy is recommended?

Accepted Answer

Dense ANN and sparse inverted index retrieval run separately; ranked lists are fused via Reciprocal Rank Fusion (RRF) or score interpolation

Answer

Sparse TF-IDF vectors are concatenated with dense embeddings into a single high-dimensional vector for one ANN query

Answer

The dense encoder is fine-tuned on BM25 pseudo-labels to absorb sparse signal into the dense index alone

Answer

A two-stage IVF uses sparse quantization as the coarse stage and dense HNSW as the fine re-ranking stage

Question 16

Comparing HNSW and IVF-PQ for a 10M-vector, 768-dim dataset: which statement most accurately describes their tradeoffs in memory and recall-latency?

Accepted Answer

HNSW consumes ~4-8× more RAM but achieves better recall-latency; IVF-PQ with m=16 uses only ~16 bytes/vector, making it far more memory-efficient

Answer

IVF-PQ always achieves better recall at the same latency because PQ reduces quantization variance in distance estimation

Answer

HNSW and IVF-PQ have identical memory footprints when M=16 and m=16 PQ sub-spaces are used

Answer

Both indexes support O(1) incremental inserts without touching existing graph or cluster structure

Question 17

What is 'index warm-up' in a production vector search service, and how is it typically mitigated?

Accepted Answer

Pre-loading the ANN index into RAM or page cache before serving traffic to prevent cold-start latency spikes caused by OS page faults

Answer

Running a small training set through the embedding model before serving live queries to prime the model cache

Answer

Re-training PQ centroids on newly arriving data after the initial index construction phase

Answer

Compiling GPU CUDA kernels for distance computation before the first query batch is processed

Question 18

What does the Pareto frontier represent in ann-benchmarks.com evaluations, and what does it tell a practitioner choosing an ANN algorithm?

Accepted Answer

The set of configurations where no other config achieves both higher recall and higher QPS simultaneously; guides practitioners to the best algorithm for a target recall

Answer

The single algorithm-parameter combination with the globally highest recall across all tested datasets

Answer

The boundary between exact and approximate search regimes, used to select the minimum nprobe value

Answer

The minimum latency achievable regardless of recall for each index type tested

Question 19

What is the key algorithmic innovation in ScaNN (Scalable Nearest Neighbors from Google) that distinguishes it from standard IVF-PQ?

Accepted Answer

Anisotropic vector quantization that penalizes quantization error in the query-parallel direction more than the perpendicular direction, directly reducing distance ranking errors

Answer

A learned hash function trained end-to-end with the quantizer, replacing the IVF inverted file structure

Answer

A hierarchical HNSW graph used as the coarse quantizer instead of flat k-means centroids

Answer

Binary embedding applied to PQ codes to speed up the distance lookup table computation via POPCNT

Question 20

What is 'tombstoning' in HNSW-based vector databases, what problem does it solve, and why does accumulation of tombstones degrade recall?

Accepted Answer

Tombstoning (soft delete) marks deleted nodes as dead without rewiring the graph; nodes remain until background compaction, and excess tombstones degrade recall by consuming beam slots

Answer

Tombstoning refers to marking expired TTL-based embeddings as invalid at insert time before they enter the index

Answer

Tombstoning is a technique to merge duplicate vectors that hash to the same HNSW layer node

Answer

Tombstoning refers to the process of replacing quantized vector codes with full-precision ones during index optimization

Question 21

How does Annoy differ from HNSW in architecture and deployment model, particularly for read-only multi-process workloads?

Accepted Answer

Annoy uses random projection trees stored as memory-mapped files; multiple processes share the mmap without serialization, but incremental inserts require a full rebuild

Answer

Annoy uses a graph traversal algorithm like HNSW but with binary edge weights for faster SIMD operations

Answer

Annoy is a GPU-accelerated wrapper around FAISS IVF-PQ optimized for high-concurrency reads

Answer

Annoy uses kd-trees with exact axis-aligned splits, offering perfect recall unlike HNSW's approximate graph

Question 22

Why does ColBERT's MaxSim late-interaction scoring require different ANN infrastructure than standard single-vector bi-encoders?

Accepted Answer

ColBERT encodes documents as multiple per-token vectors and scores via MaxSim, requiring multi-vector ANN with centroid-based candidate retrieval not needed by single-vector bi-encoders

Answer

ColBERT uses a single pooled CLS vector like a bi-encoder but requires earth mover's distance instead of cosine similarity

Answer

ColBERT uses binary token embeddings requiring POPCNT-based ANN instead of floating-point similarity

Answer

ColBERT uses cross-attention between query and document tokens at serving time, making offline precomputation of document vectors impossible

Question 23

What does quantization-aware training (QAT) achieve for embedding models targeting binary or int8 ANN indexes?

Accepted Answer

QAT fine-tunes the embedding model with simulated quantization noise so it concentrates discriminative signal into quantization-stable dimensions, preserving recall after compression

Answer

QAT refers to quantizing the transformer's attention weight matrices, not the output embedding vectors

Answer

QAT is a post-training compression applied to the ANN index structure rather than the embedding model

Answer

QAT reduces the embedding model's parameter count via structured pruning to match int8 arithmetic unit constraints

Question 24

How does the NSG (Navigating Spreading-out Graph) index improve on HNSW's neighbor selection strategy during graph construction?

Accepted Answer

NSG uses a monotonic path diversification constraint (MRNG) during neighbor selection that spreads neighbors across directions, achieving competitive recall-latency with well-diversified edge sets over HNSW

Answer

NSG uses a hierarchical layer structure like HNSW but adds random long-range edges to improve global navigability

Answer

NSG uses locality-sensitive hashing to pre-cluster nodes before starting graph construction

Answer

NSG uses neural network-predicted edge weights to prioritize high-similarity neighbors in graph construction

Question 25

What enables GPU-accelerated vector search (e.g., FAISS GPU, NVIDIA cuVS/RAFT) to achieve significantly higher throughput than CPU-based indexes?

Accepted Answer

GPU ANN uses cuBLAS GEMM for all-pairs distance computation and parallel top-k reduction, achieving 10-100× higher throughput than multi-core CPU for batch similarity search; the tradeoff is the index must fit in GPU VRAM

Answer

GPU ANN parallelizes HNSW graph traversal across thousands of CUDA cores simultaneously for each query

Answer

GPU ANN uses PCIe DMA to stream database vectors directly from SSD to GPU without CPU involvement

Answer

GPU ANN compiles query-specific CUDA kernels at runtime to exploit embedding sparsity patterns

Question 26

What is the 'quantization gap' in two-stage ANN retrieval pipelines, and how do production systems address it?

Accepted Answer

The recall lost when true nearest neighbors fall outside the ANN candidate set; addressed by over-retrieval and cascaded retrieval stages

Answer

The bit-width mismatch between int8-quantized queries and float32 database vectors causing score calibration errors

Answer

The latency difference between PQ approximate scoring and exact re-ranking in the pipeline

Answer

The score distribution gap between BM25 and dense retrieval that complicates hybrid fusion

Question 27

How does query fan-out work in a sharded vector database, and does sharding affect Recall@k?

Accepted Answer

Each shard runs ANN independently and returns its local top-k; the coordinator merges results globally; recall is unaffected if each shard returns at least k candidates

Answer

Fan-out degrades recall proportionally to the number of shards because each shard sees only a fraction of the dataset

Answer

Fan-out only applies to IVF indexes where shards map one-to-one with Voronoi cells

Answer

Fan-out requires the coordinator to re-embed the query per shard to account for shard-specific embedding normalization

Question 28

How does SPLADE differ from BM25 for sparse vector retrieval, and what advantage does it have in ANN pipelines?

Accepted Answer

SPLADE uses a learned transformer to produce sparse vocabulary-space vectors with semantic term expansion, while BM25 uses non-learned TF-IDF statistics; both index identically in standard inverted indexes

Answer

SPLADE produces dense low-dimensional vectors similar to bi-encoders; BM25 produces sparse vocabulary-space vectors

Answer

SPLADE uses a PQ-compressed inverted index; BM25 uses an uncompressed inverted index

Answer

SPLADE requires an ANN vector database; BM25 can run on a standard document-oriented search engine

Question 29

How does the curse of dimensionality affect ANN index performance, and at what approximate dimension does it become practically problematic?

Accepted Answer

As dimension grows, pairwise distances concentrate around a single value, degrading ANN graph traversal heuristics; PQ compression and PCA are common mitigations

Answer

The curse of dimensionality improves ANN performance by making clusters more spherical and easier to partition with Voronoi cells

Answer

The curse of dimensionality is eliminated by switching from L2 to cosine similarity distance

Answer

The curse of dimensionality only affects brute-force search; ANN graph indexes are immune due to their hierarchical structure

Question 30

When should you prefer IndexHNSWSQ over IndexHNSWFlat in FAISS, and what recall penalty does it incur?

Accepted Answer

When d >= 256 and memory or throughput is constrained: SQ8 quantizes neighbor vectors to int8, reducing memory ~4x with ~0.5% recall loss vs. IndexHNSWFlat

Answer

When maximum possible recall is required regardless of memory, because SQ reduces quantization noise in distance estimates

Answer

When the dataset has fewer than 100k vectors, because SQ is specifically optimized for small-scale indexes

Answer

When deploying on GPU only, because SQ8 maps directly to CUDA int8 SIMD without float conversion overhead

Test yourself