PaperlayerView exact revision on arXiv

Source-linked AI summary

LinRec: Linear Attention Mechanism for Long-term Sequential Recommender Systems

Langming Liu, Xiangyu Zhao, Chi Zhang, Jingtong Gao, Wanyu Wang, Wenqi Fan, Yiqi Wang, Ming He, Zitao Liu, Qing Li

arXiv:2411.01537v1cs.IR

TL;DR

Long-term sequential recommendation must manage the quadratic costs of dot-product attention over lengthy interaction histories. LinRec modifies Transformer attention to achieve linear complexity while preserving its attention properties. Experiments report competitive or superior performance and improved efficiency on public benchmarks.

  • Problem

    Dot-product attention has quadratic complexity in sequence length, making its computational costs high for long-term sequential recommendation.

    Source: §1 · p. 1

  • Method

    LinRec changes attention computation order and normalizes and activates Query and Key to obtain linear complexity while retaining attention properties.

    Source: §1 · p. 2, §3.2 · p. 3, §3.2.1 · p. 4

  • Results

    Experiments on ML-1m and Gowalla report competitive or superior performance with reduced computational and memory costs, and LinRec outperforms two state-of-the-art efficient Transformer methods.

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

  • Takeaways & Limitations

    The authors conclude that LinRec improves efficiency while keeping accuracy, and that its equivalence conditions may inform efficient attention mechanisms beyond long-term SRSs.

    Source: §6 · p. 9

    Linear-complexity mappings are hard to satisfy the stated equivalence conditions strictly, so the design relaxes those conditions while approximating attention’s learning capabilities.

    Source: §3.2.1 · p. 4

Abstract

from arXiv · show

Transformer models have achieved remarkable success in sequential recommender systems (SRSs). However, computing the attention matrix in traditional dot-product attention mechanisms results in a quadratic complexity with sequence lengths, leading to high computational costs for long-term sequential recommendation. Motivated by the above observation, we propose a novel L2-Normalized Linear Attention for the Transformer-based Sequential Recommender Systems (LinRec), which theoretically improves efficiency while preserving the learning capabilities of the traditional dot-product attention. Specifically, by thoroughly examining the equivalence conditions of efficient attention mechanisms, we show that LinRec possesses linear complexity while preserving the property of attention mechanisms. In addition, we reveal its latent efficiency properties by interpreting the proposed LinRec mechanism through a statistical lens. Extensive experiments are conducted based on two public benchmark datasets, demonstrating that the combination of LinRec and Transformer models achieves comparable or even superior performance than state-of-the-art Transformer-based SRS models while significantly improving time and memory efficiency.

1 INTRODUCTION

Long-term sequential recommendation must identify important interactions in lengthy histories without losing useful information. LinRec modifies Transformer attention to reduce complexity while retaining attention properties, and experiments report competitive or superior recommendation performance with lower computational and memory costs.

1 INTRODUCTION

  • Long-term histories contain interactions of unequal importance, so recommendation requires identifying important interactions without losing valuable sequence information.The goal is better sequence representations for next-item recommendations.Source: §1 · p. 1
  • When sequence length N far exceeds embedding size d, dot-product attention has O(N^2) computational and memory complexity.This makes costs rise sharply with sequence length in long-term recommendation.Source: §1 · p. 2
  • Existing linear-complexity approaches may add steps and sacrifice accuracy or stability; Linformer’s Query and Key projections are described as impairing accuracy.The introduction also frames LinRec as preserving attention learning capabilities and being applicable to existing Transformer-based recommenders.Source: §1 · p. 2
  • LinRec changes the attention operation order, applies row-wise and column-wise normalization to Query and Key, and adds activation to reduce complexity to O(N).The paper says these modifications preserve attention properties and provide sparsity.Source: §1 · p. 2
  • On ML-1m and Gowalla, LinRec with Transformer models achieves competitive or superior performance while reducing computational and memory costs.The authors report empirical evaluations against representative Transformer-based SRS models.Source: §1 · p. 2

2 PRELIMINARY

The preliminary section describes standard dot-product attention and its costs, then characterizes long-term sequential recommendation by the length of the interaction history relative to embedding size.

2.1 Dot-Product Attention

  • Standard attention forms an N × N Query-Key attention matrix whose scores represent relationships between sequence elements, then applies it to Values.The projections produce Query, Key, and Value matrices from the input sequence; attention output retains its dimension.Source: §2.1 · p. 2
  • When N is much larger than d, attention complexity is O(N^2), creating time and memory costs; softmax also concentrates scores on a few positions.The passage says standard attention is impractical for sufficiently long sequences.Source: §2.1 · pp. 2–3

2.2 Long-term Sequential Recommender Systems

  • Long-term SRSs use extended interaction histories, with N/d greater than 1.5 given as a common threshold.The threshold varies with application and context; the passage gives d = 64 and at least 100 interactions as an example.Source: §2.2 · p. 3

3 METHODOLOGY

LinRec takes a user’s interaction sequence and predicts the top-k items most likely to be interacted with at the next time step, using embedding, Transformer, and prediction components.

