Approximate Nearest Neighbor (ANN)

ANN algorithms replace an exhaustive O(N) linear scan with an intelligent index structure that achieves O(log N) or better query complexity. The core bargain is recall vs. latency: a perfectly accurate k-NN search is computationally prohibitive at scale, so ANN accepts a recall of 95-99.9% in exchange for query times dropping from seconds to single-digit milliseconds.

• Exact Search: Brute-force cosine similarity over all vectors. Guaranteed 100% recall, but linear time complexity.
• ANN Search: Navigates a compressed graph or quantized space. Sub-linear time, with a tunable accuracy knob.
• Legal Domain Impact: A corpus of 50 million case law paragraphs becomes unqueryable with exact methods; ANN makes it interactive.

The Hierarchical Navigable Small World algorithm constructs a multi-layered proximity graph where long-range edges at higher layers enable logarithmic scaling. Search begins at the topmost sparse layer for coarse navigation and descends through denser lower layers for fine-grained refinement.

• Greedy Traversal: At each step, the algorithm moves to the neighbor closest to the query vector until a local minimum is reached.
• Layered Structure: Higher layers contain fewer nodes with long-distance links, acting as an express highway; lower layers provide local precision.
• Legal Relevance: HNSW excels in high-recall legal retrieval because its graph structure naturally preserves the semantic neighborhoods of dense legal embeddings, ensuring related precedents are discoverable even under approximate search.

Product Quantization (PQ) addresses the memory bottleneck of storing billions of high-dimensional vectors. It decomposes each d-dimensional vector into m sub-vectors, clusters each subspace independently into a codebook of centroids, and stores only the short code of centroid indices.

• Memory Reduction: A 1024-dimensional float32 vector (4KB) can be compressed to 64 bytes using PQ with m=64 and 8-bit codes—a 64x reduction.
• Asymmetric Distance Computation: At query time, distances are computed between the uncompressed query and the stored codes using pre-computed lookup tables, balancing speed and accuracy.
• Trade-Off: Compression introduces quantization error, slightly reducing recall. This is often mitigated by pairing PQ with a coarse quantizer for inverted file indexing.

The Inverted File structure partitions the vector space into Voronoi cells defined by a set of cluster centroids. At query time, only a small fraction of cells closest to the query vector are searched, dramatically reducing the candidate set.

• Coarse Quantizer: A k-means clustering step assigns each database vector to its nearest centroid, creating an inverted list per cell.
• nprobe Parameter: Controls how many cells are searched. Higher nprobe increases recall at the cost of latency, providing a direct tunable accuracy-speed knob.
• IVF+PQ Combination: The industry-standard FAISS library combines IVF for candidate pruning with PQ for memory compression, enabling billion-scale legal retrieval on a single GPU.

Tree-based ANN methods recursively partition the vector space using random hyperplanes or axis-aligned splits, building a forest of binary trees. Annoy (Approximate Nearest Neighbors Oh Yeah) builds multiple random projection trees and aggregates results by priority queue traversal.

• Build Process: Each tree is constructed by picking two random points, splitting the space with a hyperplane equidistant between them, and recursing until leaf nodes contain few points.
• Query Process: The query descends each tree to a leaf and then backtracks to explore neighboring branches, collecting candidates across all trees.
• Limitations: Tree-based methods struggle with high intrinsic dimensionality common in legal embeddings, where graph-based methods like HNSW typically outperform them on both recall and speed.

LSH uses hash functions designed so that similar vectors collide into the same bucket with high probability, while dissimilar vectors are separated. It was the dominant ANN paradigm before graph-based methods emerged.

• Random Projection LSH: For cosine similarity, hash functions are random hyperplanes; the sign of the dot product determines the hash bit.
• AND-OR Amplification: Multiple hash tables (OR) increase recall, while concatenating hash functions within a table (AND) reduces false positives, providing tunable precision.
• Modern Role: LSH has largely been superseded by HNSW and IVF for dense embeddings but remains relevant for sparse high-dimensional data and theoretical guarantees. In legal retrieval, it is rarely the first choice for production systems.

A graph-based ANN index that constructs a multi-layered navigable structure. The top layers contain long-range links for fast traversal, while bottom layers enable exhaustive local search. HNSW achieves logarithmic search complexity with high recall, making it the default index in many vector databases for legal document retrieval. It requires no training phase, unlike clustering-based methods, and supports incremental insertion without full index rebuilds.

A vector compression technique that decomposes high-dimensional embeddings into smaller sub-vectors and quantizes each independently using k-means clustering. For legal embeddings with 768 or 1024 dimensions, PQ can achieve 10-30x memory reduction with minimal recall loss. This enables billion-scale legal document indices to fit in RAM, dramatically reducing infrastructure costs for production retrieval systems.

The fundamental engineering tension in ANN search. Recall@k measures the fraction of true nearest neighbors found in the top-k results, while latency measures query response time. In legal retrieval, practitioners typically target:

• 95-99% Recall@100 for high-stakes case law research
• 80-90% Recall@10 for real-time contract clause matching
• Sub-100ms latency for interactive user experiences Tuning index parameters like HNSW's M (connections per node) and efSearch (search depth) navigates this trade-off.

A retrieval paradigm where short queries and long documents use different encoding strategies. In legal ANN search, queries are typically a few words while documents span thousands of tokens. Asymmetric approaches may encode documents with a heavyweight model like Legal-BERT and queries with a lightweight encoder, or use separate index structures optimized for each side of the similarity computation. This addresses the length imbalance inherent in legal research.

An algorithm that merges ranked result lists from multiple retrieval systems by computing a reciprocal rank score: 1 / (k + rank) where k is a constant (typically 60). RRF requires no score calibration between systems, making it ideal for combining ANN-based dense retrieval with BM25 sparse retrieval in hybrid legal search architectures. It consistently outperforms linear combination methods when score distributions differ significantly.