SPRINT: Single-Step Generative Recommendation via Average Probability Velocity
Zhuo Cai, Shoujin Wang, Peilin Zhou, Min Xu, Julian McAuley, Fang Chen
cs.IR
2026-09-28
SPRINT emits a full item SID in one pass via average probability velocity. On 8 datasets it is 8.39–10.04x faster than the next AR/NAR method and 7.77% more accurate.
Generative recommendation encodes each item as a short sequence of discrete tokens, a semantic ID (SID), and recommends by producing the SID of the next item. An SID is typically 3-4 tokens long. Autoregressive models decode left to right, so L tokens cost L forward passes. Masked diffusion (cover some SID positions and reveal them round by round) can emit tokens in parallel, but it still refines one position per round to stay accurate. The bill remains L passes, then multiplied by beam width. Latency-sensitive recommenders cannot absorb that.
Collapsing an off-the-shelf masked diffusion model to one step fails. On Instruments, LLaDA-Rec drops from 0.0623 to 0.0023 R@10 when going from 4 steps to 1, a 96.31% collapse; DiffGRM drops 76.93% under the same cut. Existing one-step designs pay elsewhere. RPG predicts every position at once but stretches the SID to 16-64 tokens and grows the embedding table 4-16x. OneGR emits position-wise scores in one pass, then runs A search.
The question is whether a discrete SID can be produced in a single forward pass without throwing away the coherence that makes those tokens an item.
SPRINT treats SID generation as a probability flow from an all-mask sequence to the target SID. Multi-step models track instantaneous velocity. The average velocity over the whole interval is fully determined by each position's average generation probability. Continuous mean-flow methods recover that average by differentiating with respect to a continuous state, which does not exist for categorical tokens. A convex interpolant keeps the transport direction constant in time, so the average velocity has a closed form and the network just fits the average generation probability.
The backbone is a bidirectional Transformer: a 1-layer encoder over a user history of at most 20 items, and a 4-layer decoder that reads L mask queries and emits a distribution over each position's codebook. Items are tokenized with OPQ (optimized product quantization) into L=4 tokens from independent subspaces, 256 codes each. Residual quantizers assume later codes depend on earlier residuals, which single-step prediction never conditions on. Replacing OPQ with RQ-VAE or RQ-Kmeans drops Sports R@5 from 0.0411 to 0.0284 and 0.0296.
Those probabilities are independent across positions, so a plausible token at every slot can still form a tuple that is not a real item. A dual-level flow contrastive loss puts the dependence back:
Training always targets t=1. The start time r is 0 with probability ρ (all-mask, matching inference) and otherwise drawn uniformly, so the model also learns to complete a partly revealed SID. ρ of 0.75 or 1 works best. Negatives default to 100, 1000 on Arts. Inference scores only valid SIDs in a prefix trie: token log-probability sum plus SID-level similarity, then top-K.
Eight datasets, leave-one-out, full-catalog Recall and NDCG at K=5 and 10, five random seeds. Baselines cover item-ID models (SASRec, FAVE), autoregressive SID models (TIGER, ActionPiece, COBRA, SID-MLP), and non-autoregressive ones (RPG, LLaDA-Rec, DiffGRM, OneGR).
R@5 on the six Amazon subsets in the main table:
| Dataset | SPRINT | Second-best | Rel. gain |
| Sports | 0.0411 | 0.0377 (OneGR) | 9.02% |
| Beauty | 0.0675 | 0.0628 (OneGR) | 7.48% |
| Toys | 0.0708 | 0.0635 (OneGR) | 11.50% |
| Scientific | 0.0444 | 0.0405 (DiffGRM) | 9.63% |
| Instruments | 0.0462 | 0.0426 (DiffGRM) | 8.45% |
| Games | 0.0636 | 0.0623 (LLaDA-Rec) | 2.09% |
The largest N@5 lift is on Scientific, 0.0301 vs 0.0273 (10.26%). Across all datasets and metrics the paper reports 7.77% over the second-best; Yelp and Arts sit in that average and are detailed in an appendix. Games is essentially tied with LLaDA-Rec. On R@10, Toys improves 14.19% (0.0998) and Sports 8.19% (0.0621 vs OneGR 0.0574).
Efficiency uses matched batch size, sequence length, and beam width 10 where applicable. Whole-test-set generation for SPRINT takes 2.65, 1.52, 1.28, 4.08, 4.62, 7.55 seconds on the six Amazon subsets. RPG, the next-fastest, takes 24.70 to 64.43 seconds, an 8.39-10.04x speedup. Versus TIGER the gap is about 25-37x; versus LLaDA-Rec it exceeds 100x (125.94x on Toys). Training time per epoch is also lower, but only 1.11-1.31x faster than RPG. The serving win is the one that matters.
Ablations: dropping the SID-level term hurts more than dropping the token-level term (Sports R@5 0.0411 to 0.0297 vs 0.0387). Replacing the contrastive objective with per-token cross-entropy falls to 0.0250. Accuracy rises with negatives up to 100, then flattens while training time climbs.
Generative recommenders have been paying L forwards times beam per item. SPRINT keeps a compact 4-token SID, does not inflate the embedding table, and does not run A at decode time. One pass produces an L-by-M probability table and a user vector; scoring a valid SID is a table lookup plus one matrix product.
For teams already on SID generation this is a decoder and objective swap, not a new retrieval stack. It will not drop in on TIGER's RQ-VAE: residual codes fight parallel prediction, so the tokenizer needs something like OPQ. Accuracy gains are steady and incremental; on Games they are about 2%. Speed is the reason to look.
All numbers are leave-one-out on Amazon and Yelp, with catalogs of roughly 12k-90k items, mean sequence length 8-10, and history capped at 20. There is no industrial traffic and no online A/B. Inference cost is wall-clock over the test set, not p99 latency. Accuracy tables use per-paper tuned hyperparameters; the speed table is the one that aligns batch size and beam. Those two comparisons may not share the same baseline weights.
The rate coefficient λ from the derivation is unused in training and generation. What the network actually fits is an interval-averaged posterior, trained with a two-level contrastive loss. The discrete mean-flow writeup is mathematically closed. There is no ablation of the same backbone and loss without the flow story, so the theory and the engineering gain stay glued together.
Inference softmaxes over the set T of valid SIDs. At this catalog size that is close to scoring the whole item set. Autoregressive baselines with beam 10 expand only a handful of paths. SPRINT may get a full-catalog scoring bonus that the main table does not isolate. Whether the SID-level matrix product stays cheap at a 10x larger catalog is also untested. Arts already uses 1000 negatives, so those runs are not on the same hyperparameter.