PaperlayerView exact revision on arXiv

Source-linked AI summary

End-to-End User Behavior Retrieval in Click-Through RatePrediction Model

Qiwei Chen, Changhua Pei, Shanshan Lv, Chao Li, Junfeng Ge, Wenwu Ou

arXiv:2108.04468v1cs.IRcs.AI

TL;DR

Long-term behavior histories offer useful signals for CTR prediction, but inference constraints and gaps between retrieval and the main CTR task limit their use. ETA applies SimHash-based retrieval end to end, and its deployment reports 3.1% extra GMV compared with a two-stage CTR model.

  • Problem

    Strict inference-time constraints limit CTR models’ ability to use long-term behavior, while two-stage retrieval can diverge from the CTR objective or use outdated embeddings.

    Source: §1 · p. 2, §4.4 · p. 5

  • Method

    ETA uses SimHash fingerprints and Hamming distance to retrieve top-k behaviors end to end for target attention, reducing retrieval complexity from O(L*B*d) to O(L*B).

    Source: §1 · p. 2, §6 · p. 10

  • Results

    3.1% extra GMV was reported after ETA deployment compared with a two-stage CTR model.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The reduced retrieval complexity supports real-time retrieval during training and serving without an offline auxiliary model.

    Source: §1 · p. 2

Abstract

from arXiv · show

Click-Through Rate (CTR) prediction is one of the core tasks in recommender systems (RS). It predicts a personalized click probability for each user-item pair. Recently, researchers have found that the performance of CTR model can be improved greatly by taking user behavior sequence into consideration, especially long-term user behavior sequence. The report on an e-commerce website shows that 23\% of users have more than 1000 clicks during the past 5 months. Though there are numerous works focus on modeling sequential user behaviors, few works can handle long-term user behavior sequence due to the strict inference time constraint in real world system. Two-stage methods are proposed to push the limit for better performance. At the first stage, an auxiliary task is designed to retrieve the top-$k$ similar items from long-term user behavior sequence. At the second stage, the classical attention mechanism is conducted between the candidate item and $k$ items selected in the first stage. However, information gap happens between retrieval stage and the main CTR task. This goal divergence can greatly diminishing the performance gain of long-term user sequence. In this paper, inspired by Reformer, we propose a locality-sensitive hashing (LSH) method called ETA (End-to-end Target Attention) which can greatly reduce the training and inference cost and make the end-to-end training with long-term user behavior sequence possible. Both offline and online experiments confirm the effectiveness of our model. We deploy ETA into a large-scale real world E-commerce system and achieve extra 3.1\% improvements on GMV (Gross Merchandise Value) compared to a two-stage long user sequence CTR model.

1 INTRODUCTION

Long-term user behavior can improve CTR prediction, but inference constraints and gaps between retrieval and the main CTR task limit its use. ETA uses end-to-end retrieval to address those gaps and reports online gains over a two-stage model.

1 INTRODUCTION

  • 23% of users in one e-commerce report had more than 1,000 clicks over five months, motivating the use of long-term behavior histories.The paper presents these histories as informative signals for CTR prediction.Source: §1 · p. 1
  • DIN uses target attention to represent candidate-specific interests, but applies it to only the recent 50 behaviors because of computation and storage costs.Earlier pooling and sequence models can miss local interests for different candidate items and add noise by encoding all historical behaviors.Source: §1 · p. 1
  • Two-stage methods retrieve similar items before target attention, but attribute-based retrieval can diverge from the CTR objective and offline embeddings can become outdated.The paper identifies both issues as information gaps between retrieval and the main CTR model.Source: §1 · p. 2
  • ETA uses SimHash fingerprints and Hamming distance to retrieve top-k behaviors, reducing retrieval complexity from O(L*B*d) to O(L*B).The lower complexity supports real-time retrieval during training and serving without an offline auxiliary model.Source: §1 · p. 2
  • 3.1% extra GMV was achieved by ETA after deployment, compared with a two-stage CTR model.The paper also reports offline experiments and online A/B tests showing improvements over state-of-the-art models.Source: §1 · p. 2

