WEST: Word Encoded Sequence Transducers.

Ehsan Variani, Ananda Theertha Suresh, Mitchel Weintraub

TL;DR

WEST (Word Encoded Sequence Transducers) is a novel single-stage compression technique that drastically reduces the memory footprint of large vocabulary models by factorizing embedding and softmax layers. By representing words as sequences of sub-units (like characters or random codes) while maintaining word-level operational cycles, WEST achieves up to 1000x compression for embeddings and significant softmax reduction without sacrificing performance.

What Problem Does This Paper Address?

In modern natural language processing and speech recognition, large vocabulary models are the gold standard. However, they come with a massive "parameter tax." As shown in the figure below, the vast majority of parameters in these models are tied up in two places: the embedding layer (mapping words to vectors) and the softmax layer (predicting the next word).

Figure 1: Model parameters for language models.

This memory bloat is a major hurdle for on-device applications. Whether it's running a speech recognizer on a smartphone or training models via federated learning, memory and bandwidth are strictly limited. While sub-unit models (like character-level RNNs) are smaller, they often perform worse because they have to track much longer sequences and can mistakenly predict "words" that don't exist in the language. The authors sought a way to get the memory efficiency of sub-units with the modeling power of word-level units.

Methods

The core of WEST is a sparse-dense matrix factorization. Instead of storing a massive $V \times d$ matrix $E$ (where $V$ is vocabulary size and $d$ is dimension), the authors factorize it as: $$E = C \times E^c$$

  • $C$ (Structured Sparse Matrix): This matrix encodes how words are mapped to sub-units. Each row represents a word as a sequence of $n$ sub-units chosen from an alphabet of size $k$.
  • $E^c$ (Structured Dense Matrix): This matrix stores the actual embeddings for the sub-units.
An example of WEST factorization where a large matrix is broken down into a structured sparse matrix and a smaller dense matrix.

The authors explore two types of encoding for $C$:

  1. Language Coding: Using actual characters or word-pieces.
  2. Random Coding: Assigning each word a unique random sequence of sub-units. Surprisingly, this often works as well as or better than linguistic sub-units.

For the dense matrix $E^c$, they propose two structures: Block-diagonal (where sub-unit embeddings are concatenated) and Band structure (where they are summed). Crucially, WEST is a single-stage approach; the model is trained with this compressed structure from the start, rather than being compressed after training.

Datasets

The authors evaluated WEST on several diverse benchmarks:

  • Penn Treebank (PTB): A standard public dataset for language modeling (10k vocabulary).
  • YouTube Language Model: A large-scale internal dataset.
  • One-billion Words: A massive public benchmark for language modeling.
  • Embedded ASR Task: A state-of-the-art on-device speech recognition system using a 64k vocabulary.

Key Insights and Ideas

  • Word-Level Normalization is Key: The primary reason character-level models fail is that they normalize probabilities at the character level. WEST uses sub-units internally but normalizes at the word level. This prevents the model from wasting probability mass on non-vocabulary strings.
  • Random Codes are Powerful: One of the most counter-intuitive findings is that random codes work exceptionally well. This suggests that the subsequent non-linear layers in a neural network are capable of learning the necessary features even if the initial "alphabet" assigned to a word is arbitrary.
  • MaxEnt Interpretation: The authors show that the WEST softmax layer can be interpreted as a Maximum Entropy (MaxEnt) model over sub-unit features. This provides a strong theoretical bridge between traditional word models and sub-word models.
  • Better Generalization: Compressed WEST models often show a smaller gap between training and test perplexity compared to baseline models, suggesting that the structured bottleneck acts as a form of regularization that prevents overfitting.
Figure 2: Different recurrent neural network language models (RNN LM) of sentence ‘West world’. (a) In the word model, the input word is fed to predict the next word. (b) In character model, the input and output operate on character level. (c, d) In WEST, while the word is represented by smaller sub-units (language dependent or random), the model still operates on larger units i.e., word in this example.

Key Results

  • Massive Embedding Compression: On the PTB dataset, the embedding layer was compressed by 1000x with perplexity results very close to the uncompressed baseline.
  • State-of-the-Art for Size: By reallocating the memory saved from embeddings/softmax to the LSTM layers, the authors achieved a test perplexity of 92.36 on PTB, which they claim is the best result for a model of that size.
  • On-Device ASR Success: In a real-world ASR task, WEST compressed the embedding layer by 15.5x and the softmax by 3.1x. When combined with standard quantization, the total model size plummeted from 15 MB to just 1.35 MB without any degradation in Word Error Rate (WER). In fact, by reallocating parameters, they even improved the WER by 3% relative to the baseline.

Limitations and Future Work

While WEST is highly effective, the paper notes that the choice of sparse and dense matrix structures matters more for the softmax layer than the embedding layer. The authors also mention that while random codes are efficient, they require storing a seed or a small codebook (though this is negligible compared to full embeddings).

Future work could involve applying these structured decompositions to other types of layers or exploring more complex domain-dependent sub-units beyond simple characters and word-pieces. The authors also suggest that the MaxEnt interpretation could lead to new ways of designing feature extractors for large-scale classification.

Summary updated

Abstract

Most of the parameters in large vocabulary models are used in embedding layer to map categorical features to vectors and in softmax layer for classification weights. This is a bottle-neck in memory constraint on-device training applications like federated learning and on-device inference applications like automatic speech recognition (ASR). One way of compressing the embedding and softmax layers is to substitute larger units such as words with smaller sub-units such as characters. However, often the sub-unit models perform poorly compared to the larger unit models. We propose WEST, an algorithm for encoding categorical features and output classes with a sequence of random or domain dependent sub-units and demonstrate that this transduction can lead to significant compression without compromising performance. WEST bridges the gap between larger unit and sub-unit models and can be interpreted as a MaxEnt model over sub-unit features, which can be of independent interest.
BibTeX
@misc{variani2018west,
  author = {Ehsan Variani and Ananda Theertha Suresh and Mitchel Weintraub},
  title = {{WEST: Word Encoded Sequence Transducers.}},
  year = {2018},
  eprint = {1811.08417},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1811.08417},
}
Figure