Multi-Probe Zero Collision Hash (MPZCH): Mitigating Embedding Collisions and Enhancing Model Freshness in Large-Scale Recommenders

Zhao et al., ByteDance, 2026 — arXiv:2602.17050

Relations

Builds on: Monolith (Liu et al., ByteDance, 2022)

Table of Contents

• 1. Motivation: Two Problems With Prior Collisionless Methods
• 2. MPZCH: The Algorithm
  • 2.1 Data Structures
  • 2.2 Two-Pass Lookup
  • 2.3 Eviction Policies
  • 2.4 Optimizer State Reset
• 3. System Integration
  • 3.1 Sharding and CUDA Kernels
  • 3.2 Inference and Online Training
• 4. Experiments
  • 4.1 Collision Rate
  • 4.2 Model Quality
  • 4.3 Latency
• References

1. Motivation: Two Problems With Prior Collisionless Methods

Monolith introduced cuckoo hashing for collisionless embedding tables, but it left two problems unresolved:

Problem 1 — Remaining collisions in dynamic settings. Cuckoo hashing is collision-free at insertion time — but only if the table has spare capacity. In a production system with billions of IDs and tight memory budgets, the table eventually fills to its load factor limit, and new IDs fall back to standard hashing (with collisions). Furthermore, Monolith’s TTL-based eviction frees slots for reuse, but the reuse is uncontrolled: a new ID may collide with an existing one in the available slot pool.

Problem 2 — Stale embedding inheritance. When a TTL-expired slot is evicted and a new ID is assigned that slot, the new ID inherits the previous occupant’s embedding weights and optimizer state (Adam moment estimates, etc.). This negative transfer is especially damaging for fresh content: a newly posted video that happens to reuse an old video’s embedding slot starts its training with a strongly biased prior, causing erratic learning and poor early recommendations.

MPZCH addresses both problems with a single mechanism: multi-probe linear probing with active eviction and full slot reset.

2. MPZCH: The Algorithm

2.1 Data Structures

MPZCH augments the standard embedding table with two auxiliary tensors:

• Identities tensor \(\mathcal{I} \in \mathbb{Z}^N\): \(\mathcal{I}[s]\) stores the ID currently occupying slot \(s\). Initialized to \(-1\) (empty).
• Metadata tensor \(\mathcal{M} \in \mathbb{R}^N\): \(\mathcal{M}[s]\) stores temporal information for slot \(s\) — either a TTL timestamp (last-seen time) or an LRU counter.

The probe range for an ID \(x\) with base hash \(h = \text{hash}(x) \bmod N\) is the window \([h, h+P)\) (with wraparound), where \(P\) is the probe depth hyperparameter.

2.2 Two-Pass Lookup

MPZCH uses a read-before-write two-pass strategy to handle each lookup/insertion:

Pass 1 — Discovery (read-only): Scan slots \(h, h+1, \ldots, h+P-1\) without writing. Record: - Whether \(x\) already exists (found at some slot \(s^*\)) - The best eviction candidate \(s_\text{evict}\) (empty slot, or slot with minimum metadata value)

def lookup(I, M, embed, x, P, policy):
    h = hash(x) % len(I)
    found_slot = None
    evict_slot = None
    evict_score = float('inf')

    # Pass 1: scan, no writes
    for i in range(P):
        s = (h + i) % len(I)
        if I[s] == x:
            found_slot = s
            break
        score = eviction_score(M[s], policy)  # 0 if empty, TTL or LRU score otherwise
        if score < evict_score:
            evict_score, evict_slot = score, s

    # Pass 2: act
    if found_slot is not None:
        M[found_slot] = current_time()        # refresh metadata
        return embed[found_slot]
    elif evict_slot is not None and is_evictable(M[evict_slot], policy):
        reset_slot(I, M, embed, evict_slot, x)  # evict + assign to x
        return embed[evict_slot]
    else:
        return embed[h]                        # fallback: return base slot (collision)

Pass 2 — Action: Based on Pass 1 findings, exactly one of three outcomes: 1. Update: ID found at \(s^*\) → refresh \(\mathcal{M}[s^*]\), return embedding. 2. Allocate: ID not found, evictable slot found → reset slot and assign to \(x\). 3. Fallback: No evictable slot in probe range → return base hash slot (collision, rare at appropriate capacity).

