acceptodds
Under review as a conference paper at ICLR 2027

Order Matters: A Finite-Capacity Model for Selecting Insertion Order in Graph-Based Maximum Inner Product Search

Abstract

Graph-based indexes for maximum inner product search (MIPS) are constructed incrementally, yet the effect of insertion order on the resulting graph is largely overlooked. We show that insertion order can substantially change search performance even when the graph algorithm and all of its parameters remain fixed, and study three schedules: increasing norm, decreasing norm, and random insertion. A stylized finite-capacity model relates their behavior to two geometric properties of the base vectors. The first measures directional redundancy within candidate sets matched to the neighbor-list size, while the second measures how three-vector concentration changes along the norm ranking beyond what pairwise concentration explains. Random projections estimate both quantities before construction and yield a closed-form rule for selecting an order. At matched recall, the selected order achieves about 1.4 query throughput over the better of the other two schedules.

Primary area:
infrastructure, software libraries, hardware, systems, etc.
Keywords:
Maximum inner product search, Graph index, Random projections

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_6FDDOpenReview ↗
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.

1 comment

Thank you for the comments and questions.

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.

We tested PAG at k=10k=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%94.7\% zero coordinates. In the variant with the heavier norm tail, the coefficient of variation is 3.33.3 and the largest norm is 164.6164.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.

Q1. How sensitive is the final prediction accuracy to the depth selection of nested random hyperplanes? Is there a theoretical lower bound guarantee?

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 SS, 2S2S, and 4S4S, keeping the endpoint score fixed. The three targets give 12, 12, and 11 correct selections out of 12, respectively. With 4S4S, 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.

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?

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.81.8 to 18.418.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%25\%, 50%50\%, 75%75\%, and 100%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%50\% and 75%75\%.

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.

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.

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.

Reviewer_5MBDOpenReview ↗
Rating
1
Confidence
3
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

This paper studies how insertion order affects graph-based maximum inner product search. It proposes a selector for insertion in increasing norm order, decreasing norm order, or random order. The selector uses directional redundancy and concentration to compare these orders under a limited neighbor budget. Experiments on 12 datasets show accurate order selection and improved query throughput with low prediction overhead.

Critical strengths
  1. The problem is real and practically relevant. The experiments show that insertion order can substantially affect search performance under the same graph builder and construction settings.

  2. The reported results are strong. At the default graph degree, the selector matches the best measured order in all 42 comparable settings. The additional cost of selecting an order is also small.

Critical weaknesses
  1. The paper writing needs substantial improvement. Nearly every paragraph in the Section 3 and 4 introduce new symbols or definitions, often several at once. I think the manuscript cannot reach the clarity expected in a research paper. The authors should explain their functional motivation and target before introducing the equations. Otherwise, the main ideas are difficult to follow.

  2. Figure 1 and Table 6 show changes in degree and pruning behavior, but do not measure the directional coverage of retained neighbors. Thus, they do not establish whether preserving more useful directions explains the search gains (as introduced in Section 1).

  3. The analysis in the experimental section is very brief. And the experimental analysis does not sufficiently support the proposed mechanism. The paper uses (\Delta_e), derived from candidate directional redundancy, to decide whether high-norm vectors should be inserted early or late. However, it does not examine whether this metric reflects changes in the directional coverage of retained neighbors, or whether those changes explain the search gains.

  4. Section 3.1 assigns the same score to later neighbor positions under ASC and DESC. Yet Appendix B.4 reports substantial differences in rejection rates and retained degrees. It is unclear why averaging out these effects should preserve the ranking of the two orders.

Questions for authors

See weaknesses.

3 comments

Thank you for your comments and suggestions. We revised Sections 3 and 4 and added measurements of the directions that pruning retains.

(W1) The authors should explain their functional motivation and target before introducing the equations.

Section 3.2 now explains why it matters whether the strongest candidates cover different directions or compete for the same ones. We introduce the candidate pool and explain what the squared cosines measure before defining the endpoint coefficient. Section 3.3 uses the role of a retained neighbor in pruning to motivate the pair and triple probabilities along a sorted prefix. Section 4 estimates the coefficients in the same order. Appendix B.2 reports the projection settings and shows that using distinct pairs and independent Gaussian directions for the endpoint estimate gives the same twelve selections when the sorting estimates are held fixed.

