Skip to content

LIME: Link-based User-item Interaction Modeling with Decoupled XOR Attention for Efficient Test Time Scaling

Conference: NeurIPS 2026
arXiv: 2510.18239
Code: https://github.com/facebookresearch/repo
Area: recommender
Keywords: recommender systems, test time scaling, linear attention, link embeddings, decoupled attention

TL;DR

LIME resolves the fundamental expressiveness-efficiency dilemma in recommendation test time scaling by introducing global learnable link embeddings as an intermediary, using decoupled XOR attention on the user side for \(O(\ell \cdot N)\) linear long-history modeling and caching offline candidate attention weights on the item side for constant-time \(O(\ell)\) scoring.

Background & Motivation

Modern commercial recommendation platforms must rank massive candidate sets of tens of thousands to hundreds of thousands of items within strict multi-millisecond latency budgets. To navigate the trade-off between predictive capacity and inference efficiency, industrial systems have long been divided into two conflicting paradigms. At one extreme, two-tower models (TTSN) decouple user and item representations into separate vector spaces, allowing rapid candidate scoring via dot products and approximate nearest neighbor (ANN) retrieval. However, confining user-item interaction to a shallow late dot product completely prevents deep, target-aware cross-attention between candidates and specific user behaviors. At the other extreme, deep sequential Transformers such as BST and HSTU achieve superior accuracy by applying multi-layer self-attention across user interaction history (UIH) and computing deep cross-attention for each candidate. Nevertheless, their serving latency scales quadratically with history length (\(O(N^2)\)) and linearly with candidate set size (\(O(M \cdot N)\)), making it computationally prohibitive to deploy them over long user histories or large candidate pools at test time.

This architectural barrier severely restricts recommendation systems from scaling across three vital dimensions: expanding candidate set size, processing longer user interaction sequences, and deepening model capacity. While two-stage retrieval cascades (e.g., SIM, TWIN) attempt to compress history via search units, their general-search stage still incurs an \(O(M \cdot N)\) latency bottleneck and discards rich intra-history self-attention. Hybrid models such as IntTower add shallow interaction layers above two-tower representations, but offer only marginal expressiveness gains. The quadratic self-attention cost and the uncacheable online candidate-to-history cross-attention remain the primary computational bottlenecks hindering scalable test time inference.

Guided by low-rank singular value decomposition and information bottleneck principlesโ€”which reveal that the top 32 singular values account for over 90% of variance in full attention matricesโ€”this paper introduces a decoupled architecture based on global link embeddings. Core idea: introduce a compact sequence of globally learned link embeddings as an intermediary, factorizing user history modeling into an \(O(\ell \cdot N)\) bidirectional XOR linear attention while fixing candidate-side keys to static links to enable offline precomputation and caching of Query-Key attention weights, shrinking per-candidate online scoring cost to a near-constant \(O(\ell)\).

Method

Overall Architecture

LIME decouples user-item interaction modeling into two stages bridged by a small, fixed set of globally learnable auxiliary vectors called link embeddings \(L \in \mathbb{R}^{\ell \times d}\) (where \(\ell \ll N(U)\), typically \(\ell=32\)). On the user side, raw link embeddings are first combined with user context features to generate contextualized links \(L^C\), which then interact with the user's long interaction history \(E \in \mathbb{R}^{N(U) \times d}\) through deep XOR-attention layers to produce personalized link embeddings \(L^P\). On the candidate side, incoming candidate items \(T \in \mathbb{R}^{M(U) \times d}\) do not attend to the raw user history directly; instead, they treat the static global links \(L\) as Keys and the dynamic personalized links \(L^P\) as Values. Because the Query-Key attention weights depend solely on item features and static link vectors, they are precomputed and cached offline in a high-speed QK Cache. Online serving per candidate is thus reduced to retrieving cached weights and computing a lightweight weighted sum over personalized links.

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    subgraph Offline["Offline Precomputation: Candidate Item Side"]
        direction TB
        C["Item Catalog / Candidates T"]
        L_raw["Global Shared Links L"]
        W_pre["Compute Attention Matrix<br/>ฯ•(TL^T)"]
        Cache[("QK Weight Cache<br/>(Rebuilt per model publication)")]
        C --> W_pre
        L_raw --> W_pre
        W_pre --> Cache
    end

    subgraph OnlineUser["Online Parallel Stage: User Encoding (Concurrently with Retrieval)"]
        direction TB
        U_feat["User Context Features E^C"]
        UIH["User Interaction History E<br/>(N items)"]
        L_ctx["Contextualized Links<br/>L^C = MLP(L โŠ• E^C)"]
        XOR_Block["Decoupled XOR Linear Attention<br/>(Bidirectional E โ†” L^C, eliminates E โ†” E)"]
        LP["Personalized Links L^P<br/>(โ„“ compact vectors)"]
        U_feat --> L_ctx
        UIH --> XOR_Block
        L_ctx --> XOR_Block
        XOR_Block --> LP
    end

    subgraph OnlineScoring["Online Lightweight Stage: Target Interaction & Scoring"]
        direction TB
        Lookup["Lookup Attention Weights from Cache<br/>ฯ•(T_m L^T)"]
        WeightedSum["Weighted Sum over Links<br/>O_m = ฯ•(T_m L^T) L^P"]
        FinalMLP["Shallow Interaction MLP<br/>Prediction p(engagement)"]
        Cache -->|Sub-millisecond access| Lookup
        LP --> WeightedSum
        Lookup --> WeightedSum
        WeightedSum --> FinalMLP
    end

