PaperlayerView exact revision on arXiv

Source-linked AI summary

SPRINT: Single-Step Generative Recommendation via Average Probability Velocity

Zhuo Cai, Shoujin Wang, Peilin Zhou, Min Xu, Julian McAuley, Fang Chen

arXiv:2609.34306v1cs.IR

TL;DR

SID-based generative recommendation generally needs multiple forward passes, limiting its fit for latency-sensitive systems. SPRINT generates token probabilities in one pass using average probability velocity and a dual-level contrastive objective. Across 8 datasets, it reports faster generation and improved accuracy than competing methods.

  • Problem

    Existing SID recommendation generally needs multiple forward passes, while single-step generation faces discrete-token and inter-token coherence challenges that matter for latency-sensitive systems.

    Source: §1 · pp. 1–2

  • Method

    SPRINT learns each token's average generation probability in one bidirectional Transformer pass and uses token- and SID-level contrastive objectives to restore coherence.

    Source: §1 · pp. 2–3

  • Results

    8.39–10.04× faster than the second-fastest AR/NAR method and 7.77% average accuracy improvement over the second-best across 8 datasets.

    Source: §1 · p. 3

  • Takeaways & Limitations

    SPRINT combines a compact 4-token SID with a lightweight architecture that omits auxiliary mask-scheduling and data-augmentation machinery.

    Source: §1 · p. 3

    Training fixes terminal time t = 1 and anchors most sources at r = 0; intermediate intervals are auxiliary supervision, not inference or tunable few-step generation.

    Source: F LIMITATIONS · p. 30

Abstract

from arXiv · show

Semantic ID (SID) based generative recommendation represents each item as a sequence of discrete tokens, and recommends by generating the SID of the item a user would like to interact with. Both dominant paradigms in this domain generally pay for generation token by token: autoregressive models decode the tokens left-to-right, while non-autoregressive models decode in parallel yet still need multiple rounds of refinement to stay competitive. Therefore, both generally spend multiple forward passes per item, a cost that is prohibitive in latency-sensitive recommender systems. We ask whether an item can be generated in a single forward pass, and answer it through a new perspective which we call average probability velocity. We view SID generation as a flow of token generation probabilities and characterize it by its average velocity over the whole generation process. We prove that this average velocity is fully determined by the average generation probability of each token. Therefore, we directly parameterize and learn the probabilities of all tokens in a single forward pass with a bidirectional Transformer. As these probabilities are generated independently across positions and the coherence among tokens is lost, we further design a dual-level flow contrastive objective to restore the coherence among an item's tokens. It contrasts the target SID against negative SIDs at both the token and SID levels. The token level ranks the generation probabilities of the target tokens above those of negative SIDs, while the SID level scores the tokens of each SID as a whole item for capturing token coherence of each item. Extensive experiments show that our model not only generates recommendations far more efficiently ($8.39-10.04\times$ speedup over the second-fastest AR/NAR method) but also attains superior recommendation accuracy ($7.77\%$ average improvement over the second-best.

1 INTRODUCTION

SPRINT targets the latency cost and token-coherence challenges of single-step SID generation. It learns token probabilities through average probability velocity and uses contrastive objectives to preserve coherence, while reporting faster and more accurate recommendations.

1 INTRODUCTION

  • AR and NAR recommendation generally require L forward passes per item, creating an efficiency bottleneck for latency-sensitive systems.AR decodes left-to-right; NAR methods generally refine tokens iteratively to capture their dependencies.Source: §1 · p. 1
  • Single-step generation faces discrete-token and coherence challenges, while prior approaches either lose up to 96.31% of accuracy, enlarge SIDs, or use costly search.Independent token decoding loses conditioning; RPG uses 16–64 tokens, and OneGR performs an A∗ search.Source: §1 · p. 2
  • SPRINT characterizes SID generation as a probability flow and proves its average velocity is determined by each token's average generation probability.A bidirectional Transformer predicts all token probabilities from user history in one forward pass.Source: §1 · p. 2
  • The dual-level flow contrastive objective ranks target tokens above negative SID tokens and scores each SID as a whole to restore token coherence.Token-level and SID-level comparisons address per-position prediction and coherent token combinations, respectively.Source: §1 · p. 3
  • 8.39–10.04× faster than the second-fastest AR/NAR method, with a 7.77% average accuracy improvement over the second-best across 8 datasets.SPRINT uses a compact 4-token SID and a 1-layer encoder with a 4-layer decoder.Source: §1 · p. 3