3 METHODOLOGY

  • LinRec maps a user’s historical interaction sequence to top-k items predicted for the next time step.The candidate items come from the item set V.Source: §3 · p. 3
  • The architecture has an embedding layer for item embeddings, a Transformer layer for sequence representations, and a final prediction layer.The proposed attention mechanism is located in the Transformer layer.Source: §3 · p. 3
  • The attention mechanism is proposed to improve efficiency and applicability for long-term SRSs.Source: §3 · p. 3

3.1 Embedding Layer

The embedding layer initializes sequence representations using trainable matrices for item IDs and positions.

3.1 Embedding Layer

  • The embedding layer uses two parameter matrices, E_s and E_p, as lookup tables for item and position embeddings.Source: §3.1 · p. 3
  • The sequence representation combines item and position embeddings at each position.The displayed sequence construction adds the corresponding E_s and E_p entries.Source: §3.1 · p. 3
  • E_s and E_p are trainable matrices in R^(N×d) that map item IDs and sequence positions into d-dimensional dense vectors.Source: §3.1 · p. 3

3.2 Transformer Layer

LinRec replaces dot-product attention’s mapping with separate transformations that permit reordered computation, aiming to preserve attention’s learning capabilities while reducing cost. It combines row- and column-wise L2 normalization with ELU and can be integrated into Transformer recommenders.

3.2.1 Equivalence Conditions.

  • The design starts from attention’s normalized, non-negative scores and seeks decomposable mappings that allow K^T V to be computed first.This reordering is intended to reduce computation without jeopardizing attention’s learning capabilities.Source: §3.2.1 · pp. 3–4

3.2.2 L2 Normalized Linear Attention Mechanism (LinRec).

  • LinRec uses row-wise L2 normalization for Q and column-wise L2 normalization for K, with ELU activation to control negative values.The paper says this combination satisfies the design requirements for attention properties, efficiency, and numerical stability.Source: §3.2.2 · p. 4
  • The resulting attention matrix satisfies the normalized property, while ELU addresses non-negativity without the zero-gradient concern associated with standard ReLU.The paper also notes that standard ReLU can cause information loss by setting negative elements to zero.Source: §3.2.2 · p. 4
  • LinRec reduces attention complexity to O(N) for long-term SRSs without additional trainable parameters, while retaining item-importance comparisons and numerical stability.The stated time complexity is O(Nd^2), approximated as O(N) when N >> d.Source: §3.2.2 · p. 5
  • The mechanism is integrated into existing Transformer recommenders to generate sequence representations H.The architecture description identifies multi-head attention, LayerNorm, and a feed-forward network in the sequence-representation pipeline.Source: §3.2.2 · p. 5

3.3 Prediction and Model Optimization

The section describes next-item scoring from sequence representations, then specifies cross-entropy training with Adam optimization.

3.3 Prediction and Model Optimization

  • For each candidate item, the model uses the sequence representation and item embedding to calculate a recommendation score and next-item probability.The recommendation target is a probability distribution over the whole item set.Source: §3.3 · p. 5
  • Training minimizes cross-entropy between the predicted recommendation distribution and the ground truth.Source: §3.3 · p. 5
  • Adam optimizes the network parameters, including the attention projection matrices and parameters outside the attention layer.The passage describes Adam as a stochastic method using moment estimation.Source: §3.3 · p. 5

3.4 In-depth Analyses

The analyses contrast L2 normalization with Softmax normalization and report LinRec’s computational complexity and backbone comparisons.

3.4.1 Comparison with Other Normalization Methods.

  • Softmax satisfies the stated condition, but its exponential weighting can concentrate attention on a few positions; L2 normalization is described as producing smoother scores.Source: §3.4.1 · p. 5

3.4.2 Model Complexity Analysis.

  • LinRec has time complexity O(Nd^2), approximated as O(N) for long-term SRSs when N >> d.The paper compares this efficiency with lightweight methods including Linformer, Linear Transformers, and Big Bird.Source: §3.4.2 · p. 5
  • Improvements with LinRec are statistically significant over backbone models except for SASRec Recall.The cited table is identified as an overall performance comparison, but the supplied passages do not give its metric values.Source: §3.4.2 · p. 6, Table 2 · p. 6

4 EXPERIMENTS

Experiments on ML-1M and Gowalla compare LinRec-equipped recommenders with traditional and efficient Transformer baselines, while testing efficiency, component contributions, and attention patterns. LinRec+SASRec leads efficient baselines on both datasets, and LinRec reduces compute costs while retaining or improving recommendation performance.

4.1.1 Datasets and Evaluation Metrics.

  • Evaluation uses chronological interaction sequences from ML-1M and Gowalla, a leave-one-out split, and Recall, MRR, and NDCG at k=10.ML-1M contains about one million movie ratings; Gowalla contains check-ins.Source: §4.1.1 · p. 6

4.1.2 Baselines.

  • The baselines include traditional and efficient Transformer-based sequential recommenders, with SASRec used as the backbone for the efficient-method comparison.The listed efficient baselines include Linear Transformer and Efficient Attention.Source: §4.1.2 · p. 6, §4.3 · p. 7

