From transformer parallelism to HSTU

This page walks a single thread from one end to the other: why the transformer's training-time parallelism exists, what the per-position loss has to do with it, and how that machinery gets adapted to recommendation — a domain with billion-scale vocabularies, heterogeneous features, and a hard inference budget. The destination is HSTU, but the route matters more than the destination.

Everything is built up from first principles with concrete numbers. If you already know why attention is a matmul, skip to §2.

Part OneWhy transformers parallelize

1.1  The RNN bottleneck

A recurrent network computes its hidden state as

Position t literally cannot be computed until position t−1 exists. For a sequence of length N, the dependency chain has depth N. You may have ten thousand cores idle; it does not help. The critical path is serial by construction.

This is not a fixable implementation detail. It's the semantics of the model.

1.2  Attention as one matrix multiply

Self-attention replaces the recurrence with a direct all-pairs comparison. Given $X \in \mathbb{R}^{N \times d}$, project to queries, keys, values, then:

$QK^{\top}$ is a single $N \times N$ matrix multiply. Every position's score against every other position is computed in one shot. There is no loop.

Causality is restored by the mask $M$, which is $0$ on and below the diagonal and $-\infty$ above it. After softmax, the $-\infty$ entries become exactly zero.

The second ingredient is teacher forcing. During training you feed the model the true previous tokens, not its own predictions. If you fed back predictions, position t would depend on the model's output at t−1 and you'd be right back in the serial regime. Teacher forcing is what makes the inputs available up front.

1.3  The loss over a sequence is the whole point

Here is the part that turns parallelism into an actual training advantage.

One forward pass emits N output vectors — one per position. Each is trained to predict the next token. So you compute cross-entropy at every position and average:

A length-2048 sequence is not one training example. It is 2048 next-token prediction examples that share computation. Backprop then flows through the entire graph in one pass, and gradients from every position accumulate into the same shared weights.

Compare the alternative. A classic two-tower recommender typically builds one (user, item) pair per training example and re-encodes the user's history from scratch for each. Same data, a fraction of the supervision per unit of compute. This gap is a large part of why sequential formulations scale so well, and we'll return to it in §4.2.

1.4  Work vs. depth: is it actually cheaper?

A natural question: if you generated tokens one at a time during training instead, would it cost more? The honest answer is roughly the same total arithmetic, dramatically different wall-clock time. This is the classic work-versus-depth distinction from parallel algorithms.

Work

Sequential generation with a KV cache: at step t you compute one query and attend to t cached keys, costing $O(t \cdot d)$. Summing over the sequence:

Identical order to the parallel form's $N \times N$ score matrix. The feed-forward block is $O(d^2)$ per step times N steps, so $O(Nd^2)$ — also identical. Without a cache, recomputing every previous state at each step, you'd get $O(N^3 d)$, which is strictly worse.

Depth

Parallel training has a dependency chain of length L (the number of layers). Sequential has $N \times L$. For $N = 2048$ that's a 2048× longer critical path. But the depth argument, bad as it is, isn't even the main problem.

1.5  The real reason: arithmetic intensity

The dominant effect is hardware utilization, and it comes down to a single ratio: FLOPs performed per byte moved from memory.

Take a weight matrix $W \in \mathbb{R}^{d \times d}$ with $d = 512$, stored in bf16 (2 bytes per parameter).

Now compare against the hardware's ridge point — the intensity at which a chip transitions from memory-bound to compute-bound. For an A100 at roughly 312 TFLOP/s bf16 and about 2.0 TB/s of HBM bandwidth:

H100 lands in a similar neighborhood. So at intensity 1, you are running at roughly $1/156 \approx 0.6\%$ of peak arithmetic throughput. At intensity 2048, you are comfortably compute-bound and actually saturating the tensor cores.

Add kernel-launch overhead — N times as many tiny kernels instead of a handful of large ones — and the practical gap between parallel and sequential training lands somewhere in the 10× to 100× range on achieved throughput, not on FLOP count.