2 RELATED WORK

Related work spans CTR feature-interaction models, methods for encoding user behavior, and approaches to long-term histories. Long-sequence systems use retrieval followed by target attention, while transformer-efficiency methods do not directly address online CTR constraints.

2 RELATED WORK

  • CTR prediction supplies ranking scores for downstream tasks, and prior approaches include feature-interaction, user-sequence, and long-term-sequence methods.Feature-interaction models vary in deep-learning use, embedding sharing, and need for feature engineering.Source: §2 · p. 2
  • CNNs, RNNs, attention, and capsule networks model user behavior, while DIN uses target attention to capture interests specific to different target items.Earlier sequence models produce global user-interest vectors.Source: §2 · p. 2
  • MIMN handles long histories by updating interests offline, whereas SIM and UBR4CTR retrieve top-k items before applying target attention.The two-stage methods use an auxiliary retrieval task followed by attention between the target item and selected behaviors.Source: §2 · p. 2
  • Reformer and Informer optimize transformers but are not directly applicable to large-scale online CTR prediction under strict inference-time constraints.The passage identifies online recommendation constraints as the reason for this distinction.Source: §2 · pp. 2–3

3 PRELIMINARIES

The preliminaries introduce CTR prediction and SimHash fingerprints. CTR is formulated as supervised click-probability prediction, and SimHash provides a compact, locality-sensitive representation for comparing item embeddings.

3 PRELIMINARIES

  • The preliminaries cover CTR prediction and explain how SimHash generates fingerprints from embedding vectors.The section introduces the CTR formulation before describing fingerprint generation.Source: §3 · p. 3

3.1 Formulation of CTR Prediction Task

  • CTR predicts the click probability for an impression from its feature vector, and training minimizes cross-entropy over labeled impressions.The model parameters are trainable, with each impression represented by features and a click label.Source: §3.1 · p. 3

3.2 SimHash

  • SimHash maps item embeddings to binary fingerprints, with nearby embeddings likely to receive the same signature.The signature can be decoded as an integer to reduce storage and speed Hamming-distance calculations; similarity between embeddings can be approximated by Hamming distance between signatures.Source: §3.2 · p. 3

4 MODEL

The model section outlines ETA’s architecture and submodules. Its figure identifies behavior-item and target-item embeddings and their SimHash fingerprints.

4 MODEL

  • The model section introduces ETA’s architecture, submodules, and deployment experience.The named components include the Long-term Interest Extraction Unit, Multi-head Target Attention, and Embedding Layer.Source: §4 · p. 3
  • Figure 2 identifies embeddings for a behavior item and target item, alongside their SimHash-generated fingerprints.The behavior-item embedding is d-dimensional and can be hashed into an m-bit integer.Source: Figure 2 · p. 4
  • The figure omits the embeddings’ projections before SimHash for clarity.Source: Figure 2 · p. 4

4.1 Model Overview

The model converts user, item, context, and behavior inputs into hidden vectors, combines them in an MLP, and outputs a click probability usable for ranking.

4.1 Model Overview

  • User/item-side features are converted into hidden vectors by the embedding layer, multi-head target attention, and long-term interest extraction unit, then concatenated for the MLP.The inputs include long- and short-term behavior sequences, user and target features, and context features.Source: §4.1 · p. 4
  • A sigmoid at the MLP's last layer maps its hidden vector to the click probability for a user-item pair.Source: §4.1 · p. 4
  • The predicted probability serves as the ranking score for downstream tasks.Source: §4.1 · p. 4

4.2 Embedding Layer

The embedding layer represents categorical and numerical features with one-hot encodings, then maps sparse vectors into low-dimensional hidden vectors.

