Amortizing Maximum Inner Product Search with Learned Support Functions

2026-06-17 · Source: stat.ML updates on arXiv.org · Field: Technology & Digital — Artificial Intelligence & Machine Learning, Data Science & Analytics · Depth: Expert, extended

Summary

Amortized Maximum Inner Product Search (MIPS) is a novel learning-based approach that trains neural networks to predict MIPS solutions, amortizing computational costs for queries from a fixed distribution. This method leverages the MIPS value function's property as a support function, which is convex and 1-homogeneous, with its gradient equaling the optimal key. Two architectures are proposed: SupportNet, an Input Convex Neural Network (ICNN) that models the support function directly, recovering keys via gradient computation; and KeyNet, which directly regresses the optimal key, bypassing inference-time gradient computation. Experiments on BEIR benchmark datasets (FIQA, Quora, Natural Questions, HotpotQA) with $d=384$ dimensional embeddings demonstrate high match rates and significant speedups. The approach also integrates effectively into approximate search indices like FAISS IVF, improving recall with fewer floating-point operations.

Key takeaway

For AI Scientists and Machine Learning Engineers optimizing large-scale MIPS, consider implementing amortized MIPS with SupportNet or KeyNet. This approach significantly reduces inference costs for predictable query distributions, offering speedups and higher match rates on datasets like FIQA and HotpotQA. You can achieve better routing accuracy in clustered databases or enhance approximate search indices by mapping queries to predicted keys, improving recall with fewer operations.

Key insights

Amortized MIPS uses neural networks to predict optimal keys, exploiting the support function's convex and homogeneous properties.

Principles

• MIPS value function is a convex, 1-homogeneous support function.
• Support function's gradient equals the optimal database vector.
• Learning-based MIPS amortizes cost for known query distributions.

Method

Train SupportNet (ICNN for support function, gradient for key) or KeyNet (direct key regression) using score regression, gradient matching, or score consistency losses, with optional homogenization wrappers.

In practice

• Use SupportNet for mathematically aligned convex function learning.
• Employ KeyNet for direct, faster key prediction at inference.
• Integrate KeyNet with FAISS IVF for improved approximate search.

Topics

• Maximum Inner Product Search
• Amortized Optimization
• Support Functions
• Input Convex Neural Networks
• Neural Networks
• Information Retrieval

Best for: Research Scientist, AI Engineer, NLP Engineer, AI Scientist, Machine Learning Engineer

Related on AIssential

• Amortizing Maximum Inner Product Search with Learned Support Functions — Amortized MIPS uses neural networks to predict optimal keys by modeling the support function or directly regressing keys.
• Quantization Effects of Artificial Neural Networks for Embedded Edge-Computing Applications — LUT-based 2-bit BNNs trained with GAs enable sub-50ns real-time waveform classification on FPGAs.
• Large-Scale Data Parallelization of Product Quantization and Inverted Indexing Using Dask — Combining PQ, Inverted Indexing, and Dask enables efficient, accurate large-scale ANN search.
• One Operator for Many Densities: Amortized Approximation of Conditioning by Neural Operators — Neural operators can universally approximate probabilistic conditioning, enabling amortized inference across diverse joint distributions.
• Largest empty shapes — Finding largest empty shapes in point sets requires diverse optimization models depending on the shape.
• Amortized Optimal Transport from Sliced Potentials — Amortized optimal transport methods efficiently predict OT plans by reusing learned Kantorovich potentials from sliced OT.

Open in AIssential →

Editorial summary, takeaway, and curation by AIssential. Original article published by stat.ML updates on arXiv.org.