(W2) Figure 1 and Table 6 show changes in degree and pruning behavior, but do not measure the directional coverage of retained neighbors.

We now measure effective directional rank, which accounts for both the length of a neighbor list and how similar its directions are. We measure rank in lists obtained by pruning candidates sampled from the ASC and DESC prefixes, using eight paired repetitions per dataset. We also measure rank in the lists of sampled vertices in the top 20%20\% by norm in separate PAG builds. Appendix B.5 and Figure 4 relate both measurements to recall AUC.

(W3) The paper uses (\Delta_e), derived from candidate directional redundancy, to decide whether high-norm vectors should be inserted early or late. However, it does not examine whether this metric reflects changes in the directional coverage of retained neighbors, or whether those changes explain the search gains.

We compute recall AUC over the same efSearch values for all three orders. Across the ten datasets favoring ASC or DESC, we compare the DESC minus ASC differences in effective rank and recall AUC. The endpoint estimates in Table 3 have Spearman correlations of 0.30.3 and 0.470.47 with the rank differences for sampled pruning and final PAG lists, respectively (Appendix B.5). The rank differences correlate 0.530.53 and 0.390.39 with the recall difference. The endpoint estimates correlate 0.780.78 with that difference, and the difference in angular diversity after sampled pruning correlates −0.76-0.76 (Figure 4).

The order with the highest recall AUC also has the best QPS at matched recall in 41 of the 42 conditions where all three recall curves overlap. It matches the measured dataset preferences in 47 of all 48 conditions (Appendix B.5).

(W4) Section 3.1 assigns the same score to later neighbor positions under ASC and DESC. Yet Appendix B.4 reports substantial differences in rejection rates and retained degrees. It is unclear why averaging out these effects should preserve the ranking of the two orders.

The midpoint preserves the average of ASC and DESC for comparison with RAND. When comparing ASC with DESC, the shared later score cancels, so the model ranks them by the sign of the endpoint coefficient. Section 3.1 shows the difference in later scores that this comparison sets aside. At the default degree, the endpoint coefficient matches the measured winner on all ten datasets that favor a sorted order (Appendix B.6, Table 8).

In the sampled pruning test, DESC raises rejection rates and blocker to source norm ratios on all twelve datasets. The decrease in retained degree is at least 8.28.2 on every dataset favoring ASC and at most 6.516.51 on those favoring DESC (Appendix B.4, Table 6).

Dear Authors,

Thank you for revising the submitted manuscript. The revision arrived so close to the deadline that I do not have enough time to give it a careful reading. I also noticed that nearly the entire main text is marked in red, suggesting that most of it has been rewritten. It raises some concerns for me about the quality of the submission. For these reasons, I maintain my original score.

Dear Reviewer,

Thank you for your quick response. After the reviewer-author discussion phase, the AC-reviewer discussion phase begins on November 19. We would appreciate it if you could take some time to review our revisions and make your decision during that phase.

Reviewer_FScDOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper investigates how the insertion order of base vectors affects the topology and query performance of incrementally constructed graph-based indexes for Maximum Inner Product Search (MIPS), focusing on ip-NSW and PAG. While keeping the graph construction algorithms and hyperparameters fixed, the authors study three schedules—increasing norm (ASC), decreasing norm (DESC), and uniformly random permutation (RAND)—and demonstrate that insertion order substantially alters outgoing degree distributions across norm levels and shifts query throughput (QPS) versus recall frontiers. To predict the optimal schedule before graph construction without expensive trial builds, the authors develop a stylized finite-capacity utility model of neighbor-list pruning for a list of capacity SS, connecting first-position and later-position pruning decisions to two geometric quantities estimated via random projections and nested random hyperplanes: local directional redundancy among top-2S2S inner-product candidates (Δe\Delta_e) and shifts in normalized three-vector directional concentration along norm-ranked prefixes (Δs\Delta_s). Validated across 12 million-scale datasets, the resulting closed-form selector (RAND if (S−1)Δ^s>3∣Δ^e∣(S-1)\widehat{\Delta}_s > 3|\widehat{\Delta}_e|, DESC if Φ^S≤0\widehat{\Phi}_S \le 0 and Δ^e>0\widehat{\Delta}_e > 0, and ASC otherwise) accurately identifies the best schedule in all 42 shared-recall conditions at the default degree S=M=32S=M=32, achieving roughly 1.4×1.4\times geometric-mean query throughput over the runner-up schedule while adding less than 6%6\% construction time overhead.

