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 Nyström 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 the downstream tasks of document classification, sentence similarity, and cross-document coreference.
Introduction
In modern NLP, many tasks rely on computing pairwise similarities between $n$ data points, such as sentences, documents, or entities. For large datasets, the full similarity matrix requires $O(n^2)$ comparisons. When these comparisons involve computationally intensive operations—such as multi-layer Transformer models (e.g., BERT cross-encoders) or Word Mover’s Distance (WMD)—this quadratic scaling becomes a prohibitive bottleneck.
While approximation techniques like the Nyström method are commonly used to mitigate this cost, they traditionally assume the similarity matrix is Positive Semidefinite (PSD). Unfortunately, many popular NLP similarity functions are "indefinite," failing to satisfy PSD requirements. Applying standard Nyström to these matrices often leads to numerical instability and high approximation error. This work introduces a sublinear-time approach to efficiently approximate these indefinite matrices.
Methodology: SMS-Nyström
The proposed Submatrix-Shifted Nyström (SMS-Nyström) algorithm "corrects" an indefinite matrix to improve its approximation stability. The core steps include:
- Eigenvalue Shifting: Instead of computing the minimum eigenvalue of the full $n \times n$ matrix (which is $O(n^2)$), the algorithm samples a small random principal submatrix.
- Correction: The minimum eigenvalue of this submatrix is used to shift the diagonal of the approximation, stabilizing the inversion process that typically fails in standard Nyström for indefinite matrices.
- Sublinear Complexity: The algorithm requires only $O(ns)$ similarity computations, where $s$ is the number of landmark points, making it significantly faster than exact computation.
The authors also evaluate SiCUR (Simple CUR decomposition), which provides stability through a rectangular "joining matrix" without an explicit eigenvalue shift.
Spectral Properties of NLP Matrices
A key insight of this research is that while many NLP similarity matrices (like those from BERT or WMD) are technically indefinite, they are often "near-PSD."
As shown in the eigenvalue spectra above, the Twitter WMD matrix is PSD, while STS-B and MRPC exhibit negative eigenvalues. The distribution of these eigenvalues, shown below, highlights the "stability gap" that SMS-Nyström addresses by shifting eigenvalues away from zero.
Experimental Results
The methods were tested across several benchmarks, including document classification (Twitter, Recipe-L), sentence similarity (STS-B, MRPC, RTE), and cross-document coreference (ECB+).
- Efficiency: On the Recipe-L dataset, the approximation maintained high accuracy while requiring only 14% of the computation needed for the full WMD kernel.
- Accuracy: SMS-Nyström and SiCUR consistently outperformed classic Nyström and other CUR variants. In document classification, SMS-Nyström results were within 2-4 points of the exact similarity matrix.
- Downstream Performance: In GLUE tasks, approximated matrices allowed models to reach performance levels nearly identical to full BERT cross-encoders at a fraction of the cost. For the ECB+ dataset, SiCUR achieved a comparable F1 score using only 50% of the data as landmarks.
Conclusion
SMS-Nyström and SiCUR provide a robust framework for approximating indefinite similarity matrices in sublinear time. While the methods show strong empirical success, future work includes developing rigorous theoretical approximation bounds for the indefinite case and scaling these techniques to datasets with millions of documents.
Summary updated