# When do cheap embeddings beat protein language models? A theoretically-grounded hashing sketch for biological sequence classification

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 11 of its 32 references that are in the map.
- First posted on arXiv 10 Dec 2025.

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

- [Unsupervised Deep Embedding for Clustering Analysis](https://mlsanity.com/paper/1511.06335/) (2015)
- [Why do tree-based models still outperform deep learning on tabular data?](https://mlsanity.com/paper/2207.08815/) (2022)
- [Dropout Training as Adaptive Regularization](https://mlsanity.com/paper/1307.1493/) (2013)
- [Uncertainty in Gradient Boosting via Ensembles](https://mlsanity.com/paper/2006.10562/) (2020)
- [Spike2Vec: An Efficient and Scalable Embedding Approach for COVID-19 Spike Sequences](https://mlsanity.com/paper/2109.05019/) (2021)
- [A k-mer Based Approach for SARS-CoV-2 Variant Identification](https://mlsanity.com/paper/2108.03465/) (2021)
- [PWM2Vec: An Efficient Embedding Approach for Viral Host Specification from Coronavirus Spike Sequences](https://mlsanity.com/paper/2201.02273/) (2022)
- [Efficient Approximate Kernel Based Spike Sequence Classification](https://mlsanity.com/paper/2209.04952/) (2022)
- [Neural Distance Embeddings for Biological Sequences](https://mlsanity.com/paper/2109.09740/) (2021)
- [Robust Representation and Efficient Feature Selection Allows for Effective Clustering of SARS-CoV-2 Variants](https://mlsanity.com/paper/2110.09622/) (2021)
- [GaKCo: a Fast GApped k-mer string Kernel using COunting](https://mlsanity.com/paper/1704.07468/) (2017)

## Abstract (arXiv)

Motivation: Pre-trained protein language models (PLMs) such as ESM-2 have become the default representation for biological sequence tasks, but they are computationally heavy and require GPUs both for embedding and for fine-tuning. Whether they are actually necessary for sequence classification, as opposed to structure prediction, is rarely tested against strong, principled, lightweight alternatives. This question has direct practical stakes for large-scale genomic surveillance, where embedding millions of sequences on commodity hardware is a recurring bottleneck. Results: We introduce Murmur2Vec, an alignment-free, training-free embedding that aggregates k-mer counts into a small hash table via the deterministic MurmurHash function, and we cast it as a randomized sketch of the classical k-mer spectrum kernel. We provide a complete theoretical treatment: closed-form bias/variance of the inner product, an unbiased signed variant with a Johnson--Lindenstrauss-type concentration bound, an excess-risk bound for downstream linear classifiers that makes the bias--variance trade-off in the hash-table size explicit, and an implicit-regularization mechanism by which collisions damage frequent non-discriminative k-mers more than rare lineage-defining ones. Across four classification tasks, SARS-CoV-2 spike lineage (22 classes), HIV-1 Env subtype (8 classes), and two protein-family benchmarks (8 and 6 classes), Murmur2Vec matches a LoRA-fine-tuned 650M-parameter ESM-2 model on the two tasks for which LoRA fine-tuning was run to convergence (SARS-CoV-2 and HIV-1) and ties frozen ESM-2 on the two protein-family tasks, and it outperforms the fine-tuned model on the hardest task (SARS-CoV-2 lineage: 0.854 vs. 0.807 accuracy; macro-F1 0.684 vs. 0.401).