1.6  Why inference is slow anyway

None of this applies at generation time. You don't know the next token, so you must produce one, feed it back, and repeat. Decoding is exactly the memory-bound matrix–vector regime described above — which is why generation feels slow despite being cheap in FLOPs per token, and why two mitigations exist:

• KV caching — avoid recomputing keys and values for the prefix at every step (turns $O(N^3d)$ back into $O(N^2d)$).
• Batching many requests — restores arithmetic intensity by giving the weight matrix more vectors to multiply.

Hold onto this. The ranking half of HSTU faces a structurally identical problem — one user history, many candidates to score — and solves it with the same insight (§5).

Part TwoFeatures in recommendation

2.1  Sparse vs. dense

A production Deep Learning Recommendation Model (DLRM) is trained on thousands of heterogeneous features, and they come in two flavors that get treated completely differently.

That last row is the one that ends up mattering most, and we'll come back to it in §3.2.

The parameter asymmetry drives the standard systems design: shard the enormous embedding tables model-parallel across machines while keeping the comparatively tiny dense MLP data-parallel. Trillion-parameter counts in this domain are a sharding problem, not a FLOPs problem.

2.2  Four ways to encode a float

Whatever you do with a continuous feature, it has to end up as a d-dimensional vector before attention can touch it, because attention operates on a uniform embedding space. The options:

1. Bucketize, then embed

The most common choice. Discretize the value into bins (equal-frequency, or log-spaced when the distribution is heavy-tailed) and give each bin its own embedding. This makes floats structurally identical to sparse features, captures nonlinearity for free, and handles missing values elegantly — they get their own bucket.

2. Linear projection

Normalize the scalar and project it to d: $e = w \cdot \tilde{v} + b$. Cheap, but weak on its own — it can only express a monotone linear relationship, and one direction in embedding space now carries the whole feature.

3. Gating / FiLM

The float doesn't become a token; it scales or shifts another representation: $e' = \gamma(v) \odot e + \beta(v)$. Good when the value modulates a relationship rather than being a thing in its own right.

4. Attention bias

The float becomes a scalar added directly to attention logits. This turns out to be the right treatment for anything relational — most importantly, time. Covered in §2.4.

2.3  Three places attention appears

"Attention in a recommender" means at least three structurally different things, and they disagree about what a token even is. Getting this straight prevents a lot of confusion.

Sequential

Each token is a past interaction, its embedding built by summing or concatenating that item's sparse fields with its dense features. Self-attention runs over the history. This is the direct analogue of language modeling and it's what HSTU is.

Feature-field

Every field — sparse or bucketized-float — is one token. Self-attention learns feature interactions automatically, replacing hand-designed FM or DCN cross layers. Note the "sequence" here has no temporal order at all; it's a set.

Target attention

The candidate item being scored is the query; the user's history supplies keys and values. Attention weights answer: how relevant is each past behavior to the thing I'm scoring right now?

DIN is worth a closer look because two of its choices reappear in HSTU. It replaces the dot-product score with a small MLP over $[\,q,\; k,\; q-k,\; q \odot k\,]$, and — critically — it skips softmax normalization, so total attention mass reflects the intensity of interest rather than being forced to sum to one. Remember that; it comes back in §3.4.

2.4  Dense features as attention bias

For dense quantities that describe a relationship between two positions rather than a property of one position, the natural home is not the token — it's the attention logit.

Bucketize the time gap, look up a learned scalar, add it to the score. Structurally this is identical to relative position bias in NLP (T5, ALiBi) — the only change is that the "distance" is measured in seconds rather than token index. The same trick handles session boundaries, recency, and any other pairwise continuous quantity.

Part ThreeThe HSTU architecture

HSTU — Hierarchical Sequential Transduction Units — is the encoder proposed in Zhai et al., "Actions Speak Louder than Words: Trillion-Parameter Sequential Transducers for Generative Recommendations" (ICML 2024). It is the backbone of a framework called Generative Recommenders (GRs), and it's important to be precise about the relationship: HSTU is not "a retrieval model." It's an encoder that GR instantiates twice — once for retrieval, once for ranking — with different sequence constructions and different heads.

