Approximate Nearest Neighbor Search

Vector search technique trading small precision loss for significant speed improvements when finding similar documents in large reference datasets. Essential for scaling few-shot example selection in high-volume document processing at alan-health, particularly using Hierarchical Navigable Small World (HNSW) indexes.

Problem: Exact Search Scalability

Performance Bottleneck

Exact L2 distance search: Accurate but computationally expensive at scale

• Linear complexity: Search time increases proportionally with dataset size
• Million-document challenge: Exact search becomes prohibitively slow
• Production requirements: Sub-second response times needed for real-time processing
• Growing datasets: Reference collections expand continuously with new validated documents

Business Context at Scale

alan-health's document processing requires:

• High-volume processing: Thousands of documents daily requiring few-shot examples
• Large reference datasets: Millions of previously processed documents available as examples
• Real-time selection: Few-shot examples must be selected within processing time limits
• Quality maintenance: Similar examples improve extraction accuracy

Solution: HNSW Implementation

Algorithm Choice

Hierarchical Navigable Small World (HNSW): Graph-based approximate search providing logarithmic complexity

• Speed improvement: Significant performance gains over exact search
• Controlled precision loss: Tunable accuracy-speed tradeoffs
• Scalability: Maintains performance as reference datasets grow
• Production-ready: Mature implementation available in vector databases

Technical Benefits

• Sub-linear search time: Logarithmic rather than linear complexity
• Tunable parameters: Control precision-speed balance based on requirements
• Memory efficiency: Graph structure more compact than exhaustive indexes
• Incremental updates: Can add new reference documents without rebuilding entire index

Production Implementation

Few-Shot Selection Workflow

1. Document encoding: Convert input document to vector representation
2. Similarity search: Query HNSW index for nearest neighbors in reference dataset
3. Example retrieval: Return most similar documents as few-shot examples
4. Extraction processing: Use selected examples in LLM prompt for structured extraction

Performance Characteristics

• Speed gains: Significant reduction in selection time compared to exact search
• Precision tradeoffs: Small accuracy loss acceptable for production speed requirements
• Scalability: Maintains performance as reference dataset grows to millions
• Quality impact: Approximate selection still provides high-quality examples for extraction

Alternative Approaches

Exact Search Limitations

• Brute force: Compute L2 distance against every reference document
• Scalability wall: Becomes prohibitively slow beyond certain dataset sizes
• Resource intensity: High CPU/memory requirements for large comparisons

Other Approximate Methods

• LSH (Locality Sensitive Hashing): Hash-based approximate search
• Product quantization: Compressed vector representations
• Tree-based methods: KD-trees and variations for high-dimensional search

Configuration Considerations

Accuracy-Speed Tuning

• Index parameters: Control graph construction for desired precision-recall characteristics
• Search parameters: Runtime tuning for specific speed-accuracy requirements
• Quality validation: Measure impact of approximate search on extraction accuracy
• Performance monitoring: Track search times and result quality over time

See also

• hierarchical-navigable-small-world
• document-processing-pipeline
• few-shot-contamination
• vector-databases
• alan-health