Technical Summary: ANNLib – A Development Framework for Efficient Approximate Nearest Neighbor Search

1. Problem Statement

Approximate Nearest Neighbor Search (ANNS) is a critical component in modern deep learning pipelines, enabling efficient retrieval in high-dimensional vector spaces. While significant research has focused on either broadening the functionality of ANNS systems (e.g., supporting dynamic updates, filtering, or historical snapshots) or maximizing performance (throughput and recall), few systems successfully achieve both with minimal programming effort.

Current solutions face a dichotomy:

• Feature-rich vector databases (e.g., Milvus, Weaviate) prioritize ease of use but often underperform compared to specialized algorithms.
• Performance-optimized systems (e.g., DiskANN, ParlayANN) offer high throughput but consist of highly optimized, monolithic codebases that are difficult to adapt to new functionalities or application-specific constraints.

Developers are forced to choose between performance and flexibility, often requiring extensive code rewriting to implement advanced features like filtered search or dynamic deletions on top of existing high-performance engines.

2. Methodology: The ANNLib Framework

The authors propose ANNLib, a C++ header-only library designed to decouple the algorithmic logic and data structure components of graph-based ANNS systems. The framework allows developers to compose high-performance ANNS systems by mixing and matching pre-built, deeply optimized modules.

2.1 Core Design Principles

• Decoupling and Modularity: ANNLib separates the system into two independent core components: Algorithms and Data Structures.
  • Algorithms: Provide the logic for index construction and querying. ANNLib includes base algorithms (Vamana, HNSW, HCNNG) and algorithm modules for advanced functionalities (batch insertion, deletion, filtered search, snapshots).
  • Data Structures: Manage the underlying graph representation. ANNLib provides unified interfaces for reading and modifying the graph, supporting various container types (e.g., Nested Arrays for static workloads, Functional Trees for snapshots, and a new Chrono Prefix Array).
• Common Logic Abstraction: The framework abstracts common graph operations (specifically neighbor collection and pruning) into generic interfaces (collect and prune). Developers only need to implement the unique logic of their specific algorithm, while reusing the shared parallelization and traversal logic.
• Edge Agent Pattern: To support diverse data structures without exposing container-specific details to algorithm developers, ANNLib introduces an "Edge Agent." This intermediate structure acts as a view over a vertex's edges, allowing containers to apply their own optimizations (e.g., copy-on-write for trees, direct array access for nested arrays) while presenting a uniform interface to the algorithm.

2.2 Key Technical Implementations

• Filtered Search: Implemented via Stitched-vamana (merging sub-graphs built per label) and Filtered-vamana (relaxing pruning conditions to preserve candidates with specific labels). Both are achieved by customizing the neighbor filtering predicate (f_nbhs) without altering the core beam search logic.
• Dynamic Updates (Deletion): Based on the FreshDiskANN approach, ANNLib implements a two-step process: marking deleted points (using a state array and "tombstone" logic for quick path checks) and consolidating neighbors to restore graph connectivity.
• Historical Snapshots: The framework supports querying historical states of the index. It introduces two data structures:
  • Functional Tree (CPAM): Uses copy-on-write (CoW) to preserve versions.
  • Chrono Prefix Array: A novel structure specifically for ANNS graphs that compresses edge versions over time by sharing prefixes. This avoids duplicating edges across snapshots, significantly reducing memory overhead compared to full tree copies.

2.3 Application Examples

The paper demonstrates the framework's flexibility by building four applications with minimal code atop ANNLib:

1. Regular ANNS: Standard static search using Vamana or HNSW.
2. Fully Dynamic Updates: Supporting batch insertions and deletions.
3. Filtered Search: Implementing Stitched-vamana and Filtered-vamana.
4. Streaming with Snapshots: Maintaining historical versions of the index for temporal queries.

3. Experimental Results

The authors evaluated ANNLib against state-of-the-art baselines (ParlayANN, DiskANN, Milvus, Weaviate) across multiple datasets (BIGANN, DEEP, OpenAI, Cohere, MARCO, YFCC) and scenarios.

• Insertion Performance: ANNLib's Vamana implementation achieved an average 1.58× speedup over ParlayANN, with up to 8.11× faster on specific batches. HNSW performance was comparable to ParlayHNSW (0.99–1.34× speedup). These gains are attributed to copy elision and optimized interfaces.
• Query Throughput (Regular Search): ANNLib achieved competitive QPS-recall trade-offs. On large datasets like BIGANN, performance matched ParlayANN. On smaller datasets, it converged to comparable QPS at high recall, though it lacked specialized low-recall optimizations present in ParlayANN.
• Filtered Search: ANNLib outperformed monolithic solutions (DiskANN, Milvus, Weaviate) in almost all cases regarding QPS-recall curves, demonstrating that modular design does not sacrifice performance.
• Deletion: The consolidation phase in ANNLib restored index recall to near-rebuild levels, though it incurred computational costs proportional to the number of affected points.
• Snapshots: The Chrono Prefix Array reduced memory usage by up to 70.4% compared to a naive chronological list scheme by avoiding full edge duplication. While enabling snapshots increased build time (1.22× to 3.32× depending on the structure), the memory efficiency gains were significant for large-scale, dynamic datasets.

4. Key Contributions

1. A Modular Framework: ANNLib provides the first programming framework that successfully decouples algorithmic logic from data structure implementation for graph-based ANNS, enabling flexible composition.
2. Unified Abstractions: The introduction of generic collect/prune interfaces and the Edge Agent pattern allows diverse algorithms and data structures to interoperate seamlessly.
3. Novel Data Structures: The proposal of the Chrono Prefix Array offers a space-efficient solution for maintaining historical snapshots of dynamic graphs, addressing a specific bottleneck in existing snapshot mechanisms.
4. Demonstrated Flexibility and Performance: The paper validates that complex functionalities (filtering, deletion, snapshots) can be implemented with minimal code while achieving performance comparable to or better than specialized, monolithic systems.

5. Significance and Claims

The paper claims that ANNLib bridges the gap between high-performance research prototypes and flexible, production-ready systems. By allowing developers to "plug and play" optimized components, ANNLib reduces the engineering effort required to build sophisticated ANNS systems without compromising efficiency.

The authors emphasize that their design enables the creation of hybrid systems (e.g., performing filtered queries on a historical snapshot of a dynamically changing dataset) that would be difficult to implement in existing monolithic frameworks. The release of the code aims to facilitate further research and application development in the ANNS domain.