The Quadratic Bottleneck of Pairwise Similarity Learning

634 concepts553 papers3 proposals

Traditional machine learning often evaluates data points individually—assigning a single label to an image or calculating a point-wise loss. However, many complex tasks require understanding the underlying geometry and structural relationships of a dataset. To capture this, researchers frequently turn to pairwise similarity learning.

Instead of looking at instances in isolation, pairwise learning models the relationships between pairs of data points. While this approach provides a rich supervisory signal, it introduces a fundamental computational challenge: quadratic complexity. As batch sizes or dataset scales grow, the resources required to compute these relationships explode, creating a critical bottleneck across deep metric learning, knowledge distillation, and contrastive frameworks.

The Power of Relational Representation

To understand why researchers accept the burden of pairwise computations, we must look at the rich structural information they unlock.

In deep metric learning, the goal is to map data into an embedding space where similar items cluster together and dissimilar items are pushed apart. As shown by Hyun Oh Song et al. in Deep Metric Learning via Lifted Structured Feature Embedding, treating an entire mini-batch as a dense matrix of pairwise distances allows models to look beyond isolated pairs or triplets. This global view enables the algorithm to effectively mine "hard negatives," significantly improving image retrieval and clustering performance.

Point-wise Learning:   [ Item A ] ---> Loss
                        [ Item B ] ---> Loss

Pairwise Learning:     [ Item A ] <---> [ Item B ]
                           ^               ^
                           |               |
                           v               v
                       [ Item C ] <---> [ Item D ]

This relational perspective is equally powerful in knowledge distillation. Rather than forcing a student network to rigidly mimic a teacher's exact point-wise outputs, relational distillation teaches the student to preserve the relative topology of the data.

The authors of Knowledge Distillation via Instance Relationship Graph (IRG) (Yufan Liu 0001 et al.) and Similarity-Preserving Knowledge Distillation (Frederick Tung et al.) demonstrated that if a teacher model perceives two distinct images as structurally similar, that similarity matrix serves as a highly robust "hint" for the student. Similarly, in generative modeling, Shaohui Liu et al. utilized pairwise distance matrices in Normalized Diversification to force generators to preserve latent-space relationships, effectively preventing mode collapse.

Why It Fails to Scale: The $O(N^2)$ Explosion

Despite its representational power, pairwise learning hits a mathematical wall when scaling up. When an algorithm computes all-to-all similarities within a batch of size $N$, it must populate an $N \times N$ matrix. If the batch size doubles, the number of pairwise evaluations quadruples.

In modern deep learning, where massive batch sizes are critical for stabilizing contrastive learning and training foundation models, this $O(N^2)$ scaling behavior creates severe bottlenecks in two primary dimensions:

Computational Overhead

Evaluating dense similarity graphs or kernel losses requires extensive pairwise dot products or distance metrics. As noted by Yihao Feng et al. in A Kernel Loss for Solving the Bellman Equation, calculating gradients for kernel-based losses requires exhaustive pairwise evaluations across all samples in a batch. This makes the approach significantly more resource-intensive than standard temporal difference methods that scale linearly with batch size.

Memory Constraints

The problem intensifies when tracking gradients through the pairwise matrix or applying optimization constraints. For example, Weiwei Kong et al. observed in Differentially private optimization for non-decomposable objective functions that materializing gradients for every pair of inputs under differential privacy constraints creates an unsustainable memory bottleneck, strictly limiting the maximum feasible batch size during distributed training.

Breaking the Bottleneck

To harness the benefits of relational learning without succumbing to quadratic scaling, researchers have developed three core strategies to bypass or optimize the all-pairs computation.

1. Transitioning to Point-Wise Proxies

One direct solution is to reformulate the objective to avoid explicit pairwise matrices entirely. In large-scale image retrieval, Kevin Lin et al. demonstrated in Deep learning of binary hash codes for fast image retrieval that shifting from a pairwise similarity matrix to a scalable "point-wise" approach allows supervised hashing models to scale smoothly to millions of images.

Similarly, for unsupervised person re-identification, Hong-Xing Yu introduced a framework in Unsupervised Person Re-Identification by Soft Multilabel Learning that compares unlabeled target images against a fixed set of reference agents rather than performing exhaustive all-to-all comparisons within massive mini-batches.

2. Intelligent Pair Weighting and Sampling

Instead of computing a dense, unweighted matrix of every possible pair, algorithms can dynamically select or weight only the most informative pairs. Xun Wang et al. established in Multi-Similarity Loss With General Pair Weighting for Deep Metric Learning that traditional pair-mining strategies can be unified under a general weighting framework. By focusing computational effort on self-similarity and relative similarities, models can achieve state-of-the-art metric embeddings without wasting resources on redundant, uninformative pairs.

3. Online Learning and Pruning

When dealing with full dataset scales rather than mini-batches, the quadratic problem scales with the total number of training samples, leading to an impossible $O(D^2)$ cost. In Latent Coincidence Analysis: A Hidden Variable Model for Distance Metric Learning, Matthew F. Der et al. observed that while geometric pruning techniques can mitigate the initial pair explosion, scaling to massive datasets ultimately requires transitioning to advanced online learning strategies that process pairs dynamically rather than statically.

History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_quadratic_pairwise_complexity_708d6a2a,
  title = {quadratic pairwise complexity},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/quadratic-pairwise-complexity/rdr_708d6a2aa45f451ca363c1997bf0e6a8},
  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_quadratic_pairwise_complexity_708d6a2a_v1,
  title = {quadratic pairwise complexity},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/quadratic-pairwise-complexity/rdr_708d6a2aa45f451ca363c1997bf0e6a8/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake