PaperlayerView exact revision on arXiv

Source-linked AI summary

Sampling Is All You Need on Modeling Long-Term User Behaviors for CTR Prediction

Yue Cao, XiaoJiang Zhou, Jiaqi Feng, Peihao Huang, Yao Xiao, Dayao Chen, Sheng Chen

arXiv:2205.10249v2cs.IRcs.AI

TL;DR

Long user histories are difficult to use for CTR prediction under online serving-time limits, and retrieval-based methods can lose information or trade effectiveness for efficiency. SDIM uses hash sampling to gather behavior items matching a candidate item, and the paper reports performance on par with DIN(Long Seq.) while being faster. It was deployed in Meituan’s search system, with reported CTR and VBR lifts.

  • Problem

    Serving-time limits make it difficult for real-world CTR systems to use long user behavior histories, while retrieval-based approaches are described as sub-optimal and difficult to balance for effectiveness and efficiency.

    Source: §1 · p. 1

  • Method

    SDIM samples multiple hash functions and gathers behavior items sharing a hash signature with the candidate item to form user interest.

    Source: §1 · p. 2

  • Results

    SDIM performs on par with DIN(Long Seq.) while being sizable times faster, and Meituan deployment brought 2.98% CTR and 2.69% VBR lift.

    Source: §1 · p. 2, §7 · p. 9

  • Takeaways & Limitations

    SDIM is deployed online in Meituan APP, with a separate behavior-sequence hashing module decoupled from the CTR model.

    Source: §1 · p. 2, §7 · p. 9

    Future work includes reducing transmission cost and exploring more complex structures such as multi-head hashing.

    Source: §7 · p. 9

Abstract

from arXiv · show

Rich user behavior data has been proven to be of great value for Click-Through Rate (CTR) prediction applications, especially in industrial recommender, search, or advertising systems. However, it's non-trivial for real-world systems to make full use of long-term user behaviors due to the strict requirements of online serving time. Most previous works adopt the retrieval-based strategy, where a small number of user behaviors are retrieved first for subsequent attention. However, the retrieval-based methods are sub-optimal and would cause more or less information losses, and it's difficult to balance the effectiveness and efficiency of the retrieval algorithm. In this paper, we propose SDIM (Sampling-based Deep Interest Modeling), a simple yet effective sampling-based end-to-end approach for modeling long-term user behaviors. We sample from multiple hash functions to generate hash signatures of the candidate item and each item in the user behavior sequence, and obtain the user interest by directly gathering behavior items associated with the candidate item with the same hash signature. We show theoretically and experimentally that the proposed method performs on par with standard attention-based models on modeling long-term user behaviors, while being sizable times faster. We also introduce the deployment of SDIM in our system. Specifically, we decouple the behavior sequence hashing, which is the most time-consuming part, from the CTR model by designing a separate module named BSE (behavior Sequence Encoding). BSE is latency-free for the CTR server, enabling us to model extremely long user behaviors. Both offline and online experiments are conducted to demonstrate the effectiveness of SDIM. SDIM now has been deployed online in the search system of Meituan APP.

1 INTRODUCTION

Long user histories are valuable for CTR prediction, but serving-time limits and retrieval-based approaches can restrict their use. SDIM hashes the candidate and behavior items to gather matching behaviors, and is reported to perform on par with attention-based methods while speeding up modeling.

1 INTRODUCTION

  • Serving-time limits lead many industrial systems to truncate user behavior sequences to the recent 50 behaviors, losing information.Meituan users may have at least 1,000 or 5,000 behaviors over a year, motivating the use of longer histories.Source: §1 · p. 1
  • Retrieval-based approaches can bias long-term interest estimates and make effectiveness difficult to balance against efficiency.The introduction contrasts a simple retrieval method with an approach whose more complex retrieval module makes inference 4× slower.Source: §1 · p. 2
  • SDIM samples multiple hash functions and gathers behavior items sharing a hash signature with the target item to form user interest.The paper describes this as approximating the softmax distribution with LSH collision probability and producing attention patterns similar to target attention.Source: §1 · p. 2
  • SDIM separates behavior-sequence hashing from the CTR server because hashing is the most time-consuming part of the algorithm.The introduction says this decoupling greatly reduces serving time.Source: §1 · p. 2
  • 2.98% CTR and 2.69% VBR lift were reported after SDIM was deployed in Meituan’s search system.The paper also reports that SDIM performs on par with standard attention-based methods, outperforms competitive baselines on long-term behavior modeling, and provides sizable speedups.Source: §1 · p. 2

2 RELATED WORK

Prior CTR work models interests from historical behavior, while long-term sequential methods address longer histories with differing trade-offs. The section also distinguishes efficient self-attention methods from target attention, whose complexity remains linear in sequence length.

2.1 Click-Through Rate (CTR) Prediction

  • DIN, DIEN, and DSIN model user interests through target attention, interest evolution, and session-based behavior, respectively.The section notes that DIN’s target attention is widely used in CTR models.Source: §2.1 · p. 2

2.2 Long-Term Sequential User Behavior Modeling

  • Long-term behavior methods include MIMN’s limited interest memory and search-based SIM, UBR4CTR, and ETA, with ETA applying LSH end-to-end.MIMN has difficulty modeling interaction between the behavior sequence and target item; SIM and UBR4CTR use search units, while ETA uses LSH to reduce training and inference time.Source: §2.2 · pp. 2–3
  • Efficient self-attention methods reduce complexity from O(L^2) to O(L log(L)), but do not reduce target attention’s O(L) complexity.The section identifies complex deployment and system latency as challenges for long-term behavior modeling.Source: §2.2 · pp. 2–3

3 PRELIMINARIES

The preliminaries formulate CTR prediction as estimating click probability, describe target attention over behavior sequences, and introduce LSH/SimHash as the hashing basis for similarity estimation.

3.1 Task Formulation

  • CTR prediction estimates click probability from input features, with model parameters trained by minimizing cross-entropy loss.The equation’s θ denotes trainable CTR-model parameters.Source: §3.1 · p. 3

3.2 Target Attention

  • Target attention uses the target item as query and behavior items as keys and values, weighting the sequence to form user interest.Its stated complexity is O(BLd), and the section says this is infeasible for long-term online modeling in large-scale systems.Source: §3.2 · p. 3

3.3 Locality-Sensitive Hash (LSH) and SimHash

  • LSH uses locality-preserving hashes, while multi-round SimHash samples hash functions and groups codes into signatures for collisions.SimHash samples m functions; τ codes are grouped to reduce the probability that dissimilar items share a signature.Source: §3.3 · p. 3

4 METHODOLOGY

The methodology separates behavior-sequence hashing from candidate-item processing in a two-server framework. The CTR server uses matching hash signatures to form user interests and predict click probability.

4 METHODOLOGY

  • The framework separates Behavior Sequence Encoding (BSE) and CTR servers.BSE hashes user behavior sequences; the CTR server hashes candidate items and gathers behavior items with matching signatures.Source: §4 · p. 3, Figure 1 · p. 4
  • The CTR server uses user-interest, item, and context features to predict each candidate item's click probability.Source: Figure 1 · p. 4
  • The BSE server calculates hashes for the user behavior sequence, while the CTR server forms interests from matching-signature behaviors.Source: Figure 1 · p. 4

4.1 User Behavior Modeling via Hash-Based Sampling

SDIM estimates user interest by sampling hash functions and gathering behaviors whose signatures match the candidate item. Multi-round hashing reduces collisions with dissimilar items and averages signature outputs for a lower-variance estimate.

4.1.1 Hash Sampling-Based Attention.

  • Multiple hash functions generate signatures for candidate and behavior items, replacing retrieval by similarity metric with direct signature matching.The hash functions are fixed random vectors drawn from a normal distribution, as in ETA.Source: §4.1.1 · p. 4
  • Hash collision probability estimates user interest because similar vectors fall into the same bucket with higher probability.SDIM sums behavior items sharing the candidate item's signature to form the interest representation.Source: §4.1.1 · p. 4

4.1.2 Multi-Round Hashing.

  • Multi-round hashing reduces the chance that dissimilar items collide with the candidate item.Items collide only when their aggregated signatures match; outputs from m/τ signatures are averaged for a lower-variance interest estimate.Source: §4.1.2 · pp. 4–5
  • The ℓ2-normalized model performs on par with sum-normalization and is used because its implementation is more efficient.Source: §4.1.2 · p. 4

4.2 Analysis of Attention Patterns

SDIM's expected attention aligns with target attention, and increasing τ sharpens its attention toward more similar items. Its limiting cases connect the method to SIM (hard) and mean pooling.

