Michael Brenndoerfer | Data & AI, Private Equity, Technology

Michael Brenndoerfer

FastText › Hashing N-grams for Memory Efficiency

Michael BrenndoerferUpdated March 10, 20265 min read

Language AI HandbookAll chapters

Part 4 of 67Word Embeddings

Chapter 26FastText › Hashing N-grams for Memory Efficiency

Reading section 9 of 15 · Hashing N-grams for Memory Efficiency · 5 minSection 9 of 15 · 5 min

Section 9 of 15 · 5 min read

FastText › Hashing N-grams for Memory EfficiencyOne section · Sections in this chapter9 / 15 ↓

Sections in this chapter15

Reading tools Definitions & inline links

Choose your expertise level to adjust how many terms are explained. Beginners see more tooltips, experts see fewer to maintain reading flow. Hover over underlined terms for instant definitions.

Article links

Make inline references clickable

Our implementation maintains one embedding vector per unique n-gram. For a small corpus that is fine, but for production-scale vocabularies this fails. A vocabulary of 100,000 words with n-grams of length 3 to 6 can generate several million unique n-grams. At 300 dimensions and 4 bytes per float, that exceeds 2 GB of memory before counting word embeddings. No single inference machine can load this into RAM efficiently.

FastText addresses this with hash bucketing. Rather than allocating a unique embedding for each n-gram, the model hashes each n-gram to one of $B$ buckets and stores an embedding per bucket. The memory usage is then exactly $B \times d \times 4$ bytes regardless of how many unique n-grams exist in the vocabulary.

N-gram Hashing

N-gram hashing maps each character n-gram to a bucket index via a deterministic hash function (typically FNV-1a, which is fast and produces well-distributed outputs). When multiple n-grams hash to the same bucket, they share a single embedding vector. This is called a hash collision. The number of collisions depends on the ratio of unique n-grams to buckets: at 2 million buckets for a typical English model, most buckets contain exactly one n-gram, keeping collision rates acceptably low. The key insight is that the hash function is fixed before training and never changes, so inference is deterministic.

The hashing trick was popularized in machine learning by the "feature hashing" or "hashing trick" paper, and FastText applies it directly to n-gram storage. The approach works because hash collisions are rare when the number of buckets is large relative to the number of distinct n-grams, and when collisions do occur, they cause mild accuracy degradation rather than catastrophic failures. Two unrelated n-grams sharing a bucket means their embeddings are conflated, which adds noise but does not prevent learning.

In[24]:

Code

class HashedFastText:
    """
    FastText with hash bucketing for memory-bounded n-gram storage.
    """

    def __init__(
        self, vocab, embedding_dim=50, min_n=3, max_n=6, num_buckets=10000
    ):
        self.embedding_dim = embedding_dim
        self.min_n = min_n
        self.max_n = max_n
        self.num_buckets = num_buckets
        # One embedding per bucket instead of one per n-gram
        self.bucket_embeddings = (
            np.random.randn(num_buckets, embedding_dim) * 0.01
        )

    def _hash(self, ngram):
        return hash(ngram) % self.num_buckets

    def _get_ngrams(self, word):
        return get_ngrams(word, self.min_n, self.max_n)

    def get_embedding(self, word):
        bucket_idx = [self._hash(ng) for ng in self._get_ngrams(word)]
        return self.bucket_embeddings[bucket_idx].sum(axis=0)


# Memory comparison
np.random.seed(42)
standard_ft_mem = FastText(vocab=vocab, embedding_dim=50, min_n=3, max_n=5)
n_unique_ngrams = len(standard_ft_mem.ng_to_idx)
standard_mem_bytes = n_unique_ngrams * 50 * 8  # float64

hashed_ft_mem = HashedFastText(
    vocab=vocab, embedding_dim=50, min_n=3, max_n=5, num_buckets=1000
)
hashed_mem_bytes = hashed_ft_mem.num_buckets * 50 * 8

Out[25]:

Console

Memory comparison: standard vs hashed n-gram storage
-------------------------------------------------------
  Vocabulary size:        50

  Standard FastText:
    Unique n-grams:       518
    Memory:               202.3 KB

  Hashed FastText (1,000 buckets):
    Buckets:              1,000
    Memory:               390.6 KB
    Savings:              -93.1%

  At production scale (100K vocabulary, 2M buckets):
    Standard (est.):      2289 MB
    Hashed (2M buckets):  2289 MB
    Savings:              0.0%

Out[26]:

Visualization

Log-log line chart comparing standard and hashed n-gram memory from 1,000 to 500,000 words, with separate shading for hashed overhead and memory savings. — Memory requirements for n-gram storage as vocabulary size grows. Standard storage grows linearly, while a two-million-bucket hash table remains fixed near 2.3 GB. Hashing has overhead below the 100,000-word crossover, then saves memory as the vocabulary grows, reaching an 80% reduction at 500,000 words.

Hashing introduces a modest accuracy trade-off: colliding n-grams share embeddings, which can conflate unrelated substrings. In practice, at 2 million buckets, collision rates for typical English are well below 5%, and empirical benchmarks show negligible impact on downstream task quality. The memory savings are dramatic and allow FastText models to be deployed on machines with limited RAM, including mobile devices and embedded systems.

One practical consideration when choosing the bucket count: the buckets are always allocated, even if many are empty. So choosing 2 million buckets commits to $2{,}000{,}000 \times 300 \times 4 \approx 2.4$ GB of RAM regardless of whether the vocabulary is large or small. For small vocabularies, a smaller bucket count is appropriate. The rule of thumb from the paper's experiments is to use at least as many buckets as there are unique n-grams in the training vocabulary, which avoids collisions almost entirely while still bounding memory at a fixed size.