General and Practical Tuning Method for Off-the-Shelf Graph-Based Index: SISAP Indexing Challenge Report by Team UTokyo

Yutaro Oguri, Yusuke Matsui

This report from Team UTokyo, presented for the SISAP 2023 Indexing Challenge, provides a highly practical roadmap for anyone looking to squeeze maximum performance out of graph-based Approximate Nearest Neighbor Search (ANNS) libraries.

TL;DR

Team UTokyo developed a tuning framework for off-the-shelf graph indexes (like NSG) that combines dimensionality reduction, database subsampling, and intelligent entry-point selection. By automating the parameter search with black-box optimization (Optuna), they achieved up to a 1.6x speedup over vanilla graph indexes and secured 2nd place in the SISAP 2023 competition.

What Problem Does This Paper Address?

In the world of vector databases and Large Language Models, finding the "nearest neighbor" to a query vector among millions of embeddings is a core task. Graph-based algorithms (like HNSW or NSG) are the gold standard for speed and accuracy, but they are notoriously difficult to tune.

Engineers often face a "constrained optimization" problem: How do I get the highest Queries Per Second (QPS) while maintaining at least 90% recall and staying under a specific memory limit? Because the relationship between parameters (like graph connectivity or vector dimensions) and performance is non-linear and non-monotonic, manual tuning or simple grid searches are often inefficient or ineffective.

Methods

The authors propose a three-pronged approach to optimize the search pipeline without modifying the underlying graph index code itself:

  1. Dimensionality Reduction (PCA): Profiling showed that over 90% of search time was spent calculating L2 distances. By using Principal Component Analysis (PCA) to reduce the vector dimension ($D$), they directly reduced the computational cost of every distance check.
  2. Database Subsampling (AntiHub Removal): They used a technique called "AntiHub Removal" to prune the database. This reduces the number of points ($\alpha$) the graph needs to navigate, improving efficiency while maintaining high accuracy.
  3. Optimizing Entry Points: Standard graph searches often start from a fixed or random point. The authors used $k$-means clustering to find centroids across the dataset. For any given query, the search starts at the nearest centroid, significantly shortening the traversal path.
  4. Black-box Optimization (Optuna): To find the perfect balance of $D$, $\alpha$, and the number of clusters, they employed Optuna, an optimization framework. They found that multi-objective optimization (treating QPS and Recall as competing goals to find a Pareto frontier) was more effective than treating recall as a hard constraint.

Datasets

The study utilized the LAION2B dataset, a massive collection of 768-dimensional 16-bit float vectors. For evaluation and tuning, they used subsets of:

  • 300K (for rapid tuning)
  • 10M and 30M (for competition tracks)

Key Insights and Ideas

  • L2 is the Bottleneck: The "aha moment" came from profiling. Since distance calculations dominate the CPU time, reducing the dimensionality of the vectors (even slightly) yields a much higher ROI than tweaking graph connectivity.
  • Entry Points Matter: Starting the graph traversal "closer" to the result via $k$-means centroids acts like a shortcut, preventing the algorithm from wandering through irrelevant parts of the graph.
  • Parallel-Friendly Batching: To make the $k$-means entry point strategy work with high-throughput batch processing, they developed a "gather-style" algorithm. This groups queries by their nearest entry point, allowing for efficient parallel execution in libraries like Faiss.
  • Tuning on Subsets: They discovered that tuning parameters on a small subset (300K) provided trends that remained consistent when scaled to 10M or 30M points, saving massive amounts of compute time.

Key Results

The team's approach proved highly effective in the SISAP 2023 Indexing Challenge (Task A):

  • Ranking: 2nd place in both the 10M and 30M tracks.
  • Speedup: On the 30M dataset, their method achieved 30,100 QPS at >90% recall. This is 1.6x faster than the vanilla NSG index and a staggering 1,188x faster than a brute-force search.
  • Ablation Gains: PCA alone provided a 1.53x speedup, while subsampling provided a 1.61x boost compared to the baseline.

Limitations and Future Work

  • The 100M Wall: The authors noted that their current method struggled to satisfy strict memory constraints on the 100M vector subset, suggesting that even more aggressive dimensionality or data reduction is needed for "billion-scale" problems.
  • Index Rebuild Time: A major bottleneck in their tuning process is that the index must be rebuilt every time the PCA dimension ($D$) or subsampling ratio ($\alpha$) is changed. Finding a way to tune these without full rebuilds is a key area for future research.
  • Query Sensitivity: The optimization assumes that the "public" queries used for tuning are representative of the "private" queries used in production. If the query distribution shifts, the tuned parameters might become suboptimal.

Summary updated

Abstract

Despite the efficacy of graph-based algorithms for Approximate Nearest Neighbor (ANN) searches, the optimal tuning of such systems remains unclear. This study introduces a method to tune the performance of off-the-shelf graph-based indexes, focusing on the dimension of vectors, database size, and entry points of graph traversal. We utilize a black-box optimization algorithm to perform integrated tuning to meet the required levels of recall and Queries Per Second (QPS). We applied our approach to Task A of the SISAP 2023 Indexing Challenge and got second place in the 10 M and 30 M tracks. It improves performance substantially compared to brute force methods. This research offers a universally applicable tuning method for graph-based indexes, extending beyond the specific conditions of the competition to broader uses.
BibTeX
@inproceedings{oguri2023general,
  author = {Yutaro Oguri and Yusuke Matsui},
  title = {{General and Practical Tuning Method for Off-the-Shelf Graph-Based Index: SISAP Indexing Challenge Report by Team UTokyo}},
  booktitle = {SISAP},
  year = {2023},
  url = {https://openreview.net/forum?id=G_V5swbB1A},
}

Loading related content...

Figure