3.1  The reformulation

The framing claim: recommendation should be a sequential transduction task over a single time-ordered stream of user actions, not a feature-engineering problem over a snapshot. Given tokens $x_0, \ldots, x_{n-1}$ observed at times $t_0, \ldots, t_{n-1}$, transduce them to outputs $y_0, \ldots, y_{n-1}$, where $y_i = \varnothing$ marks a position with no defined target.

The paper's argument is that the DLRM feature space is approximated by this sequence as the sequence grows — with equality in the limit. Two mechanical consequences:

Sparse features get sequentialized. Pick the longest time series (typically the items the user engaged with) as the main series. The remaining categorical features are slowly-changing time series — demographics, followed creators, language, city of request. Compress each by keeping only the earliest entry per consecutive run of identical values, then merge into the main series. Because these change rarely, this barely increases sequence length.

Dense features get deleted. Which needs its own section.

3.2  Deleting dense features

HSTU's answer to "how do you encode dense features?" is unusually blunt: you mostly don't.

The argument has two legs.

The modeling leg. The dense features in a production DLRM are overwhelmingly numerical aggregations over the user's own action sequence — CTR on a topic over 30 days, decayed count of clicks on an author, ratio features. These are derived quantities. And crucially, the categorical features they aggregate over are already in the sequence. So given a long enough sequence, a sufficiently expressive sequential architecture, and a target-aware formulation, the model can learn whatever aggregation is actually useful — rather than you guessing at window sizes and decay rates by hand.

The systems leg. Categorical features change slowly, so the dedup trick above works. Dense counters change on every event. Keeping them as sequence tokens would multiply sequence length by the number of dense fields — thousands of them — which is infeasible on both compute and storage. It is genuinely remove-or-explode. They remove.

What survives is time, which enters as an attention bias (§3.5), and actions, which become tokens rather than features. Quantities you'd normally encode as floats — watch time, engagement depth — are either bucketized into the action vocabulary or moved to the output side as regression targets.

3.3  The layer, line by line

Given input $X \in \mathbb{R}^{n \times d}$, one HSTU layer is three sub-layers.

(a) Pointwise projection

A single linear map $f_1$ followed by SiLU, then split four ways. Note that $U$ is an extra output that a standard transformer doesn't have — it's a gate, and its purpose becomes clear in (c).

(b) Spatial aggregation

Attention — but $\phi_2$ is pointwise SiLU, not softmax, and $\text{rab}^{p,t}$ is a relative attention bias combining a positional term and a temporal term. Both choices are load-bearing and get their own sections below.

(c) Pointwise transformation

with a residual connection around the block.

Now notice what's missing: there is no separate feed-forward block. In a standard transformer layer you pay for attention and then a 4×-width FFN. Here the $U$ gate plus $f_2$ absorb that role, in the style of Gated Attention Units. Recall from §1.5 that the FFN was 8.6 of the 21.5 GFLOP per layer — about 40%. That's a large part of why HSTU is cheaper per layer than a vanilla transformer at equal d.

3.4  Why not softmax

This is the most interesting design choice in the architecture, and the reasoning connects directly back to §2.1.

Softmax normalizes attention weights to sum to 1. That is exactly what you want when attention means "which of these do I select?" — a distribution over alternatives. But it discards magnitude. A user who interacted with a category fifty times and a user who did it twice can produce the same normalized attention pattern, because the denominator absorbs the difference.

And magnitude is precisely what the hand-built counter features were carrying. Un-normalized pointwise activation lets total attention mass grow with engagement volume, recovering that signal structurally rather than through a feature.

The arithmetic, if you want it by hand. With $\sigma(2) = 1/(1+e^{-2}) \approx 0.8808$:

At $k=3$ the mass is 5.28; at $k=20$ it is 35.23 — a 6.7× difference that softmax would have flattened to exactly 1.000 in both cases.