4.2 Embedding Layer

  • Categorical features are represented with one-hot encoding.Source: §4.2 · p. 4
  • Numerical features are divided into buckets, which are identified using one-hot encoding.Source: §4.2 · p. 4
  • Because one-hot vectors can be extremely sparse with billions of item IDs, they are mapped to low-dimensional hidden vectors.The embeddings of behavior items are packed into a matrix E_s with dimensions L × d, where L is sequence length and d is embedding size.Source: §4.2 · p. 4

4.3 Multi-head Target Attention

Multi-head target attention uses the target item to attend over behavior items, combining their embeddings into a weighted representation.

4.3 Multi-head Target Attention

  • The target item is the query, while each user behavior item supplies a key and value in multi-head target attention.Source: §4.3 · p. 4
  • Dot-product attention calculates target-to-behavior similarities, then uses normalized similarities as weights for a weighted sum of behavior embeddings.Source: §4.3 · pp. 4–5
  • The target and behavior embedding matrices are E_t ∈ R^(1×d) and E_s ∈ R^(L×d); query, key, and value matrices are Q, K, and V.The softmax converts inner products into weights for V, and d_k is used to avoid large inner-product values.Source: §4.3 · p. 5

4.4 Long-term Interest Extraction Unit

The long-term interest extraction unit retrieves behavior items relevant to the target using SimHash and applies target attention to the selected items.

4.4 Long-term Interest Extraction Unit

  • ETA extends user-behavior encoding from tens of items to thousands or longer, addressing the cost of attention over long sequences.With B close to 1000 and d close to 128 in large-scale online systems, direct multi-head attention over thousands of behaviors is described as infeasible.Source: §4.4 · p. 5
  • Retrieval must align with the CTR model's target and satisfy inference-time limits; prior two-stage indexes use attributes or pretrained embeddings that differ from CTR embeddings.Searching directly with CTR embeddings by inner product requires O(L*B*d) multiplications and is described as too slow for online deployment.Source: §4.4 · p. 5
  • After retrieval, multi-head target attention processes the selected behavior items, and its output represents long-term user interest for the MLP.The selected top-k embeddings are rows of E_s, with E_t as the target-item embedding.Source: §4.4 · pp. 5–6
  • SimHash compresses each embedding into a fingerprint whose similarity approximates embedding similarity, allowing Hamming distance to replace inner-product similarity.A d-dimensional embedding is encoded into an m-bit number.Source: §4.4 · p. 6
  • O(L*B*1) is the stated total complexity of Hamming-distance top-k retrieval, and stored fingerprints require only embedding lookup at inference.Hamming distance is computed by XOR followed by counting the bits set to 1.Source: §4.4 · p. 6

4.5 Deployment

ETA’s retrieval selects nearest behavior items using SimHash signatures while the CTR model’s embeddings continue to update. Deployment also describes hash-vector choices and a compact online representation for signatures.

4.5 Deployment

  • The deployment section covers retrieval training, hash-function selection, and engineering optimizations.Source: §4.5 · p. 6

4.5.1 Joint learning of retrieval part.

  • Retrieval selects the top-k nearest keys without gradient updates, then applies attention and backpropagation to the selected items’ original embeddings.A fixed random matrix initializes SimHash; updated embeddings refresh their signatures so retrieval uses the CTR model’s latest embeddings.Source: §4.5.1 · p. 6
  • SimHash implements LSH [1] through random rotation and projection, using fixed random hash vectors with values sampled around zero for binary signatures.The paper chooses this implementation for scalability and efficient matrix computation, as in Reformer [13].Source: §4.5.2 · p. 6

4.5.2 Selection of “Hash Function”.

  • Table 3 presents corpus sizes for the datasets used in the paper.Source: Table 3 · p. 7
  • Online, each m-length binary signature can be represented with log(m) bits, reducing memory cost and enabling O(1) integer Hamming-distance calculations.The paper says this calculation time can be neglected.Source: §4.5.3 · p. 7

5 EXPERIMENTS

