PaperlayerView exact revision on arXiv

Source-linked AI summary

SequenceO1: End-to-End Ultra-Long (100K) Sequence Modeling in Recommendation with Low-Rank Caching

Lin Guan, Jia-Qi Yang, Zhishan Zhao, Jiaqi Huang, Hangyu Wang, Longbin Li, Beichuan Zhang, Haonan Jiang, Jinan Ni, Xiangyu Fan, Xiaowen Li, Ziyao Ren, Yuhang Qi, Xiaolong Zhu, Xuanyuan Luo, Qiwei Chen, Yi Cheng, Lele Yu

arXiv:2609.08443v1cs.IRcs.AI

TL;DR

Ultra-long recommendation must model up to 100K interactions without repeatedly materializing and processing raw histories under production constraints. SequenceO1 compresses histories into reusable target-agnostic sketches, reasons over recent and long-term signals, and combines caching with system amortization. Production results show consistent gains while retaining most of the benefit of direct 100K scaling.

  • Problem

    Production ranking at 100K must handle raw-history storage, communication, and processing costs while preserving an end-to-end optimization path.

  • Method

    SequenceO1 uses Sketch Attention to create a fixed-size target-agnostic sketch, applies STCA to recent and ultra-long branches, and reuses sketches through cache-first system design.

  • Results

    SequenceO1 delivers consistent offline and online gains, while the compact cached sketch retains most of the benefit of directly scaling end-to-end ranking to 100K.

  • Takeaways & Limitations

    The framework provides a practical model-system approach for efficient attention, sequence compression, and scalable long-context recommendation under production constraints.

  • Takeaways & Limitations

    Explicit length-wise projections remain unsuitable for variable 100K histories because their parameters depend on maximum length and require padding or truncation.

Abstract

from arXiv · show

Modeling long-term user behavior is central to sequential recommendation and billion-scale industrial recommender systems, yet production ranking models operate under strict latency, memory, communication, and training-throughput constraints. At the 100K scale, the challenge extends beyond attention complexity: raw sequence features must be stored, transferred, and repeatedly processed during training and online serving. Existing approaches based on history truncation, multi-stage behavior retrieval, compressed lifelong histories, or train-short/infer-long extrapolation either weaken end-to-end optimization or retain substantial length-dependent cost. We present SequenceO1, an end-to-end framework for ultra-long user behavior sequence modeling, deployed at full traffic on Douyin with histories of up to 100K interactions. SequenceO1 follows a compress-then-reason design. Its Sketch Attention (SA) uses learnable prototypes and prototype-wise normalization to compress the raw history into a fixed-size, target-agnostic user representation. Target-conditioned Stacked Target-to-History Cross Attention (STCA) then models complementary time scales: a recent 10K suffix for short-term interests and the compact sketch for long-term preferences. To make training and inference practical, SequenceO1 combines low-rank user representation caching, multi-request user-level batching, pipeline lift, and a fused FlashSA kernel to amortize feature storage, communication, and computation across targets, training instances, and consecutive requests. Production experiments show consistent offline and online gains, while the compact cached sketch retains most of the benefit of directly scaling end-to-end sequence ranking to 100K. These results provide a practical model-system approach to efficient attention, sequence compression, and scalable long-sequence and long-context recommendation systems.

1 Introduction

SequenceO1 addresses the storage, communication, and computation costs of end-to-end 100K sequence ranking by combining fixed-size user-history compression with cache-first reuse. It preserves most of direct long-sequence quality while enabling production-scale training and serving.

  • Results: At 100K truncation, SequenceO1 retains 83% of directly scaled STCA’s gain: +1.07% versus +1.29% Finish AUC.The comparison is from the ablation setting against the STCA(512) baseline.
  • Motivation: At 100K, ultra-long ranking must avoid repeatedly storing, transferring, and processing raw histories, not merely reduce per-layer attention complexity.Direct STCA remains length-dependent and target-conditioned, while multi-stage transfer can weaken end-to-end optimization.
  • Approach: SequenceO1 compresses the full history into a fixed-size, target-agnostic sketch, then applies target-conditioned reasoning to the sketch and recent 10K suffix.The sketch is produced by Sketch Attention and supports complementary long- and short-term signals.
  • System Design: Training-side local KVCache and serving-side sketch reuse amortize user-only computation across instances, targets, and consecutive requests.MRLB, multi-request batching, pipeline lift, and FlashSA further reduce repeated system work.
  • Results: SequenceO1 enables end-to-end sequence ranking to move from the 10K regime to 100K under real production constraints while retaining most direct-scaling quality gains.The reported trade-off covers both cheaper execution and preserved ranking quality.