There is a second motivation. Softmax's denominator is a sum over the attended set, and in a domain with a non-stationary, billion-scale vocabulary that denominator is an unstable quantity. Pointwise activation sidesteps the issue.

3.5  The relative attention bias

The $\text{rab}^{p,t}$ term carries both position and time. The temporal half is the entire dense-feature story in HSTU: a continuous quantity that shapes attention weights without ever becoming an embedding.

bucket:  0     1     2     3     4     5      6      7       8        9        10
edges:   0     1     5     30    60    300    1800   3600    86400    604800   2.6e6   ∞
                                 1m    5m     30m    1h      1d       1w       1mo

Two things worth appreciating. First, this handles irregular sampling natively — user actions do not arrive on a uniform grid, and positional index alone would treat "two clicks 3 seconds apart" and "two clicks 3 months apart" identically. Second, it costs a lookup table of ~11 scalars per head, versus an embedding table.

Part FourRetrieval

Retrieval is the stage that narrows millions of candidates to hundreds. In GR it becomes almost exactly next-token prediction.

4.1  Sequence construction

The retrieval formulation learns a distribution $p(\Phi_{i+1} \mid u_i)$ over content items $\Phi_{i+1} \in \mathbb{X}_c$, where $u_i$ is the user's representation at token i.

Note the exact input construction — this is a detail people frequently get wrong. Retrieval does not interleave item and action tokens the way ranking does. Instead each (item, action) pair is merged into a single token:

This is a meaningful departure from plain language modeling, and the paper flags it explicitly. In an LM, the supervision at position i is always the literal next token. Here it isn't: a user can respond negatively to the item they were shown next, and you don't want to train the retrieval model to go fetch more of that. Negative-response items still appear as inputs — they're real evidence about the user — but they don't serve as targets.

4.2  The loss

The scoring function must stay a dot product between the position-i output embedding and a candidate item embedding, usually with a learned temperature $\tau$:

This is non-negotiable — an MLP scorer would be more expressive but would destroy the Maximum Inner Product Search property you need at serving time (§4.3).

Since the vocabulary is in the billions, a full softmax is impossible. You use sampled softmax with in-batch negatives, plus a logQ correction to debias sampling toward popular items:

where $\mathcal{S}$ is the sampled negative set and $Q(\cdot)$ is the probability of an item appearing as a negative. Without the correction, popular items appear as negatives far more often than chance and get systematically suppressed — the model learns to avoid recommending anything popular, which is exactly backwards.

4.3  Serving via MIPS

At inference the model collapses to ordinary embedding retrieval:

1. Run HSTU over the user's history. Take the output embedding at the final position as the query vector $u$.
2. Item vectors come from the embedding table — often weight-tied with the input table.
3. MIPS / ANN search over the corpus: HNSW, IVF-PQ, ScaNN, whatever index you already run.

The index infrastructure is unchanged from a two-tower system. That's a significant deployment property — you're swapping the query encoder, not rebuilding the serving stack. What changed is that the encoder is now HSTU over raw actions instead of an MLP over pooled features.

And with incremental decoding you can cache the history's keys and values, extending the sequence as new actions arrive rather than re-encoding from scratch on every request. Same KV-cache logic as §1.6.

4.4  The non-stationary vocabulary

This is the biggest genuine structural difference from language modeling, and the paper names it as a defining property of the domain.

A language model has a fixed ~100K-token vocabulary that never changes. A recommender has a billion-scale vocabulary where new content appears every minute and old content dies. A "fixed item vocabulary" is a fiction in production.

The mitigations are continuous streaming training, ID hashing so unseen IDs land somewhere sensible, and content-feature fallbacks so a brand-new item has a representation before it has any interaction data. None of this is unique to HSTU — it's the cost of admission for the domain.

Part FiveRanking and M-FALCON

5.1  Interleaved sequence

Ranking scores the few hundred candidates retrieval handed over. Its sequence construction is different: items and actions interleave as separate tokens.

