9  Sequential & Session-Based Recommendation

Traditional Recommender Systems modeled recommendation as filling in a user–item matrix. That view quietly threw away something every real log carries: order. Bob did not just watch Titanic and Vendetta — he watched Titanic then Vendetta, and what he reaches for next can depend more on what he reached for last (a claim from practice, not tested here). This chapter builds the order-aware recommenders from zero: the data is now a sequence, the task is predict the next item, and the models climb from a one-step Markov chain (guess the next film from the last one alone) to self-attention (each film in the session looking at the other films), in two models called SASRec and BERT4Rec — the same machinery the Transformer chapter built, now reading a session instead of a sentence.

What this chapter assumes. Four things from earlier chapters, each explained again where it is used; nothing else is assumed.

This chapter is the on-ramp to the era of large language models (LLMs): SASRec and BERT4Rec are the Transformer applied to item sequences, and an LLM is itself a sequence model.

1. From a matrix to a sequence: what order adds

Bob rated Titanic 4 and Vendetta 5, and the site must pick his next film. A table of ratings cannot say which film he watched first, yet the order may matter more than the stars. This section turns the table into a time-ordered list and names the task the rest of the chapter solves.

Collaborative filtering (CF) — the central approach of Traditional Recommender Systems, which fills a user’s blanks from other users’ ratings — asks “what rating goes in this empty cell?” — a question about a static matrix in which the rows could be shuffled and nothing would change. But a recommendation log is a stream of events in time. Take Bob from that chapter’s running example: his row of the user–item matrix holds Titanic 4, Vendetta 5 and a blank for Matrix (three films this chapter abbreviates T, V and M). In a log, those two ratings arrive as two events, one after the other: \[ \text{Bob's history} = (\ \text{Titanic},\ \text{Vendetta},\ \underbrace{?}_{\text{next}}\ ). \]

Two facts the matrix cannot see: the events have an order (Titanic came before Vendetta), and the most recent ones usually matter most (what you watched an hour ago says more about your next click than what you watched a year ago: a claim from practice, not tested here).

The order is real information. Bob’s two films can arrive in \(2\times1=2\) orders, (Titanic, Vendetta) or (Vendetta, Titanic), and the matrix stores both the same way; a session of three films can arrive in \(3\times2\times1=6\) orders, and the matrix keeps none of them. (The models in this chapter see only the order of events — 1st, 2nd, 3rd — not the clock time between them, so time is not modelled here; time-aware variants add the gaps as an extra input, beyond our scope. Time returns in §6, where the test split must respect it.) Sequential recommendation is the problem of using that order.

A note on the cast. The viewing logs in this chapter are sessions with their own histories: what each person watched, in order, over a longer time than the ratings snapshot of Traditional Recommender Systems. They are not that matrix. So Ann’s and Cara’s logs in later sections need not match their rows there (in that matrix Ann has not rated Vendetta, and Cara has not rated Titanic); only Bob’s two ratings above are taken from it. Likewise the exercise logs, and the sessions of §5 and §6 (where Bob watches Matrix although his matrix cell is “?”), are their own logs, not the ratings table.

Two settings, one task. The literature splits on how much you know about the user:

  • Sequential recommendation — you have a long, identified history for each user (their whole watch list), and predict the next item in it.
  • Session-based recommendation — you have only the current, short, often anonymous session (the handful of clicks since the page loaded), with no user id at all — nothing that ties this visit to an earlier one. This is the harder case, said to be very common in e-commerce (a claim from practice, not tested here): a logged-out visitor with three clicks (Wang et al., 2021, survey the methods built for it). §6 shows how a raw log is cut into such sessions.

(The literature uses “sequential recommendation” both for the umbrella problem and, narrowly, for the long-history setting of the first bullet; this chapter means the umbrella unless it says “long-history”.)

Both reduce to the same core question — next-item prediction:

Given the items seen so far, \((i_1, i_2, \dots, i_{t-1})\) — \(i_1\) is the first item, \(i_2\) the second, and so on; such a beginning of a list is called a prefix — score every item of the catalog (all the items the site offers) for being the next one, \(i_t\), and recommend the top-\(K\) (the \(K\) highest-scoring items).

The shape of the answer is unchanged from Traditional Recommender Systems: a score per item, ranked. What changes is the input — an ordered prefix instead of a user id — and so what the model must capture: which earlier items, in which order, predict what comes next.

Three views of the same interactions. Traditional Recommender Systems reads them as a static matrix (rows can be shuffled — no order).
Figure 9.1: Three views of the same interactions. Traditional Recommender Systems reads them as a static matrix (rows can be shuffled — no order). This chapter reads one user’s history as an ordered sequence and predicts the next item. The next chapter reads them as a graph of who-touched-what. Bob’s data appear in all three (T \(=\) Titanic, V \(=\) Vendetta, M \(=\) Matrix): his matrix row (outlined: T 4, V 5, M blank), his history Titanic then Vendetta then the unknown next item, and his two graph edges. Ann’s and Cara’s logs in later sections are separate sessions, not these rows.

Why “sequential” and “session.” Sequential = the model consumes an ordered sequence of past items. Session = one unbroken visit (the clicks between arriving and leaving); session-based models work from that short window alone, with no long-term profile.

Next-item prediction on Bob. The catalog here is the three films Titanic, Vendetta and Matrix. Bob’s prefix is (Titanic, Vendetta), so the model must score all \(3\) films for the next slot, and with \(K=2\) the site shows the \(2\) highest of the \(3\). Whether the true next film (suppose it is Matrix, as §5 will) lands in that short list is what §6 grades (at \(K=1\); one aside there uses \(K=2\)).

In one line: a matrix keeps Bob’s two ratings but not their order, which has \(2\times1=2\) possibilities; a sequence model keeps the order and scores all \(3\) films of the catalog for the next slot.

2. The simplest sequence model: Markov chains

Ann has just finished Titanic. Which film will she press play on next? The cheapest guess is to look at what other viewers pressed after Titanic, and count. This section turns that counting into a table of odds, and then shows what the table cannot do.

Start with the crudest possible use of order: the next item depends only on the last one. A (first-order) Markov chain models the sequence by a table of transition probabilities \(P(\text{next}=i \mid \text{last}=l)\) — “after \(l\), how often does \(i\) follow?” (read the bar \(\mid\) as “given”; \(l\) is the last item, \(i\) a candidate next item) — estimated by counting in the log.

Why “Markov.” After Andrey Markov, who studied processes with the memoryless property: the next state depends only on the current state, not the full history. A first-order chain remembers exactly one step back.

Worked example — transitions by counting. Take four tiny sessions over our three movies — Titanic (T), Vendetta (V), Matrix (M); the second one is Bob’s session so far: \[ \text{T}\!\to\!\text{V}\!\to\!\text{M},\qquad \text{T}\!\to\!\text{V},\qquad \text{V}\!\to\!\text{M},\qquad \text{T}\!\to\!\text{M}. \]

Count every adjacent (from \(\to\) to) pair, and file each count in a table whose rows are the last item and whose columns are the next item:

Table 9.1: Counts of each adjacent (from, to) pair in the four sessions; rows are the last item, columns the next item.
last item (row) / next item (column) T V M row total
T 0 2 1 3
V 0 0 2 2
M 0 0 0 0

From T we see \(\text{T}\!\to\!\text{V}\) twice and \(\text{T}\!\to\!\text{M}\) once (\(3\) transitions out of T); from V we see \(\text{V}\!\to\!\text{M}\) twice (\(2\) out of V); from M we see nothing, because Matrix ended every session it appeared in. Dividing each count by its row total gives the transition probabilities: \[ P(\text{V}\mid\text{T})=\tfrac{2}{3}\approx0.667,\quad P(\text{M}\mid\text{T})=\tfrac{1}{3}\approx0.333,\quad P(\text{M}\mid\text{V})=\tfrac{2}{2}=1.0. \]

Per component: the numerator is how often that specific pair occurred; the denominator is how often the from-item appeared as a “from” at all — so every row that has any outgoing transitions becomes a normalized vote that sums to \(1\) (the T row: \(0+0.667+0.333=1\)).

Two gaps show in the table. Matrix’s row is empty — nobody moved on from Matrix in our log — so the chain has no prediction after it at all (\(\tfrac00\) is undefined); and in any row that does have transitions, it gives every pair it never saw probability \(0\) (Titanic after Vendetta, for instance). The factorized model below is built to fix both gaps.

Reading the table: a user whose last movie was Titanic is predicted to watch Vendetta next (probability \(0.667\), the bigger count); a user whose last was Vendetta is sent to Matrix (\(1.0\)) — so Bob, whose session so far ends in Vendetta, is sent to Matrix, the very blank in his rating-matrix row. (Bob’s own session T\(\to\)V is one of the four we counted, which is harmless in a toy and would not be allowed in a real test, §6.) The whole “model” is a counted table.

A first-order Markov chain counted from four sessions.
Figure 9.2: A first-order Markov chain counted from four sessions. Each arrow is \(P(\text{next}\mid\text{last})\), estimated by dividing the transition count by the row total. After Titanic, Vendetta is the likely next watch (\(0.667\), thick) over Matrix (\(0.333\), thin); after Vendetta, Matrix is certain in this toy (\(1.0\)) — so Bob, whose session ends in Vendetta, is sent to Matrix. Matrix has no outgoing arrow: nobody moved on from it in the four sessions. The model is just these counted, row-normalized arrows.

The two limits — and the fix. A plain Markov chain has no memory beyond the last item (it cannot learn “users who saw both Titanic and Vendetta like Inception”), and it is not personalized (everyone shares one transition table).

The classic remedy for the second limit is Factorizing Personalized Markov Chains (FPMC) (Rendle et al., 2010), which scores the next item as a sum of two dot products (a dot product multiplies two vectors entry by entry and adds: \([a,b]\cdot[c,d]=ac+bd\) — Linear-Algebra primer §4): one from matrix factorization (MF), the user-meets-item score of Traditional Recommender Systems §5, and one from a learned Markov step. (The first limit — memory of more than one step — is what the recurrent network of §3 and the attention model of §4 remove.)

\[ \hat s(u,\,\text{last}=l,\,\text{next}=i)\;=\;\underbrace{\mathbf p_u\cdot\mathbf q_i}_{\text{matrix factorization: does }u\text{ like }i?}\;+\;\underbrace{\mathbf q'_l\cdot\mathbf q''_i}_{\text{Markov: does }i\text{ follow }l?}. \]

Every symbol, in words:

  • \(\hat s\) — the predicted score (the hat marks an estimate, as in the \(\hat r\) of Traditional Recommender Systems); FPMC ranks the candidates by it. It is a score, not a probability.
  • \(u\) — the user; \(l\) — the last item they interacted with; \(i\) — a candidate next item.
  • \(\mathbf p_u\) — user \(u\)’s taste vector, and \(\mathbf q_i\) — item \(i\)’s trait vector: vectors of the kind Traditional Recommender Systems §5 builds (this chapter’s own toy numbers are below), whose dot product is a “does \(u\) like \(i\)?” score.
  • \(\mathbf q'_l\) — a second vector of item \(l\), used when it is the item just watched (the “from” side of a transition); \(\mathbf q''_i\) — a third vector of item \(i\), used when it is the candidate next item (the “to” side). The primes are only labels (read “q-prime” and “q-double-prime”), not derivatives.

So every item carries three vectors: \(\mathbf q\) for its traits, \(\mathbf q'\) for when it is the item just watched, and \(\mathbf q''\) for when it is a candidate next item. Why two transition vectors instead of reusing \(\mathbf q\)? A dot product is symmetric — \(\mathbf q_{\text{T}}\cdot\mathbf q_{\text{V}}=\mathbf q_{\text{V}}\cdot\mathbf q_{\text{T}}\) — so one vector per item would force “Vendetta after Titanic” and “Titanic after Vendetta” to score the same, yet in our log T→V happened twice and V→T never. Transitions have a direction; separate “from” and “to” vectors give them one.

What the two terms do: the first is exactly the MF score of Traditional Recommender Systems §5 (user taste meets item traits); the second replaces the counted transition table with a learned one — “\(i\) tends to follow \(l\)” becomes the dot product \(\mathbf q'_l\cdot\mathbf q''_i\), which can score pairs never seen together (the same low-rank trick that let MF fill blank cells). FPMC is, in one line, MF plus a factorized Markov step — the hinge between the static matrix and the deep sequence models below. (Rendle et al. average the second term over a whole basket of last items; with a single last item it is exactly the formula above.)

Worked example — FPMC scores Bob’s next film. FPMC needs learned vectors, so suppose training on a larger log (our four sessions are a sample of it) produced the \(d=2\) vectors below — two numbers each. For the trait vectors \(\mathbf q\) we use this chapter’s own toy item embeddings (learned item vectors of the kind Traditional Recommender Systems §5 builds, but a fresh set: there Titanic is \([2,0]\)), which every later section reuses so that only the mechanism changes: Titanic \(=[1,0]\), Vendetta \(=[0,1]\), Matrix \(=[1,1]\). Bob’s taste vector is \(\mathbf p_{\text{Bob}}=[0.4,\,0.5]\) (he leans a little more to Vendetta’s feature, as his 5 for Vendetta against 4 for Titanic suggests).

Table 9.2: The toy vectors of each item: traits \(\mathbf q\) (matrix factorization), \(\mathbf q'\) when just watched, \(\mathbf q''\) as the candidate next item.
item traits \(\mathbf q\) (MF) from \(\mathbf q'\) (just watched) to \(\mathbf q''\) (candidate next)
Titanic (T) \([1,0]\) \([1,0]\) \([0.2,\,0.1]\)
Vendetta (V) \([0,1]\) \([0,1]\) \([0.6,\,0.1]\)
Matrix (M) \([1,1]\) \([1,0]\) \([0.3,\,0.9]\)

Bob’s session so far ends in Vendetta, so \(l=\text{V}\) and the Markov term uses \(\mathbf q'_{\text{V}}=[0,1]\). Score each candidate — MF term plus Markov term: \[ \begin{aligned} \hat s(\text{Bob},\text{V},\text{T}) &= [0.4,0.5]\cdot[1,0]+[0,1]\cdot[0.2,0.1] = 0.4+0.1 = 0.5,\\ \hat s(\text{Bob},\text{V},\text{V}) &= [0.4,0.5]\cdot[0,1]+[0,1]\cdot[0.6,0.1] = 0.5+0.1 = 0.6,\\ \hat s(\text{Bob},\text{V},\text{M}) &= [0.4,0.5]\cdot[1,1]+[0,1]\cdot[0.3,0.9] = 0.9+0.9 = \boxed{1.8}. \end{aligned} \]

Matrix wins: Bob’s taste and the “what follows Vendetta” signal both point to it. (We score all three films, including the two he has already seen, to compare with the later sections; a real system usually drops items already in the session, a claim from practice, not tested here.) Two more readings show what the extra vectors buy:

  • Direction. “Vendetta after Titanic” scores \(\mathbf q'_{\text{T}}\cdot\mathbf q''_{\text{V}}=[1,0]\cdot[0.6,0.1]=0.6\), while “Titanic after Vendetta” scores \(\mathbf q'_{\text{V}}\cdot\mathbf q''_{\text{T}}=[0,1]\cdot[0.2,0.1]=0.1\) — matching a log with T→V twice and V→T never. With one vector per item, both would be \(\mathbf q_{\text{T}}\cdot\mathbf q_{\text{V}}=[1,0]\cdot[0,1]=0\).
  • Pairs never seen. The counted table has no Matrix row, so it cannot say anything after Matrix. FPMC can: in the larger log, what people watch after Matrix resembles what they watch after Titanic, so Matrix’s “from” vector came out equal to Titanic’s, \(\mathbf q'_{\text{M}}=[1,0]\). After Matrix, Vendetta then scores \([1,0]\cdot[0.6,0.1]=0.6\) — the largest transition term of the three (M→M \(0.3\), M→T \(0.2\)) — for a pair (M→V) that never occurred in our four sessions. (Adding Bob’s MF term puts Matrix itself on top overall, \(1.2\) against Vendetta’s \(1.1\) and Titanic’s \(0.6\); it is the transition half that has learned where to go after Matrix.)

The learned transition scores echo the counted table without copying it: after Titanic, Vendetta \(0.6\) against Matrix \(0.3\) (counted: \(0.667\) against \(0.333\)); after Vendetta, Matrix \(0.9\) (counted: \(1.0\)). They are scores, not probabilities — only their order matters.

The toy embeddings are learned — each model in this chapter fits its own from the log, and we simply give them all the same values — so they are not the hand-made genre vectors of Traditional Recommender Systems §2, where the same three films sat in a 3-D (action, sci-fi, romance) genre space. Same cast, different space: what carries over is the mechanism (a dot product), not the coordinates.

Why “FPMC.” Factorizing Personalized Markov Chains: it factorizes the transition table into item vectors (so it generalizes), and makes it personalized by adding the per-user MF term.

In one line: counting four sessions gives \(P(\text{V}\mid\text{T})=2/3\approx0.667\) and sends Bob from Vendetta to Matrix with probability \(1.0\); FPMC replaces the counts by vectors, and scores Bob’s three candidates \(0.5\), \(0.6\) and \(1.8\), so Matrix wins and a pair the log never showed (Matrix then Vendetta) still gets a score, \(0.6\).

3. Reading the whole session: GRU4Rec

Bob has watched two films in a row, and the site must guess the third. A guess that looks only at his last film throws half of his evening away. This section builds a running note that is updated after every film, so that the whole evening counts.

A Markov chain forgets everything but the last click. To use the whole session we need a model that carries a running summary of it. A recurrent neural network (RNN) does exactly that: it reads the items left-to-right, and after each one updates a hidden state \(\mathbf h_t\) — a fixed-length vector meant to encode “everything relevant so far” — then scores every candidate next item against it: \[ \mathbf h_t \;=\; f\big(\mathbf h_{t-1},\ \text{embed}(i_t)\big),\qquad \hat s_{t+1}(i) \;=\; \mathbf h_t\cdot\text{embed}(i). \]

Decoded: \(\text{embed}(i_t)\) is the embedding of the item at position \(t\) — its learned vector (§2’s toy embeddings); \(f\) folds it into the previous summary \(\mathbf h_{t-1}\) to produce the new summary \(\mathbf h_t\); and \(\hat s_{t+1}(i)\), the score of a candidate item \(i\) for the next position, \(t+1\), is the dot product of that summary with \(i\)’s embedding — the same dot-product idea as §2 and §4. So after reading \(i_1,\dots,i_t\) the state \(\mathbf h_t\) predicts \(i_{t+1}\) — §1’s convention (read \(i_1,\dots,i_{t-1}\), predict \(i_t\)) moved one step along. The state is the memory — unlike the Markov chain, it can in principle carry information from any earlier position. A case of one number: after Bob’s Titanic the first entry of the summary is \(0.76\); after his Vendetta it has shrunk to \(0.36\) and a second entry has appeared (both worked out below).

GRU4Rec (Hidasi et al., 2016) brought this idea to session-based recommendation. Its \(f\) is a gated recurrent unit (GRU), a cell of the recurrent family. The family has three members, the plain recurrent network, the long short-term memory (LSTM) network and the GRU, and Representation Learning & the Transformer §3 builds all three. The gates of a GRU learn what to keep and what to forget from the running state. A gate is a number between \(0\) and \(1\) that the cell computes at each step: a gate of \(0.2\), for instance, lets the cell keep \(80\%\) of the old value and take \(20\%\) from the newest item (the second worked example below follows one number).

Worked example — a recurrent summary of Bob’s session. To keep the numbers calculator-sized, we use the plain recurrent cell that Representation Learning & the Transformer §3.1 steps by hand, in place of the GRU (the gates would change how much of the old summary is kept, not the shape of the computation), and apply it to each of the two numbers of the vector separately: \[ \mathbf h_t=\tanh\!\big(0.5\,\mathbf h_{t-1}+\text{embed}(i_t)\big),\qquad \mathbf h_0=[0,0], \]

where \(\tanh\) (the hyperbolic tangent) squashes each number into the range \((-1,1)\) — \(\tanh 0=0\), \(\tanh 1=0.7616\) — and \(0.5\) is how much of the old summary carries forward (the same recurrent weight as that chapter’s example). Bob’s session is Titanic \(=[1,0]\), then Vendetta \(=[0,1]\): \[ \begin{aligned} \mathbf h_1 &= \tanh\big(0.5\,[0,0]+[1,0]\big)=[\tanh 1,\ \tanh 0]=[0.7616,\ 0],\\ \mathbf h_2 &= \tanh\big(0.5\,[0.7616,\ 0]+[0,1]\big)=[\tanh 0.3808,\ \tanh 1]=[0.3634,\ 0.7616]. \end{aligned} \]

Score the candidates with \(\hat s_3(i)=\mathbf h_2\cdot\text{embed}(i)\): Titanic \(0.363\), Vendetta \(0.762\), and Matrix \(0.3634+0.7616=\boxed{1.125}\) — Matrix again. Watch Titanic’s trace: \(0.7616\) right after it was read, \(0.3634\) one step later (halved by the \(0.5\), then squashed), while Vendetta enters at full strength. With this cell’s recurrent weight of \(0.5\), the recurrence makes the newer item count more: reverse the session to (Vendetta, Titanic) and \(\mathbf h_2=[0.7616,\ 0.3634]\), tilting toward Titanic instead. Order is built into a recurrent net; §4 shows that attention needs help to see it.

Worked example — what a gate does. In the common form of the GRU, the new state is \(\mathbf h_t=(1-z_t)\,\mathbf h_{t-1}+z_t\,\tilde{\mathbf h}_t\), where \(\tilde{\mathbf h}_t\) is a candidate state built from the newest item and \(z_t\) is the update gate. Follow one number, the Titanic entry of Bob’s summary, which stood at \(0.7616\) after the first film. Suppose the next two films add nothing to that entry (candidate \(\tilde h=0\), set by hand here).

With a gate \(z=0.2\) the cell keeps \(80\%\) of the old value each step: \(0.7616\to0.609\to0.487\). With \(z=0.9\) it almost overwrites: \(0.7616\to0.076\to0.008\). The plain cell above, which has no gate, leaves \(0.7616\to0.363\to0.180\) over the same two steps. Each step shrinks the old value by nearly the same factor (exactly \(0.8\) and \(0.1\) for the two gates, about one half for the plain cell), so two steps show the pattern a longer session would repeat. The plain cell is not a fair rival for the gate, since it differs by more than a gate (an arbitrary weight of \(0.5\) and a squashing \(\tanh\)), and the gate values are hand-picked: the example shows what a gate can do, and that trained GRUs learn to hold useful context this way over a long session is a claim from practice, not tested here.

Why “GRU4Rec.” It is a GRU recurrent network for Recommendation; “4” is the internet’s “for.” The point of the name is the cell: a gated RNN reading a session.

The recurrent view has one structural weakness, though: it must compress the entire past into one vector and process strictly left-to-right, step by step. Long-range dependencies fade (Titanic’s trace above more than halved in a single step — the fade the GRU’s gates are there to slow), and within one session the computation is strictly sequential — step \(t\) must wait for step \(t-1\) — so it cannot be parallelized along the sequence; the session-parallel mini-batches of the box below only parallelize across different sessions. Both complaints are answered by letting each position look directly at every earlier one — attention.

Side issue: two engineering ideas behind GRU4Rec. The paper presents them as the modifications that make a recurrent network viable for session data (a claim from practice, not tested here), and neither changes the arithmetic above.

  • Session-parallel mini-batches. A mini-batch is the handful of examples processed together in one training step. GRU4Rec fills it with many short sessions side by side, so that the graphics processing unit (GPU) — a chip that runs many simple computations at once — always has work to do.
  • A ranking loss. The loss is a pairwise one in the style of Bayesian Personalized Ranking (BPR): it pushes the true next item above a sampled item that did not come next (Loss Functions & Regularizers §9), rather than computing a full softmax over a huge catalog (a softmax turns a score for every item into probabilities that sum to \(1\); §4 computes a small one).

In one line: a recurrent net folds Bob’s session into one running summary, \([0.3634,\ 0.7616]\) after Titanic then Vendetta, which scores Matrix \(1.125\) against Vendetta \(0.762\) and Titanic \(0.363\); a gate near \(0\) keeps the old value and a gate near \(1\) overwrites it (Titanic’s trace is \(0.487\) two films later for \(z=0.2\) and \(0.008\) for \(z=0.9\)).

4. Attention over the session: SASRec

Bob’s evening so far is two films, and the guess for the third should lean on both, though perhaps not equally. How much should each earlier film count? This section computes those weights from the films themselves, by hand, and uses them to score the next film.

Representation Learning & the Transformer built the Transformer — the attention-based neural network behind today’s large language models — and at its heart self-attention: a mechanism where each position forms a query (the question it asks of the other positions; Vendetta, Bob’s last film, asks “which earlier films are like me?”), compares it, by dot product, against the key each position holds (a label saying what that position is about), turns those similarities into softmax weights, and reads out a weighted average of the values (what each position hands over when it is matched). Self-Attentive Sequential Recommendation (SASRec) (Kang & McAuley, 2018) is that mechanism applied to a session: stack the item embeddings of the prefix, run self-attention, and the output at the last position is the summary used to score the next item.

Two adaptations make attention fit recommendation:

  • A causal mask. A mask is a grid of yes/no entries that says which position may look at which; the causal one lets the output at position \(t\) attend only to positions \(\le t\) — itself and earlier ones — and that output is used to predict the item at the next position, \(t+1\), so the model never sees the item it is trying to predict. (Same lower-triangular mask the Transformer chapter used for left-to-right language models.) In a three-item session, position \(2\) may look at positions \(1\) and \(2\) but not at \(3\).
  • Positional embeddings: raw attention is order-blind (hold the query fixed, permute the keys and values, and the weighted average is unchanged), so SASRec adds a learned position vector to each item embedding, re-injecting “this was the 1st / 2nd / … click,” so that the same film at position \(1\) and at position \(3\) gets two different vectors. A case, with the toy embeddings and the last film Titanic as the query: the sessions (Vendetta, Matrix, Titanic) and (Matrix, Vendetta, Titanic) give the same context (the attention-weighted average of the values, here just the embeddings, set up below) \([0.802,\,0.599]\) without positions (weights \(0.198,\,0.401,\,0.401\) on Vendetta, Matrix, Titanic); adding \([0,0.5]\) to the first film’s key and value turns them into \([0.802,\,0.698]\) and \([0.802,\,0.799]\), so order now shows. (The worked example below leaves positional vectors out — so it is blind to the order of the earlier films — and says so where it matters.)

Worked example — one self-attention step, by hand. Bob’s session so far is \((\text{Titanic},\ \text{Vendetta})\); predict the next item. Use the chapter’s toy embeddings (§2), \(d=2\) numbers each: \[ \text{Titanic}=[1,0],\quad \text{Vendetta}=[0,1],\quad \text{Matrix}=[1,1]. \]

(This bold \(\mathbf q_j\) is an attention query, not the trait vector \(\mathbf q_i\) of §2; the two only share a letter.) Normally each item’s query, key and value are made from its embedding by three learned matrices: for the item \(i_j\) at position \(j\), \(\mathbf q_j=\text{embed}(i_j)\,W_Q\), \(\mathbf k_j=\text{embed}(i_j)\,W_K\) and \(\mathbf v_j=\text{embed}(i_j)\,W_V\) (a row vector times a matrix, as in the Transformer chapter §4.1). These multiplications are called projections — machine-learning jargon for multiplying by a learned matrix, not the “shadow” projection of the Linear-Algebra primer. To keep every number checkable, set all three matrices to the identity \(I\) (the matrix that leaves a vector unchanged), so query, key and value all equal the embedding. Real SASRec learns the matrices and adds positional vectors; here we expose the bare mechanism, exactly as the Transformer chapter first did.

The general step, for the query at the last position \(t\) attending to positions \(j=1,\dots,t\): \[ \alpha_{tj}=\frac{e^{\,\mathbf q_t\cdot\mathbf k_j/\sqrt d}}{e^{\,\mathbf q_t\cdot\mathbf k_1/\sqrt d}+\dots+e^{\,\mathbf q_t\cdot\mathbf k_t/\sqrt d}},\qquad \mathbf c=\alpha_{t1}\mathbf v_1+\dots+\alpha_{tt}\mathbf v_t,\qquad \hat s(i)=\mathbf c\cdot\text{embed}(i). \]

Decoded: \(\mathbf q_t\cdot\mathbf k_j\) is how well position \(j\)’s key matches the query, and dividing it by \(\sqrt d\) keeps the scores from growing with the number of entries \(d\) (large scores would make the softmax put nearly all the weight on one item; the Transformer chapter §4.1 shows why \(\sqrt d\) is the right size); \(\alpha_{tj}\), the attention weight — how much position \(t\) attends to position \(j\) — is the softmax of those scores (\(e\approx2.718\) is Euler’s number; the weights are positive and sum to \(1\)); the context vector \(\mathbf c\) is the weighted average of the values; and each candidate \(i\) is scored by the dot product of \(\mathbf c\) with its embedding.

Now the numbers. The query sits at the last position, \(t=2\): \(\mathbf q_2=\) Vendetta \(=[0,1]\). Score it against the two keys (Titanic at position 1, Vendetta at position 2), scaled by \(\sqrt d=\sqrt2\approx1.414\): \[ \frac{\mathbf q_2\cdot\mathbf k_{\text{T}}}{\sqrt d}=\frac{[0,1]\cdot[1,0]}{1.414}=\frac{0}{1.414}=0, \qquad \frac{\mathbf q_2\cdot\mathbf k_{\text{V}}}{\sqrt d}=\frac{[0,1]\cdot[0,1]}{1.414}=\frac{1}{1.414}=0.707. \]

(Both keys sit at positions \(\le 2\), the query’s own position, so the causal mask blocks nothing here.) Softmax turns the two scores \([0,\,0.707]\) into weights — \(e^{0}=1\), \(e^{0.707}=2.028\), sum \(=3.028\): \[ \alpha_{\text{T}}=\tfrac{1}{3.028}=0.330,\qquad \alpha_{\text{V}}=\tfrac{2.028}{3.028}=0.670 \]

(short for \(\alpha_{21}\) and \(\alpha_{22}\): how much position 2 attends to positions 1 and 2).

The context vector is the weighted average of the values (here the embeddings): \[ \mathbf c = 0.330\,[1,0] + 0.670\,[0,1] = [\,0.330,\ 0.670\,]. \]

Finally, score each candidate next item by its dot product with \(\mathbf c\) (the same “embedding \(\cdot\) summary” scoring rule as everywhere else in the book): \[ \begin{gathered} \text{Titanic}: [0.330,0.670]\cdot[1,0]=0.330,\qquad \text{Vendetta}: 0.670,\\[6pt] \text{Matrix}: [0.330,0.670]\cdot[1,1]=\boxed{1.000}. \end{gathered} \]

Reading it: attention gave Vendetta the larger weight (\(0.670\)) but did not ignore Titanic (\(0.330\)); the context blends both, and Matrix — which shares a feature with each — scores highest (\(1.000\)) and is recommended next. Three notes qualify this reading:

  • The larger weight is not recency. This bare step cannot see the order of the earlier films: it has no positional vectors, and attention on its own is order-blind: a film keeps its weight wherever it sits among the keys. It does see which film is last, because the last film is the query (reverse the session and the query changes, as exercise 3 shows).
  • Why Vendetta wins. Vendetta gets \(0.670\) because it is the query, and with identity projections each of these toy films matches itself at least as well as any other (\(\mathbf q_2\cdot\mathbf k_{\text{V}}=1\) against \(\mathbf q_2\cdot\mathbf k_{\text{T}}=0\)); in a session (Matrix, Vendetta) the most recent item would get only \(0.5\). Recency enters SASRec only through the positional embeddings, which a trained model can use to prefer recent items.
  • Matrix’s \(1.000\) is built into the toy. Matrix \(=[1,1]\) is Titanic \(+\) Vendetta, and the weights sum to \(1\), so Matrix scores exactly \(\alpha_{\text{T}}+\alpha_{\text{V}}=0.330+0.670=1.000\) whatever the weights are. To see the weights matter, score two other candidates: a Vendetta-like film \([0.2,\,0.9]\) gets \(0.330(0.2)+0.670(0.9)=0.669\), and a Titanic-like film \([0.9,\,0.2]\) gets \(0.330(0.9)+0.670(0.2)=0.431\) — the tilt toward Vendetta decides between them; with equal weights both would tie at \(0.55\).

The whole step is dot products and one softmax, no different from the Transformer chapter — only the input (a session) and the read-out (next-item scores) are new.

One causal self-attention step (SASRec), reproducing the worked numbers.
Figure 9.3: One causal self-attention step (SASRec), reproducing the worked numbers. The query is the session’s last item, Vendetta, reused; it is compared with the keys of the session’s two items, which also serve as the values. The last item, acting as the query, matches itself most, so the thick edge to Vendetta carries \(\alpha{=}0.670\) and the thin one to Titanic \(\alpha{=}0.330\) — a match, not recency: this bare step has no positional vectors and cannot see the order of the earlier films. The weighted average of the values is the context \([0.330,0.670]\), which scores each candidate by a dot product — Matrix wins at \(1.000\).

Why “SASRec.” Self-Attentive Sequential Recommendation: it drops the RNN for the Transformer’s self-attention, so every position reads every earlier one directly — capturing long-range “what predicts what” in one parallel layer (a claim from practice, not tested here).

In practice. The claims in this box come from the cited papers and the library’s own description; we have not tested them here. Real SASRec (Kang & McAuley, 2018) stacks a few blocks of masked self-attention, each followed by a small feed-forward network (two ordinary layers applied to each position separately; Transformer chapter), adds learned positional embeddings, and trains with a binary loss: a yes/no score that pushes the true next item up and pushes one randomly drawn item that did not come next, a negative, down (on the scores above: Matrix’s \(1.000\) up, and Titanic’s \(0.330\) down if Titanic is the one drawn).

Rather than coding it from scratch, you can start from RecBole (Zhao et al., 2021), an open-source library whose paper lists 73 recommender models (94 when the book was checked), SASRec and BERT4Rec among them, with shared evaluation code and automatic parameter tuning.

In 2023 Klenitskiy and Vasilev described SASRec and BERT4Rec as the two state-of-the-art baselines. Run SASRec before claiming that a new model wins.

In one line: for Bob’s session the attention weights are \(0.330\) (Titanic) and \(0.670\) (Vendetta), which sum to \(1\); the context is \([0.330,\ 0.670]\), and Matrix scores \(1.000\) against Vendetta \(0.670\) and Titanic \(0.330\). The larger weight comes from a self-match, not from recency.

5. Looking both ways: BERT4Rec

Ann covers one film in her watch list with a sticky label and asks Bob to guess it. Seeing the films before and after the label makes the guess easier. This section trains a model the same way, and asks what that really gains when a real recommendation has no films after it.

SASRec reads strictly left-to-right: the output at position \(t\) may use only positions up to \(t\). That is the right constraint at inference — when the trained model is used to make a live recommendation, and the future genuinely is unknown — but it makes training one-directional: each item is predicted from its left context only. The Transformer chapter showed a different pretraining recipe (learning from unlabelled data before the real task), from BERT (Bidirectional Encoder Representations from Transformers, a text model): its masked-language model hides random tokens — the words, or pieces of words, of a sentence — and predicts each from both sides at once.

BERT4Rec (Sun et al., 2019) applies that recipe to sequences. It uses bidirectional self-attention (no causal attention mask) and trains with the cloze objective (hide Vendetta in (Titanic, [mask], Matrix) and ask the model to restore it): randomly hide a fraction of the items in the session — replace each with a special [mask] token, whose embedding is one more learned vector meaning “unknown item” — and predict each hidden item from everything around it, left and right. At inference, it appends a [mask] token to the end of the session and predicts that, recovering next-item recommendation.

What does looking both ways buy, if the [mask] sits at the end? At recommendation time the appended [mask] has nothing to its right, so the gain is not there. It comes from two places. In training, every hidden item is learned from both of its sides, and one session yields many different training examples, because a different set of items can be hidden each time (Sun et al. also add examples that hide only the last item — exactly the recommendation-time situation).

At recommendation time, the model is a stack of several attention layers, and in each one every item already in the session — all of them in the past, so nothing leaks — rebuilds its vector from the items on both sides of it; the [mask] at the end then reads summaries formed in both directions, where a left-to-right model’s earlier positions saw only their own past. That this helps is a claim from practice, not tested here.

Why “BERT4Rec” and “cloze.” It ports BERT — Bidirectional Encoder Representations from Transformers, the bidirectional Transformer text model of the Transformer chapter — to Recommendation. Cloze (from “closure,” Taylor, 1953) is the fill-in-the-blank task from language testing — delete a word and have the reader restore it from context; BERT4Rec deletes an item and restores it from the surrounding session.

SASRec and BERT4Rec differ in two choices that usually travel together but are independent, and both involve something called a mask. One is the attention mask — which positions may look at which: SASRec forbids looking right, BERT4Rec allows it. The other is the training task — SASRec predicts the next item, while BERT4Rec hides random items behind [mask] tokens (masking items) and restores them.

The two are separate choices: the grids in the figure below show the first, the input rows the second. With no attention mask, every position can look at every other position, including the one whose own item is hidden behind [mask].

Causal vs. cloze. Each grid is an attention mask: a row is the position doing the looking (its query), a column the position looked at (its key), and a filled cell means “may attend”.
Figure 9.4: Causal vs. cloze. Each grid is an attention mask: a row is the position doing the looking (its query), a column the position looked at (its key), and a filled cell means “may attend”. SASRec (left) is lower-triangular — the output at position \(t\) attends only to positions \(\le t\) and predicts the item at \(t+1\), so it learns to predict the next item from the past alone. BERT4Rec (right) lets every position attend both ways, and is trained by hiding an input item behind the [mask] token (here position 2, Vendetta, in the session Titanic, Vendetta, Matrix that the worked example of this section supposes for Bob) and restoring it from the rest. The grids show which positions may attend; the input rows show which items are hidden.

Worked example — one hidden item, read both ways. Suppose Bob did go on to watch Matrix, so his session is (Titanic, Vendetta, Matrix). For one cloze training step, hide Vendetta: the input becomes (Titanic, [mask], Matrix). Use §4’s embeddings and identity projections, and give the untrained [mask] the vector \([0,0]\). The query at the hidden position is then \([0,0]\), so every scaled score is \(0/1.414=0\) and the softmax spreads the weight equally:

  • Bidirectional (BERT4Rec): all three positions are visible, weights \(\tfrac13\) each: \(\mathbf c=\tfrac13\big([1,0]+[0,0]+[1,1]\big)=[0.667,\ 0.333]\), and the hidden item Vendetta scores \(\mathbf c\cdot[0,1]=0.333\).
  • Causal (SASRec’s attention mask, for contrast only): SASRec itself never hides items, and its output at position 2 would predict position 3; here we only ask what position 2 could see under that mask on the same input. It may see only positions 1 and 2, weights \(\tfrac12\) each: \(\mathbf c=\tfrac12\big([1,0]+[0,0]\big)=[0.5,\ 0]\), and Vendetta scores \(0\).

The item to the right, Matrix, is what lifts the true hidden item from \(0\) to \(0.333\). (Neither bare step ranks Vendetta first — under the bidirectional context Titanic scores \(0.667\) and Matrix \(1.000\) — and training adjusts the vectors until the hidden item wins; the numbers only show what each attention mask lets the hidden position see.)

Which model wins is not settled. Petrov and Macdonald (2022) reviewed the papers that compare the two and found their results inconsistent; BERT4Rec matched the strength first reported for it only when trained for much longer than its default settings (up to \(30\) times). Klenitskiy and Vasilev (2023) found that SASRec, trained with the same full-softmax loss (a softmax over the whole catalog, see §6) as BERT4Rec, clearly beat it. Both studies use a few public datasets; that the same holds on yours is a claim from practice, not tested here.

So report both models, tune them with equal effort (the same amount of trial and error spent on how long each vector is, how big each training step is and how many layers there are), and say what budget each got (the reproducibility caution of the Datasets & Benchmarks appendix applies here too).

In one line: with Vendetta hidden in (Titanic, [mask], Matrix), looking both ways gives the hidden position weights \(\tfrac13\) each and scores Vendetta \(0.333\), where a left-only mask gives \(0\); which of SASRec and BERT4Rec wins overall is disputed in the literature.

6. Training and evaluating a sequence model

A recommender must be graded on films it has not seen, but which ones do we hide? Hide Bob’s last film and the test copies real life; hide a random one and the model may already know what he watched afterwards. This section sets up the training examples and a fair test.

From a log to sessions. A raw log is rows of (user, time, film); a new session starts after a long enough pause, often a fixed inactivity gap such as \(30\) minutes, or at a logout. Take a one-off user, Dan, whose rows are 20:02 Titanic, 20:15 Vendetta, 20:31 Matrix, then 09:10 next day Inception. The gaps are \(13\), \(16\) and \(759\) minutes, so the rows form two sessions, (T, V, M) and (Inception). Clock time cuts the log here; the models afterwards see only order. A film watched twice stays in the list twice; the chapter’s toys have no repeats.

Training — every prefix is an example. A single session of length \(n\) is not one training example but \(n-1\): from each prefix \((i_1,\dots,i_{t-1})\) predict \(i_t\). Take Ann’s four-item history — Titanic, Vendetta, Matrix, then a fourth film, Inception. It gives \(n-1=3\) training examples: \((\text{T})\!\to\!\text{V}\), then \((\text{T},\text{V})\!\to\!\text{M}\), then \((\text{T},\text{V},\text{M})\!\to\!\) Inception — the same history, read at three different lengths.

The loss. On each example the usual next-item objective is a softmax over the catalog, or a sampled softmax (the same formula evaluated over just the true next item plus a handful of randomly drawn others, instead of the whole catalog), or a pairwise BPR ranking loss (Loss Functions & Regularizers §9–§10), or SASRec’s own binary loss (§4). The randomly drawn others are negatives (see §4), items the user did not pick next, and negative sampling means scoring only a few of them rather than millions of items at every step (Training and Serving a Recommender). BERT4Rec instead optimizes the cloze loss (predict the masked positions). Either way the model learns embeddings and attention/recurrence weights by gradient descent (Calculus primer).

A small case on §4’s scores for Bob’s session: Titanic \(0.330\), Vendetta \(0.670\), Matrix \(1.000\), true next item Matrix. The full softmax gives Matrix \(e^{1.000}/(e^{0.330}+e^{0.670}+e^{1.000})=0.448\) and a loss of \(-\ln 0.448=0.802\). Sampling one negative, say Titanic, gives \(e^{1.000}/(e^{1.000}+e^{0.330})=0.662\) and a loss of \(0.413\), which is also the BPR loss \(-\ln\sigma(1.000-0.330)\) (\(\sigma(x)=1/(1+e^{-x})\) the logistic function), since with one negative the two coincide. SASRec’s binary loss scores the true item and the negative separately: \(-\ln\sigma(1.000)-\ln\big(1-\sigma(0.330)\big)=0.313+0.872=1.185\). For the cloze step of §5 (hidden Vendetta, scores Titanic \(0.667\), Vendetta \(0.333\), Matrix \(1.000\)) the softmax gives Vendetta \(0.230\) and a cloze loss of \(1.469\), and training pushes that probability up.

Evaluation — split by time, not at random. A sequence model must be graded the way it will be used: predict the future from the past. A common protocol, used for SASRec by Kang and McAuley (2018), is the leave-one-out (LOO) split. For each user, hold out their chronologically last interaction as the test target, the second-last for validation (used to choose settings), and train on the rest. Here is the split for two users of this chapter, Bob (the three films of §5) and Ann (the four-item history above):

Table 9.3: Each user’s history cut into training films, one validation example and one test example.
user history, in time order train validation example test example
Bob T, V, M T \((\text{T})\to\text{V}\) \((\text{T},\text{V})\to\text{M}\)
Ann T, V, M, Inception T, V \((\text{T},\text{V})\to\text{M}\) \((\text{T},\text{V},\text{M})\to\) Inception

Bob’s three films leave one film, Titanic, for training, and one film makes no prefix-to-next pair (\(n-1=0\) examples), so Bob teaches the model nothing directly. Ann’s four films leave two for training, which make one pair, \((\text{T})\to\text{V}\). A pair needs a prefix and a next film both inside the training part, so a user needs at least four films to give one under this protocol. In this chapter’s protocol the model may read the validation film as part of the test input (it lies in the past) but is never trained on it or on the test film.

The ranked list is then scored with two measures from Evaluation Metrics: the hit rate (HR), which asks only whether the held-out item made the top \(K\) at all, and the normalized discounted cumulative gain (NDCG), which asks the same question but pays more the higher up the list the item sits. Written with the cut-off \(K\) they are \(\text{HR}@K\) and \(\text{NDCG}@K\).

This chapter ranks the held-out film against the whole catalog. Many sequential-recommendation papers instead rank it against about a hundred sampled negatives, a protocol that can distort HR and NDCG, so numbers from the two protocols should not be compared (a claim from practice, not tested here).

Grading §4’s step. Bob’s test example is \((\text{T},\text{V})\to\text{M}\), exactly the session §4 scored. That step ranked Matrix \(1.000\) above Vendetta \(0.670\) above Titanic \(0.330\), so the held-out item came first: \(\text{HR}@1=1\) and \(\text{NDCG}@1=1\), a perfect grade on this one user. Had it landed at rank \(2\) instead, \(\text{HR}@1=0\), \(\text{HR}@2=1\) and \(\text{NDCG}@2=1/\log_2(2+1)=1/1.585=0.631\): the discount is what makes rank \(1\) worth more than rank \(2\).

Why not a random split. A random split could put Bob’s Matrix in training and hide his Vendetta, so the model would train on an event that happened after the one it is tested on. A small case shows the effect. Use an order-blind taste model: a user’s profile is the average of the film vectors in their training data, and a film scores by its dot product with the profile. The films are Titanic \([1,0]\), Vendetta \([0,1]\), Matrix \([1,1]\) and a decoy, Frozen \([0.4,0]\), which Bob never watched. The test hides Bob’s Vendetta (his second film) and asks which of Vendetta and the decoy scores higher.

  • Fair, past only. Train on Titanic: profile \([1,0]\). Vendetta scores \(0\) and the decoy \(0.4\), so the decoy wins and \(\text{HR}@1=0\).
  • Leaky, random split. Train on Titanic and the later Matrix: profile \(\tfrac12\big([1,0]+[1,1]\big)=[1,\ 0.5]\). Vendetta scores \(0.5\) and the decoy \(0.4\), so Vendetta wins and \(\text{HR}@1=1\).

With the same model and the same hidden film, the score went from \(0\) to \(0.5\) and the rank from second to first, only because a film Bob watched afterwards was in training. Matrix shares Vendetta’s second feature, so the future gave the answer away. This split discipline, and the leakage trap it avoids, is detailed in the Datasets & Benchmarks appendix.

Two ways to cut the history. Leave-one-out holds the future back for each user separately: every user’s own last films are the ones set aside. The global temporal split instead cuts everybody at one calendar date: train on everything before it, test on everything after (Evaluation Metrics). With a cut at 1 May, Ann’s film of 12 March goes to training and Bob’s film of 9 June to test, whatever each user’s own last film is.

In one line: a four-film history gives \(4-1=3\) training examples; evaluate by holding out each user’s last interaction (Bob: train on \(1\) film, validate on \(1\), test on the last), because a random split in our toy raised a hidden film’s score from \(0\) to \(0.5\) and flipped \(\text{HR}@1\) from \(0\) to \(1\) by letting the model see a later film.

7. Exercises

Work these by hand — the numbers are kept tiny on purpose, and reuse the chapter’s Titanic/Vendetta/Matrix sessions. Full worked solutions are in the Solutions appendix at the back of the book.

  1. (compute) A new log holds four sessions over the three films, written in time order: \(\text{M}\!\to\!\text{V}\!\to\!\text{T}\), \(\text{M}\!\to\!\text{V}\), \(\text{M}\!\to\!\text{V}\!\to\!\text{T}\) and \(\text{M}\!\to\!\text{T}\). (a) Count every adjacent pair and give the transition probabilities out of M and out of V. (b) Titanic appears in three of the four sessions. What does a first-order chain predict after Titanic, and why? Then one more session, \(\text{T}\!\to\!\text{M}\), is added to the log: what does the chain predict after Titanic now, and with what probability?

  2. (compute) Use the four-session chain of exercise 1 (before the fifth session is added). Ann’s session so far is (Matrix, Vendetta) and Cara’s is (Titanic, Vendetta). What does the chain recommend for each of them, with what probability? What does the pair of answers show about what a first-order chain can see? A chain whose state is the last two films would tell the two sessions apart: how many rows would its table need over the three films?

  3. (compute) Redo §4’s self-attention step but with Bob’s session reversed to \((\text{Vendetta},\ \text{Titanic})\) — the same two items in the opposite order, so the query is now Titanic \(=[1,0]\). Using identity projections and \(\sqrt d=\sqrt2\), compute the two raw scores, the softmax weights, the context vector, and the three candidate scores. Which item is recommended now — and what did reversing the order change, if not the top pick?

  4. (compute) In a session of three films, the scaled attention scores of the last position against the three keys are \(0\), \(0.5\) and \(1.2\). Compute the three softmax weights (use \(e^{0.5}\approx1.649\) and \(e^{1.2}\approx3.320\)), check that they add up to \(1\), and say how many times larger the biggest weight is than the smallest.

  5. (compute) Using §4’s context vector \(\mathbf c=[0.330,0.670]\), score a fourth candidate “Inception” with embedding \([2,0]\). Where does it rank against Titanic (\(0.330\)), Vendetta (\(0.670\)), and Matrix (\(1.000\))? Its score comes out double Titanic’s even though \([2,0]\) and \([1,0]\) point in exactly the same direction. Which property of Inception’s vector causes that, and compute the cosine of the angle between \(\mathbf c\) and each of the two vectors, and say what the two numbers show. (Use \(\cos\theta=\mathbf a\cdot\mathbf b\,/\,(\lVert\mathbf a\rVert\,\lVert\mathbf b\rVert)\), where \(\lVert\mathbf a\rVert=\sqrt{a_1^2+a_2^2}\) is the length of a vector and \(\theta\) the angle between the two.)

  6. (compute and concept) A plain recurrent cell reads Cara’s long session with \(h_t=\tanh(0.5\,h_{t-1}+x_t)\), one number at a time. Her first film puts \(x_1=2\) into one entry of the summary, and the films after it put \(x_t=0\) into that entry, so \(h_1=\tanh(0.5\times0+2)\). (a) Compute \(h_1\), \(h_2\) and \(h_3\). (b) After how many steps beyond \(h_1\) does the entry first fall below \(0.01\)? (c) From here on each step roughly halves the entry (once it is small, \(\tanh x\approx x\)): about how small is it at \(h_{50}\), a power of ten being enough, and what does that mean for the opening films of a fifty-film session?

  7. (apply) A colleague trains a bidirectional model to restore the last film of (Titanic, Vendetta, Matrix) but forgets to hide it: the input is the full session, with the embeddings of §4 and identity projections. (a) Compute the attention weights of position 3 (its query is Matrix, and it has three keys), the context vector, and the score the context gives Matrix. (b) Now replace the film at position 3 by a blank input \([0,0]\) (a masked slot: its query, key and value are all \([0,0]\)) and compute the weights, the context and Matrix’s score again. In which of the two runs does the score depend only on the two neighbours, and which run would you prefer for training a model to learn about what surrounds a film?

  8. (apply) Ann’s session has the same three films in two orders: A \(=\) (Titanic, Vendetta, Matrix) and B \(=\) (Vendetta, Titanic, Matrix), with the vectors of §4. (a) Compute the bag-of-items summary (the average of the three film vectors) for A and for B. (b) Compute the bare attention step of §4 for each (identity projections, no positional vectors, query \(=\) the last film, scores scaled by \(\sqrt2\)): the three weights and the context. (c) Can the bag average, the first-order Markov chain of §2, or this bare step tell A from B? Say why. (d) Now add a position vector \([0.5,0]\) to the film at position 1 of each session (keys and values) and redo the bare step: do the two contexts differ?

  9. (compute and concept) Cara watched Titanic \([1,0]\), then Matrix \([1,1]\), then Vendetta \([0,1]\). Use the order-blind taste model of §6 (profile \(=\) average of the training films, score \(=\) dot product with the profile) and a decoy film, Joker \([1.5,0]\), that Cara never watched. The test hides her second film, Matrix, and asks which of Matrix and the decoy scores higher. (a) Train on Titanic only (past only) and give both scores. (b) Train on Titanic and the later Vendetta and give both scores. (c) Which of (a) and (b) is the leak, and which split of §6 avoids it? Then: another user, Zed, clicked a film in June, after Cara’s March test film, and that click is in the log. Is Zed’s June click kept out of training by leave-one-out, and by a global temporal split whose cut-off date falls in April?

  10. (apply) FPMC (§2) scores the next item as \(\mathbf p_u\cdot\mathbf q_i+\mathbf q'_l\cdot\mathbf q''_i\). Say which term dominates for (a) a brand-new, anonymous session with a strong “last item” signal (the user vector \(\mathbf p_u\) is cold: an average, uninformative vector), and (b) a long-time user whose tastes are well known but whose last click was an accidental mis-tap. Which model of this chapter uses only a last-item (Markov) signal and no user term — and how does its version of that signal differ from \(\mathbf q'_l\cdot\mathbf q''_i\)?

  11. (compute) Cara’s taste vector is \(\mathbf p_{\text{Cara}}=[0.3,\,0.6]\) and her session ends in Matrix, whose “from” vector is \(\mathbf q'_{\text{M}}=[0.5,\,1]\) (not the §2 value). Score two candidates with FPMC (§2), using the trait vectors \(\mathbf q_{\text{T}},\mathbf q_{\text{V}}\) of §2 for the MF term and these new “to” vectors (not the §2 ones): Titanic \(\mathbf q''_{\text{T}}=[0.4,\,0.2]\) and Vendetta \(\mathbf q''_{\text{V}}=[0.1,\,0.3]\). (a) Give both scores, split into the MF term and the Markov term. (b) Which film is recommended, and which of the two terms put it ahead?

  12. (compute and concept) Another user, Eve, has this history, in time order: Inception, Titanic, Vendetta, Matrix, Joker (five films). (a) Write her leave-one-out split of §6: the training films, the validation example and the test example. (b) How many training examples (prefix to next film) does her training part give? (c) How many would the whole history give if nothing were held out? (d) For a user with \(n\) films, how many films must \(n\) be for leave-one-out to leave exactly three training examples? Give the reason in one line.

  13. (compute and concept) Follow one number of a recurrent summary through films that add nothing to it (candidate \(\tilde h=0\)), with the update rule of §3, \(h_t=(1-z)\,h_{t-1}+z\,\tilde h\). The entry stands at \(0.5\). (a) Compute it after two films for a gate \(z=0.3\) and for a gate \(z=0.8\). (b) The first film of a six-film evening must still matter at the end: compute the fraction of the entry left after six films for each gate and say which gate the model needs. For what kind of session would you want the other one? (c) After how many films does the entry first fall below \(0.01\) for each gate?

8. Where this fits in the book

Sequential recommendation is the order-aware lens on the very same interaction log that the matrix (Traditional Recommender Systems) and the graph (From Graphs to LightGCN) read differently — three complementary views of one stream of events (the three-views figure in §1). Its importance to the book is the bridge it builds: SASRec and BERT4Rec are the self-attention of the Transformer chapter pointed at item sequences, with the adaptations of §4 and §5 (a causal mask, positional embeddings, a next-item or cloze loss). That is why this chapter is the on-ramp to the era of large language models (LLMs): an LLM is a sequence model, and recommending the “next item” is the same shape of problem as predicting the next token.

Idea (here) Where it returns
Item embeddings, scored by a dot product (§2, §4) the embeddings of Traditional Recommender Systems §5 and From Graphs to LightGCN
Self-attention over a session (§4) the Transformer chapter’s mechanism, reused; the on-ramp to Large Language Models and Recommendation
Causal vs. cloze masking (§5) the GPT-style (left-to-right, predict the next token — Generative Pre-trained Transformer) vs. BERT-style (hide tokens, predict each from both sides) pretraining of the Transformer chapter
Next-item softmax / BPR loss (§6) Loss Functions & Regularizers §9–§10
Leave-one-out (LOO) split, HR@\(K\) / NDCG@\(K\) (§6) Evaluation Metrics; the leakage discussion of the Datasets & Benchmarks appendix

Carry this forward: the matrix forgets order; a sequence model remembers it — from a one-step Markov count, to a recurrent summary, to self-attention that lets the next item look back over the whole session. That last step is the Transformer, which is also what the LLM era runs on.

9. Glossary

Term Plain meaning
Sequential recommendation Predict the next item from a user’s ordered history.
Session-based recommendation Same, but from a short, often anonymous current session (no user id).
Session The ordered items one person goes through in one sitting, a visit or an evening; short, and sometimes anonymous.
Gate / GRU A gate is a number between \(0\) and \(1\) the cell computes at each step to decide how much of the new candidate to write in (near \(0\) keeps the old summary, near \(1\) overwrites it); the gated recurrent unit (GRU) is the recurrent cell built on gates (§3).
Query, key, value In attention, each position’s query asks, each key says what that position is about, and each value is what it hands over when matched (§4).
Attention weight The softmax of the scaled query-key scores: how much one position attends to another; positive, summing to \(1\).
Context vector The weighted average of the values under the attention weights; the summary that scores the next item (§4).
[mask] token A placeholder that replaces a hidden item in BERT4Rec’s input, so the answer is not in what the model reads (§5).
Prefix The beginning of a list, \((i_1,\dots,i_{t-1})\): the items seen so far, in order.
Next-item prediction The core task: given \((i_1,\dots,i_{t-1})\), score every item for being \(i_t\).
Markov chain (first-order) Next item depends only on the last one; transitions estimated by counting.
Transition probability \(P(\text{next}=i\mid\text{last}=l)\) — count of \(l\!\to\!i\) over count of \(l\)-as-from.
FPMC Factorizing Personalized Markov Chains: MF term \(+\) a learned (factorized) transition term.
RNN / hidden state \(\mathbf h_t\) A net that folds each item into a running fixed-length summary of the session.
GRU4Rec A gated RNN for session-based recommendation; session-parallel batches + a ranking loss.
Self-attention Each position attends (by dot-product softmax) to others, reading a weighted average (Transformer chapter).
SASRec Self-Attentive Sequential Recommendation: a causal Transformer over the item sequence.
Causal mask Lower-triangular mask: position \(t\) may attend only to positions \(\le t\) (no peeking at the future).
Positional embedding A learned per-position vector added to item embeddings so attention can see order.
BERT4Rec A bidirectional Transformer trained with the cloze (masked-item) objective.
Negative (sample) An item the user did not choose next, used as a wrong answer that the true next item must outscore.
Cloze objective Mask random items and predict each from both-side context (fill-in-the-blank).
Leave-one-out (LOO) split Hold out each user’s chronologically last interaction for test, the second-last for validation (a per-user cut).
Global temporal split One cut-off date for everybody: train on everything before it, test on everything after (Evaluation Metrics).
Hit-Rate@K (HR@K) / NDCG@K Was the held-out next item in the top \(K\)? / how high was it — normalized discounted cumulative gain (Evaluation Metrics).

10. References

  • Taylor, W. L. (1953). “Cloze procedure”: A new tool for measuring readability. Journalism Quarterly, 30(4), 415–433. https://doi.org/10.1177/107769905303000401

  • Rendle, S., Freudenthaler, C., & Schmidt-Thieme, L. (2010). Factorizing personalized Markov chains for next-basket recommendation. In Proceedings of the 19th International Conference on World Wide Web (WWW), 811–820. https://doi.org/10.1145/1772690.1772773

  • Hidasi, B., Karatzoglou, A., Baltrunas, L., & Tikk, D. (2016). Session-based recommendations with recurrent neural networks. In International Conference on Learning Representations (ICLR). arXiv:1511.06939

  • Kang, W.-C., & McAuley, J. (2018). Self-attentive sequential recommendation. In Proceedings of the 18th IEEE International Conference on Data Mining (ICDM), 197–206. https://doi.org/10.1109/ICDM.2018.00035 arXiv:1808.09781

  • Sun, F., Liu, J., Wu, J., Pei, C., Lin, X., Ou, W., & Jiang, P. (2019). BERT4Rec: Sequential recommendation with bidirectional encoder representations from transformer. In Proceedings of the 28th ACM International Conference on Information and Knowledge Management (CIKM), 1441–1450. https://doi.org/10.1145/3357384.3357895 arXiv:1904.06690

  • Wang, S., Cao, L., Wang, Y., Sheng, Q. Z., Orgun, M. A., & Lian, D. (2021). A survey on session-based recommender systems. ACM Computing Surveys, 54(7), 1–38. https://doi.org/10.1145/3465401

  • Zhao, W. X., Mu, S., Hou, Y., Lin, Z., Chen, Y., Pan, X., Li, K., Lu, Y., Wang, H., Tian, C., Min, Y., Feng, Z., Fan, X., Chen, X., Wang, P., Ji, W., Li, Y., Wang, X., & Wen, J.-R. (2021). RecBole: Towards a unified, comprehensive and efficient framework for recommendation algorithms. In Proceedings of the 30th ACM International Conference on Information & Knowledge Management (CIKM), 4653–4664. https://doi.org/10.1145/3459637.3482016

  • Petrov, A., & Macdonald, C. (2022). A systematic review and replicability study of BERT4Rec for sequential recommendation. In Proceedings of the 16th ACM Conference on Recommender Systems (RecSys), 436–447. https://doi.org/10.1145/3523227.3548487

  • Klenitskiy, A., & Vasilev, A. (2023). Turning dross into gold loss: is BERT4Rec really better than SASRec? In Proceedings of the 17th ACM Conference on Recommender Systems (RecSys), 1120–1125. https://doi.org/10.1145/3604915.3610644

Entries are listed by year of publication. Entries and online sources checked: Rendle (pages), Wang (pages), Zhao, Petrov and Klenitskiy against Crossref and arXiv, and the RecBole model count against its repository as it stood when the book was checked. For Wang et al. (2021), the records of Crossref, OpenAlex and Semantic Scholar give volume 54, issue 7 and pages 1–38; none of them gives an article number.