2 Background and Notations

The paper frames ultra-long ranking around a 100K history, a 10K recent suffix, and a fixed-size sketch, while contrasting quadratic self-attention with linear but still length-dependent STCA.

  • Problem Setting: The fine-ranking stage scores candidate videos using user, request, item, and interaction-history features under strict latency and cost constraints.Training and serving truncate each user history to a maximum length of 100K.
  • Notations: The notation distinguishes raw history length n, recent suffix length L_r=10K, sketch length k, and STCA input length L.The ultra-long history is represented by a sketch whose length is treated as constant with respect to n.
  • STCA Recap: Standard self-attention costs O(L^2), whereas STCA removes history–history attention and uses single-query target-to-history cross attention.STCA therefore scales linearly with its input history length per layer.
  • STCA Recap: At 100K, direct STCA remains too expensive because target-conditioned cross attention scales with raw history length and offers little reusable computation across targets.This motivates separating user-side compression from target-conditioned reasoning.
  • Related Background: Length-wise compression methods use learned summary representations or latent arrays to trade sequence length for manageable computation, but target-agnostic reuse is central to this setting.The paper positions learned compact summaries as a route to reusable ultra-long history representations.

3 Method

SequenceO1 uses Sketch Attention to convert a 100K history into a differentiable, fixed-size user sketch, then applies target-conditioned STCA at recent and ultra-long time scales.

  • Method Overview: SequenceO1 compresses the ultra-long history into a compact fixed-size representation before performing target-conditioned reasoning.The compression depends only on user-side signals, allowing reuse across targets and consecutive requests.
  • Sketch Attention: Sketch Attention uses learnable prototypes as summary slots shared across targets and requests, producing a user-history representation independent of the target.The prototypes can range from several hundred to several thousand.
  • Sketch Attention: Prototype-wise normalization allocates every history token across prototypes, encouraging coverage of the full history before target conditioning.This differs from token-wise normalization, which can select tokens early.
  • Sketch Construction: Weighted aggregation produces a fixed-size, target-agnostic, fully differentiable sketch suitable for caching and end-to-end training.The sketch acts as a data-dependent length-wise projection from n tokens to k much smaller tokens.
  • Low-Rank Caching: The cached sketch is materialized once and reused so target-conditioned reasoning operates on compact inputs rather than the raw ultra-long history.This is the operational meaning of low-rank caching.
  • Sketch Refinement: Residual refinement improves sketch capacity, with the paper reporting that N_sa=2 is sufficient in practice for ultra-long histories.The residual structure preserves information across iterations while the FFN adds representational capacity.
  • Two-Time-Scale Reasoning: Two-time-scale reasoning applies STCA directly to the recent 10K suffix and separately to the adapted fixed-length sketch before downstream fusion.The sketch branch has cost independent of the original sequence length once the sketch is available.

4 System

