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

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$\times$ query throughput over the better of the other two schedules.