Critical strengths

Compelling Empirical Discovery with High Practical Value: The paper uncovers an impactful phenomenon in incremental MIPS graph construction—showing that permuting the insertion order by vector norm (ASC, DESC, or RAND) reshapes out-degree distributions and shifts high-recall query throughput by ∼1.4×\sim 1.4\times on average across distinct builders (ip-NSW and PAG)—and provides an immediately deployable pre-construction selector that incurs less than 3%3\% median build time overhead without altering the index structure or search code.

Principled Geometric Characterization of Two-Way vs. Three-Way Pruning Interactions: The authors prove that any utility additive over pairwise arrival orders places RAND at the exact midpoint of ASC and DESC, motivating a three-vector hyperplane collision statistic (Δs\Delta_s) alongside a local top-2S2S directional redundancy measure (Δe\Delta_e) that together resolve all 12 datasets where global 1D scalar summary statistics and 5%5\% subsample trial builds fall short.

Critical weaknesses

Stylized Symmetry Assumptions in the Finite-Capacity Pruning Model: The theoretical derivation relies on idealized symmetry reductions—specifically replacing asymmetric later-position scores LASCL_{\text{ASC}} and LDESCL_{\text{DESC}} with their midpoint LmidL_{\text{mid}} (despite Appendix B.4 showing large later-position out-degree and rejection-rate asymmetries) and using a direction-agnostic 4-versus-2 arrival rule for unordered triples that abstracts away the directed (x,y,z)(x, y, z) arrival constraints and rz/rxr_z/r_x blocker ratios of Equation 1—which would benefit from clearer justification of how Δe\Delta_e proxies cumulative later-position blocking and why capacity scaling behaves as (S−1)(S-1) across degrees such as M=16M=16.

Scope Relative to Norm-Adjusted Incremental Builders and Alternative Ordering Axes: The analysis and experiments focus exclusively on builders (ip-NSW and PAG) using raw inner-product pruning and norm-sorted schedules; the authors might consider clarifying or evaluating whether the proposed finite-capacity selector extends to incremental MIPS builders that explicitly adjust for norms during routing or pruning (Reference Paper: Understanding and improving proximity graph based maximum inner product search, Jie Liu, Xiao Yan, Xinyan Dai, Zhirong Li, James Cheng, and Ming-Chang Yang, 2020; Reference Paper: Norm adjusted proximity graph for fast inner product retrieval, Shulong Tan, Zhaozhuo Xu, Weijie Zhao, Hongliang Fei, Zhixin Zhou, and Ping Li, 2021) and how norm-based schedules compare against or interact with Local Intrinsic Dimensionality (LID) insertion schedules (Reference Paper: The impacts of data, ordering, and intrinsic dimensionality on recall in hierarchical navigable small worlds, Owen Pendrigh Elliott and Jesse Clark, 2024).

Questions for authors
  • What would it take to make the classifier provably correct?
  • What other insertion orders would you consider?
1 comment

Thank you for your comments and questions.

(W1) Stylized Symmetry Assumptions in the Finite-Capacity Pruning Model: ...

The midpoint preserves the average later score used to compare the sorted orders with RAND. It sets aside the difference in later scores between ASC and DESC, leaving the endpoint coefficient to rank those orders in the model (Section 3.1). The sorting coefficient tracks how often triples of directions share a region relative to pairs as the norm prefixes grow. It reflects how sorting changes the opportunities for nearby directions to compete during pruning. Appendix B.5 relates the endpoint coefficient to observed differences in retained directional rank and recall.

A uniformly permuted triple puts the record with the smallest norm first or last in four of the six orders and in the middle in the other two. The model assigns the sorted score in the first case and the neutral score in the second (Section 3.3 and Appendix A.2). This calculation counts the possible arrivals of a fixed triple. The pruning test in Equation (1) assigns distinct roles to the source, candidate, and blocker and uses the ratio of blocker to source norms.