Experiments compare ETA with CTR baselines on public and industrial datasets, online A/B tests, inference time, and ablations. ETA improves over two-stage baselines, including a 3.1% GMV gain over SIM(hard)+timeinfo online, while ablations expose accuracy–latency trade-offs.

5.1 Datasets

  • The public Taobao dataset has 100 million instances and uses 16 recent behaviors as short-term history and 256 as long-term history; the industrial dataset has over 142 billion instances and average histories of 938.The industrial dataset uses the recent 48 and 1024 behaviors as short-term and long-term sequences, respectively.Source: §5.1 · p. 7

5.2 Baselines and Metrics

  • Baselines include pooling, DIN, DIN with long-sequence pooling, SIM(hard), and UBR4CTR; offline evaluation uses AUC and request round-trip inference time, while online tests use CLICK and CTR.The paper compares SIM and UBR4CTR directly, which had not previously been compared in the paper's account.Source: §5.2 · pp. 7–8

5.3 Experimental Setup

  • Taobao negatives were sampled from items in the same category, whereas industrial impressions supplied natural negatives; models were tuned on validation data and trained with Adam.Taobao data were split 80/10/10 by sample timestamp; industrial training used two weeks of logs and the following day for testing.Source: §5.3 · p. 8

5.4 Performance Comparison

  • ETA outperformed SIM(hard) by 0.46% and DIN(Long Sequence) by 0.6% on Taobao; ETA+timeinfo exceeded their timeinfo counterpart and DIN(Long Sequence) by 0.38% and 0.85%.DIN(Long Sequence) improved AUC over DIN by 0.35%.Source: Table 4 · p. 8, §5.4 · p. 8
  • ETA outperformed all baselines on the industrial dataset, with base ETA improving AUC by 0.34% over SIM(hard) and 0.43% over UBR4CTR.ETA+timeinfo improved by 0.35% over SIM(hard)+timeinfo and 0.42% over UBR4CTR+timeinfo.Source: Table 5 · p. 8, §5.4 · pp. 8–9
  • 3.1% extra GMV over SIM(hard)+timeinfo was achieved by ETA+timeinfo in the online A/B test.The same comparison showed 1.8% extra CTR.Source: Table 6 · p. 8, §5.4 · p. 9

5.5 Inference Time Comparison

  • ETA and SIM have comparable inference times of about 19–21 ms, while UBR4CTR takes the longest because it uses feature selection and online IDF/BM25 retrieval.Inference time rises from 8 ms for Avg-Pooling DNN to 11 ms with target attention and 14 ms after adding long-term behavior.Source: §5.5 · p. 9

5.6 Ablation Study

  • On the industrial ablation, ETA's top-k selection gives up about 0.1% AUC versus full-sequence attention while reducing inference time by 46%; inner-product retrieval adds 0.07% AUC but increases inference time by 68%.Longer behavior sequences trade off AUC and inference time, and AUC gains from longer SimHash fingerprints become marginal beyond twice the embedding size.Source: §5.6 · pp. 9–10, Table 7 · p. 9, Figure 3 · p. 9

6 CONCLUSION

ETA models CTR with long-term user behavior in an end-to-end way, using SimHash-based retrieval to reduce complexity. Offline and online experiments confirm its effectiveness, with a 3.1% online GMV improvement over the SOTA model.

6 CONCLUSION

  • 3.1% online GMV improvement over the SOTA model was reported in an A/B test, and ETA serves mainstream traffic.The total GMV improvement was measured in an online A/B test.Source: §6 · p. 10
  • ETA models CTR with long-term user behavior end to end, allowing retrieval to share information seamlessly with the main CTR model.The paper describes this paradigm as friendly to maintaining and evolving CTR models in large-scale online recommender systems.Source: §6 · p. 10
  • SimHash reduces retrieval complexity from O(L*B*d) multiplication to O(L*B) Hamming-distance calculation.L is user-sequence length, B is the number of candidate items per request, and d is item-embedding dimension.Source: §6 · p. 10
Loading 2108.04468v1…