Recommendation Systems Part 2: Ranking & Re-ranking

Part 2 of 6 | ← Part 1: Architecture | Part 3: Production Systems →

Ranking Models

The ranking stage scores candidates with a model trained to predict user engagement. Unlike retrieval, ranking models can afford to examine detailed feature interactions.

Problem Formulation

Ranking is typically framed as pointwise, pairwise, or listwise learning to rank:

Most production systems use pointwise classification (predicting P(click), P(like), P(share)) due to simplicity and scalability, with calibration layers to combine predictions into a single score.

Pointwise Loss Functions

For binary engagement labels $y \in \{0, 1\}$, the standard binary cross-entropy loss is:

where $\hat{p}\_i = \sigma(f(\mathbf{x}\_i))$ is the predicted probability. For continuous labels like watch time, regression losses apply:

Pairwise Loss Functions

Bayesian Personalized Ranking (BPR) optimizes pairwise preferences. For a positive item $i^+$ and negative item $i^-$:

This pushes the score of engaged items above non-engaged items. The hinge loss variant introduces a margin $m$:

Listwise Loss Functions

LambdaRank directly optimizes ranking metrics (NDCG, MAP) by defining gradients as:

where $|\Delta \text{NDCG}_{ij}|$ is the change in NDCG from swapping items $i$ and $j$. This gradient weighting focuses learning on swaps that most impact ranking quality.

The softmax cross-entropy over a list treats ranking as classification:

Model Architectures

Deep & Cross Networks (DCN)

DCN explicitly models feature interactions via cross layers while maintaining a parallel deep network for implicit interactions. The cross layer computes:

where $\mathbf{x}\_0 \in \mathbb{R}^d$ is the input embedding, $\mathbf{w}\_l, \mathbf{b}\_l \in \mathbb{R}^d$ are learnable parameters, and the outer product $\mathbf{x}\_0 \mathbf{x}\_l^\top$ captures feature interactions. After $L$ cross layers, the model captures polynomial interactions up to degree $L+1$.

DCN-v2 replaces the vector $\mathbf{w}\_l$ with a matrix $\mathbf{W}\_l \in \mathbb{R}^{d \times d}$:

where $\odot$ denotes element-wise multiplication. This increases expressiveness at the cost of $O(d^2)$ parameters per layer.

The full DCN architecture combines cross and deep components:

where $[\cdot ; \cdot]$ denotes concatenation.

Wide & Deep

Google’s Wide & Deep combines a linear model (wide) for memorization with a deep neural network for generalization:

where $\phi(\mathbf{x})$ represents cross-product feature transformations (e.g., AND(gender=female, language=en)) and $a^{(L)}$ is the final hidden layer of the deep network:

The wide component memorizes specific feature co-occurrences; the deep component generalizes to unseen combinations via learned embeddings.

Feature Interaction Layers

Factorization Machines (FM) model pairwise interactions efficiently:

where $\mathbf{v}\_i \in \mathbb{R}^k$ is a latent factor for feature $i$. The interaction term can be computed in $O(nk)$ time:

DeepFM stacks FM with a deep network, sharing embedding vectors between both components.

Multi-Task Learning

Social media engagement is multi-faceted: clicks, likes, comments, shares, watch time, hides, reports. Multi-task models share lower layers while branching into task-specific heads.

Shared-Bottom Architecture: All tasks share the same feature extraction layers:

Multi-gate Mixture-of-Experts (MMoE): Tasks select from a set of expert networks via learned gating:

where $f\_e$ are expert networks, $g^{(t)}(\mathbf{x}) = \text{softmax}(\mathbf{W}^{(t)}\_g \mathbf{x})$ is a task-specific gating network, and $g^{(t)}\_e$ is the weight assigned to expert $e$ for task $t$.

The joint loss is a weighted sum:

Task weights $\alpha\_t$ can be fixed or learned dynamically (e.g., via uncertainty weighting or gradient balancing).

flowchart TB
    Features --> Shared[Shared Layers]
    Shared --> Click["P(click)"]
    Shared --> Like["P(like)"]
    Shared --> Comment["P(comment)"]
    Shared --> Hide["P(hide)"]
    Shared --> WatchTime["E(watch time)"]

Final scores combine task predictions via a weighted sum or learned aggregation, enabling the platform to tune for different objectives (e.g., prioritize meaningful interactions over passive consumption).

Sequence Modeling

User engagement history is sequential: the order of interactions carries signal. Sequence models capture temporal dynamics.