SequenceO1 makes 100K history modeling practical by reusing user-only sketches across targets, requests, and training instances while optimizing the compression path for memory and throughput. Cache reuse, pipeline lift, MRLB, and FlashSA together reduce repeated raw-history processing and support billion-scale deployment.

  • System integration: Together, caching, batching, pipeline lift, and fused kernel execution make the 100K sketch path reusable, cache-friendly, and hardware-efficient at billion scale.The system design is intended to amortize expensive ultra-long compression across training and inference.
  • Caching and reuse: User-only ultra-long sketches are cached locally and reused across targets, while request-specific recent-suffix and candidate features remain uncached.The cache is keyed by user, model version, history timestamp, and sketch configuration, with TTL-based invalidation and capacity eviction.
  • Caching and reuse: Training and serving share a cache interface, with observed hit rates of about 0.5 and 0.6, respectively.The reported FLOP reductions use these operating points.
  • Caching and reuse: Multi-request user-level batching computes the ultra-long sketch once for consecutive requests from the same user, while request-specific components are computed separately.Aggregation is capped for memory stability, and request-aware masking prevents cross-request leakage in the recent-history branch.
  • Pipeline lift: Pipeline lift moves user-only sketch computation upstream, allowing cache hits to remove raw-length feature storage, communication, and computation from the sample path.On misses, user-only computation can run in parallel with upstream retrieval, reducing its latency impact.
  • FlashSA: FlashSA streams affinity, normalization statistics, and aggregation without storing the full k×n score matrix, reducing peak memory and improving throughput.Fewer kernel launches, better locality, and numerically robust softmax and accumulation also stabilize mixed-precision execution.

5 Experiments

Experiments evaluate Sketch Attention, compression alternatives, full-rank offline performance, and online deployment against production baselines. SequenceO1 improves ranking quality while retaining most of direct 100K scaling benefits and supporting production gains.

  • Sketch Attention vs. Vanilla Attention: Prototype-wise normalization improves UAUC across multiple engagement objectives under the 100K setting.The diagnostic treats normalized weights descriptively; task-level evidence comes from multi-objective UAUC improvements.
  • Ablations and Compression Methods: The final SA configuration achieves +1.07% Finish AUC over STCA(512), while larger prototype or depth settings add only +0.03% or +0.02%.The production configuration retains the smaller setting as a cost–quality choice; removing action-side fusion reduces performance by -0.20%.
  • Ablations and Compression Methods: SA performs best among the compared 100K compression methods under the same 1K × 128 representation budget.The comparison includes Kmeans, neighboring-behavior means, position-bucket queries, Lightning Attention, and recent-behavior-initialized queries.
  • Offline Performance on Douyin Dataset: SequenceO1 improves every evaluated objective after replacing production TWIN V2 with the end-to-end 100K sketch branch.The full production comparison reports relative AUC and UAUC improvements across engagement objectives.
  • Online Performance: Finish rises by +2.33% on Douyin and +3.49% on Douyin Lite in the one-month online deployment.Activeness, Duration, Comment, and Like also improve while Dislike decreases, with gains stable across activity segments.
  • Relation to Two-Stage Transfer: SequenceO1 retains 83% of directly scaled STCA’s gain at 100K truncation: +1.07% versus +1.29% Finish AUC.The compact sketch preserves most direct sequence-length scaling benefit while maintaining a cacheable path.

6 Related Work and Discussion

Prior recommendation systems lengthen, retrieve, compress, cache, or transfer user representations to manage serving constraints. SequenceO1 differs by retaining an end-to-end optimization path while using a reusable fixed-size sketch for ultra-long histories.

  • Background: Attention-based sequential recommenders evolved from target-conditioned interest models to Transformer-based behavior modeling.The related work situates SequenceO1 within established attention and sequential recommendation approaches.
  • Long-History Recommendation: Long-history systems increasingly retrieve, sample, or compress target-relevant behaviors to control serving costs.TWIN V2 uses offline hierarchical clustering followed by online retrieval and cluster-aware target attention.
  • Caching Strategies: Caching methods differ in whether cached objects are end-to-end over raw histories and whether their size scales with sequence length.Existing approaches include incremental user states, grouped or clustered summaries, cached tokens, and Transformer KV prefixes.
  • SequenceO1 Positioning: SequenceO1 keeps the ultra-long sequence path jointly optimized with the final ranking objective instead of using a separate upstream user model.It uses a simpler cacheable sketch as an alternative to multi-stage representation transfer and the previous TWIN V2-style module.

7 Conclusion