2 RELATED WORK

Related work covers sequential AR decoding, parallel NAR generation, and flow-matching approaches. SPRINT is positioned as a single-step method for discrete SID recommendation.

Autoregressive GR

  • AR methods decode SID tokens left-to-right, requiring L forward passes for an SID of L tokens.TIGER introduced this paradigm by quantizing item embeddings into SIDs and decoding token by token.Source: §2 · p. 3

Non-autoregressive GR

  • NAR methods generate SID tokens in parallel, but masked diffusion generally uses iterative refinement; RPG enlarges embeddings, while OneGR uses sequential A∗ search.SPRINT is presented as a single-step alternative.Source: §2 · p. 3

Flow matching

  • Single-step flow matching learns average velocity in continuous space, whereas discrete flow matching retains iterative sampling and SID-based GR lacks such a method.SPRINT addresses this gap with single-step generative recommendation based on average probability velocity.Source: §2 · p. 3

3 SPRINT: SINGLE-STEP GENERATIVE RECOMMENDATION

SPRINT generates a target item’s SID in one forward pass by learning average token-generation probabilities. Dual-level contrastive training adds supervision for both token accuracy and coherence across each SID.

3.1 PROBLEM FORMULATION AND OVERVIEW

  • SPRINT’s goal is to predict the next item’s SID from interaction history in one forward pass, then return the highest-scoring valid SIDs as recommendations.Inference begins with an all-mask SID and uses trie-constrained generation over valid SID trajectories.Source: §3.1 · p. 4, §3.4 · p. 7

3.2 SETUP AND NOTATIONS

  • The generation setup treats an SID as a discrete flow from an all-mask sequence to the target item’s SID, with a convex interpolant controlling how much is committed over time.SPRINT adopts OPQ because single-step generation does not condition each token on preceding tokens, as residual tokenizers assume.Source: §3.2 · p. 4, §3.1 · p. 4

3.3 AVERAGE PROBABILITY VELOCITY FOR SINGLE-STEP GR

  • Average probability velocity reduces the discrete flow to an interval-averaged scalar rate because its transport direction is constant, allowing a closed-form single-step update.The model learns an interval-averaged token posterior, parameterized by a lightweight bidirectional Transformer; training mixes fully masked and partially committed starting states.Source: §3.3 · pp. 5–6

3.4 DUAL-LEVEL FLOW CONTRASTIVE TRAINING AND INFERENCE

  • SPRINT’s dual-level flow contrastive loss trains target-token probabilities against negative SIDs and scores each SID as a whole item to capture token coherence.The token-level term sharpens position-wise predictions; the SID-level term ranks the target SID above negative ones.Source: §3.3 · p. 6

4 EXPERIMENTS

Across eight datasets, SPRINT leads the reported recommendation benchmarks and generates recommendations substantially faster than the compared methods. Ablations and hyperparameter analyses examine its tokenizer, training objectives, and settings for ρ and negative SIDs.

4.1 EXPERIMENTAL SETUP

  • Experiments cover eight datasets, evaluate Recall@K and NDCG@K at K ∈ {5, 10}, and measure per-epoch training time and total test-set inference time.Each item uses a four-token SID; results are averaged over five random-seed runs.Source: §4.1 · p. 7
  • The baselines span item-ID recommenders, semantic-ID autoregressive methods, and semantic-ID non-autoregressive methods.The comparison includes representative and state-of-the-art methods from all three families.Source: §4.1 · p. 7

4.2 MAIN RESULTS

  • N@5 improves by up to 10.26% and R@5 by up to 11.50% over the second-best method; SPRINT outperforms all baselines on every dataset.Table 2 compares baseline and SPRINT performance; asterisks mark statistically significant improvements over the second-best result (p < 0.05).Source: §4.2 · p. 7, Table 2 · p. 8
  • 8.39×–10.04× speedups over RPG make SPRINT the fastest method on all six datasets in the inference-time comparison.SPRINT uses one forward pass per user regardless of SID length, while AR and NAR baselines generally use L passes, multiplied by beam width for ranked lists.Source: Table 3 · p. 8, §4.2 · p. 8