Recurrent Architectures

Long Short-Term Memory (LSTM) networks maintain a cell state $\mathbf{c}\_t$ and hidden state $\mathbf{h}\_t$ updated at each timestep:

The final hidden state $\mathbf{h}\_T$ encodes the user’s sequential preferences.

Self-Attention for Sequences

Self-Attentive Sequential Recommendation (SASRec) applies transformer self-attention to interaction sequences. Given item embeddings $\mathbf{E} = [\mathbf{e}\_1, \ldots, \mathbf{e}\_n]$:

where $\mathbf{Q} = \mathbf{E} \mathbf{W}^Q$, $\mathbf{K} = \mathbf{E} \mathbf{W}^K$, $\mathbf{V} = \mathbf{E} \mathbf{W}^V$ are query, key, and value projections.

Causal masking ensures position $i$ only attends to positions $\leq i$:

Multi-head attention projects into $H$ parallel subspaces:

where $\text{head}\_h = \text{Attention}(\mathbf{Q} \mathbf{W}^Q\_h, \mathbf{K} \mathbf{W}^K\_h, \mathbf{V} \mathbf{W}^V\_h)$.

Temporal Position Encoding

Standard sinusoidal position encoding:

For recommendation, time-aware embeddings encode absolute or relative timestamps:

where $\Delta t\_i = t\_i - t\_{i-1}$ is the time gap and $\omega$ captures periodic patterns (hour-of-day, day-of-week).

BERT4Rec: Bidirectional Modeling

BERT4Rec uses masked language modeling for sequences: randomly mask items and predict them from context:

where $\mathcal{M}$ is the set of masked positions. Bidirectional attention (no causal mask) captures both past and future context, but requires different inference strategies (e.g., append [MASK] token for next-item prediction).

# Simplified Transformer-based user encoder (PyTorch-like pseudocode)
class UserSequenceEncoder(nn.Module):
    def __init__(self, item_vocab_size, d_model, n_heads, n_layers):
        self.item_embedding = nn.Embedding(item_vocab_size, d_model)
        self.positional_encoding = PositionalEncoding(d_model)
        self.transformer = nn.TransformerEncoder(
            nn.TransformerEncoderLayer(d_model, n_heads),
            num_layers=n_layers
        )
        self.output_proj = nn.Linear(d_model, d_model)

    def forward(self, item_sequence, mask):
        x = self.item_embedding(item_sequence)
        x = self.positional_encoding(x)
        x = self.transformer(x, src_key_padding_mask=mask)
        # Pool over sequence (e.g., mean or [CLS] token)
        return self.output_proj(x.mean(dim=1))

Re-ranking and Business Logic

Raw model scores optimize for predicted engagement, but the final feed must satisfy additional constraints:

Diversity

Showing ten similar posts degrades user experience. Diversity algorithms ensure variety.

Maximal Marginal Relevance (MMR)

MMR iteratively selects items that balance relevance and diversity:

where $S$ is the already-selected set, $\text{rel}(i)$ is the relevance score, $\text{sim}(i, j)$ is similarity (e.g., cosine similarity of embeddings), and $\lambda \in [0, 1]$ controls the relevance-diversity trade-off.

Complexity: $O(k \cdot n)$ for selecting $k$ items from $n$ candidates, assuming similarity lookup is $O(1)$.

Determinantal Point Processes (DPP)

DPPs are probabilistic models that assign higher probability to diverse subsets. Given a positive semi-definite kernel matrix $\mathbf{L} \in \mathbb{R}^{n \times n}$:

where $\mathbf{L}_S$ is the submatrix indexed by $S$. The kernel encodes both quality (diagonal) and similarity (off-diagonal):

where $q_i$ is item quality (relevance score) and $\phi(\mathbf{x}_i)$ is the diversity feature vector.

Properties:

• Items with high quality are more likely to be selected.
• Similar items (high $\phi(\mathbf{x}_i)^\top \phi(\mathbf{x}_j)$) are unlikely to appear together.
• Exact sampling is $O(n^3)$; approximate methods (greedy, MCMC) are used in practice.

MAP Inference finds the most diverse high-quality set:

This is NP-hard but admits a $(1 - 1/e)$-approximation via greedy selection.

Submodular Optimization

A set function $F: 2^{\mathcal{I}} \rightarrow \mathbb{R}$ is submodular if it exhibits diminishing returns:

Coverage functions capture diversity:

where $\mathcal{C}$ is a set of categories/topics and $w\_{ic}$ is item $i$’s coverage of category $c$.

