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

• URL: http://arxiv.org/abs/2506.01254v1
• Date: Mon, 02 Jun 2025 02:11:22 GMT
• Title: Memory-Efficient FastText: A Comprehensive Approach Using Double-Array Trie Structures and Mark-Compact Memory Management
• Authors: Yimin Du,
• Abstract summary: FastText has established itself as a fundamental algorithm for learning word representations.<n>However, its hash-based bucketing mechanism introduces critical limitations for large-scale industrial deployment.<n>This paper presents a memory optimization framework that reimagines FastText's memory management.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• 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. Code and experimental implementations are available at: https://github.com/initial-d/me_fasttext

Related papers

• From Verbatim to Gist: Distilling Pyramidal Multimodal Memory via Semantic Information Bottleneck for Long-Horizon Video Agents [78.30630000529133]
  We propose MM-Mem, a pyramidal multimodal memory architecture grounded in Fuzzy-Trace Theory.<n> MM-Mem memory structures hierarchically into a Sensory Buffer, Episodic Stream, and Symbolic.<n>Experiments confirm the effectiveness of MM-Mem on both offline and streaming tasks.
  arXiv  Detail & Related papers  (2026-03-02T05:12:45Z)
• Cognitive Memory in Large Language Models [8.059261857307881]
  This paper examines memory mechanisms in Large Language Models (LLMs), emphasizing their importance for context-rich responses, reduced hallucinations, and improved efficiency.<n>It categorizes memory into sensory, short-term, and long-term, with sensory memory corresponding to input prompts, short-term memory processing immediate context, and long-term memory implemented via external databases or structures.
  arXiv  Detail & Related papers  (2025-04-03T09:58:19Z)
• ChunkKV: Semantic-Preserving KV Cache Compression for Efficient Long-Context LLM Inference [61.412894960600205]
  Large Language Models (LLMs) require significant GPU memory when processing long texts.<n>ChunkKV reimagines KV cache compression by treating semantic chunks as basic compression units.<n>Result: ChunkKV outperforms state-of-the-art methods by up to 8.7% in precision.
  arXiv  Detail & Related papers  (2025-02-01T03:49:47Z)
• Efficient Beam Search for Large Language Models Using Trie-Based Decoding [10.302821791274129]
  We introduce a novel parallel decoding method that addresses the memory inefficiency of batch-based beam search.<n>By sharing a single cache among all beams that share the same prefix, the proposed method not only reduces memory consumption dramatically but also enables parallel decoding across all branches.<n>This innovative use of a prefix tree offers an efficient alternative for beam search, achieving significant memory savings while preserving inference speed, making it particularly well-suited for memory-constrained environments or large-scale model deployments.
  arXiv  Detail & Related papers  (2025-01-31T16:22:36Z)
• BitStack: Any-Size Compression of Large Language Models in Variable Memory Environments [53.71158537264695]
  Large language models (LLMs) have revolutionized numerous applications, yet their deployment remains challenged by memory constraints on local devices.<n>We introduce textbfBitStack, a novel, training-free weight compression approach that enables megabyte-level trade-offs between memory usage and model performance.
  arXiv  Detail & Related papers  (2024-10-31T13:26:11Z)
• Batching BPE Tokenization Merges [55.2480439325792]
  BatchBPE is an open-source pure Python implementation of the Byte Pair algorithm. It is used to train a high quality tokenizer on a basic laptop.
  arXiv  Detail & Related papers  (2024-08-05T09:37:21Z)
• BTR: Binary Token Representations for Efficient Retrieval Augmented Language Models [77.0501668780182]
  Retrieval augmentation addresses many critical problems in large language models. Running retrieval-augmented language models (LMs) is slow and difficult to scale due to processing large amounts of retrieved text. We introduce binary token representations (BTR), which use 1-bit vectors to precompute every token in passages.
  arXiv  Detail & Related papers  (2023-10-02T16:48:47Z)
• ELITE: Encoding Visual Concepts into Textual Embeddings for Customized Text-to-Image Generation [59.44301617306483]
  We propose a learning-based encoder for fast and accurate customized text-to-image generation. Our method enables high-fidelity inversion and more robust editability with a significantly faster encoding process.
  arXiv  Detail & Related papers  (2023-02-27T14:49:53Z)
• LexLIP: Lexicon-Bottlenecked Language-Image Pre-Training for Large-Scale Image-Text Retrieval [71.01982683581572]
  The conventional dense retrieval paradigm relies on encoding images and texts into dense representations using dual-stream encoders. We propose the lexicon-weighting paradigm, where sparse representations in vocabulary space are learned for images and texts. We introduce a novel pre-training framework, that learns importance-aware lexicon representations. Our framework achieves a 5.5 221.3X faster retrieval speed and 13.2 48.8X less index storage memory.
  arXiv  Detail & Related papers  (2023-02-06T16:24:41Z)
• Multi hash embeddings in spaCy [1.6790532021482656]
  spaCy is a machine learning system that generates multi-embedding representations of words. The default embedding layer in spaCy is a hash embeddings layer. In this technical report we lay out a bit of history and introduce the embedding methods in spaCy in detail.
  arXiv  Detail & Related papers  (2022-12-19T06:03:04Z)
• Autoregressive Search Engines: Generating Substrings as Document Identifiers [53.0729058170278]
  Autoregressive language models are emerging as the de-facto standard for generating answers. Previous work has explored ways to partition the search space into hierarchical structures. In this work we propose an alternative that doesn't force any structure in the search space: using all ngrams in a passage as its possible identifiers.
  arXiv  Detail & Related papers  (2022-04-22T10:45:01Z)
• Tree-constrained Pointer Generator for End-to-end Contextual Speech Recognition [16.160767678589895]
  TCPGen is proposed that incorporates such knowledge as a list of biasing words into both attention-based encoder-decoder and transducer end-to-end ASR models. TCPGen structures the biasing words into an efficient prefix tree to serve as its symbolic input and creates a neural shortcut to facilitate recognising biasing words during decoding.
  arXiv  Detail & Related papers  (2021-09-01T21:41:59Z)
• IMRAM: Iterative Matching with Recurrent Attention Memory for Cross-Modal Image-Text Retrieval [105.77562776008459]
  Existing methods leverage the attention mechanism to explore such correspondence in a fine-grained manner. It may be difficult to optimally capture such sophisticated correspondences in existing methods. We propose an Iterative Matching with Recurrent Attention Memory (IMRAM) method, in which correspondences are captured with multiple steps of alignments.
  arXiv  Detail & Related papers  (2020-03-08T12:24:41Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.