# Memory-Efficient FastText: A Comprehensive Approach Using Double-Array Trie Structures and Mark-Compact Memory Management

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 25 of its 38 references that are in the map.
- First posted on arXiv 2 Jun 2025.

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

- [Distilling the Knowledge in a Neural Network](https://mlsanity.com/paper/1503.02531/) (2015)
- [Retrieval-Augmented Generation for Knowledge-Intensive NLP Tasks](https://mlsanity.com/paper/2005.11401/) (2020)
- [Sentence-BERT: Sentence Embeddings using Siamese BERT-Networks](https://mlsanity.com/paper/1908.10084/) (2019)
- [Efficient Estimation of Word Representations in Vector Space](https://mlsanity.com/paper/1301.3781/) (2013)
- [Dense Passage Retrieval for Open-Domain Question Answering](https://mlsanity.com/paper/2004.04906/) (2020)
- [Distributed Representations of Words and Phrases and their Compositionality](https://mlsanity.com/paper/1310.4546/) (2013)
- [Neural Machine Translation of Rare Words with Subword Units](https://mlsanity.com/paper/1508.07909/) (2015)
- [ALBERT: A Lite BERT for Self-supervised Learning of Language Representations](https://mlsanity.com/paper/1909.11942/) (2019)
- [Learning both Weights and Connections for Efficient Neural Networks](https://mlsanity.com/paper/1506.02626/) (2015)
- [SentencePiece: A simple and language independent subword tokenizer and detokenizer for Neural Text Processing](https://mlsanity.com/paper/1808.06226/) (2018)
- [Quantization and Training of Neural Networks for Efficient Integer-Arithmetic-Only Inference](https://mlsanity.com/paper/1712.05877/) (2017)
- [Enriching Word Vectors with Subword Information](https://mlsanity.com/paper/1607.04606/) (2016)
- [Google's Neural Machine Translation System: Bridging the Gap between Human and Machine Translation](https://mlsanity.com/paper/1609.08144/) (2016)
- [Text Embeddings by Weakly-Supervised Contrastive Pre-training](https://mlsanity.com/paper/2212.03533/) (2022)
- [BEIR: A Heterogenous Benchmark for Zero-shot Evaluation of Information Retrieval Models](https://mlsanity.com/paper/2104.08663/) (2021)
- [Bag of Tricks for Efficient Text Classification](https://mlsanity.com/paper/1607.01759/) (2016)
- [Quantizing deep convolutional networks for efficient inference: A whitepaper](https://mlsanity.com/paper/1806.08342/) (2018)
- [Deep Gradient Compression: Reducing the Communication Bandwidth for Distributed Training](https://mlsanity.com/paper/1712.01887/) (2017)
- [NV-Embed: Improved Techniques for Training LLMs as Generalist Embedding Models](https://mlsanity.com/paper/2405.17428/) (2024)
- [SPLADE: Sparse Lexical and Expansion Model for First Stage Ranking](https://mlsanity.com/paper/2107.05720/) (2021)
- [TernGrad: Ternary Gradients to Reduce Communication in Distributed Deep Learning](https://mlsanity.com/paper/1705.07878/) (2017)
- [Adaptive Input Representations for Neural Language Modeling](https://mlsanity.com/paper/1809.10853/) (2018)
- [jina-embeddings-v3: Multilingual Embeddings With Task LoRA](https://mlsanity.com/paper/2409.10173/) (2024)
- [MMTEB: Massive Multilingual Text Embedding Benchmark](https://mlsanity.com/paper/2502.13595/) (2025)
- [Compressing Word Embeddings via Deep Compositional Code Learning](https://mlsanity.com/paper/1711.01068/) (2017)

## Abstract (arXiv)

FastText remains a practical choice for industrial word representation because it can synthesize vectors for out-of-vocabulary words from character n-grams. Its original hash-bucket implementation, however, couples two engineering compromises that become painful at large scale: unrelated n-grams collide into the same row, while increasing the bucket count quickly turns the input matrix into the dominant memory cost. This paper presents a memory-efficient FastText variant based on an exact-then-compress principle: first give every observed word and n-gram an explicit identity, then compress only those rows whose learned vectors and lexical structure justify sharing. Concretely, we replace hash buckets with collision-free double-array trie indexes and compress the resulting n-gram matrix through structurally constrained prefix and suffix merging followed by mark-compact row reorganization. Unlike arbitrary hashing, the proposed method shares rows only after a high cosine-similarity test, preserving interpretable n-gram identities while reducing the number of live rows. We describe the full training and serving pipeline, including UTF-8 aware n-gram enumeration, double-array trie lookup, memory-mapped model loading, and vector reconstruction for words and sentences. On a large Chinese vocabulary benchmark with 30.1M words and 287.4M extracted n-grams, the compressed model reduces memory from 145.2GB to 28.9GB, improves load time from 12.3 minutes to 3.2 minutes, and preserves downstream quality within 0.3 points of a hash-free model. We position the result as a compact lexical memory layer for LLM-era retrieval systems and release the implementation as an extended FastText prototype.