- Rating
- 3
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper investigates the impact of insertion order on the performance of graph-based indexes for Maximum Inner Product Search. The authors propose a finite-capacity model that derives a closed-form selection rule among ascending, descending, and random insertion orders by analyzing the directional redundancy and three-vector concentration of the data. Experiments on twelve datasets and two graph index methods show that the approach selects the optimal insertion order with minimal prediction overhead, significantly improving query throughput at matched recall.
Critical strengths
S1. This paper systematically formulates the insertion order selection for graph indexes as a prediction problem based on data geometric properties, effectively avoiding costly trial-and-error construction.
S2. The proposed closed-form selection rule has low computational complexity and minimal prediction overhead relative to construction time, offering high deployment value in large-scale vector retrieval scenarios.
Critical weaknesses
W1. The finite-capacity model relies heavily on directional redundancy and three-vector concentration, but it does not adequately discuss the failure boundaries of these geometric assumptions under high-dimensional extreme sparsity or long-tail distributions.
W2. Experiments mainly focus on two incremental construction methods. The generalization ability of the selector in dynamic or non-incremental graph index structures is not sufficiently validated.
Questions for authors
Q1. How sensitive is the final prediction accuracy to the depth selection of nested random hyperplanes? Is there a theoretical lower bound guarantee?
Q2. If the dataset undergoes dynamic updates (e.g., adding new vectors) after construction, does the selector need to be re-executed? What is the evaluated overhead for such incremental updates?
Q3. It is recommended to supplement the analysis and experimental validation of the selector's applicability in more complex graph structures, such as hierarchical graph indexes, in future work.
Thank you for the comments and questions.
We tested PAG at k=10 on 200,000 ImageNet vectors with 150 coordinates each and four variants of that subset (Appendix B.10). Two variants keep the 32 or 8 largest coordinates by magnitude in each base and query vector and restore the original norms. The other two keep the directions and assign Pareto norms to the base vectors. The sparsest variant has 94.7% zero coordinates. In the variant with the heavier norm tail, the coefficient of variation is 3.3 and the largest norm is 164.6 times the median. With the same selector settings and exact ground truth for each case, the selector chooses ASC in all five cases, matching the highest QPS at shared recall.
Equation (8) sets the depth using the average number of other records in the same region. We recompute the depth and sorting score for targets S, 2S, and 4S, keeping the endpoint score fixed. The three targets give 12, 12, and 11 correct selections out of 12, respectively. With 4S, only DINOv2 changes, from RAND to ASC (Appendix B.3, Table 5). Proposition 1 gives consistency for the estimator in Section 4 when the partner count strictly crosses the threshold and the model has a unique winner. A lower bound on accuracy for actual graphs would require a quantitative link between the model utilities and the builder's search performance.
Appending vectors to an existing graph uses the builder's usual insertion procedure. The selector runs only before a build or rebuild to choose the order. Table 1 reports 1.8 to 18.4 seconds for that selection step across the twelve datasets.
To see whether the recommended order changes as the dataset grows, we ran the selector on the first 25%, 50%, 75%, and 100% of the vectors in storage order for four datasets. GloVe-200 stays DESC, Word2Vec stays ASC, and ZZSN stays RAND. DINOv2 switches from ASC to RAND between 50% and 75%.
At the default degree, the selector matches the measured winner in the shared recall comparisons for both hierarchical ip-NSW and single-layer PAG (Section 5.1 and Appendix B.1). The official ip-NSW+ comparison shows that insertion order also affects performance in that implementation (Appendix B.10, Figure 8, right panel). For the selector to apply, the builder must construct the graph incrementally and accept a chosen input order.