# Sublinear Time Approximation of Text Similarity Matrices

arXiv: https://arxiv.org/abs/2112.09631 · HTML: https://mlsanity.com/paper/2112.09631/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 67 references that are in the map.
- First posted on arXiv 17 Dec 2021.

## Builds on (most cited first, 25 of 25)

- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [RoBERTa: A Robustly Optimized BERT Pretraining Approach](https://mlsanity.com/paper/1907.11692/) (2019)
- [Efficient Estimation of Word Representations in Vector Space](https://mlsanity.com/paper/1301.3781/) (2013)
- [DistilBERT, a distilled version of BERT: smaller, faster, cheaper and lighter](https://mlsanity.com/paper/1910.01108/) (2019)
- [Dense Passage Retrieval for Open-Domain Question Answering](https://mlsanity.com/paper/2004.04906/) (2020)
- [ALBERT: A Lite BERT for Self-supervised Learning of Language Representations](https://mlsanity.com/paper/1909.11942/) (2019)
- [Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distances](https://mlsanity.com/paper/1306.0895/) (2013)
- [TinyBERT: Distilling BERT for Natural Language Understanding](https://mlsanity.com/paper/1909.10351/) (2019)
- [SemEval-2017 Task 1: Semantic Textual Similarity - Multilingual and Cross-lingual Focused Evaluation](https://mlsanity.com/paper/1708.00055/) (2017)
- [Are Sixteen Heads Really Better than One?](https://mlsanity.com/paper/1905.10650/) (2019)
- [Q8BERT: Quantized 8Bit BERT](https://mlsanity.com/paper/1910.06188/) (2019)
- [Sketching as a Tool for Numerical Linear Algebra](https://mlsanity.com/paper/1411.4357/) (2014)
- [Kernel methods through the roof: handling billions of points efficiently](https://mlsanity.com/paper/2006.10350/) (2020)
- [Revisiting the Nystrom Method for Improved Large-Scale Machine Learning](https://mlsanity.com/paper/1303.1849/) (2013)
- [Fastfood: Approximate Kernel Expansions in Loglinear Time](https://mlsanity.com/paper/1408.3060/) (2014)
- [Word Mover's Embedding: From Word2Vec to Document Embedding](https://mlsanity.com/paper/1811.01713/) (2018)
- [Improving CUR Matrix Decomposition and the Nystr"om Approximation via Adaptive Sampling](https://mlsanity.com/paper/1303.4207/) (2013)
- [Sublinear Time Low-Rank Approximation of Positive Semidefinite Matrices](https://mlsanity.com/paper/1704.03371/) (2017)
- [Streamlining Cross-Document Coreference Resolution: Evaluation and Modeling](https://mlsanity.com/paper/2009.11032/) (2020)
- [Sample-Optimal Low-Rank Approximation of Distance Matrices](https://mlsanity.com/paper/1906.00339/) (2019)
- [Sublinear Time Low-Rank Approximation of Distance Matrices](https://mlsanity.com/paper/1809.06986/) (2018)
- [Matrix Coherence and the Nystrom Method](https://mlsanity.com/paper/1408.2044/) (2014)
- [Scalable Global Alignment Graph Kernel Using Random Features: From Node Embedding to Graph Embedding](https://mlsanity.com/paper/1911.11119/) (2019)
- [Optimal Transport-based Alignment of Learned Character Representations for String Similarity](https://mlsanity.com/paper/1907.10165/) (2019)
- [Metric and non-metric proximity transformations at linear costs](https://mlsanity.com/paper/1411.1646/) (2014)

## Built on by (most cited first, 3 of 3)

- [Efficient Nearest Neighbor Search for Cross-Encoder Models using Matrix Factorization](https://mlsanity.com/paper/2210.12579/) (2022)
- [Adaptive Retrieval and Scalable Indexing for k-NN Search with Cross-Encoders](https://mlsanity.com/paper/2405.03651/) (2024)
- [NysAct: A Scalable Preconditioned Gradient Descent using Nystrom Approximation](https://mlsanity.com/paper/2506.08360/) (2025)

## Abstract (arXiv)

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(n2) 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"om 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.