2.3 Eviction Policies

MPZCH supports two eviction policies, selected per embedding table:

TTL (Time-To-Live): A slot is evictable if \(\mathcal{M}[s] < t_\text{current}\) (its last-seen timestamp has expired). Among all evictable slots in the probe range, MPZCH selects the most expired one (smallest \(\mathcal{M}[s]\)). TTL is appropriate for item embeddings with well-defined lifetimes (e.g., video post IDs expire after 24h; creator IDs expire after 72h).

LRU (Least Recently Used): The slot with the minimum \(\mathcal{M}[s]\) (oldest last-access time) is evicted, regardless of absolute age. LRU is appropriate for user IDs, where no hard expiry makes semantic sense but inactive users’ slots can be reclaimed.

2.4 Optimizer State Reset

This is the key novelty over Monolith’s cuckoo approach. When a slot is evicted and assigned to a new ID, MPZCH performs a full reset:

1. \(\mathcal{I}[s] \leftarrow x_\text{new}\)
2. \(\mathcal{M}[s] \leftarrow t_\text{current}\)
3. Embedding weights: \(\mathbf{e}[s] \leftarrow \mathbf{0}\) (reset to zero)
4. Optimizer state: Adam moments \(m_1[s], m_2[s] \leftarrow \mathbf{0}\) (reset both first and second moment estimates)

Step 4 is the critical difference. Without optimizer state reset, the new ID’s embedding inherits the previous occupant’s Adam moment history — which encodes a “velocity” in the direction of the old ID’s gradients. Even if the embedding weights are reset to zero, the optimizer will immediately push the weights in the old ID’s direction on the first gradient step, recreating the stale embedding.

3. System Integration

3.1 Sharding and CUDA Kernels

MPZCH uses row-wise sharding: embedding table rows are distributed across ranks such that the full probe window \([h, h+P)\) for any ID falls within a single rank’s local memory. This eliminates inter-rank communication during probe lookups — each lookup is a purely local CUDA kernel operation.

The CUDA kernel implements the two-pass scan in a single thread block per ID, with auxiliary tensors \(\mathcal{I}\) and \(\mathcal{M}\) stored in HBM alongside the embedding table. Key performance property: probe depth \(P\) has negligible effect on latency (0.80 ms at \(P=256\) vs. 0.90 ms at \(P=8\)) because the bottleneck is HBM memory bandwidth, not the sequential probe scan — modern HBM can read a 512-element contiguous probe window in a single burst.

3.2 Inference and Online Training

At inference: The identities tensor \(\mathcal{I}\) is published alongside embedding weights and frozen as read-only. The metadata tensor \(\mathcal{M}\) is omitted from the published model (reducing model size). Inference lookups use \(\mathcal{I}\) to identify slot occupancy but skip all eviction logic.

Online training: Training updates stream through the same two-pass probe mechanism, updating \(\mathcal{M}\) timestamps on access. New IDs seen in the stream trigger allocation; expired IDs are evicted as their slots are needed. Delta synchronization (as in Monolith) transfers updated embeddings to the serving system, including newly allocated and reset slots.

4. Experiments

4.1 Collision Rate

Test: 150M unique user IDs, varying table sizes, probe depth \(P=256\).

Production deployment: 4-billion-row table for 3 billion MAU, \(P=512\) — zero collisions achieved.

4.2 Model Quality

User embedding task (Share, video view metrics):

Item embedding freshness (HSTU architecture, 24h Post ID TTL, 72h Owner ID TTL):

• +0.83% impressions for videos posted within 48 hours — the freshness metric most sensitive to stale embedding inheritance.
• Intra-creator embedding similarity (same-day videos): baseline 25% → MPZCH 38% (t-SNE cosine similarity). Same-day videos by the same creator now cluster correctly.
• Embedding trajectory analysis: MPZCH trajectories are smooth and monotone; baseline trajectories show erratic shifts from collision-induced gradient interference.

4.3 Latency

Probe depth has negligible impact on training throughput:

The non-monotone trend (\(P=256\) slightly faster than \(P=8\)) is likely a CUDA kernel scheduling artifact; all values are within measurement noise. Production training QPS is maintained.

References