Key Designs

1. Global Link Embeddings and Decoupled Attention: Shifting Online Cross-Attention to Offline Cache Lookup Standard Multi-Head Attention (MHA) forces each candidate item \(T\) to compute attention scores against every token in the user interaction history \(E\), binding computational cost to the product of candidate count \(M(U)\) and history length \(N(U)\). LIME breaks this coupling by introducing an asymmetric Key-Value formulation for candidate-side attention. Rather than using the user's personalized link embeddings \(L^P\) for both Keys and Values, LIME utilizes the static, user-independent global link embeddings \(L\) as Keys, while assigning personalized links \(L^P\) as Values: $\(O = \text{MHA}(T, L, L^P; J; \theta) = \phi(T L^\top) L^P\)$ where \(\phi\) denotes the activation function (scaled Softmax or SiLU) and \(J\) is the all-ones attention mask. Because the attention weight matrix \(\phi(T L^\top) \in \mathbb{R}^{M(U) \times \ell}\) depends strictly on candidate embeddings and global parameters \(L\), it is entirely independent of user-specific dynamics. Consequently, for a catalog of hundreds of millions of items, attention weights can be precomputed offline whenever models or items update and stored in an in-memory key-value cache. During live serving, candidate scoring bypasses expensive matrix multiplications, executing a fast memory lookup followed by a lightweight weighted sum over \(\ell\) vectors. This guarantees that per-candidate serving latency is strictly \(O(\ell)\) and invariant to user sequence length \(N(U)\).

2. Decoupled XOR Attention: Eliminating Quadratic History Self-Attention via Bipartite Cross-Attention To build deep multi-layer representations of long user histories (e.g., 3-layer HSTU transducers), conventional sequence encoders enforce causal self-attention masks \(M_{\text{causal}}\), generating quadratic \(O(N(U)^2)\) complexity as all historical tokens attend to each other. LIME replaces this with an exclusive-or attention mask \(M_{\text{xor}}\) over the concatenated sequence \(X = E \oplus L^C\): $\(M_{\text{xor}}[i, j] := \mathbf{1}_{i \in [0, |E|)} \wedge \mathbf{1}_{j \in [0, |E|)}\)$ This structured XOR mask systematically zeroes out dense history-to-history interactions (\(E \leftrightarrow E\)), decomposing the self-attention block into two complementary cross-attention streams: $\(\text{XORA}(X, X, X; \theta) = \text{MHA}(E, L^C, L^C; J; \theta) \oplus \text{MHA}(L^C, E, E; J; \theta)\)$ Under this formulation, historical interactions \(E\) attend to contextualized links \(L^C\) (\(E \to L^C\)) to modulate item representations with global context, while link tokens attend back to user history (\(L^C \to E\)) to compress sequence information into \(\ell\) personalized vectors. This structural factorization reduces self-attention complexity from \(O(N(U)^2)\) to \(O(\ell \cdot N(U))\), enabling linear scaling across tens of thousands of historical behaviors. Stacking \(n\) such XOR layers with gated MLPs generates deep personalized link embeddings \(L^P = \sum_{j=1}^n \text{GatedMLP}(\text{XORA}(E \oplus L^C); \eta_j)\) that match the expressiveness of full HSTU models.

