Technical Summary: Multi-Probe Zero Collision Hash (MPZCH)

1. Problem Statement

Large-scale recommendation systems rely on embedding tables to map high-cardinality categorical features (e.g., user IDs, item IDs) into dense vector representations. However, as the volume of unique IDs grows, traditional hash-based indexing methods face two critical challenges:

1. Embedding Collisions: Due to memory constraints, the "hashing trick" maps multiple distinct IDs to the same index. When unrelated users or items share an embedding vector, it conflates their semantics, degrading model performance and personalization quality.
2. Model Staleness and Negative Transfer: In dynamic environments, new items frequently collide with slots occupied by obsolete, stale IDs. Standard hash methods lack mechanisms to retire these old IDs. Consequently, new items "inherit" pre-trained embeddings from unrelated entities, forcing the model to unlearn noise before converging on useful signals. This "negative transfer" hinders the learning of accurate representations for new features.

While increasing table size reduces collision probability, it cannot eliminate collisions entirely due to memory limits, and standard hash algorithms may still produce significant collisions even with large tables.

2. Methodology: MPZCH

The authors propose Multi-Probe Zero Collision Hash (MPZCH), a novel indexing mechanism implemented as a high-performance CUDA kernel. It combines linear probing with auxiliary state management to mitigate collisions and actively manage ID lifecycles.

2.1 Core Components

• Auxiliary Tensors: MPZCH maintains two tensors alongside the embedding table:
  • Identities Tensor: Records the specific ID occupying each slot (initialized to -1). This allows the kernel to strictly distinguish between occupied slots and available ones.
  • Metadata Tensor: Stores auxiliary information, such as Time-To-Live (TTL) values or timestamps, to guide eviction decisions.
• Two-Pass Linear Probing: To ensure consistency and prevent duplicate storage or premature eviction, the kernel executes a two-pass scan for each ID:
  1. Pass 1 (Discovery): Scans the probe range to determine if the ID already exists. No write operations occur.
  2. Pass 2 (Action): Based on Pass 1 results:
     • Update: If the ID exists, metadata (e.g., timestamp) is refreshed.
     • Allocation: If the ID is new, the kernel attempts to find an empty slot or evict an expired entry.
     • Collision Fallback: If no empty or evictable slot is found within the probe range, the system defaults to the initial hash slot (though with sufficient table sizing and probe depth, this is rare).

2.2 Eviction and Freshness Strategies

MPZCH introduces configurable eviction policies to manage table capacity and ensure freshness:

• TTL (Time-To-Live) Policy: Slots are marked as expired if their metadata timestamp falls below the current training timestamp. Eviction is lazy, triggered only when a new ID requires allocation.
• LRU (Least Recently Used) Policy: The kernel scans the probe range to evict the entry with the oldest timestamp.
• Optimizer Reset: Crucially, upon eviction, both the embedding weights and the optimizer state (e.g., momentum) are reset. This prevents new items from inheriting stale embeddings, ensuring they learn from scratch.

2.3 System Integration

• TorchRec Integration: MPZCH is designed for seamless integration with Meta's TorchRec library. The identity and metadata tensors are row-wise sharded across ranks to match the embedding table, ensuring all operations remain local to the shard without complex inter-rank synchronization.
• Inference Optimization: During model publishing, the metadata tensor is omitted to reduce model size, and the identities tensor is frozen. The inference service becomes strictly read-only, providing deterministic and efficient lookups.
• Streaming Updates: The system supports online training with streaming updates, ensuring the identities tensor remains consistent with embedding row modifications.

3. Key Contributions

1. Zero Collision Guarantee: By combining sufficient table sizing with configurable probe depths, MPZCH effectively eliminates embedding collisions for user embeddings, a feat difficult to achieve with standard hashing.
2. Active Lifecycle Management: Unlike static hash tables, MPZCH actively retires obsolete IDs and resets optimizer states, directly addressing the "negative transfer" problem and enhancing model freshness.
3. High-Performance Implementation: The algorithm is implemented as a custom CUDA kernel that handles tens of thousands of IDs in parallel. Benchmarks show that the linear probing overhead is negligible (latency remains stable even with increased probe depth), maintaining training QPS and inference latency comparable to existing methods.
4. Open-Source Release: The solution has been released within the open-source TorchRec library.

4. Experimental Results

The authors evaluated MPZCH through rigorous online A/B tests and offline benchmarks:

• Collision Rates: In experiments with 150 million unique user IDs, MPZCH achieved zero collisions with a table size of 200 million (1.33x capacity) and a probe depth of 256. In contrast, the baseline Sigrid hash maintained a ~30% collision rate even with a table size triple the ID cardinality.
• User Embeddings (Video Ranking): Deployed in a production video ranking model serving 3 billion monthly active users. The elimination of collisions resulted in statistically significant improvements in Normalized Entropy (NE) for 14 out of 17 prediction tasks, including Share (+0.38%) and Video View Duration (+0.12%).
• Item Embeddings (Video Retrieval): Integrated into an HSTU-based retrieval model with TTL-based eviction (24h for Posts, 72h for Owners).
  • Performance: New videos (posted within 48 hours) saw a 0.83% increase in impressions.
  • Semantic Quality: t-SNE analysis revealed that MPZCH significantly improved the clustering of embeddings for videos from the same creator. Intra-creator similarity increased from 0.66% to 0.91% for same-day posts (+38% relative lift).
  • Learning Stability: Embedding trajectories became smoother and more consistent, eliminating the volatile shifts observed in the baseline model caused by hash collisions.

5. Significance

The paper posits that MPZCH offers a dual-advantage solution for modern recommendation systems. First, by guaranteeing a collision-free environment, it elevates embedding quality and prediction accuracy by removing stochastic interference. Second, by introducing active eviction and optimizer reset mechanisms, it fundamentally enhances embedding freshness, allowing models to adapt rapidly to shifting data distributions without unbounded memory growth. The authors conclude that these empirical improvements in both model freshness and quality validate MPZCH as a robust solution for large-scale recommenders.