SequenceO1 frames ultra-long recommendation as a compress-then-reason problem: compact, fixed-size history representations reduce length-dependent computation while preserving useful ranking signals. Its low-rank perspective motivates summarizing 100K histories into k≪n representations before target-conditioned reasoning.

  • Conclusion: SequenceO1 scales end-to-end sequence recommendation to 100K histories by combining Sketch Attention, two-time-scale STCA reasoning, and cache amortization.The framework is deployed in production and is described as supporting extension toward million-scale histories.
  • Self-Attention as a Length-Wise Mapping: Self-attention applies a length-wise transformation to value representations, but a dense n×n attention matrix can incur quadratic complexity.The attention matrix may have rank up to n, motivating lower-dimensional alternatives.
  • Low-Rank Approximation along the Length Dimension: Low-rank attention methods suggest that sequence interactions may be represented over k positions rather than n, with fixed k remaining sufficient as n grows.This intuition is attractive for ultra-long histories because they may contain substantial redundancy.

A.3 Limitations of Explicit Length-Wise Projections

Explicit length-wise projections are poorly matched to industrial 100K histories because they depend on maximum length, handle variable sequences inefficiently, and do not naturally produce reusable user-only states. SequenceO1 instead uses input-dependent Sketch Attention to create fixed-size, cacheable representations for downstream reasoning.

  • Limitations of Explicit Length-Wise Projections: Explicit projections scale with maximum sequence length, require padding or truncation for variable histories, and do not naturally yield reusable target-agnostic states.These limitations motivate a length-agnostic, data-dependent, cacheable compression mechanism.
  • Sketch Attention: Sketch Attention constructs a data-dependent assignment from history embeddings and learnable prototypes, producing a fixed-size sketch regardless of input length.Its parameters are independent of n, while the output has shape k×d.
  • Relation to Low-Rank Projection: Unlike explicit projections, Sketch Attention is an input-dependent compression front-end whose user-only output can be cached and reused across targets and requests.The low-rank connection is structural rather than an exact Linformer instantiation or approximation guarantee.
  • Normalization Choice: Prototype-wise normalization makes each token distribute mass across prototypes, encouraging broad history coverage before target-conditioned selection.Token-wise normalization can let multiple prototypes focus on the same salient subset and underrepresent other history regions.
  • Interpretation and Scope: The diagnostic maximum normalized weight does not provide calibrated evidence of specialization, overlap, or retrieval quality, and larger maxima do not guarantee diverse coverage.Prototype-wise normalization is supported at task level by UAUC improvements, while proposed downstream interfaces are not evaluated.

D Implementation Details of Action-Side Fusion

Action-side fusion incorporates feedback type into each historical behavior before sketch construction, while stacked Sketch Attention iteratively allocates tokens to prototypes and aggregates them into a refined user summary.

  • Action-Side Fusion: Action-side SwiGLU fusion combines item and action embeddings so the same item can contribute differently for finish, skip, like, or follow feedback.Removing this gated fusion defines the corresponding ablation.
  • Iterative Allocation–Aggregation: Each Sketch Attention refinement assigns history tokens across prototypes and aggregates token embeddings into fixed sketch slots.The process alternates allocation and prototype-side summarization of the history.
  • Stacked Refinement: Stacked Sketch Attention repeats allocation and aggregation so refined prototype states can adjust subsequent token grouping and summarization.The EM-like interpretation is conceptual; the model is trained end-to-end with gradient descent and additional neural layers.
  • Refinement Depth: One or two refinement rounds can provide substantial gains because behavior sequences are redundant and the sketch targets salient long-range signals rather than token-level recovery.Additional iterations yield diminishing returns.

F Error Decomposition

