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

Yutaro Oguri, Yusuke Matsui

Introduction

In the rapidly evolving landscape of vector databases and Large Language Models (LLMs), the efficiency of Approximate Nearest Neighbor Search (ANNS) is paramount. While graph-based algorithms such as Hierarchical Navigable Small World (HNSW) and Neighborhood Graph (NSG) are considered the gold standard for speed and accuracy, they present a significant challenge: they are notoriously difficult to tune. Engineers often grapple with a complex constrained optimization problem—maximizing Queries Per Second (QPS) while maintaining a recall threshold (typically >90%) and adhering to strict memory limits.

This report, presented by Team UTokyo for the SISAP 2023 Indexing Challenge, details a highly practical tuning framework designed to optimize off-the-shelf graph indexes. By combining dimensionality reduction, database subsampling, and intelligent entry-point selection, the team achieved a 1.6x speedup over vanilla graph indexes, securing 2nd place in the competition.

Methodology

The core philosophy of the UTokyo approach is to optimize the search pipeline without modifying the underlying source code of the graph index. The framework consists of three primary technical interventions coordinated by an automated optimization layer.

1. Dimensionality Reduction (PCA)

Profiling of standard graph-based searches revealed that over 90% of search time is consumed by L2 distance calculations. To address this bottleneck, the team employed Principal Component Analysis (PCA). By reducing the vector dimension ($D$), they directly lowered the computational cost of every distance check performed during graph traversal. The team found that even slight reductions in dimensionality yielded a higher return on investment (ROI) than traditional graph connectivity tweaks.

2. Database Subsampling (AntiHub Removal)

To further streamline the search space, the team utilized "AntiHub Removal." This technique prunes the database to reduce the total number of points ($\alpha$) the graph must navigate. By removing points that do not contribute significantly to the structural integrity of the search graph, the algorithm improves efficiency while maintaining high accuracy.

3. Intelligent Entry-Point Selection

Standard graph searches typically begin at a fixed or random entry point. Team UTokyo optimized this by using $k$-means clustering to identify centroids across the dataset. For any given query, the search begins at the nearest centroid, significantly shortening the traversal path. To ensure this remained compatible with high-throughput batch processing, they developed a "gather-style" algorithm that groups queries by their nearest entry point, allowing for efficient parallel execution in libraries like Faiss.

4. Automated Tuning with Optuna

Because the relationship between parameters (dimension $D$, subsampling ratio $\alpha$, and cluster count) and performance is non-linear, the team employed Optuna, a black-box optimization framework. They utilized multi-objective optimization to treat QPS and Recall as competing goals, allowing them to identify the Pareto frontier rather than treating recall as a simple hard constraint.

Experimental Setup and Results

The framework was evaluated using the LAION2B dataset, consisting of 768-dimensional 16-bit float vectors. Tuning was performed on a 300K subset, while the competition tracks focused on 10M and 30M vector subsets.

Performance Highlights

  • Competition Ranking: The team secured 2nd place in both the 10M and 30M tracks of the SISAP 2023 Indexing Challenge (Task A).
  • Throughput: On the 30M dataset, the method achieved 30,100 QPS at >90% recall. This represents a 1.6x speedup over the vanilla NSG index and is approximately 1,188x faster than a brute-force search.
  • Ablation Analysis: PCA alone contributed a 1.53x speedup, while subsampling provided a 1.61x boost compared to the baseline, validating the multi-pronged approach.

Discussion and Future Work

A key insight from the study is that tuning parameters on a small subset (300K) provides performance trends that remain consistent when scaled to 10M or 30M points. This "subset tuning" strategy significantly reduces the computational overhead of the optimization process.

However, limitations remain. The team noted that their current method struggled with the strict memory constraints of the 100M vector subset, suggesting that "billion-scale" problems will require even more aggressive data reduction techniques. Additionally, the current workflow requires the index to be rebuilt whenever the PCA dimension or subsampling ratio changes. Future research will focus on methods to tune these parameters without requiring full index reconstruction and addressing potential performance shifts if the production query distribution differs from the tuning set.

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 10M and 30M 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},
}
Figure