3. Windowed Attention Hybridization and Hardware-Aware Triton Kernel Optimization While global link embeddings capture overarching user interest themes, fine-grained sequential recommendations also benefit from local behavioral dynamics, such as rapid successive clicks on related items. LIME-XOR+Window enriches the XOR mask with a sliding-window pattern spanning \(\ell\) neighboring tokens on each side. Each history token attends to \(2\ell\) items (\(\ell\) link tokens plus \(\ell\) local neighbors), capturing both global long-range context and local temporal shifts while maintaining strictly linear computational complexity. To optimize hardware efficiency on modern GPUs, the authors engineered custom Triton kernels featuring Block Range Selection: during query block processing, the kernel identifies whether queries belong entirely to source tokens (history) or target tokens (links) and loads exclusively the opposite key-value blocks. This skips irrelevant attention tiles completely, avoiding unneeded Tensor Core cycles and global memory bandwidth consumption, and yielding major speedups over standard FlashAttention implementations.

A Worked Example

Consider an industrial short-video platform serving a user request at inference: 1. Offline Item Preparation: The platform maintains \(\ell=32\) global link embeddings of dimension \(d=256\). For an incoming video candidate \(c\) (e.g., a "half-marathon training guide"), its embedding \(T_c \in \mathbb{R}^{256}\) is projected against global links \(L\) to compute \(\phi(T_c L^\top) \in \mathbb{R}^{32}\). The resulting attention distribution concentrates heavily on Link 30 (Sports & Fitness, weight 0.45) and Link 2 (Long-form Educational, weight 0.38), with near-zero weights elsewhere. These 32 weights are quantized to int8 format and stored in the localized QK Cache, updated every five minutes in GPU memory. 2. Online User Processing: A user session initiates with an interaction history of length \(N=1024\) and context \(E^C\) (device, location, time). Global links are contextualized into \(L^C\) and passed into a 3-layer LIME-XOR module alongside the 1024 history embeddings. This user-side encoding runs concurrently with candidate retrieval RPCs, effectively masking its execution time, and outputs 32 personalized link vectors \(L^P \in \mathbb{R}^{32 \times 256}\). 3. Lightweight Candidate Scoring: The retrieval engine delivers \(M=10,000\) candidates. For video \(c\), rather than executing cross-attention over all 1024 past interactions, the serving engine executes an \(O(1)\) memory lookup to fetch the 32 precomputed weights \([w_1, \dots, w_{32}]\) and performs a fused weighted sum: \(O_c = \sum_{k=1}^{32} w_k L^P_k\). 4. Final Inference: The aggregated 256-dimensional interaction vector \(O_c\) is passed to a shallow ranking MLP. The entire candidate-side scoring executes in just 0.16 ms on GPU, successfully integrating deep contextual interest signals without causing inference latency spikes.

Loss & Training

LIME is trained end-to-end using standard multi-task cross-entropy loss across concurrent engagement objectives, such as Video Completion (VC) and Watch Time (WT): $\(\mathcal{L} = \sum_{k \in \{\text{VC}, \text{WT}\}} \lambda_k \left( - \sum_{i=1}^B \left( y_i^{(k)} \log p_i^{(k)} + (1 - y_i^{(k)}) \log (1 - p_i^{(k)}) \right) \right)\)$ To ensure optimization stability across deep architectures, Layer Normalization is applied prior to linear QKV projections, preventing embedding norm explosion and subsequent attention score collapse. Raw link embeddings \(L\) are initialized from standard normal distributions \(\mathcal{N}(0, I)\) to encourage maximum initial diversity among anchor concepts. Single-layer MHA variants utilize scaled Softmax, while deep multi-layer models use SiLU activation for attention weights. On the industrial dataset containing over 100 billion interactions, LIME is trained in a streaming single-pass regime with an Adam-based optimizer, learning rate \(4 \times 10^{-4}\), and batch size 1024.

Key Experimental Results

Main Results