The error analysis separates SequenceO1’s approximation error from sketch compression and downstream reasoning, while the FLOPs analysis describes how cached sketches and reordered attention reduce repeated length-dependent work. This frames efficiency as a balance between preserving information and limiting target-conditioned computation.

  • Error Decomposition: SequenceO1’s approximation error has two sources: information lost during fixed-size compression and modeling error during reasoning over the compressed representation.The decomposition compares an ideal full-history predictor with the best predictor available from the compressed sketch.
  • Error Control: Sketch quality controls compression error, while STCA over the recent 10K suffix and ultra-long sketch addresses downstream reasoning error.The design allocates target-aware capacity to compressed representations rather than repeatedly scanning the raw ultra-long sequence.
  • STCA Reordering: Reordered single-query attention removes O(LD^2) length-dependent projections and replaces them with O(LD d_h) weighted reductions, reducing those FLOPs by approximately d_h=D/h.The reordered path avoids materializing length-L key and value projection intermediates.
  • Cache Hits and Misses: A cache miss computes SA, adaptation, and sketch-STCA, whereas a cache hit reuses the sketch and computes only adaptation plus sketch-STCA.Expected FLOPs equal hit-path cost plus the miss-only SA cost weighted by one minus the hit probability.

G.5 Hyperparameter instantiation for analysis

The analysis instantiates SA+STCA with a fixed 1,024-token sketch and evaluates how caching and multi-request batching change compute as raw history length grows.

  • Hyperparameter settings: SA uses width d = 128, two layers, and sketch length L_s = 1024, while STCA uses four layers with 16 heads and width D = 1024.The analysis also assumes training and inference cache-hit rates of 0.5 and 0.6, respectively.
  • Cache-aware cost: The expected compute equals cache-hit cost plus the uncached SA cost weighted by 1 − p_hit.This makes cache-hit sensitivity explicit while keeping STCA on the fixed sketch length.
  • Complexity comparison: STCA-only scales linearly with history length and layer count, with width D governing both history-side transforms and query-side transforms.Its dominant terms are the per-layer history-side pre-FFN and query–history interaction costs.
  • Complexity comparison: Both SA and STCA are O(L), but SA is a lightweight compressor at smaller width d, whereas STCA performs heavyweight target-conditioned reasoning at width D.SA produces a fixed-size sketch, concentrating expensive representational capacity in target–history interaction over compressed inputs.
  • Cache-aware cost: On cache hits, SA+STCA compute is independent of raw history length and consists of the adapter plus STCA over the fixed sketch.Cache misses add the length-dependent SA computation.
  • Multi-request reuse: Within MRLB, user-only computations are reused across target instances, while optimized STCA exposes fewer reusable components than SA+STCA.For SA+STCA, SA and the adapter are reusable; sketch-STCA retains target-dependent computation.

G.7 Cache-Hit Sensitivity and Miss Cost

The cache-hit analysis shows that caching and multi-request reuse reduce the cost of ultra-long modeling without returning the system to target-conditioned computation over the raw 100K history.

  • Cache-hit sensitivity: Cache hits remove raw-length SA sketching, while cache misses reintroduce only lightweight user-only SA computation.The heavyweight target-conditioned STCA branch continues operating on fixed sketch length L_s in both cases.
  • Cache-hit sensitivity: Lower cache-hit rates reduce the amortization benefit smoothly but do not restore target-conditioned reasoning over the raw 100K history.This preserves the fixed-sketch execution path even when cache misses occur.
  • Reuse boundary: With single-query reordering, MRLB cannot reuse explicit per-layer history-side K/V projections in STCA; only target-independent pre-FFNs are amortized.The remaining attention interaction is query-dependent, whereas SA sketching can be amortized across requests.
  • Without MRLB: At 100K, the expected training-side FLOP ratio is approximately 49.94× without MRLB when the cache-hit rate is 0.5.The comparison uses direct STCA versus the SequenceO1 ultra-long branch under the stated training-side assumptions.
  • Inference-side amortization: Inference-side amortization gives approximately 43.076 GFLOPs/target for STCA and 0.67419 GFLOPs/target for SequenceO1.These values use serving-side reuse ratio R_infer = 300 and the stated inference cache assumptions.
  • Training-side MRLB: Under training-side MRLB with reuse ratio R_train = 40, the expected FLOP reduction increases to approximately 63.89×.Reordering leaves STCA with only per-layer pre-FFNs reusable, while SequenceO1 amortizes all SA sketching and reasons over the fixed sketch.
Loading 2609.08443v1…