4.1.3 Implementation Details.

  • Models use two Transformer layers and eight attention heads; maximum sequence lengths are 200 on ML-1M and 100 on Gowalla.The study uses early stopping based on validation NDCG@10.Source: §4.1.3 · p. 6

4.2 Traditional Transformer Comparison (RQ1)

  • LinRec-integrated recommenders generally outperform their original Transformer counterparts, with LinRec+SASRec best on ML-1M and LinRec+CORE best on Gowalla.The reported improvements are statistically significant at p < 0.05.Source: §4.2 · pp. 6–7

4.3 Efficient Transformer Comparison (RQ2)

  • LinRec+SASRec consistently outperforms other efficient approaches on ML-1M and Gowalla, with about 10% average improvement over other baselines on ML-1M.The comparison reports statistically significant improvements at p < 0.05.Source: §4.3 · p. 7, Table 3 · p. 7

4.4 Scalability Study (RQ3)

  • On ML-1M, LinRec reduces GPU memory and time costs to approximately one-third for most baseline models, and reduces SASRec computation across tested sequence lengths.The sequence-length settings range from 140 to 240.Source: §4.4 · p. 7, Figure 3 · p. 7

4.5 Ablation Study (RQ4)

  • On Gowalla, the LinRec+SASRec ablation study shows that both L2 normalization and ELU contribute to performance, with L2 normalization particularly crucial for LinRec.The study compares variants without L2 normalization and without ELU, reporting Recall@10, MRR, and NDCG@10.Source: §4.5 · p. 7

4.6 Case Study (RQ5)

  • In one ML-1M case study, LinRec attention is smoother than SASRec’s and, across Transformer layers, attends to both short- and long-term patterns.The illustrated user sequence has length 50; the authors contrast LinRec’s spread of attention with SASRec’s concentration on a few, often recent, items.Source: §4.6 · p. 8

5 RELATED WORKS

Transformer-based sequential recommenders use attention to represent user-item sequences, but traditional dot-product attention is computationally inefficient. Efficient Transformer research reduces this cost through varied attention approximations, while LinRec is presented as preserving attention properties and performance as it reduces cost.

5.1 Transformer-based SRSs

  • Transformer-based SRSs use attention to distinguish item importance and represent long- and short-term preferences, but dot-product attention makes attention-matrix computation inefficient.The cited examples include ATTRec, SASRec, BERT4Rec, FDSA, BST, SSE-PT, and CORE.Source: §5.1 · p. 8

5.2 Efficient Transformers

  • Efficient Transformer approaches include sparse fixed or learnable patterns, neural memory, low-rank approximations, and kernel-like rearrangements of dot-product operations.Other strategies mentioned include efficient retraining and sequence chunking.Source: §5.2 · pp. 8–9
  • The paper positions LinRec as reducing computational costs while preserving attention properties and performance, unlike existing efficient methods that may sacrifice accuracy or efficiency.The related-work discussion describes those trade-offs as applying to existing efficient Transformer methods.Source: §5.2 · p. 9

6 CONCLUSION

The conclusion frames long-term sequential recommendation as a problem of reducing dot-product attention complexity. LinRec is presented as a linear-complexity mechanism that captures more information from long-term sequences, with experiments reporting improved efficiency while keeping accuracy and outperforming two efficient Transformer-based methods.

6 CONCLUSION

  • LinRec reduces attention complexity to O(N) while capturing more information from long-term sequences for recommendation.The conclusion presents this as a way to generate better sequence representations efficiently.Source: §6 · p. 9
  • Experiments report that LinRec improves efficiency while keeping accuracy and outperforms two state-of-the-art efficient Transformer-based methods.The conclusion also identifies equivalence conditions and statistical interpretation as theoretical support for the mechanism.Source: §6 · p. 9

A STATISTICAL INTERPRETATION

LinRec’s attention scores are interpreted statistically through probability conditions, with attention positions represented as events. The section also links shared conditional probabilities to fewer parameters and more efficient computing.

A STATISTICAL INTERPRETATION

  • LinRec’s attention scores satisfy probability properties: each row’s position probabilities sum to at most 1, and each position probability is nonnegative.The text identifies these as corresponding probability properties of dot-product attention as well.Source: A STATISTICAL INTERPRETATION · p. 9
  • The analysis models attention to position k as an event and represents attention through d independent sub-events tied to latent features of the hidden states.It defines probabilities for the sub-events and conditional probabilities of attention given each sub-event, then applies Bayes’ theorem.Source: A STATISTICAL INTERPRETATION · p. 9
  • The section states that all LinRec components have statistical meaning and that Eq. (18) holds for every position i.It introduces a further property of LinRec without specifying that property in these passages.Source: A STATISTICAL INTERPRETATION · p. 9
  • A shared conditional probability can reduce parameter numbers, resulting in more efficient computing.Source: A STATISTICAL INTERPRETATION · p. 9

Related papers

Loading 2411.01537v1…