Collisionless Embedding Tables

Embedding tables are the foundation of modern recommendation systems. They convert sparse, categorical data (User IDs, Video IDs, Hashtags) into dense mathematical vectors that neural networks can process. TikTok's Monolith Framework uses collisionless embedding tables via Cuckoo hashing to maintain precision at billion-scale.

What are embeddings?

An embedding is a dense vector representation of a sparse entity. For example:

• User @varun_78923 -> a 256-dimensional vector like [0.12, -0.87, 0.34, ...]
• Video v_abc123 -> a 256-dimensional vector like [0.45, 0.22, -0.91, ...]

The geometry of these vectors encodes semantic meaning. Users who watch similar content have nearby vectors. Videos about similar topics have nearby vectors. The recommendation engine finds matches by searching for nearby vectors in this high-dimensional space.

See Two-Tower Neural Network for how these embeddings are actually used.

The collision problem

Traditional recommendation systems use hash tables to map IDs to embedding vectors. A hash table has a fixed memory allocation, and when the number of unique IDs exceeds the table size, collisions occur: two different IDs map to the same slot.

Cuckoo hashing: the solution

TikTok's Monolith uses a Cuckoo HashMap, which ensures every unique ID maintains a distinct embedding. The mechanics:

1. Each ID hashes to a primary location in the table
2. If that location is occupied, the existing data is kicked out to a secondary location (determined by a second hash function)
3. The process repeats recursively until every ID has its own slot
4. The name comes from the cuckoo bird, which pushes other eggs out of the nest

ID_A hashes to slot 5 -> stored at slot 5
ID_B hashes to slot 5 -> ID_A kicked to slot 12, ID_B stored at slot 5
ID_C hashes to slot 12 -> ID_A kicked to slot 8, ID_C stored at slot 12
...until all IDs find unique slots

The key guarantee: zero collisions. Every user and every video gets a unique, undistorted embedding vector.

Memory management

Collisionless tables require careful memory management since every unique ID consumes a dedicated slot. At billions of IDs, this can explode server memory. Three strategies keep it manageable:

Probabilistic frequency filtering

IDs that appear only once or twice (e.g., a user who visited once and never returned) are filtered out using Bloom filters or Count-Min Sketch. These rare IDs add noise more than signal.

ID Timer (stale eviction)

Embeddings for users who have been inactive for months are evicted. This frees memory while preserving the embedding for any returning user (which gets reconstructed from fresh interactions).

Sparse optimization

Only the non-zero dimensions of each embedding are stored. Since most embeddings are sparse (most dimensions are zero), this dramatically reduces memory footprint.

Why this matters for recommendation quality

The precision of the entire recommendation pipeline depends on embedding quality. If User A's embedding is corrupted by collisions with unrelated users, the Two-Tower Neural Network will retrieve irrelevant candidates, the Multi-Stage Ranking Pipeline will score them poorly, and the user sees content they don't care about.

Collisionless embeddings ensure that:

• Each user's taste profile is uniquely represented
• Each video's content signature is uniquely represented
• The ANN search in the retrieval stage returns genuinely similar content
• The TikTok Signal Hierarchy is applied to accurately matched candidates

Comparison with traditional approaches

See also

• Monolith Framework - The training system that uses these tables
• Two-Tower Neural Network - How embeddings are used for retrieval
• Vector Database - Infrastructure for ANN search over embeddings
• TikTok Recommendation Engine Overview - Where this fits in the architecture