Sublinear Time Approximation of Text Similarity Matrices

Archan Ray, Nicholas Monath, Andrew McCallum, Cameron Musco

Introduction

In modern Natural Language Processing (NLP), computing similarity between thousands of documents or sentences is a core operation for tasks like clustering, retrieval, and coreference resolution. However, these comparisons typically require $O(n^2)$ work, which becomes computationally prohibitive as datasets grow. For example, comparing 10,000 sentences using a high-accuracy BERT cross-encoder requires 100 million model inferences.

This paper introduces Submatrix-Shifted Nyström (SMS-Nyström), a novel algorithm that approximates these massive similarity matrices in sublinear time relative to the matrix size. By focusing on a small subset of "landmark" data points, SMS-Nyström enables the use of expensive similarity measures on large-scale datasets where full computation was previously impossible.

The Challenge of Indefinite Matrices

A common technique for matrix approximation is the Nyström method, which works efficiently for "Positive Semidefinite" (PSD) matrices. However, most NLP similarity measures—such as Word Mover's Distance (WMD) or BERT-based scores—are indefinite (non-PSD).

When standard Nyström is applied to these indefinite matrices, the mathematical operations become unstable. Small negative eigenvalues are amplified during matrix inversion, leading to approximation errors so massive they are often "off the charts." Researchers were previously forced to choose between fast but inaccurate approximations or the computationally expensive full $n^2$ matrix.

SMS-Nyström: Stabilizing the Approximation

The authors' key insight is that while NLP similarity matrices are not perfectly PSD, they are "near-PSD." They typically possess very few negative eigenvalues, and those they do have are small in magnitude.

Eigenvalue distribution across different NLP datasets (MRPC, STS-B, Twitter), illustrating the "near-PSD" structure where most eigenvalues are positive and negative ones remain small.

To stabilize the approximation, SMS-Nyström applies an eigenvalue shift. Rather than computing the full matrix to find the minimum eigenvalue (which would defeat the purpose of a sublinear algorithm), the method samples a small $s \times s$ principal submatrix. It finds the minimum eigenvalue of this submatrix and uses a scaled version of it to "correct" the larger matrix into a stable state. This process runs in $O(ns)$ time, making it truly sublinear.

Key Insights and Results

The effectiveness of SMS-Nyström stems from the fact that a small sub-sample can capture the global structure of the similarity space.

Histograms showing the distribution of eigenvalues for Twitter, STS-B, and MRPC datasets. The concentration of values near zero and in the positive range confirms the near-PSD nature of these NLP tasks.

The authors evaluated their approach across document classification, sentence similarity, and coreference resolution tasks:

  • Efficiency: On the Recipe-L dataset, the proposed methods achieved high accuracy using only 14% of the computations required for the full WMD kernel.
  • Accuracy: On GLUE benchmarks (STS-B, MRPC), SMS-Nyström achieved performance within 1-2 points of exact BERT cross-encoder scores.
  • Stability: SMS-Nyström proved significantly more stable than the classic Nyström method, matching the performance of "optimal" SVD-based approximations at a fraction of the computational cost.

Conclusion

SMS-Nyström offers a practical, "plug-and-play" solution for scaling computationally expensive NLP pipelines. By leveraging the near-PSD structure inherent in text similarity, it allows researchers to apply state-of-the-art models to million-scale datasets. Future work will explore theoretical bounds for indefinite approximations and further scaling to even larger corpora.

Summary updated

Abstract

We study algorithms for approximating pairwise similarity matrices that arise in natural language processing. Generally, computing a similarity matrix for n data points requires Omega(n^2) similarity computations. This quadratic scaling is a significant bottleneck, especially when similarities are computed via expensive functions, e.g., via transformer models. Approximation methods reduce this quadratic complexity, often by using a small subset of exactly computed similarities to approximate the remainder of the complete pairwise similarity matrix. Significant work focuses on the efficient approximation of positive semidefinite (PSD) similarity matrices, which arise e.g., in kernel methods. However, much less is understood about indefinite (non-PSD) similarity matrices, which often arise in NLP. Motivated by the observation that many of these matrices are still somewhat close to PSD, we introduce a generalization of the popular Nystrom method to the indefinite setting. Our algorithm can be applied to any similarity matrix and runs in sublinear time in the size of the matrix, producing a rank-s approximation with just O(ns) similarity computations. We show that our method, along with a simple variant of CUR decomposition, performs very well in approximating a variety of similarity matrices arising in NLP tasks. We demonstrate high accuracy of the approximated similarity matrices in tasks of document classification, sentence similarity, and cross-document coreference.
BibTeX
@inproceedings{ray2022sublinear,
  author = {Archan Ray and Nicholas Monath and Andrew McCallum and Cameron Musco},
  title = {{Sublinear Time Approximation of Text Similarity Matrices}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2022},
  doi = {10.1609/aaai.v36i7.20779},
}
Figure