4.3 ABLATION STUDY

  • The full model performs best across six datasets and both metrics; removing the SID-level flow causes a sharper accuracy drop than removing the token-level flow, while removing contrast causes an even larger drop.The SID-level score evaluates the SID as a whole, and the contrastive objective also distinguishes target items from competing candidates.Source: §4.3 · pp. 8–9
  • Replacing OPQ with RQ-VAE or RQ-Kmeans substantially reduces performance across datasets; OPQ’s parallel, mutually independent subspaces fit simultaneous token prediction.The authors therefore adopt OPQ for their single-step formulation.Source: §4.3 · p. 8

4.4 HYPERPARAMETER ANALYSIS

  • As ρ increases, accuracy generally improves and peaks at ρ = 0.75 or 1, while convergence accelerates.The authors attribute faster convergence to shifting training toward the all-mask source used at inference.Source: Figure 3 · p. 9, §4.4 · p. 9
  • Accuracy rises as the number of negative SIDs N grows to 100, then improves slowly up to 1000, while per-epoch training time rises sharply beyond 100.The authors set N = 100 by default and note it can be adjusted to balance accuracy and training cost.Source: Figure 4 · p. 9, §4.4 · p. 9

5 CONCLUSION

SPRINT replaces multi-pass SID decoding with single-step generation based on average probability velocity and dual-level contrastive training. The conclusion reports efficiency and accuracy gains across eight real-world datasets, alongside statements on AI use, ethics, and reproducibility.

5 CONCLUSION

  • Across eight real-world datasets, SPRINT significantly improves both generation efficiency and recommendation accuracy.The conclusion describes its average-probability-velocity approach and dual-level flow contrastive objective for restoring inter-token coherence.Source: §5 · pp. 9–10

AI USE STATEMENT

  • The authors used LLMs to polish manuscript language and automate parts of the experimental workflow, not to develop the research idea, methodology, or model design.Authors reviewed and verified AI-assisted text and results and take responsibility for the paper.Source: AI USE STATEMENT · p. 10

ETHICS STATEMENT

  • The authors report no anticipated negative impacts and state that the work does not violate the ICLR code of ethics.Source: ETHICS STATEMENT · p. 10

REPRODUCIBILITY STATEMENT

  • The paper states that results are reproducible and provides pseudocode, implementation details, hyperparameters, and a code repository.Source: REPRODUCIBILITY STATEMENT · p. 10

A.1.1 AUTOREGRESSIVE GENERATIVE RECOMMENDATION.

  • Autoregressive methods require L passes, while competitive masked-diffusion methods retain iterative refinement; RPG instead uses 16–64-token SIDs, and OneGR uses sequential search.SPRINT is presented as a single-step alternative to these trade-offs.Source: §A.1.1 · p. 17, §A.1.2 · p. 18

A.2 FLOW MATCHING

The flow-matching literature separates single-step generation in continuous space from discrete generation that remains iterative. SPRINT addresses this gap by deriving average probability velocity in discrete token space.

A.2 FLOW MATCHING

  • Single-step flow matching models average velocity over a finite interval, but their enabling identity is defined only in continuous, differentiable space.Source: §A.2 · p. 18
  • Discrete flow matching handles categorical data with continuous-time Markov chains, but its instantaneous transition rates leave sampling iterative.The paper characterizes the continuous single-step and discrete multi-step approaches as complementary but disjoint.Source: §A.2 · p. 18

B NOTATIONS

  • The notation table defines Transformer parameters and hidden states, token embeddings, joint user/SID representations, cosine similarity, negative-sample count, training data, and the dual-level loss.Source: §A.2 · p. 19, Table 5 · p. 19

A.2 FLOW MATCHING

  • SPRINT bridges these approaches by deriving average probability velocity directly in discrete token space.Source: §A.2 · p. 19

C THEORETICAL DERIVATIONS

The derivation builds a valid conditional velocity for a fixed target, then averages it over an interval and marginalizes over unknown targets. The marginal average requires a time-weighted posterior rather than a single posterior mean.

