Memory-Efficient FastText: A Comprehensive Approach Using Double-Array Trie Structures and Mark-Compact Memory Management
Yimin Du · 2025
Read Memory-Efficient FastText: A Comprehensive Approach Using Double-Array Trie Structures and Mark-Compact Memory Management by Yimin Du (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-01254.txt.
Introduction
Yimin Du presented a memory-efficient version of FastText in a 2025 paper. FastText is a practical word representation tool that can build vectors for unseen words from letter chunks. Its hash-bucket design, though, mixes unrelated chunks and eats memory as buckets grow.
The new design first gives every word and chunk an exact identity, then compresses only rows that tests justify sharing. A double-array trie replaces hash buckets, and chunk rows merge by prefix and suffix structure before compact reordering. On a huge Chinese benchmark, memory fell from about one hundred forty-five to twenty-nine gigabytes. Load time also dropped sharply, with task quality nearly unchanged.
Catalog record
| CREATOR | Yimin Du |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 42 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2506-01254
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Memory-Efficient FastText: A Comprehensive Approach Using Double-Array Trie Structures and Mark-Compact Memory Management Yimin Du Abstract FastText has established itself as a fundamental algorithm for learning word representations, demonstrating exceptional capability in handling out-of-vocabulary words through character-level n-gram embeddings. However, its hash-based bucketing mechanism introduces critical limitations for large-scale industrial deployment: hash collisions cause semantic drift, and memory requirements become prohibitively expensive when dealing with real-world vocabularies containing millions of terms. This paper presents a comprehensive memory optimization framework that fundamentally reimagines FastText’s memory management through the integration of double-array trie (DA-trie) structures and mark-compact garbage collection principles. Our approach leverages the linguistic insight that n-grams sharing common prefixes or suffixes exhibit highly correlated embeddings due to co-occurrence patterns in natural language. By systematically identifying and merging semantically similar embeddings based on structural relationships, we achieve compression ratios of 4:1 to 10:1 while maintaining near-perfect embedding quality. The algorithm consists of four sophisticated phases: prefix trie construction with embedding mapping, prefix-based similarity compression, suffix-based similarity compression, and mark-compact memory reorganization. Comprehensive experiments on a 30-million Chinese vocabulary dataset demonstrate memory reduction from over 100GB to approximately 30GB with negligible performance degradation. Our industrial deployment results show significant cost reduction, faster loading times, and improved model reliability through the elimination of hash collision artifacts. 1 1 1 Code and experimental implementations are available at: https://github.com/initial-d/me_fasttext I Introduction The landscape of natural language processing has been fundamentally transformed by the advent of distributed word representations, which encode semantic and syntactic relationships in dense vector spaces. Among the various embedding techniques that have emerged, FastText [ 1 ] represents a significant advancement by incorporating subword information through character-level n-gram embeddings, enabling effective handling of out-of-vocabulary (OOV) words and morphologically rich languages. FastText’s core innovation lies in its subword-aware architecture, where each word is represented as a bag of character n-grams. This approach allows the model to generate meaningful representations for previously unseen words by combining the embeddings of their constituent n-gram sequences. The effectiveness of this method has been demonstrated across numerous languages and applications, making FastText a preferred choice for many industrial natural language processing systems. However, as we transition from research environments to large-scale deployment, FastText’s hash-based bucketing mechanism reveals several critical limitations that significantly impact its viability: I-A Hash Collision Problems The hash-based approach maps different n-grams to the same bucket through a modulo operation on hash values. This creates artificial collisions where semantically unrelated character sequences are forced to share the same embedding vector. For instance, n-grams like ”ing” and ”xyz” might be mapped to the same bucket despite having completely different linguistic properties. This collision mechanism introduces semantic drift, where the shared embedding represents an averaged approximation of all colliding n-grams rather than capturing the specific linguistic characteristics of individual sequences. The severity of this problem increases with vocabulary size and n-gram diversity. In real-world scenarios with millions of vocabulary items, the collision rate can become substantial, leading to degraded model performance and unpredictable behavior in downstream applications. I-B Memory Scalability Challenges For industrial applications dealing with large-scale vocabularies, the memory requirements of FastText become prohibitively expensive. Consider a typical Chinese corpus with 30 million vocabulary items: when extracting n-grams of lengths 2-6, the total number of unique n-grams can reach 200-300 million. With 128-dimensional embeddings, this translates to memory requirements exceeding 100 gigabytes, making deployment on standard hardware configurations economically unfeasible. The memory scalability problem is further exacerbated by the need for multiple model instances in production environments, where load balancing and fault tolerance require redundant deployments across multiple servers. I-C Training Inefficiency Hash collisions force the training algorithm to learn averaged representations across colliding n-grams, reducing the effective capacity of the model and requiring longer training times to achieve convergence. This inefficiency not only increases computational costs but also limits the model’s ability to capture fine-grained semantic distinctions. I-D Our Contributions This paper addresses these fundamental limitations through a comprehensive memory optimization framework that makes several key contributions: 1. Theoretical Foundation : We provide a rigorous theoretical analysis of why n-grams sharing common prefixes or suffixes exhibit embedding similarity, establishing the linguistic basis for our compression approach. 2. Double-Array Trie Integration : We develop a novel application of double-array trie structures for organizing and compressing n-gram embeddings, leveraging their space-efficient properties for large-scale string processing. 3. Mark-Compact Memory Management : We adapt mark-compact garbage collection principles to create an efficient memory reorganization algorithm that eliminates fragmentation while preserving embedding relationships. 4. Comprehensive Implementation : We provide a complete reimplementation of the FastText algorithm incorporating our optimization techniques, with extensive configurability for different deployment scenarios. 5. Practical Application Verification : We demonstrate the effectiveness of our approach through large-scale experiments and real-world deployment results, showing significant improvements in memory efficiency, model quality, and operational costs. The remainder of this paper is organized as follows: Section II reviews related work in embedding optimization and memory management. Section III provides detailed background on the algorithmic components used in our approach. Section IV presents our methodology and theoretical analysis. Section V describes the experimental setup and results. Section VI discusses the implications and limitations of our work, and Section VII concludes with future research directions. II Related Work II-A Word Embedding Evolution The development of word embeddings has progressed through several major paradigms. The foundational Word2Vec models [ 2 ] introduced the skip-gram and continuous bag-of-words (CBOW) architectures, demonstrating that meaningful semantic relationships could be captured through context prediction tasks. These models revealed the famous property that vector arithmetic could capture analogical relationships, such as ”king - man + woman = queen.” GloVe [ 3 ] advanced the field by combining global matrix factorization with local context windows, effectively bridging the gap between count-based and prediction-based methods. The model demonstrated that global corpus statistics could be incorporated more effectively than purely local context-based approaches. FastText represented a significant leap forward by incorporating subword information, making it particularly effective for morphologically rich languages and enabling robust handling of OOV words. However, the hash-based bucketing mechanism, while computationally efficient, introduced the collision problems that our work addresses. II-B Memory Optimization in Deep Learning Memory optimization has become increasingly critical as deep learning models grow in size and complexity. Several approaches have been developed to address memory constraints: Gradient Compression : Techniques like gradient quantization [ 5 ] and sparsification [ 6 ] reduce communication overhead in distributed training by compressing gradient updates. These methods trade off some accuracy for significant reductions in memory and bandwidth requirements. Model Quantization : Post-training quantization [ 7 ] and quantization-aware training [ 8 ] reduce model size by using lower precision representations. While effective for inference, these approaches typically focus on neural network weights rather than embedding structures. Knowledge Distillation : Teacher-student frameworks [ 9 ] can produce smaller models that approximate the behavior of larger ones. However, these approaches require training additional models and may not preserve the specific properties needed for embedding applications. II-C Subword and Character-Level Models The success of FastText has inspired numerous extensions and improvements. Byte-Pair Encoding (BPE) [ 10 ] provides an alternative approach to subword tokenization, learning optimal segmentations based on corpus statistics. SentencePiece [ 11 ] extends this