In large-scale machine learning, we often encounter features with massive vocabularies. Whether it is millions of user IDs in a recommendation system, billions of n-grams in natural language processing, or the vast space of possible chemical substructures in drug discovery, the "curse of cardinality" creates a memory bottleneck.
The traditional solution is the hashing trick, popularized by Kilian Q Weinberger and colleagues in Feature hashing for large scale multitask learning. By using a hash function to map a high-dimensional feature space into a fixed-size vector, we can cap memory usage regardless of vocabulary growth. However, this convenience comes with a fundamental flaw: collisions. When two unrelated features map to the same index, they are forced to share parameters, introducing stochastic noise that degrades model accuracy.
Recent research has moved beyond "blind" random hashing toward structured compression—techniques that resolve or avoid collisions by exploiting the underlying geometry and semantics of the data.
The Collision Floor and Information Loss
The primary limitation of random feature hashing is the "performance tipping point." As Cornelia Caragea, Adrian Silvescu, and Prasenjit Mitra observe in Combining Hashing and Abstraction in Sparse High Dimensional Feature Spaces, accuracy remains stable until the hash space becomes small enough that high-frequency features begin to collide. At this threshold, the noise introduced by random collisions outweighs the benefits of dimensionality reduction, causing a sharp decline in predictive signal.
In specialized domains like cheminformatics, these collisions are even more destructive. Markus Dablander and colleagues argue in Sort & Slice that mapping chemical substructures to bit vectors via hashing obscures the relationship between structure and property. They suggest that simply selecting the most frequent features ("Sort & Slice") is often superior to hashing because it eliminates the noise of bit collisions entirely.
Compositional Embeddings: Resolving Identity
If the problem is that two items share the same "address," one solution is to give them multiple addresses. Compositional embeddings use multiple hash functions or partitions to create a unique signature for each entity.
Hao-Jun Michael Shi and researchers at Facebook introduced Compositional Embeddings Using Complementary Partitions. Instead of one giant table, they split an index into components (like a quotient and a remainder) and look up vectors in two smaller tables. By combining these vectors, the model can represent millions of items with a fraction of the parameters. Because it is statistically unlikely for two different IDs to have the same quotient and the same remainder, the "identity" of the item is preserved even under heavy compression.
Similarly, Dan Svenstrup and Ole Winther proposed Hash Embeddings, which represent each word as a weighted combination of shared vectors. By using independent hash functions to select both the vectors and their importance weights, the model can "untangle" collisions that would otherwise render tokens indistinguishable.
Semantic Awareness: Clustering the Sketch
Random hashing is "data-blind"—it treats every feature as an independent, opaque string. Structured compression attempts to make hashing "data-aware" by grouping semantically similar features before they are compressed.
Henry Ling-Hei Tsang and Thomas Dybdahl Ahle developed Clustered Compositional Embeddings (CCE), detailed in Clustering the Sketch: Dynamic Compression for Embedding Tables. CCE interleaves training with periodic clustering steps. By forcing semantically related items to share parameters intentionally, the model uses collisions as a form of regularization rather than a source of noise. This approach can reduce parameters by up to 11,000x while maintaining or even improving accuracy.
In the realm of computer vision, Bin Zhao and Eric P. Xing proposed HESHING in Hierarchical Feature Hashing for Fast Dimensionality Reduction. By hashing features along the path of a semantic category tree, they ensure that features from similar categories are more likely to share space in a structured way, preserving the global relationship between classes.
Dynamic and Neural Collision Resolution
Beyond static mapping, some researchers look to dynamic data structures or neural capacity to handle overlaps.
- Dynamic Re-assignment: Beng Chin Ooi and colleagues introduced Cuckoo Feature Hashing, which allows features to "choose" between two possible hash locations during training. If one bucket is already occupied by a highly predictive feature, the new feature can move to an alternative bucket, minimizing the interference that degrades performance.
- Neural Decoding: The paper Short and Deep: Sketching and Neural Networks suggests that while linear models cannot "untangle" hash collisions, even a simple single-layer neural network has the capacity to decode compressed information. This allows for compression far beyond traditional theoretical limits by shifting the burden of collision resolution from the hashing function to the model's hidden layers.
- Contextual Unhashing: In Superbloom: Bloom filter meets Transformer, Walid Krichene and Steffen Rendle use a Transformer to "unhash" collisions. When multiple entities map to the same Bloom filter signature, the Transformer uses the surrounding context to determine which entity was likely intended, effectively using sequence information to resolve representation ambiguity.
Conclusion
The shift from random hashing to structured compression represents a move toward more efficient, "aware" representations. By replacing blind randomization with techniques like complementary partitioning, semantic clustering, and neural decoding, researchers are enabling models to fit into the tiny memory footprints of on-device hardware—as seen in the 7KB models of Sujith Ravi SGNN++—without sacrificing the discriminative power of high-dimensional data.