Averaging over one first position and S−1S-1 later positions gives weights 1/S1/S and (S−1)/S(S-1)/S to the two scores. In the degree sweep at k=10k=10 (Appendix B.3, Table 4), the selector matches the measured winner in 19/2419/24, 24/2424/24, and 23/2423/24 cases at M=SM=S equal to 16, 32, and 64, respectively. The corresponding throughput regrets are 3.83%3.83\%, 0%0\%, and 1.58%1.58\%, all below the regret of the best fixed order at that degree.

(W2) Scope Relative to Norm-Adjusted Incremental Builders and Alternative Ordering Axes: ...

Insertion order also matters in ip-NSW+. We ran ASC, DESC, and RAND at k=10k=10 on all twelve datasets using the official implementation with its original routing and pruning. At matched recall, the best order gives 1.261.26 times the geometric mean QPS of the next best and 1.761.76 times that of the worst. It also uses the fewest distance computations at matched recall on 8 of 12 datasets. For Word2Vec, the selector's ASC choice matches ip-NSW, while ip-NSW+ favors DESC (Table 3 and Appendix B.10).

With PAG at k=10k=10, we compared ASC, DESC, and RAND with two orders based on local intrinsic dimensionality (LID). On each of the eleven datasets where all five orders share a recall interval, one of ASC, DESC, and RAND wins. The geometric mean QPS ratio to the better LID order is 1.151.15. On SproosV3, ASC reaches zero recall. Over the shared recall interval of the four remaining curves, RAND is the best canonical order and reaches 0.860.86 times the QPS of decreasing LID. Including that comparison gives an overall ratio of 1.131.13 (Appendix B.10).

(Q1) What would it take to make the classifier provably correct?

For a fixed builder and query distribution, we would need a bound on the difference between each order's model utility and its search performance at matched recall, measured on a common scale. One sufficient condition is that every absolute error is less than half the gap between the two highest model utilities. The bound would need to account for candidate discovery, pruning, and reciprocal edge updates. Proposition 1 in Appendix A.3 gives consistency for the estimator in Section 4. With a strict depth crossing and a unique utility maximizer, the estimated choice eventually agrees with the model's decision almost surely.

(Q2) What other insertion orders would you consider?

We tested two additional insertion orders, one sorting vectors by increasing LID and the other by decreasing LID. We compared both with ASC, DESC, and RAND on all twelve datasets using PAG at k=10k=10. Figure 8 (left panel) and Appendix B.10 report the results.

Comments on the paper

2 comments

Dear reviewers,

The rebuttal period is ending soon. Please read the authors rebuttal and check if they addressed your concerns. Please acknowledge the rebuttal and adjust your scores accordingly.

Thanks.

-AC

Dear AC and Reviewers,

In this paper, we show that changing the insertion order alone can substantially affect MIPS search performance even when the graph builder and its settings stay the same.

We provided our responses to the review comments and revised the paper accordingly. Please refer to the updated PDF for the revised sections. Next, we summarize our revisions.

FScD

  • W1. We clarified the use of the average later score and the scoring of the six arrival orders (Sections 3.1 and 3.3).
  • W2. We tested the three original orders with the official ip-NSW+ implementation and compared them with orders based on local intrinsic dimensionality (LID) in PAG (Appendix B.10 and Figure 8).
  • Q1. Our reply explains what a guarantee for actual graph performance would require.
  • Q2. The two additional orders tested in PAG sort vectors by increasing and decreasing LID (Figure 8, left panel).

5MBD

  • W1. We revised Sections 3 and 4 to explain the motivation for both coefficients before introducing the equations.
  • W2, W3. We measured the directional coverage of retained neighbors and related it to the endpoint score (Appendix B.5) and to recall AUC (Figure 4).
  • W4. Section 3.1 clarifies how the shared later score affects the comparison between ASC and DESC.

6FDD

  • W1. We added tests on an ImageNet subset and four variants with greater sparsity or heavier norm tails (Appendix B.10).
  • W2. Our reply explains the scope of the selector for incremental builders that accept a chosen input order.
  • Q1. We discuss the sensitivity to hyperplane depth reported in Table 5.
  • Q2. Our reply explains when to run the selector for construction or rebuilding.
  • Q3. Our reply discusses the selector's use with hierarchical ip-NSW.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.