4.2.1 Expectation of Hash Sampling-Based Attention.

  • When m/τ ≥ 16, empirical estimation error is very small; the online model uses m = 48 and τ = 3.As the number of signatures increases, the estimate converges to its expected value.Source: §4.2.1 · p. 5
  • SDIM attention weights align well with target-attention softmax weights, producing outputs theoretically close to target attention.Figure 2 visualizes the two attention patterns after shifting the target-attention curve without changing normalized weights.Source: §4.2.1 · p. 5, Figure 2 · p. 5

4.2.2 The Property of 𝜏and Relation to Other Methods.

  • As τ increases, attention-distribution entropy decreases strictly and weight concentrates more sharply on highly similar items.This makes τ a control on how strongly the model favors similar items.Source: §4.2.2 · p. 5
  • At τ → +∞, SDIM attends only to identical items and can behave like SIM (hard) with category hashing; at τ = 0 or m = 1, it becomes mean pooling.These extremes make SDIM flexible across attention patterns by varying τ.Source: §4.2.2 · p. 5

4.3 Implementation and Complexity Analysis

SDIM is reported to be 10x–20x faster than standard attention-based methods for training user behavior modeling in the authors' scenario. Its speed advantage comes from hashing behavior sequences once per request and using a lower-cost hashing operation.

4.3 Implementation and Complexity Analysis

  • Standard target attention requires two matrix multiplications and has time complexity O(BLd).Source: §4.3 · p. 5
  • Because behavior sequences are independent of candidate items, SDIM computes their hashes once per user per request, reducing B to 1 in its time complexity.Matching-signature sequence items are then selected and summed to form user interest; the gather step is described as negligible in Tensorflow.Source: §4.3 · pp. 5–6
  • 10x–20x speedups are achieved in training the user behavior modeling part in the authors' scenario.The hashing operation costs O(Lm log(d)) with Approximating Random Projection, versus O(BLd) for standard attention.Source: §4.3 · p. 6

4.4 Deployment of the Whole System

SDIM separates behavior-sequence hashing from candidate-item hashing, maintaining user-wise behavior hashes in a BSE server and gathering candidate-matched representations in the CTR server. This separation makes BSE latency-free for the CTR server and keeps its candidate-hashing cost independent of behavior-sequence length; transmitted bucket representations have fixed size.

4.4 Deployment of the Whole System

  • BSE maintains user-wise behavior-sequence hashes independently of the candidate item, while the CTR server hashes candidates and gathers representations from corresponding buckets.BSE samples multiple hash functions to assign behavior items to buckets; the CTR server uses candidate signatures to select matching buckets.Source: §4.4 · p. 6
  • SDIM is jointly trained with the rest of the CTR model but deployed as separate modules online, without changing the CTR model’s structure.The CTR model combines item, context, short-term-interest, and long-term-interest features and uses a multilayer perceptron to predict click probability.Source: §4.4 · pp. 6–7
  • The BSE computation is latency-free for the CTR server, and the BSE server runs in parallel with the retrieval module.The paper notes that the serving system resembles MIMN [10], but SDIM models deep interests whereas MIMN models shallow interests.Source: §4.4 · p. 7
  • Candidate-item hashing costs O(Bm log(d)) and is independent of sequence length L, so the CTR server’s long-term-interest computation can handle extremely long behavior sequences theoretically.The paper describes this serving cost as comparable to adding a common feature.Source: §4.4 · p. 7

4.4.1 Remark on Transmission Cost of Servers.

  • The servers transmit fixed-length bucket-representation vectors regardless of behavior-sequence length; the online vector is 8KB and transmission costs about 1ms.The number of hash functions is fixed.Source: §4.4.1 · p. 7

5 EXPERIMENTS

The experiments evaluate SDIM on Taobao and Meituan search data, using AUC and training and inference speed offline and CTR and VBR online. They compare it with short- and long-sequence DIN variants and retrieval-based models under shared features, model structure, and behavior-sequence lengths.

5.1 Dataset and Evaluation Metrics

  • Taobao experiments predict each behavior from preceding behaviors, using the recent 16 as short-term history and 256 as long-term history, with an 80/10/10 time-ordered train/validation/test split.The dataset also adds an is_weekend feature derived from timestamps.Source: §5.1 · p. 7
  • Meituan search data uses consecutive 14-day samples for training and the next two days for evaluation and testing, with about 10 billion training examples and up to 1,024 long-term behaviors.The setup uses 50 recent behaviors for the short-term sequence and adds about 20 important ID features.Source: §5.1 · p. 7
  • Offline evaluation uses AUC and training and inference speed, while online evaluation uses CTR and VBR.Source: §5.1 · p. 7

