In modern natural language processing and recommendation systems, the embedding layer is often the largest component of the model. A standard lookup table assigns a unique, high-dimensional vector to every word or item in a vocabulary. As vocabularies grow into the millions, these tables consume gigabytes of memory, making them impossible to deploy on mobile devices and prone to overfitting on rare terms.
Compositional embeddings solve this "embedding bottleneck" by replacing the massive one-to-one lookup table with a many-to-many mapping. Instead of storing a unique vector for every entry, the model stores a small pool of shared components and learns a "recipe" to compose each entry's representation on the fly.
The Combinatorial Power of Codebooks
The most common approach to composition is the use of discrete codebooks. Rather than one large table, the model maintains several small tables (codebooks) containing basis vectors. Each vocabulary item is assigned a short list of indices—a "code"—that selects one vector from each codebook. These selected vectors are then aggregated, usually by summation, to form the final embedding.
This approach, explored by Chen et al. in their work on KD encoding, leverages combinatorial explosion. If you have 2 codebooks with 100 vectors each, you only store 200 vectors, but you can represent $100 \times 100 = 10,000$ unique items. Shu et al. demonstrated in Deep Compositional Code Learning that these codes can be learned end-to-end using the Gumbel-softmax trick, allowing the model to discover semantic redundancies automatically.
Recent applications have pushed this further for specialized tasks. Prakash et al. applied compositional code embeddings to Transformer-based semantic parsers, reducing embedding size by 95% with minimal accuracy loss. In recommendation systems, Xia et al. used similar techniques to enable communication-efficient updates for on-device models, while Lu et al. proposed weighted combinations of codewords to increase representational flexibility.
Hashing and Stochastic Sharing
Another way to define the "recipe" for an embedding is through hashing. Instead of learning which components a word should use, Svenstrup et al. proposed Hash Embeddings, where multiple hash functions deterministically map a token to a subset of vectors in a shared pool. To differentiate words that might collide under a hash function, the model learns "importance weights" for each shared component.
A simpler version of this is found in the Slim Embedding (SE) layers described by Li et al., which randomly share sub-vectors across different words. Because the shared components are concatenated rather than summed, the model can achieve extreme compression ratios by simply reducing the size of the shared pool.
Generating Representations from Form
While codebooks and hashing use arbitrary indices, character-aware models use the internal structure of a word as the composition recipe. This provides a natural solution to the "out-of-vocabulary" problem: if a model knows how to embed "play" and "-ing," it can synthesize a representation for "playing" even if it has never seen the word before.
Wang et al. pioneered this with the C2W (Character-to-Word) model, which uses a bidirectional LSTM to "read" characters and generate a word vector. This theme of dynamic generation is echoed by Malykh, who used a Begin-Middle-End (BME) character representation to make word vectors robust to typos, and Wehrmann et al., who utilized character-level embeddings to create language-agnostic visual-semantic retrievers.
By shifting from static lookups to dynamic construction, the authors of these works demonstrate that neural models can maintain high performance with a fraction of the parameters, making them more robust, generalizable, and efficient.
Key Foundational Work
Hash Embeddings for Efficient Word Representations (2017) — contributed 1 concept elements to this direction.
Finding Function in Form: Compositional Character Models for Open Vocabulary Word Representation (2015) — contributed 1 concept elements to this direction.
Generalizable Architecture for Robust Word Vectors Tested by Noisy Paraphrases (2017) — contributed 1 concept elements to this direction.