Greedy maximization of monotone submodular functions achieves a $(1 - 1/e) \approx 0.63$ approximation ratio:

Novelty, Serendipity, and Exploration

While diversity ensures variety of topics/creators within a single feed, novelty and serendipity address different user needs:

Novelty: Items the user hasn’t encountered before. Pure relevance-based ranking can get stuck recommending the same high-scoring items. Novelty ensures forward progress through the catalog.

Serendipity: Surprising discoveries—items outside the user’s typical consumption pattern that they end up enjoying. A sports fan unexpectedly loving a cooking video. Serendipity combats filter bubbles and enables exploration.

Implementation strategies:

1. Novelty filtering:

   unseen_candidates = [c for c in candidates if c.id not in user.seen_history]
   

   • Requires tracking user impression history (Bloom filter or distributed cache)
   • Balance: Don’t filter TOO aggressively (catalog exhaustion for power users)

2. Serendipity injection:

   • Reserve 5-10% of feed slots for “exploration” items
   • Sample from topics user hasn’t engaged with recently
   • Use contextual bandits (Thompson Sampling, LinUCB) to balance exploration vs. exploitation
   $$ \text{UCB}\_i = \hat{\mu}\_i + \beta \sqrt{\frac{\ln t}{n\_i}} $$

   where $\hat{\mu}\_i$ is estimated reward, $n\_i$ is times shown, $\beta$ controls exploration

3. Calibrated surprise scores:

   • Train a model to predict: $P(\text{engage} | \text{item}, \text{user profile})$
   • Compute unexpectedness: how different is this item from user’s historical profile?
   • Serendipity score: $\text{relevance} \times \text{unexpectedness}$
   • Reward items that are both relevant AND surprising

User-level adaptation:

• Explorers: Users who engage with diverse content → increase serendipity budget
• Conservatives: Users who stick to familiar topics → reduce serendipity, focus on relevance
• Cohort analysis: New users need more exploration; established users have known preferences

Measuring success:

• Immediate engagement: Do users click on serendipitous items?
• Session length: Does serendipity increase time spent?
• Long-term retention: Do users with more serendipity return more often?
• Regret signals: Do users hide/dismiss serendipitous items?

Fairness and Creator Economics

Platforms balance exposure across creators to maintain a healthy ecosystem:

• Exposure parity: Ensure new or small creators receive baseline visibility.
• Anti-concentration: Prevent a handful of viral posts from dominating feeds.
• Monetization constraints: Ensure ad load targets are met without degrading organic experience.

Policy Enforcement

Content policy violations (misinformation, hate speech, spam) must be filtered or demoted:

• Hard blocks: Remove items flagged by integrity classifiers.
• Soft demotion: Reduce scores for borderline content.
• Contextual warnings: Overlay labels on sensitive content.

Deduplication and Near-Duplicate Detection

Users experience fatigue when shown the same or nearly identical content repeatedly. Deduplication removes exact duplicates and near-duplicates before final ranking.

Exact Deduplication

The simplest case: multiple candidates point to the same underlying content.

Common causes:

• Cross-posting: Same content shared to multiple groups/pages
• Reposts/retweets: User shares an existing post
• Viral spread: Same image/video uploaded by multiple users

Solution: Content-based hashing

• Text: Hash normalized text (lowercased, punctuation removed) with SHA-256 or MurmurHash
• Images: Perceptual hashing (pHash, dHash) produces similar hashes for visually similar images despite format changes, crops, or compression
• Videos: Hash keyframes or audio fingerprints (Chromaprint, AudioSet embeddings)

At serving time, deduplicate by hash:

seen_hashes = set()
deduplicated = []
for item in ranked_candidates:
    h = hash(item.content)
    if h not in seen_hashes:
        deduplicated.append(item)
        seen_hashes.add(h)

Complexity: $O(n)$ with hash table lookups.

Semantic Near-Duplicate Detection

Harder problem: content that’s functionally identical but not byte-for-byte the same.

Examples:

• Same news story from different outlets (different wording, same facts)
• Meme templates with different captions
• Screenshots of tweets vs. embedded tweets
• Videos with different aspect ratios or watermarks

Embedding-based approach:

1. Compute content embeddings (BERT for text, CLIP for images/video)
2. For each candidate, check cosine similarity against already-selected items: $$ \text{sim}(i, j) = \frac{\mathbf{e}_i^\top \mathbf{e}_j}{\|\mathbf{e}_i\| \|\mathbf{e}_j\|} $$
3. If $\text{sim}(i, j) > \tau$ (e.g., $\tau = 0.9$), mark as near-duplicate