C.1 DERIVATION OF THE INTERPOLANT IN EQUATION 3

  • Conditioning on a fixed target SID turns the path from the all-mask source into a simple convex interpolant whose time derivative depends on κτ.The derivation uses the Kolmogorov equation to identify a velocity that generates this path.Source: §C.1 · pp. 19–20

C.2 VALIDITY OF THE CONDITIONAL VELOCITY IN PROPOSITION 1

  • The conditional velocity is a valid CTMC generator when probability is conserved and off-diagonal jump rates are nonnegative; the monotone scheduler and 1 − κτ ≥ 0 satisfy the latter condition.Source: §C.2 · p. 20

C.3 CONDITIONAL AVERAGE PROBABILITY VELOCITY

  • Averaging the conditional velocity over an interval preserves its target-minus-current direction and collapses the time-varying rate into one interval-level scalar.Because transport direction does not change with time, averaging the scalar rate makes a single interval-spanning step well-defined.Source: §C.3 · p. 21

C.4 MARGINAL AVERAGE PROBABILITY VELOCITY

  • Because the target posterior varies with time inside the integral, marginal average velocity uses a rate-weighted average posterior, not a single posterior mean.The resulting velocity retains a posterior-minus-current form.Source: §C.4 · p. 21

D.1 DATASETS STATISTICS

The experiments use eight datasets, compare recommendation methods from several families, and report implementation and evaluation details. SPRINT consistently outperforms baselines on R@10 and N@10.

D.1 DATASETS STATISTICS

  • Evaluation covers eight datasets: Sports, Beauty, and Toys from Amazon Reviews 2014; four categories from Amazon Reviews 2023; and Yelp.The leave-one-out split assigns the latest interaction to testing, the second latest to validation, and earlier interactions to training.Source: §D.1 · pp. 22–23

D.2 BASELINE DESCRIPTION

  • The baselines span item-ID, autoregressive semantic-ID, and non-autoregressive semantic-ID methods, including GRU4Rec, TIGER, and RPG.Source: §D.2 · pp. 23–24

D.3 MORE IMPLEMENTATION DETAILS

  • The implementation uses four-token OPQ SIDs, a bidirectional Transformer with a 1-layer encoder and 4-layer decoder, and a history length of 20.The efficiency comparison standardizes batch sizes, sequence length, beam width where applicable, and token embedding size; accuracy-comparison settings are tuned per dataset.Source: §D.3 · pp. 24–25

D.4 MORE COMPARISON RESULTS (K = 10)

D.5 TRAINING EFFICIENCY ANALYSIS

SPRINT reduces training time relative to existing AR and NAR generative recommenders. It also converges faster than RPG, generally reaching convergence in 20–40 epochs.

D.5 TRAINING EFFICIENCY ANALYSIS

  • SPRINT’s training time is lower than existing AR and NAR generative recommenders.The paper attributes this to single-step generation, a lightweight 1-layer encoder and 4-layer decoder, and no auxiliary mask-scheduling or data-augmentation machinery.Source: §D.5 · p. 25
  • 20–40 epochs generally suffice for SPRINT to converge, faster than the RPG baseline.Figure 5 compares training convergence on six datasets.Source: §D.5 · p. 25, Figure 5 · p. 26

D.6 COMPARISON BETWEEN SPRINT AND OTHER EFFICIENCY-ORIENTED METHODS

Across six datasets, SPRINT has the lowest inference cost among the efficiency-oriented methods compared. It also matches the most compact baseline’s parameter count while achieving the paper’s best recommendation accuracy.

D.6 COMPARISON BETWEEN SPRINT AND OTHER EFFICIENCY-ORIENTED METHODS

  • 1.28–7.55s is SPRINT’s inference cost across six datasets, the lowest among the compared efficiency-oriented methods.It is about 24–29× faster than AtSpeed and EARN, about 6× faster than NEZHA, and faster than SID-MLP while delivering substantially higher accuracy.Source: §D.6 · pp. 26–27, Table 10 · p. 26

D.7 PARAMETER MEMORY

  • 5.59 M parameters makes SPRINT the lightest model within the AR and NAR paradigms, on par with DiffGRM (5.60 M) and roughly 2.5× smaller than TIGER.The paper reports that SPRINT also delivers the best recommendation accuracy.Source: §D.7 · p. 27, Table 11 · p. 27