5.2 Competitive Models

  • Comparisons include DIN variants, SIM, UBR4CTR, and ETA, which model long-term behavior through pooling, retrieval, or target attention.DIN uses only short-term behaviors in its standard baseline; the long-sequence DIN variants use sequence lengths of 256 on Taobao and 1,024 on the industrial dataset.Source: §5.2 · p. 7
  • Models use the same input features and model structure except for the long-term behavior module, and use equal long-term sequence lengths: 256 for Taobao and 1,024 for the industrial dataset.Performance comparison tables are provided for Taobao and the industrial dataset.Source: §5.2 · pp. 7–8, Table 2 · p. 8, Table 3 · p. 8

6 RESULTS AND ANALYSIS

On Taobao and industrial data, SDIM performs on par with DIN(Long Seq.) while outperforming retrieval-based long-term behavior models. Hyperparameter and online experiments also report efficient performance, including gains over the existing Meituan search model.

6.1 Results on Taobao Dataset

  • On Taobao, SDIM performs on par with DIN(Long Seq.) while running 5x faster, and outperforms long-term-behavior baselines SIM, UBR4CTR, and ETA by 1.62%, 1.02%, and 1.01%, respectively.DIN(Long Seq.) brings 2.21% improvement on AUC compared to DIN.Source: §6.1 · p. 8

6.2 Results on Industrial Dataset

  • SDIM performs on par with DIN(Long Seq.) on industrial data and improves over SIM by 1.92%, UBR4CTR by 2.08%, and ETA by 1.38%.The authors attribute retrieval methods' gap to difficulty selecting valuable items for diverse interests and new-category food searches.Source: §6.2 · p. 8

6.3 Hyper-Parameter Analysis

  • For hash counts m > 48, models perform almost the same; the online model uses m = 48 for efficiency.Figure 4 reports AUC results on the industrial dataset as the number of hashes changes.Source: Figure 4 · p. 8, §6.3.1 · p. 9
  • SDIM performs well for 2 ≤ τ ≤ 5 and uses τ = 3 online for effectiveness and efficiency; τ = 1 performs poorly from too many noise behaviors, while τ = 10 performs poorly and is unfriendly to users with few behaviors.Source: §6.3.1 · p. 9

6.4 Experiments on Short-Term User Behavior Modeling

  • On short sequences, SDIM achieves results comparable to standard target attention while being more efficient.The authors describe this as a special-case experiment; SDIM is primarily proposed for long-term interest modeling.Source: §6.4 · p. 9, Table 5 · p. 9

6.5 Online A/B Test

  • SDIM(T=2000) improves CTR by 2.98% (p-value < 0.001) and VBR by 2.69% (p-value < 0.005) over the online base model.The test used 2,000 recent behaviors; inference time increased by 1 ms, mostly due to transmission between BSE and CTR servers.Source: §6.5 · p. 9, Table 6 · p. 9
  • SDIM performs on par with direct target attention on long sequences while saving 95% of online inference time; it is deployed on Meituan home search's main traffic.Direct attention increased inference time by about 50% (25–30 ms), which the system found unacceptable.Source: §6.5 · p. 9

7 CONCLUSIONS

SDIM models long-term user behaviors by gathering items that share a hash signature with the candidate item, and its separate hashing framework is latency-free for the CTR server. It performs on par with DIN(Long Seq.) while being faster, and future work includes reducing transmission cost and exploring multi-head hashing.

7 CONCLUSIONS

  • SDIM gathers behavior items sharing the candidate item's hash signature to form user interest, avoiding complicated retrieval modules.The paper describes this as a hash sampling-based method for modeling long-term user behaviors.Source: §7 · p. 9
  • SDIM performs on par with DIN(Long Seq.) while being sizable times faster, and has been deployed online in Meituan APP.A separate framework decouples behavior-sequence hashing from the CTR model, making it latency-free for the CTR server.Source: §7 · p. 9
  • Reducing transmission cost and exploring more complex structures such as multi-head hashing are identified as future work.Source: §7 · p. 9

Related papers

Loading 2205.10249v2…