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.
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.
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