Technical Summary: Distributional Approximate Nearest Neighbour Search for Uncertainty-Aware Retrieval (dinosaur)

1. Problem Statement

Modern large-scale recommender systems rely on Approximate Nearest Neighbour (ANN) search for the candidate generation stage, filtering millions of items down to a manageable set for ranking. Standard implementations treat user and item representations as deterministic point estimates (single vectors) in a shared latent space.

The paper identifies a fundamental flaw in this paradigm:

• Inherent Uncertainty: Embeddings learned from sparse interaction data are inherently uncertain. This uncertainty is twofold:
  • Epistemic: High variance for long-tail items due to lack of interaction data.
  • Aleatoric: Information loss inherent in low-rank latent factor models.
• Systematic Bias: Deterministic ANN retrieval creates rigid geometric boundaries. Items with high uncertainty (typically niche, long-tail content) whose true relevance might be high but whose point-estimate mean is slightly off are permanently excluded from the top-$k$ candidates.
• Consequences: This leads to popularity bias and a "rich-get-richer" feedback loop where head items dominate exposure, while long-tail creators and diverse content are systematically starved of impressions. Existing remedies (e.g., post-hoc re-ranking or diversity objectives) are often heuristic and disconnected from the root cause at the retrieval stage.

2. Methodology: The dinosaur Framework

The authors propose dinosaur (Distributional Approximate Nearest Neighbour Search for Uncertainty-Aware Retrieval), a framework that incorporates embedding uncertainty directly into the candidate generation process without altering the underlying ANN infrastructure or scoring models.

Core Mechanism

Instead of indexing a single point estimate $\mu_i$ for each item $i$, dinosaur treats items as distributions $P(v_i)$ (characterized by mean $\mu_i$ and covariance $\Sigma_i$).

1. Index Construction (Offline): For each item $i$, the system draws $S_i$ independent samples $v_i^{(j)} \sim P(v_i)$ from its embedding distribution. The ANN index is built over this augmented set of vectors.
2. Query Execution (Online): At serving time, a user embedding $v_u$ is sampled from the user's distribution $P(v_u)$. The ANN index is queried to find the nearest neighbors to this sampled vector.
3. Deduplication: The retrieved vectors are mapped back to their original item identifiers, and duplicates are removed until exactly $k$ distinct items are returned.

Key Properties

• Infrastructure Compatibility: The method requires no changes to the ANN index algorithm (e.g., FAISS, HNSW, ScaNN) or the scoring model. It only requires an index capable of handling a larger number of vectors.
• Two-Sided vs. One-Sided: While the framework supports sampling for both users and items, the paper focuses on item-side uncertainty to drive exploration. This is particularly useful in dynamic marketplaces where real-time user sampling might violate latency constraints.
• Adaptive Sampling: To manage memory costs (index bloat), the paper proposes Adaptive Sampling, where the sample budget $S_i$ is conditioned on the item's uncertainty. High-confidence head items receive $S_i=1$, while uncertain long-tail items receive $S_i > 1$.

Theoretical Underpinnings

The paper provides theoretical guarantees for the framework:

• Recovery: As embedding variance vanishes ($\sigma^2 \to 0$), dinosaur converges to standard deterministic point-estimate retrieval.
• Monotonic Coverage Expansion: For any item outside the deterministic top-$k$, the probability of retrieval strictly increases with its embedding variance. This mathematically guarantees that uncertain items receive a "retrieval-phase exploration bonus," structurally favoring long-tail content without random noise injection.
• Connection to Thompson Sampling: The mechanism is formally linked to Thompson Sampling, where sampling from the posterior distribution balances exploration and exploitation.

3. Experimental Setup

The authors evaluated dinosaur on the MovieLens-32M dataset (32M interactions, ~200k users, ~84k items).

• Baselines: Exact Inner Product Search (Flat) and Approximate Search (IVFFlat).
• Uncertainty Proxy: Since the base model (iALS) is deterministic, the authors constructed a synthetic epistemic posterior where the standard deviation $\sigma_i$ is inversely proportional to the item's interaction count ($n_i$): $\sigma_i = \alpha / (1 + n_i)^\gamma$.
• Metrics:
  • Recall@K: Standard offline utility metric.
  • Catalogue Coverage@K: The fraction of the total item catalogue appearing in at least one user's top-$K$ list.
  • Stratified Coverage: Analysis by popularity quintiles (B0 = most popular, B4 = least popular).

4. Key Results

• Massive Coverage Gains: Increasing the sample budget from $S=1$ (baseline) to $S=5$ nearly tripled global catalogue coverage (from 23.52% to 62.97% at $K=1000$).
• Negligible Recall Loss: This expansion in coverage came at a minimal cost to offline recall, with a reduction of only 0.0041 in Recall@1000.
• Long-Tail Exposure:
  • Standard IVFFlat achieved 0.00% coverage for the least popular items (Bucket B4).
  • dinosaur ($S=5$) achieved 81.88% coverage for Bucket B4, ensuring that over 13% of users received recommendations from the most obscure items.
• Pareto Dominance: When compared against an $\epsilon$-greedy heuristic, dinosaur strictly dominated the baseline, achieving higher recall for the same fraction of exploratory recommendations across various retrieval depths ($K \in \{100, 500, 1000\}$).

5. Significance and Claims

The paper claims that dinosaur offers a principled, infrastructure-compatible solution to the exploration-exploitation trade-off in retrieval.

• Shift in Paradigm: It moves the burden of handling uncertainty from post-hoc re-ranking or heuristic diversification to the retrieval stage itself.
• Breaking Feedback Loops: By allowing uncertain items to enter the candidate set, it breaks the algorithmic feedback loop where deterministic policies prevent long-tail items from ever being exposed and thus never learning.
• Practicality: The method requires no new hyperparameters beyond the sample count and works with existing production-grade ANN libraries.
• Limitations Acknowledged: The authors note that their uncertainty proxy is based on interaction counts rather than learned distributions, and that offline metrics (Recall) are biased by Missing Not At Random (MNAR) data. They suggest future work should combine propensity-aware offline evaluation with online A/B testing to measure true marketplace impact.

In summary, dinosaur demonstrates that treating embeddings as distributions rather than points can significantly improve catalogue diversity and long-tail exposure with virtually no degradation in standard retrieval utility.