LIME was evaluated extensively on an industrial recommendation dataset (100 billion interactions, max sequence length 1024) and two public benchmarks: KuaiRand-1K (12M interactions, max sequence length 256) and Taobao-Ad (25M interactions, max sequence length 50). Evaluation metrics include Normalized Entropy (NE, lower is better) for video completion, Watch Time AUC, and Click AUC.

The following table summarizes offline, online A/B testing, and public dataset performance:

Architecture Industrial VC NE Drop Industrial WT AUC Gain Online A/B VC Lift Online A/B WT Lift KuaiRand-1K Click AUC Taobao-Ad Click AUC Candidate Interaction Complexity
TTSN (Two-Tower Baseline) Baseline (0.00%) Baseline (0.00%) Baseline (0.00%) Baseline (0.00%) 0.7389 (+0.00%) 0.6452 (+0.00%) \(O(1)\) (dot product)
DIN (Target Attention) - - - - 0.7404 (+0.20%) 0.6468 (+0.25%) \(O(N)\)
SASRec (Transformer) - - - - 0.7419 (+0.41%) 0.6462 (+0.15%) \(O(N)\)
Truncated MHA - - - - 0.7351 (-0.51%) 0.6456 (+0.06%) \(O(\ell)\)
LREA (Linformer-style) - - - - 0.7408 (+0.26%) 0.6447 (-0.08%) \(O(N)\)
LIME-MHA (1-layer Decoupled) -0.72% +0.46% +28.6% +22.1% 0.7433 (+0.60%) 0.6465 (+0.20%) \(O(\ell)\) (cacheable)
MHA Skyline (Single-layer) -0.73% +0.53% N/A (unserveable) N/A (unserveable) 0.7428 (+0.53%) 0.6464 (+0.19%) \(O(N)\) (uncacheable)
LIME-XOR (3-layer XOR) -1.04% +0.76% +37.9% +28.6% 0.7448 (+0.80%) 0.6467 (+0.23%) \(O(\ell)\) (cacheable)
LIME-XOR+Window (Hybrid) -1.11% +0.80% - - 0.7453 (+0.87%) 0.6468 (+0.25%) \(O(\ell)\) (cacheable)
HSTU Skyline (3-layer HSTU) -1.06% +0.77% N/A (unserveable) N/A (unserveable) 0.7444 (+0.74%) 0.6475 (+0.36%) \(O(N)\) (uncacheable)

Note: MHA Skyline and HSTU Skyline cannot be evaluated online due to excessive serving latency on large candidate pools. In live industrial A/B testing covering over 10 million users, LIME-XOR delivered a platform-wide lift of +0.375% in total watch time (90% CI [0.205%, 0.545%]) and +0.233% in positive session engagements without regressing capacity budgets.

Ablation Study & Serving Benchmarks

The table below details component ablations on the KuaiRand-1K dataset alongside candidate-side serving latencies measured on an NVIDIA PG509-210 Ampere GPU:

Model Configuration / Variant KuaiRand AUC Theoretical Complexity Candidate P50 BF16 Latency @ 10k Items 100M Catalog Int8 Cache Size Mechanism Details
LIME-XOR (Full Model) 0.7448 \(O(N\ell + M\ell)\) 0.162 ms 12.8 GB (32 links) Multi-layer XOR attention + decoupled QK caching
w/ Link Pooling (Sum Pool) 0.7400 \(O(N\ell + M)\) - - Replaces candidate attention with uniform sum pooling
w/ Dot Product 0.7404 \(O(N\ell + M\ell)\) - - Replaces attention with raw dot products into MLP
LIME-MLP (All-MLP Baseline) 0.7407 Fixed MLP - - Replaces attention layers with length-padded MLPs
LIME-XOR-MLP Hybrid 0.7442 Hybrid Decoupled - - XOR user module + candidate weights learned via MLP
Linear Transformer Baseline 0.7423 \(O(NM)\) - - Standard linear kernel attention without item decoupling
Longformer Baseline 0.7443 \(O(NM)\) - - Sliding-window attention; uncacheable cross-attention
LREA (Linformer Baseline) 0.7408 \(O(NM)\) - - Low-rank projection degrades fine-grained signals