D.8 EXPERIMENTS ON MORE DIVERSE DATASETS

SPRINT achieves the best reported performance on Yelp and Arts. Its effectiveness also transfers across encoder-decoder and decoder-only backbones, with dataset-specific differences between them.

D.8 EXPERIMENTS ON MORE DIVERSE DATASETS

  • SPRINT consistently achieves the best performance on Yelp and Arts, extending evaluation beyond the six Amazon datasets.Table 12 marks statistically significant improvement over the second-best result with “*” (p < 0.05), but the supplied passage does not specify which results carry that mark.Source: §D.8 · p. 27, Table 12 · p. 27

D.9 PERFORMANCE OF DECODER-ONLY ARCHITECTURE

  • The decoder-only SPRINT variant is slightly worse on Sports, Beauty, Scientific, and Games, but better on Toys and Instruments than the encoder-decoder variant.The comparison covers both architectures across six datasets.Source: §D.9 · p. 28, Table 13 · p. 28

D.10 MORE HYPERPARAMETER ANALYSIS

The hyperparameter analyses find that ρ = 1 and N = 100 offer favorable accuracy and training-cost trade-offs on the tested datasets. Further analyses report SPRINT’s performance at larger K, examine TIGER with OPQ, and provide its training and inference algorithms.

D.10 MORE HYPERPARAMETER ANALYSIS

  • ρ = 1 gives the highest accuracy and best accuracy–convergence trade-off on Sports, Beauty, and Toys.As ρ grows, accuracy improves while the best epoch drops sharply; Figure 6 reports R@5 and best epoch.Source: §D.10 · p. 28, Figure 6 · p. 28
  • N = 100 captures most accuracy gains at nearly flat per-epoch training time on Sports, Beauty, and Toys.Beyond 100, training time rises sharply; accuracy gains slow, and R@5 slightly declines at N = 1000 on Beauty and Toys. Figure 7 reports R@5 and training time per epoch.Source: §D.10 · p. 28, Figure 7 · p. 28

D.11 PERFORMANCE COMPARISON UNDER LARGER K

  • SPRINT remains best on R@K and N@K for every evaluated K from 20 to 1000 across all six datasets, with its margin over the strongest baseline not eroding as K grows.The paper attributes this tail-ranking robustness to jointly scoring each candidate SID; Figure 8 compares SPRINT with DiffGRM, LLaDA-Rec, RPG, and ActionPiece.Source: §D.11 · p. 29, Figure 8 · p. 29

D.12 PERFORMANCE OF TIGER USING OPQ AS THE TOKENIZER

  • Replacing TIGER’s RQ-VAE with OPQ degrades performance across all six datasets and metrics.The paper explains that RQ-VAE’s coarse-to-fine code order fits TIGER’s left-to-right decoding, whereas OPQ’s independent subspaces provide no inherent token ordering.Source: §D.12 · p. 29, Table 14 · p. 29

E ALGORITHMS

  • SPRINT’s training algorithm tokenizes items into L-token OPQ SIDs, learns token- and SID-level contrastive scores, and updates parameters with AdamW; inference uses one encoder-decoder pass from an all-mask sequence to rank valid SIDs.The inference algorithm precomputes SID-prefix-tree vectors independently of users and sequences.Source: E ALGORITHMS · p. 30

F LIMITATIONS

SPRINT uses intermediate intervals only as auxiliary supervision for its single-step map, and its inference cost grows with the item corpus. The authors therefore position it for ranking after candidate retrieval rather than end-to-end retrieval from billions of items.

F LIMITATIONS

  • SPRINT fixes terminal time at t = 1 and anchors most training sources at r = 0, leaving intermediate intervals unexplored at inference or in tunable few-step variants.Best performance mostly occurs with ρ ∈ {0.75, 1}, though a small fraction of partially committed sources can still help.Source: F LIMITATIONS · p. 30
  • Inference cost grows with the item corpus because SPRINT decodes over all valid trajectories in the SID prefix tree.Source: F LIMITATIONS · p. 30
  • SPRINT is best suited to ranking retrieved candidates, not end-to-end recommendation that retrieves directly from billions of items.Scaling single-step generation to such settings is left to future work.Source: F LIMITATIONS · p. 30

Related papers

Loading 2609.34306v1…