Can elastic addressing instead of hashing solve embedding table scaling?
This explores whether collision-free, dynamically-sized embedding tables (where each ID gets its own slot that the table grows to accommodate) can replace fixed-size hashing as the way recommendation systems handle billions of user and item IDs.
This explores whether collision-free, elastically-grown embedding tables can replace fixed-size hashing for the enormous lookup tables that recommendation models rely on. The corpus comes down firmly on why hashing is the wrong default — and the answer turns on a fact about the real world rather than about clever data structures. Recommendation IDs don't arrive uniformly; they follow a power-law, where a small set of users and items account for most of the traffic Do hash collisions really harm popular recommendation items?. When you cram those IDs into a fixed-size hashed table, collisions don't spread out evenly — they pile up on exactly the high-frequency entities the model most needs to represent precisely Why do hash collisions hurt recommendation models so much?. So hashing quietly degrades quality where it hurts most, and gets worse over time as new IDs keep arriving into a table that can't grow.
That framing is what makes "elastic addressing" attractive: instead of mapping many IDs into a fixed slot count and eating the collisions, you give each ID its own entry and let the table expand as the ID space grows. This is the design Monolith popularized — collision-free embeddings backed by a hash table that grows on demand. The corpus material here is the empirical case *for* abandoning fixed-size hashing, which is the harder half of the argument; the elastic structure is the natural mechanism that follows once you accept that collisions are concentrated rather than diffuse.
Worth knowing, though, that elastic addressing solves the *collision* problem without touching a deeper *capacity* problem. There's a separate, more fundamental limit: for any fixed embedding dimension, communication-complexity theory bounds how many distinct combinations of items an embedding space can even represent — a ceiling that holds even when embeddings are optimized directly on the test data Do embedding dimensions fundamentally limit retrievable document combinations?. Giving every ID a clean, uncollided slot doesn't raise that ceiling; it just stops you from wasting capacity on avoidable collisions. Scaling the *number* of rows is not the same problem as scaling the *expressiveness* of each row.
There's also a sideways alternative the corpus surfaces that's worth your curiosity: rather than scaling the table at all, you can shrink what needs an entry. VQ-Rec maps item text to a small set of discrete codes via product quantization, then indexes shared learned embeddings through those codes Can discretizing text embeddings improve recommendation transfer?. That collapses a potentially unbounded item space into a compact, reusable codebook — and as a bonus it transfers across domains better than raw text embeddings, because the discrete intermediate strips out text-similarity bias Can discrete codes transfer better than text embeddings?. So the field actually offers two divergent answers to embedding-table scaling: grow the table cleanly (elastic addressing), or stop needing a giant table at all (discrete codebooks). Elastic addressing fixes the collision pathology that dooms fixed hashing — but it's one of two strategies, and neither escapes the dimensional capacity bound underneath both.
Sources 5 notes
Real recommendation IDs follow power-law distributions, not uniform ones. High-frequency users and items collide more often, degrading model quality exactly where traffic is highest, making fixed-size hash tables inadequate for production systems.
Monolith's empirical work shows that real recommendation systems have power-law distributed frequencies, causing collisions to accumulate precisely on the entities models need most accurate. Fixed-size hashed tables worsen this over time as new IDs arrive.
Communication complexity theory proves that for any embedding dimension d, there exists a maximum number of top-k document combinations that can be returned as results. Even embeddings optimized directly on test data hit this polynomial limit, demonstrated on trivially simple retrieval tasks.
VQ-Rec uses product quantization to map item text to discrete codes that index learned embeddings, breaking the tight coupling between text and recommendations. This decoupling prevents text-similarity bias and allows lookup tables to adapt to new domains without retraining the text encoder.
VQ-Rec demonstrates that mapping item text to discrete codes via product quantization, then to embeddings, improves cross-domain transfer compared to direct text encoding. The discrete intermediate reduces text bias and enables efficient per-domain fine-tuning.