When scaling candidate sets from 16 to 65,536 items, HSTU Skyline latency surges from 3.60 s to 23.83 s. In contrast, LIME-MHA latency remains nearly flat, increasing only from 0.84 s to 1.35 s, while LIME-XOR rises moderately from 2.62 s to 5.95 s, confirming that decoupled caching provides effective constant-time candidate scaling.

Key Findings

  • Low-Rank Attention Hypothesis Confirmed: SVD analysis on trained HSTU models reveals that the top 32 singular values capture over 90% of information in self- and cross-attention matrices. Concurrently, the learned link embeddings maintain near full rank with minimal redundancy, yielding a small Jensen-Shannon divergence of 0.055 and high cosine similarity of 0.915 relative to full MHA.
  • Critical Role of Decoupled Attention: Degrading decoupled attention into sum pooling, dot products, or MLPs drops AUC by 0.41โ€“0.48%, proving that target-aware attention weighting over structured link representations is essential for variable-length user interaction histories.
  • Empirical Test-Time Scaling Laws: Scaling sequence length from 1k to 4k items yields major accuracy gains (VC NE improvement of -0.55%) only when link capacity is expanded from 32 to 256. Deepening the XOR Transformer from 3 to 12 layers further improves VC NE by -0.38%, proving that the decoupled architecture obeys predictable compute-scaling properties.

Highlights & Insights

  • Asymmetric Key-Value Decoupling is Brilliant: Substituting user-specific keys with static global link embeddings decouples Query-Key attention calculation from online user state. This enables offline precomputation and caching of cross-attention weights with virtually zero degradation in ranking accuracy.
  • XOR Masking Eliminates Quadratic Redundancy: Rather than approximating full self-attention, the XOR attention mask deliberately removes the dense \(E \leftrightarrow E\) block, relying solely on two-way cross-attention between user history and global links to achieve true \(O(\ell \cdot N)\) linear complexity alongside native Triton memory optimizations.
  • General Blueprint for Test-Time Interaction Decoupling: The design of factorizing online interaction into "dynamic low-rank state encoding + static target projection" provides a general architectural paradigm for low-latency retrieval in large-scale RAG, multimodal search, and conversational memory systems.

Limitations & Future Work

  • Reliance on Low-Rank Assumption: The model presumes user preferences can be compressed into a compact set of link vectors (\(\ell=32\)); domains with extreme interest fragmentation or long-tail behavioral diversity may require substantially larger link spaces.
  • Cache Invalidation and Cold-Start Costs: Item QK weights must be periodically recomputed as items and models update (rebuilt every five minutes in memory). Uncached or rapid real-time cold-start items require fallback online dot products, introducing system heterogeneity.
  • Future Directions: Exploring larger link pools with dynamic contextual routing (Mixture-of-Links) to conditionally activate link subsets per user segment, as well as extending the decoupled framework to multimodal cross-domain recommendation.
  • vs Two-Tower Models (TTSN): Two-tower models isolate user and item processing until a final dot product, offering low latency but completely missing item-specific historical interactions; LIME matches two-tower inference throughput while capturing deep target-aware cross-attention.
  • vs Two-Stage Cascade Models (SIM / TWIN): SIM and TWIN rely on sequential search units where the first-stage retrieval still costs \(O(MN)\) and discards history self-attention; LIME preserves multi-layer user history modeling and reduces candidate scoring to cached \(O(\ell)\) lookups.
  • vs Efficient NLP Transformers (Linear Transformer / Longformer / Linformer): Traditional linear attention mechanisms target NLP self-attention bottlenecks but leave the \(O(MN)\) candidate cross-attention unresolved in recommender settings; LIME's co-designed XOR mask and decoupled link caching address both bottlenecks simultaneously.

Rating

  • Novelty: โญโญโญโญโญ (Decoupled static-key attention enabling offline QK caching and hardware-efficient XOR linear attention)
  • Experimental Thoroughness: โญโญโญโญโญ (100B+ industrial dataset, public benchmarks, live A/B testing on 10M+ users, GPU kernel microbenchmarks, and SVD spectral analysis)
  • Writing Quality: โญโญโญโญโญ (Clear problem framing, detailed mathematical derivations, Triton algorithm pseudocode, and systematic ablation analysis)
  • Value: โญโญโญโญโญ (A practical, production-ready framework for breaking the inference latency wall in large-scale recommendation systems)