Imagine you have a dataset of $N$ items. To understand how they relate to one another—whether you are clustering images, aligning vocabularies, or sorting sequences—the most intuitive first step is to compare every item to every other item. This creates an $N \times N$ matrix: an affinity matrix, a distance matrix, or a joint probability distribution.
This approach works beautifully for small datasets. However, memory consumption scales quadratically ($O(N^2)$). If $N = 10,000$, storing the matrix takes a manageable few hundred megabytes. If $N$ scales to $1,000,000$, a dense matrix requires several terabytes of memory, instantly causing out-of-memory errors on standard hardware. This quadratic memory bottleneck is a pervasive challenge across machine learning, forcing a paradigm shift away from explicit pairwise storage toward implicit, compressed, and localized representations.
The Anatomy of Pairwise Scaling
Why do so many distinct algorithms hit the exact same wall? The bottleneck arises whenever an algorithm requires explicit, global relational knowledge.
In unsupervised learning, methods like spectral clustering or subspace clustering rely on an affinity matrix to capture data manifolds. For instance, Pan Ji et al. demonstrate in Deep Subspace Clustering Networks that learning pairwise affinities simultaneously with deep features yields high accuracy, but the $O(N^2)$ weight matrix prevents scaling to massive datasets. Similarly, in 3D computer vision, the author of SGPN: Similarity Group Proposal Network for 3D Point Cloud Instance Segmentation shows that grouping point clouds via an $N \times N$ similarity matrix restricts the resolution of point clouds that can be processed in a single pass.
The problem extends to structural alignment and optimal transport. When aligning word embeddings across languages, David Alvarez-Melis et al. note in Gromov-Wasserstein Alignment of Word Embedding Spaces that optimizing relational distances across large vocabularies is strictly bounded by the memory required for dense similarity matrices. Even differentiable operations like sorting suffer from this; Julian Martin Eisenschlos et al. point out in SoftSort: A Continuous Relaxation for the argsort Operator that constructing continuous permutation matrices introduces a severe quadratic space bottleneck for long sequences.
To scale these algorithms, researchers have developed three primary strategies to bypass the explicit construction of $N \times N$ matrices.
Strategy 1: Anchor-Based and Low-Rank Approximations
How do we bypass the $O(N^2)$ matrix without losing global context? The core intuition is to introduce an intermediary: instead of comparing every point to every other point, we compare every point to a much smaller set of $M$ "anchors" or "sketches" ($M \ll N$).
Mathematically, this decomposes a massive $N \times N$ matrix into the product of smaller matrices (e.g., $N \times M$ and $M \times N$). The memory footprint drops from $O(N^2)$ to $O(NM)$, which scales linearly with the dataset size. This works because real-world data often lies on a low-dimensional manifold, meaning the massive pairwise matrix contains highly redundant information that can be compressed into a lower-dimensional subspace without significant loss of fidelity.
Traditional Pairwise Matrix:
[ N x N ] --> Requires O(N^2) Memory
Anchor-Based Decomposition:
[ N x M ] x [ M x N ] --> Requires O(NM) Memory (where M << N)
For example, in multi-view clustering, Qiyuan Ou et al. utilize this mechanism in Anchor-based Multi-view Subspace Clustering with Hierarchical Feature Descent to slash spatial complexity and prevent out-of-memory failures. In optimal transport, Meyer Scetbon et al. apply a similar insight in Linear-Time Gromov Wasserstein Distances using Low Rank Couplings and Costs, enforcing low-rank constraints on the transport coupling matrix to prevent memory exhaustion. Furthermore, Rong Yin et al. prove in Randomized Sketches for Clustering: Fast and Optimal Kernel $k$-Means that a sketch dimension of only $\Omega(\sqrt{n})$ is sufficient to maintain statistical optimality while drastically reducing the memory overhead of storing pairwise relationships.
Strategy 2: Sparsification and Local Neighborhoods
Another core intuition is that global connectivity is often redundant. In many applications, a data point is strongly related only to its immediate neighbors; its affinity with distant points approaches zero.
By enforcing sparsity—such as keeping only the top-$k$ nearest neighbors—the dense $N \times N$ matrix transforms into a sparse graph with only $N \times k$ non-zero entries. This shifts the memory requirement from quadratic to linear relative to $N$. Setting distant affinities to zero saves massive memory while preserving the local geometric structure of the data.
The authors of Leveraging Sparsity for Efficient Submodular Data Summarization demonstrate that sparsifying similarity matrices yields up to 100x speedups with negligible loss in solution quality, proving that dense global matrices are often unnecessary. This principle is also vital in domain adaptation, where Astuti Sharma et al. leverage local $k$-NN structures in Instance Level Affinity-Based Transfer for Unsupervised Domain Adaptation to manage batch-wise affinity overhead without sacrificing fine-grained category alignment.
Strategy 3: Functional and Implicit Representations
The most radical way to solve the quadratic memory bottleneck is to avoid constructing a relational matrix altogether. Instead of storing explicit pairwise scores in a discrete lookup table, we can train a parametric model (like a neural network) to implicitly learn the underlying structure or mapping.
Instead of an $N \times N$ table lookup, the model uses a fixed number of parameters to map an input directly to its destination space. The memory cost is shifted from the size of the dataset to the size of the model's weights, making memory consumption independent of $N$ during inference.
Jason Weston et al. pioneered this in Large-Scale Clustering through Functional Embedding, replacing traditional spectral affinity matrices with a single-stage neural network optimized via stochastic gradient descent. This allows graph-based clustering to scale to millions of points within the physical RAM of a single machine.
In the context of supervised hashing, Long-Kai Huang et al. achieve a similar reduction in Class-Wise Supervised Hashing with Label Embedding and Active Bits. Instead of relying on an instance-pairwise similarity matrix that scales quadratically with the number of training samples, they map instances to compact class-pairwise code prototypes, bypassing the $O(N^2)$ training bottleneck entirely.