Proximity Graphs for Maximum Inner Product Search

This direction is merged into another direction: triangle inequality violation (non-metric similarity search). Its last version stays readable and citable here.

Version 1 of 16 papers16 conceptsfrozen 2026-10-04

Maximum Inner Product Search (MIPS) is the engine behind modern recommendation systems and large-scale retrieval. Unlike standard Nearest Neighbor Search (NNS), which looks for points close together in Euclidean space, MIPS seeks the vector $x$ that maximizes the dot product $q \cdot x$. This introduces a unique challenge: the result depends not just on the angle between vectors, but also on their magnitudes (norms).

Recent research has moved away from forcing MIPS into Euclidean frameworks, instead building proximity graphs that directly exploit the structural properties of inner product spaces.

The Power of Norm Bias

The defining characteristic of MIPS is norm bias. In any sufficiently large dataset, items with large vector magnitudes disproportionately dominate the top results. As Jie Liu and Xiao Yan demonstrate in Understanding and Improving Proximity Graph based Maximum Inner Product Search, the probability of a small-norm item appearing in the top results decreases exponentially as the dataset grows.

While this might seem like a search hurdle, it is actually the secret to efficiency. In a proximity graph, these high-norm items naturally become hubs—nodes with high in-degrees that attract search walks. Because these hubs are statistically likely to be the "winners" for many different queries, a search algorithm that encounters them early can prune the rest of the search space effectively.

Why Transformations Fail

Historically, researchers tried to solve MIPS by transforming vectors into a higher-dimensional space where the inner product search becomes a Euclidean distance search. However, Artem Babenko and Stanislav Morozov argue in Non-metric Similarity Graphs for Maximum Inner Product Search that these transformations are counterproductive for graph-based methods.

Standard transformations often bias graph edges toward vectors with smaller norms. This creates a misalignment: the graph's connectivity forces the search to wander through irrelevant, low-magnitude nodes, moving away from the high-norm candidates that actually maximize the inner product. By using ip-NSW, a graph built directly on the non-metric inner product similarity, the authors bypass these distortions and achieve significant speedups.

Stitching Metrics for Global and Local Navigation

If high-norm items are so dominant, why not just search them? The problem is that MIPS still requires directional alignment. A very large vector in the wrong direction is still a poor match. This creates a tension between "angular" similarity (direction) and "inner product" similarity (direction + magnitude).

To resolve this, Tingyang Chen and colleagues proposed a "metric-amphibious" approach in Stitching Inner Product and Euclidean Metrics for Topology-aware Maximum Inner Product Search. Their method, MAG, "stitches" two paradigms together:

  1. Euclidean/Angular Connectivity: Provides global reachability, allowing the search to quickly navigate to the correct "slice" of the vector space.
  2. Inner Product Shortcuts: Connects nodes directly to "regional dominators"—local high-norm vectors that are likely optimal solutions for that spatial cluster.

This hybrid topology allows a switching search algorithm (ANMS) to use Euclidean distance for fast global navigation and then "jump" to high-norm hubs via inner product shortcuts for rapid local convergence.

The Dual-Graph Strategy

Building on the insight that norm bias is both a tool and a trap, Jie Liu and James Cheng developed ip-NSW+ (Understanding and Improving Proximity Graph Based Maximum Inner Product Search). This approach uses a dual-graph structure to balance the search.

By maintaining an angular graph alongside an inner-product-aware graph, the system ensures that the search doesn't get "stuck" evaluating irrelevant high-norm distractors. The angular component ensures the search stays in the right direction, while the inner product component leverages the high-degree hubs to find the maximum value quickly. This combination proves robust across diverse data distributions, turning the inherent bias of MIPS into a structural advantage.

Papers in this version

History & citationVersion 1 · 2026-10-04

Merged into another direction · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_proximity_graphs_for_maximum_inner_produ_37398438,
  title = {Proximity Graphs for Maximum Inner Product Search},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/proximity-graphs-for-maximum-inner-product-search/rdr_37398438c1b84700a0e65f7d76aa247f},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_proximity_graphs_for_maximum_inner_produ_37398438_v1,
  title = {Proximity Graphs for Maximum Inner Product Search},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/proximity-graphs-for-maximum-inner-product-search/rdr_37398438c1b84700a0e65f7d76aa247f/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}