5.2  Target awareness, for free and at full depth

Here's the elegant part. Because the candidate sits inside the sequence rather than outside it, target-awareness is structural. DIN gets one attention layer of candidate↔history interaction. HSTU gets L layers of it. Strictly more expressive, with no extra mechanism.

5.3  M-FALCON

The obvious cost of putting the candidate in the sequence: ranking scores hundreds of candidates per request, and naively that's hundreds of forward passes over the whole history.

M-FALCON — Microbatched-Fast Attention Leveraging Cacheable OperatioNs — fixes it. Encode the user history once, cache its keys and values, then process candidates in microbatches that all attend to the shared cache, with an attention mask preventing candidates from attending to each other so each is scored independently.

The paper reports this enabling models roughly 285× more computationally complex than the DLRM baseline while achieving 1.50×–2.99× speedups, within the same inference budget. That combination — far more model, less latency — is what made deployment possible at all.

Part SixEfficiency and scaling

Three efficiency techniques carry most of the weight:

Stochastic Length. During training, long sequences are randomly sparsified, so cost grows sublinearly in history length while the model still sees the tail. Long user histories are heavily redundant; you don't need every token every step.

Sequence sparsification. The dedup of slowly-changing categoricals from §3.1, plus the removal of dense features, keeps n tractable.

Fused kernels. Sparse grouped GEMMs and a fused relative-attention-bias kernel, plus the absence of a separate FFN block, minimize both FLOPs and activation memory.

Reported results

The scaling-law result is arguably the headline. DLRMs had been observed to scale poorly with compute — you could throw more hardware at them and get very little. Demonstrating a clean power law in a deployed, billion-user recommender was the thing the field had failed to show.

Part SevenCaveats worth holding onto

Four, in rough order of how likely they are to bite you.

The dense-feature result is validated at scale. The ablations justifying removal run with long sequences, large models, and Meta-sized data. The argument is explicitly asymptotic — the sequence approximates the DLRM feature space as length grows. At shorter histories or smaller capacity, hand-built counters are still doing real work, and dropping them because a paper did is a mistake.

The definition of "positive" does a lot of quiet lifting. Retrieval quality depends heavily on which actions count as positive for target masking (§4.1). That threshold is a modeling decision, it's dataset-specific, and it will not be in anyone's architecture diagram.

Un-normalized attention is a genuine departure. It's motivated by a specific property of engagement data — that intensity carries signal. If you port HSTU to a domain where engagement-intensity distributions look different, ablate it rather than assuming.

Trillion-parameter counts are misleading. Almost all of it is embedding tables. The dense compute is far smaller than the parameter count suggests, and the engineering challenge is sharding and memory, not arithmetic. Comparisons to LLM parameter counts are close to meaningless.

Part EightNotation and references

Notation

References

1. Zhai, Liao, Liu, Wang, Li, Cao, Gao, Gong, Gu, He, Lu, Shi. Actions Speak Louder than Words: Trillion-Parameter Sequential Transducers for Generative Recommendations. ICML 2024. arXiv:2402.17152 — the HSTU / GR / M-FALCON paper. Appendices F–H cover Stochastic Length, fused kernels, and M-FALCON in detail.
2. meta-recsys/generative-recommenders — reference implementation, with reproducible configs for MovieLens and Amazon Reviews.
3. Zhou et al. Deep Interest Network (KDD 2018) — target attention; the original argument for dropping softmax normalization in recommendation.
4. Kang & McAuley. SASRec (ICDM 2018) — self-attentive sequential recommendation; the academic ancestor of the sequential formulation.
5. Song et al. AutoInt (CIKM 2019) — attention over feature fields rather than over time.
6. Yi et al. Sampling-Bias-Corrected Neural Modeling for Large Corpus Item Recommendations (RecSys 2019) — the logQ correction.
7. Hua et al. Transformer Quality in Linear Time (ICML 2022) — Gated Attention Units, the lineage of HSTU's gated single-block design.