Optimization: Use ANN indexes (HNSW, FAISS) to find near neighbors in embedding space without checking all pairs. Complexity: $O(n \log n)$ amortized.

flowchart LR
    Candidates[Ranked Candidates] --> Hash[Content Hashing]
    Hash --> ExactDedup[Exact Deduplication]

    ExactDedup --> Embed[Embedding Lookup]
    Embed --> ANN[ANN Similarity Search]
    ANN --> NearDedup[Near-Duplicate Filter]

    NearDedup --> Final[Deduplicated Feed]

Multi-Session Deduplication

Within a single feed request, deduplication is straightforward. Across sessions, it’s harder:

Challenges:

• State management: Must track what the user has already seen. This requires persistent storage (Redis, DynamoDB) keyed by user ID.
• Recency: Content seen days ago might be worth showing again; content seen minutes ago should be suppressed.
• False positives: Overly aggressive deduplication can starve feeds of content.

Strategies:

Production pattern: Bloom filter for short-term deduplication (hours), with daily resets to avoid memory bloat.

Novelty vs. Diversity vs. Deduplication

These are related but distinct:

Deduplication is a prerequisite for novelty (can’t be novel if it’s a duplicate). Diversity operates at a higher semantic level (topic/creator variety, not content similarity).

Re-ranking as Constrained Optimization

Re-ranking involves multiple competing objectives (relevance, diversity, fairness, business constraints) that cannot be simultaneously maximized. Formal treatment requires constrained optimization or multi-objective frameworks.

Single-Objective Formulation with Constraints

The simplest formulation maximizes a weighted utility subject to hard constraints (Carbonell & Goldstein 1998; Agrawal et al. 2009):

subject to:

• Diversity: $\text{sim}(\pi\_i, \pi\_j) < \theta \quad \forall i \neq j$
• Fairness: $\sum\_{i : \text{creator}(\pi\_i) = c} 1 \leq m\_c \quad \forall c \in \mathcal{C}$ (per-creator exposure cap)
• Freshness: $|\{i : \text{age}(\pi\_i) < 24h\}| \geq n$
• Policy: $\text{policy-score}(\pi\_i) > \tau \quad \forall i$

where $\Pi$ is the set of permutations of candidate items, $r(\pi\_i)$ is relevance score, and $w\_{\text{pos}}(i)$ is position-dependent weight.

Computational challenge: This is a constrained integer optimization problem (NP-hard). Practical solutions:

• Greedy approximation: MMR, submodular maximization ($1 - 1/e$ approximation)
• Relaxation: Continuous relaxation + rounding
• Constraint satisfaction: Filter candidates, then rank

Lagrangian Formulation

For soft constraints, use Lagrangian relaxation (Boyd & Vandenberghe 2004):

where $g\_j(\pi)$ are constraint violations (diversity deficit, fairness violation, etc.) and $\lambda\_j \geq 0$ are Lagrange multipliers.

Optimization: Solve the dual problem:

Interpretation: Lagrange multipliers $\lambda\_j$ represent the “price” of violating constraint $j$. At optimum, if $\lambda\_j > 0$, constraint $j$ is active (binding).

Example - Diversity constraint:

quadrantChart
    title Relevance-Diversity Pareto Frontier
    x-axis Low Diversity --> High Diversity
    y-axis Low Relevance --> High Relevance
    quadrant-1 Pareto Optimal
    quadrant-2 High Relevance Focus
    quadrant-3 Dominated
    quadrant-4 High Diversity Focus
    Point A: [0.20, 0.95]
    Point B: [0.35, 0.88]
    Point C: [0.48, 0.78]
    Point D: [0.60, 0.65]
    Point E: [0.72, 0.52]
    Point F: [0.82, 0.38]
    Point G: [0.90, 0.25]
    Dominated X: [0.45, 0.45]
    Dominated Y: [0.55, 0.35]

flowchart LR
    Scores[Ranking Scores] --> Rerank[Re-ranking]
    Diversity[Diversity Constraints] --> Rerank
    Policy[Policy Filters] --> Rerank
    Business[Business Rules] --> Rerank
    Rerank --> Final[Final Feed]

flowchart LR
    App[User App] -->|events| Stream[Event Stream]
    Stream --> Processor[Stream Processor]
    Processor --> State[(User State Store)]
    State --> Inference[Ranking Service]
    Inference --> App