When we want to find the most similar item in a massive database—whether it is a matching face, a relevant document, or the next word in a sentence—we face a fundamental computational bottleneck.
Efficient, sub-linear search algorithms (such as KD-trees, Locality-Sensitive Hashing (LSH), or graph-based indices like HNSW) rely heavily on metric properties, specifically the triangle inequality:
$$d(a, c) \le d(a, b) + d(b, c)$$
This geometric rule allows search algorithms to safely prune away large portions of a database. If a cluster center is far from a query, the algorithm can mathematically guarantee that no individual point inside that cluster can be the nearest neighbor, skipping millions of distance calculations.
The problem is that many of our most powerful AI models do not naturally operate in metric spaces. Maximum Inner Product Search (MIPS) in recommender systems, dot-product attention in Transformers, and comparisons between linear subspaces all violate the triangle inequality. Without metric properties, we are often forced to fall back on exhaustive linear scans ($O(N)$), which quickly become intractable at scale.
To solve this, researchers have developed a powerful paradigm: mathematically transforming non-metric proximity problems into standard Euclidean or angular nearest neighbor search (NNS). By building geometric bridges between these spaces, we can unlock sub-linear search speeds for inherently non-metric tasks.
The Intuition of Asymmetric Lifting
To understand why we can transform an inner product into a Euclidean distance, consider the standard algebraic expansion of squared Euclidean distance between a query vector $x$ and a database vector $y$:
$$\|x - y\|^2 = \|x\|^2 + \|y\|^2 - 2\langle x, y \rangle$$
If we want to find a vector $y$ that maximizes the inner product $\langle x, y \rangle$, this equation shows that the varying norm $\|y\|^2$ disrupts a direct relationship with Euclidean distance. If every database vector had the exact same norm ($\|y\| = \text{constant}$), maximizing the inner product would be perfectly equivalent to minimizing the Euclidean distance.
The breakthrough concept of asymmetric lifting, introduced by Anshumali Shrivastava et al. in Asymmetric LSH (ALSH) for Sublinear Time Maximum Inner Product Search (MIPS), is to artificially equalize these norms by adding extra dimensions.
If we append a new coordinate to each database vector that compensates for its missing length—specifically, a term tracking $\sqrt{M^2 - \|y\|^2}$ where $M$ is the maximum norm in the dataset—the total norm of every modified database vector becomes identical. By transforming the query vector with a matching placeholder dimension, the non-metric inner product search is perfectly reduced to a standard Euclidean distance minimization task.
Original Space (Varying Norms) Lifted Space (Equalized Norms)
y2 (long) y2'
/ /
/ /
o---x (query) o-------x' (query)
/ /
y1 (short) y1'
Inner product depends on norm. Distance directly corresponds
Pruning is impossible. to inner product.
A symmetric variant of this idea was demonstrated by Behnam Neyshabur et al. in On Symmetric and Asymmetric LSHs for Inner Product Search, where database vectors are mapped onto a higher-dimensional unit hypersphere by appending the square root of the difference between unity and their squared norm. This maps inner product search directly onto an angular similarity problem on the surface of a sphere.
This mathematical bridge has become vital for accelerating modern deep learning architectures. For example, neural language models suffer from a "softmax bottleneck," where the model must calculate dot products against every word in a massive vocabulary to predict the next token. Minjia Zhang et al. leveraged asymmetric lifting in Navigating with Graph Representations for Fast and Scalable Decoding of Neural Language Models to map word embeddings into a space where maximum inner products match minimum Euclidean distances, enabling graph-based spatial indexing.
Similarly, Yuzhen Mao et al. applied this strategy in IceFormer: Accelerated Inference with Long-Sequence Transformers on CPUs, reformulating self-attention dot products as a distance minimization task to accelerate long-sequence Transformer inference on standard CPUs without requiring model retraining. For retrieval systems that cache historical context, Ophir Frieder et al. showed in Caching Historical Embeddings in Conversational Search that transforming inner-product embeddings into Euclidean space allows search results to be modeled as geometric hyperballs, facilitating rapid distance-based cache lookups.
Dynamic Scaling and Conformal Mappings
Instead of statically modifying the underlying dataset, alternative approaches alter the search space dynamically at runtime or apply advanced conformal mappings.
Tingyang Chen et al. demonstrated in Maximum Inner Product is Query-Scaled Nearest Neighbor that MIPS can be mathematically reduced to Euclidean NNS purely by applying a scaling factor to the query vector during the search phase. This insight means that highly optimized Euclidean graph indexing techniques can be deployed for inner product problems out of the box, completely avoiding complex data transformations or index size inflation.
Taking a more geometric approach, Zhixin Zhou et al. introduced Möbius Transformation for Fast Inner Product Search on Graph. They proved a theoretical isomorphism by applying a Möbius transformation—scaling vectors by their inverse squared norm. This transformation maps the flat, linear decision hyperplanes characteristic of inner product spaces into curved, spherical boundaries in a metric space.
Inner Product Space Möbius Transformed Space
| .---.
| Linear Boundary / \ Spherical Boundary
| (Hard to prune) | o | (Defines Voronoi cells)
| \ /
v '---'
This conversion maps non-metric search boundaries into standard metric Voronoi cells, allowing graph-based spatial partitioning and pruning algorithms to operate with full mathematical validity.
Generalizing to Subspaces, Weights, and Sets
The philosophy of mapping complex proximities into point-based Euclidean spaces extends far beyond vector dot products.
Subspaces to Points
In computer vision tasks like face recognition or motion analysis, data is often represented as a linear subspace rather than a single point. Finding the nearest subspace to a query point traditionally requires expensive projection calculations.
Ronen Basri et al. solved this in Approximate Nearest Subspace Search with Applications to Pattern Recognition and A general framework for Approximate Nearest Subspace search by mapping entire subspaces into single points in a higher-dimensional Euclidean space via their projection matrices. This mapping ensures that the geometric distance between the transformed points is a linear function of the original distance between the point and the subspace, allowing sub-linear point-search structures like KD-trees or locality-sensitive hashing to index complex geometric subspaces.
Weighted Spaces and Set Queries
When similarity metrics incorporate dynamic weights or aggregate across sets of points, similar lifting principles apply:
- Generalized Weighted Spaces: For search tasks where query weights can be arbitrary or negative, Yifan Lei et al. developed a spherical asymmetric transformation in Sublinear Time Nearest Neighbor Search over Generalized Weighted Space. By using trigonometric functions to map data into a higher-dimensional spherical space, they approximated weighted squared Euclidean distances as inner products, making the task compatible with fast inner-product indices.
- Set-Query Proximity: In group recommendation systems, the goal is to find database items that minimize the average Euclidean distance to a set of query points. Haim Kaplan et al. showed in Locality Sensitive Hashing for Set-Queries, Motivated by Group Recommendations that shrinking the coordinates of data points and lifting them onto a higher-dimensional unit hypersphere converts group-average Euclidean proximity into standard angular similarity search.
- Physical Metrics: This paradigm even extends to computational physics. Bahador Bahmani demonstrated in A kd-tree-accelerated hybrid data-driven/model-based approach for poroelasticity problems with multi-fidelity multi-physics data that complex, physics-based energy metrics can be projected into a standard Euclidean space, allowing off-the-shelf spatial indexing libraries to accelerate data-driven simulations by orders of magnitude.
Direct Metric Learning: Eliminating Post-Hoc Transformations
While the previous methods focus on transforming existing non-metric spaces, a parallel paradigm shifts this transformation directly into the representation learning phase. Instead of learning a representation and fixing its metric flaws later, why not force the neural network to construct a native Euclidean space from the start?
This is the core intuition behind deep metric learning. In FaceNet: A unified embedding for face recognition and clustering, Florian Schroff et al. bypassed traditional classification layers entirely. By optimizing a "triplet loss" directly in a compact embedding space, they forced the network to map raw face images directly to vectors where the geometric Euclidean distance corresponds exactly to semantic identity similarity.
Traditional Approach:
Raw Data ---> Classification Layers ---> Feature Vector ---> Post-Hoc Transformation ---> Index
Direct Metric Learning (FaceNet):
Raw Data ---> Triplet Loss Optimization ---> Native Euclidean Space ---> Immediate Indexing
The authors demonstrated that directly optimizing the similarity metric in a unified embedding space represents identity more accurately and efficiently than using internal layers of classification networks as feature vectors.
Similarly, Edgar Simo-Serra et al. in Discriminative Learning of Deep Convolutional Feature Point Descriptors and Hongye Liu et al. in Deep Relative Distance Learning: Tell the Difference between Similar Vehicles applied this direct mapping to local image descriptors and vehicle re-identification. By training deep neural networks to output embeddings where identity similarity is measured by standard Euclidean distance, these systems ensure that the learned features can be indexed and queried using efficient spatial data structures like KD-trees out of the box, without requiring any downstream mathematical transformations or additional neural processing.
Key Foundational Work
Approximate Nearest Subspace Search with Applications to Pattern Recognition (2007) — contributed 2 concept elements to this direction.
A general framework for Approximate Nearest Subspace search (2009) — contributed 1 concept elements to this direction.