Technical Summary: Don't Contrast the Impossible

Problem Statement

In large-scale recommender systems, contrastive learning is the standard paradigm for learning user representations. These methods typically treat observed user-item interactions as positives and other items within a mini-batch as negatives. A common, often implicit, assumption underlying random mini-batch sampling is universal exposure: the idea that any user could theoretically be exposed to any item.

This assumption fails on local community platforms like Karrot (Danggeun Market), where exposure is geographically constrained by design. On such platforms, the vast majority of user-item pairs are impossible by policy; items located outside a user's viewable region are never exposed to that user. Consequently, standard random batching introduces a high volume of impossible negatives—items a user could never have seen due to geographic rules, not because of a lack of preference.

The paper distinguishes between two types of negatives:

1. Feasible Negatives: Items a user could have been exposed to but chose not to engage with. These carry a meaningful preference signal.
2. Impossible Negatives: Items a user could never have been exposed to due to platform constraints. These carry little to no preference signal, as non-engagement is determined by the system rather than user choice.

When impossible negatives dominate a training batch, they dilute the contrastive learning signal, leading to less discriminative user representations.

Methodology: Region-Constrained Batch Sampling (RCBS)

To address the "impossible negatives" problem, the authors propose Region-Constrained Batch Sampling (RCBS). This is a data-level correction that modifies how mini-batches are constructed without altering the underlying model architecture or the loss function.

Core Mechanism

RCBS constructs region-homogeneous mini-batches. Instead of sampling users uniformly at random from the entire platform, RCBS samples users from a specific geographic region $r$.

• Feasibility Definition: A user-item pair is defined as feasible if the distance between the user's region and the item's region is within a user-specific exposure radius $\delta_u$.
• Batch Construction: A batch $\mathcal{B}_r$ is formed by sampling users uniformly from a specific region pool $U_r$. Since all users in the batch share similar exposure constraints, the items associated with other users in the batch are highly likely to be feasible negatives for the target user.

Theoretical Impact

The authors derive that under random batching, the expected fraction of impossible negatives ($\rho$) is high and scales with the number of regions. In contrast, RCBS concentrates the probability mass on a single region, driving $\rho$ close to zero.

• Harder Negatives: By replacing impossible negatives with feasible ones, RCBS naturally introduces "harder" negatives. Feasible negatives represent items the user could have seen but didn't, providing a stronger, more informative signal for learning user preferences.
• Complementarity with IPS: The paper notes that RCBS is complementary to Inverse Propensity Scoring (IPS). While IPS corrects for exposure bias among observed pairs, it cannot handle pairs with zero exposure probability (impossible pairs). RCBS ensures the training batch consists primarily of feasible pairs, upon which IPS can then operate to correct residual imbalances.

Key Contributions

1. Problem Identification: The paper identifies the specific issue of "impossible negatives" in region-constrained recommendation systems, distinguishing them from standard preference-based negatives.
2. RCBS Proposal: It introduces Region-Constrained Batch Sampling, a simple yet effective method to reduce impossible negatives by enforcing geographic homogeneity in mini-batches.
3. Empirical Validation: Through extensive offline and online evaluations, the authors demonstrate that RCBS improves user representation quality and downstream performance.
4. Production Deployment: The resulting user embeddings learned via RCBS have been successfully deployed in production across various applications at Karrot.

Experimental Results

Offline Evaluation (User Modeling Pretraining)

• Metrics: Recall@10 and Recall@100.
• Findings: RCBS-trained models consistently outperformed random-batch baselines.
  • Random-Train: Achieved R@10 of 0.100 with an impossible negative ratio ($\rho_{train}$) of 0.98.
  • RCBS-Train (fine): Achieved R@10 of 0.149 with $\rho_{train}$ reduced to 0.30.
• Observation: A lower ratio of impossible negatives correlated strongly with better recall metrics. Furthermore, evaluating RCBS-trained models using RCBS-based evaluation (RCBS-Eval) yielded lower scores than Random-Eval, confirming that feasible negatives act as harder, more challenging negatives than impossible ones.

Downstream Task Performance

When applied to three downstream tasks, RCBS-trained user embeddings showed consistent improvements over random-batch baselines:

• Home Feed Ranking: +1.18% improvement in NDCG@10.
• Home Feed Retrieval: +7.56% improvement in Recall@10 (the largest gain, attributed to the structural similarity between retrieval and pretraining objectives).
• Display Ads Ranking: +3.38% improvement in PR-AUC.

Online A/B Tests

The best-performing model (RCBS-Train fine) was deployed in production A/B tests:

• Home Feed (Ranking + Retrieval): +10.0% increase in clicks, +5.12% in impressions, and +1.91% in Daily Active Viewers (DAV).
• Display Ads: +6.01% increase in eCPM and +7.46% increase in Ad CTR.

Significance and Claims

The paper claims that the "impossible negatives" problem is a critical, often overlooked issue in location-aware services (e.g., food delivery, dating apps, local marketplaces) where exposure is strictly bounded by geography. By simply constraining the batching process to be region-homogeneous, the authors demonstrate that:

1. Training signals are strengthened: Replacing impossible negatives with feasible ones provides a more accurate reflection of user preference.
2. Performance is scalable: The method improves retrieval and ranking metrics across the board, leading to significant business impact in a production environment.
3. Simplicity is effective: The solution requires no changes to the model architecture or loss function, making it a practical drop-in replacement for standard random batching in geographically constrained systems.

The authors conclude that while RCBS effectively addresses the structural impossibility of certain pairs, future work could explore adaptive region grouping for dynamic constraints and further integration with propensity-based debiasing methods.