RecSys Part I · Statement and measurement · chapter 1 of 19
The problem: why recommenders are built this way
Almost the entire design of a recommender system follows from two facts: demand is distributed extremely unevenly, and there are tens of milliseconds to answer in. From the first follows why personalisation is needed at all and where cold start comes from. From the second — why the system has to be multi-stage. We work through both with numbers you can recompute yourself.
- The tail is arithmetic, not a metaphor. Under a power law with \(\alpha = 1.2\) the top percent of the catalogue takes 85% of the interactions, while 74% of the catalogue is expected to collect fewer than ten. Cold start begins here, not in the chapter about it.
- The objective follows from the business model. Subscription, advertising and a marketplace optimise different things, and borrowing someone else's metric is the most expensive mistake you can make while stating the problem.
- Every surface is a sorting function. A feed, «similar items», an email and autoplay differ only in what is substituted into the input.
- The funnel is multi-stage out of necessity, not architectural taste. Scoring the whole catalogue does not fit the latency budget, and latency costs money.
1. Demand is distributed unevenly
The catalogue is large; attention is not. On its own that is not yet an argument for personalisation: if everyone wanted the same thing, a single shelf of hits would do. The argument comes from the shape of the demand distribution.
The power law and what follows from it
An empirical observation that reproduces in music, video, books and goods: the frequency of the \(k\)-th most popular object decays as a power law.
$$ f(k) \;\propto\; k^{-\alpha} $$The parameter \(\alpha\) sets how steeply. Its meaning is simple: on logarithmic axes a power law is a straight line with slope \(-\alpha\). If you plotted the frequencies in log–log and saw a straight line, you are looking at Zipf.
A catalogue of 100 000 items, frequencies following \(k^{-\alpha}\). The share of all interactions that goes to the top of the catalogue:
| \(\alpha\) | top 0.1% | top 1% | top 4% | top 10% | Gini |
|---|---|---|---|---|---|
| 0.8 | 17.9% | 34.0% | 47.9% | 59.5% | 0.63 |
| 1.0 | 42.9% | 61.9% | 73.4% | 81.0% | 0.83 |
| 1.2 | 70.8% | 85.2% | 91.1% | 94.3% | 0.95 |
| 1.5 | 92.6% | 97.8% | 99.0% | 99.5% | 1.00 |
The numbers are reproduced by the script _tools/longtail.py in this repository.
Notice how fast everything changes. Between \(\alpha = 0.8\) and \(\alpha = 1.2\) the difference looks small, yet the share of the top percent grows from 34% to 85%. That is why «we have a long tail» is a statement with no content until the exponent is named.
Take \(\alpha = 1.2\), a catalogue of 100 000 and ten million interactions — an entirely realistic scale. Let us count how many interactions each item can expect:
- at \(\alpha = 1.0\), fewer than ten interactions are expected for 17.3% of the catalogue;
- at \(\alpha = 1.2\) — already for 74.2%.
Three quarters of the catalogue with almost no data about it. Not because the service is young, but because that is how demand is shaped. This is where sparsity and cold start grow from, and with them the need for content features and the whole line of argument about encoding objects.
The inverse问题 is useful too: for the top 4% of the catalogue to collect 90% of demand you need \(\alpha \approx 1.18\). So «4% give 90%» and «\(\alpha\) is a little above one» are the same statement said two different ways.
- Move \(\alpha\) and watch the share of the head. Going from 0.8 to 1.2 is the move from «there is a skew» to «the tail is practically absent from the output».
- Switch to logarithmic axes: the power law becomes a straight line, and the slope of that line is \(-\alpha\). That is exactly how it is estimated in practice.
- Look at the cumulative curve. It answers the question people really ask at interviews: «what share of the catalogue covers 80% of demand».
What to say in an interview: «Tailedness is a parameter, not a picture. I would name \(\alpha\) or the Gini coefficient over impressions, because they決定 how much of the catalogue has any chance of being learned at all».
How the tail of the output is measured
A tail in the data is one thing; a tail in the output is another, and the second matters more: a recommender can deepen the skew or smooth it out. Three quantities worth being able to name.
| Quantity | What it counts | What it catches |
|---|---|---|
| Coverage@k | the share of the catalogue shown at least once over a period | answers «how much of the stock do we show at all» directly |
| Gini over impressions | inequality of impressions across items, from 0 to 1 | the skew inside what is shown: coverage can be high while 99% of impressions go to a hundred items |
| Entropy of impressions | \(-\sum_i p_i \log p_i\) over impression shares | the same as Gini, but more sensitive to very rare items |
The classic trade: a model that always recommends the popular shows decent accuracy and catastrophic coverage. Formally it is right — popular things are indeed liked more often — but the product loses its point in the process.
Hence a practical rule: accuracy and coverage are read together. Two points of accuracy bought by collapsing coverage is a bad deal: you gave away the tail and bought nothing that shows up in money.
This is worked through where the metrics themselves are introduced: «Ranking metrics».
2. Who pays, and what follows from it
The objective of a recommender system does not follow from mathematics. It follows from who pays the money. Three models — three different problem statements, and borrowing the wrong metric here costs more than getting the architecture wrong.
| Model | Who pays | What is actually optimised | How it breaks |
|---|---|---|---|
| Subscription | the user, monthly | retention: the probability that a person renews. Not views, but the feeling that «there is always something here to watch» | short-term metrics are barely related to retention, and measuring it is expensive — the feedback cycle is a month |
| Advertising | the advertiser | attention: time, impressions, returns. The user here is not the customer but the inventory | a direct conflict of interest: what holds attention is not obliged to be useful |
| Marketplace | the seller, through commission | GMV corrected for returns and for the health of supply: a seller needs demand, or they leave | optimising immediate GMV produces returns and squeezes out small sellers |
In advertising and on a marketplace what is optimised is not one quantity but a compromise between sides: the user needs relevance, the seller needs demand, the platform needs commission. Formally this is a constrained problem, not the maximisation of a single number.
In practice people almost always assemble a weighted sum and tune the weights by experiment. That works, but the solution has a price: the weights cannot be derived from first principles, and every change of product policy becomes a separate A/B test. You will meet this same construction in the walkthrough of a live system — there the action weights sit right in a config, see x05.
The proxy metric and why it goes bad
None of the real goals — enjoyment, retention, trust — can be measured directly. So a proxy is optimised instead: a click, time, a conversion. And here begins a story that will keep coming back all the way through.
Optimise clicks and you get clickbait. Optimise time and you get the infinite scroll. Optimise immediate GMV and you get returns and unhappy sellers.
The mechanism is always the same: the proxy and the real goal have a shared part and a divergence. While the pressure is light they run side by side. Start pressing and the model finds exactly the divergence, because that is the cheapest place to pick the metric up.
Cory Doctorow named the limiting case of this process enshittification: a platform is first good for its users, then starts squeezing them in favour of its business customers, then squeezes the business customers in its own favour. Every step is locally rational and measures positively.
What is done about it. Fast proxies are kept together with slow health metrics: cohort retention, the share still active on a horizon of months, returns, complaints. The fast ones move the system, the slow ones guard it. More on this in «Proxy metrics and long-term goals».
A practical instrument worth being able to read. Take a cohort — everyone who arrived in month \(m_0\) — and look at the share still active after 1, 2, 3… months.
A healthy product gives a curve that flattens out at a non-zero level: some people stay for good. An unhealthy one gives a curve falling monotonically to zero, however many new people arrive at the top.
This is the case where the shape of the curve tells you more than its height: a plateau at 20% is better than 40% in the first month collapsing by the third.
3. A recommender system is a sorting function
A definition that is convenient to reason from. Whatever the interface looks like, inside it is always the same thing: there is a set of candidates, there is a context, and the candidates have to be put in order.
$$ \mathrm{score}: (u, c, i) \;\longmapsto\; \mathbb{R}, \qquad \text{output} \;=\; \operatorname{top-}k_{\,i \in C}\ \mathrm{score}(u, c, i) $$Here \(u\) is the user, \(c\) the context (time, device, what the person is doing right now), \(i\) a candidate, and \(C\) the set we choose from.
It explains why every surface of the product is one problem. Only what is substituted changes:
| Surface | What is substituted |
|---|---|
| the feed | \(u\) is the user, \(C\) is the whole catalogue |
| «similar items» | an item instead of \(u\), \(C\) is the catalogue without it |
| «next track» | the same, but \(k = 1\) and context matters more than history |
| an email or a push | the same score, but \(C\) is trimmed by contact frequency |
| personalised search | \(C\) is narrowed by the query, the score stays the same |
It also shows where the border with search runs: in search the query narrows \(C\), in recommendations there is nothing to narrow it with, and all the work is done by \(\mathrm{score}\).
4. Why the funnel has to be multi-stage
Now the second fact that shapes the design: there is very little time. The answer has to be assembled in tens or hundreds of milliseconds, because latency costs money.
The figure is quoted constantly, so its origin is worth knowing. Greg Linden, who worked at Amazon, described internal A/B experiments in which the page was slowed down artificially in steps of 100 ms: each step cost about a percent of sales. It was said publicly in his talk Make Data Useful (2006) and was later cited in work on online experimentation.
It matters what status that number has: it is one internal experiment, twenty years old, on one particular product. The order of magnitude has been confirmed elsewhere, but «1% per 100 ms» cannot be carried over to your own service as a constant. What does carry over is the fact itself: latency has a measurable price, and you have to measure it where you are.
Suppose the budget for an answer is 100 ms, the catalogue is a million items, and the ranking model computes one score in 100 microseconds. Then scoring everything costs
$$ 10^6 \times 100\ \text{µs} \;=\; 100\ \text{seconds} $$That is a thousand times the budget. No optimisation of constants closes a gap like that — a different scheme is needed.
The scheme is the same everywhere: narrow cheaply first, then order expensively. Candidate generation selects hundreds out of millions by a cheap measure — usually a dot product in an index. Ranking runs a heavy model, but already on hundreds.
Then the budget adds up: hundreds of evaluations of a heavy model are a few milliseconds, and a nearest-neighbour lookup in an index is a few more.
Ranking cannot show what candidate generation did not select. So end-to-end quality is bounded above by the recall of the first stage, and no model further down will lift it above that ceiling.
Hence a rule that interviewers often probe: candidate generation is measured by recall, ranking by order. Measuring a candidate generator by precision makes no sense: its job is not to guess but not to lose.
- Set the recall of ranking to 1.00 — a perfect second stage. End-to-end recall still runs into the ceiling of the first: the ceiling is set by candidate generation.
- Add a second source of candidates. End-to-end recall grows, but does not add up: the sources overlap, and the overlap brings nothing new.
- Increase \(k\) of the first stage. Recall grows, but every next hundred candidates costs more in time and brings less in value — the usual diminishing returns.
What to say in an interview: «End-to-end recall is a product over the stages, so the one to improve is the weakest. And the metric for candidate generation is recall, not precision: it selects, it does not decide».
Interview questions
What is the long tail and how do you measure how long it is?
Demand follows a power law: the frequency of the \(k\)-th most popular object is proportional to \(k^{-\alpha}\). On logarithmic axes that is a straight line with slope \(-\alpha\), and that is how it is estimated.
One picture is not enough, you have to name the quantity. About the data — \(\alpha\), or Gini over frequencies. About the output — coverage@k (the share of the catalogue shown at least once), Gini over impressions and the entropy of impressions. The difference matters: a system can deepen the skew or smooth it.
Orders of magnitude: at \(\alpha = 1.0\) the top percent of the catalogue collects about 62% of interactions, at \(\alpha = 1.2\) — already 85%.
Why does the long tail make cold start inevitable?
It is a direct consequence of the arithmetic. At \(\alpha = 1.2\), a catalogue of 100 thousand and ten million interactions, 74% of items are expected to have fewer than ten interactions. At \(\alpha = 1.0\) — 17%.
That is, most of the catalogue is always in a state where there is practically no collaborative signal, and that is not the problem of a young service but a property of the demand distribution. Hence the need for content features: they let you say something about an item before it has accumulated a history.
How does the business model affect the objective of a recommender?
Subscription pays for retention: what matters is the probability of renewal, not views. The metric is slow, the feedback cycle is a month.
Advertising pays for attention: impressions, time, returns. A conflict is built in here — what holds attention is not obliged to be useful.
A marketplace pays a commission on turnover, but with two corrections: returns and the health of supply. A seller needs demand, or they leave, and the platform is left without an assortment.
The practical conclusion: borrowing someone else's metric is the most expensive mistake in stating the problem. And in a two-sided market this is a constrained problem, which in practice is reduced to a weighted sum with weights from experiments.
Why does optimising a proxy metric spoil the product over time?
A proxy and the real goal have a shared part and a divergence. Under light pressure they run side by side; when you start pressing, the model finds exactly the divergence — that is the cheapest place to pick the metric up.
Hence clickbait when optimising clicks, the infinite scroll when optimising time, returns when optimising immediate GMV.
The cure is not to give up proxies but to pair them: fast proxies move the system, slow health metrics (cohort retention, the share active on a horizon of months, complaints, returns) guard it. The retention curve is read by its shape: a healthy product flattens out at a non-zero level.
Why is a recommender multi-stage rather than one big model?
The budget does not add up. With a catalogue of a million and a score costing 100 µs, scoring everything is 100 seconds against a budget of 100 ms — a thousand times over. A gap like that is not closed by constants.
So: narrow cheaply (candidate generation, hundreds out of millions, usually a dot product in an index), then order expensively (ranking on hundreds). Sometimes pre-ranking is added in between and re-ranking on top of the head.
Latency here is not an abstraction: slowing down costs measurable money — the well-known observation about 100 ms and a percent of sales goes back to internal experiments at Amazon that Greg Linden described in 2006.
Which metric measures candidate generation, and why not precision?
Recall. The job of the first stage is not to guess the answer but not to lose it: what it did not select, ranking will never show.
It follows that end-to-end quality is bounded above by the recall of the first stage. Even perfect ranking will not lift the system above that ceiling, so the stage to improve is the weakest one, not the most visible one.
Precision at this stage is not merely useless but harmful as a target: it pushes you to select fewer and safer items, that is, straight into the popular ones, collapsing coverage.
One-screen cheat sheet
Power law
\(f(k) \propto k^{-\alpha}\), a straight line with slope \(-\alpha\) in log–log. At \(\alpha=1.2\) the top 1% takes 85%.
Cold start
At \(\alpha=1.2\), 74% of the catalogue has fewer than ten interactions. A property of demand, not of the service's age.
Tail of the output
Coverage@k, Gini over impressions, entropy. Read together with accuracy, or you win accuracy and lose the catalogue.
Three models
Subscription — retention. Advertising — attention. Marketplace — GMV minus returns plus the health of supply.
Sorting function
\(\mathrm{score}(u,c,i)\) and \(\operatorname{top-}k\). All surfaces differ in what is substituted into the input.
The funnel
10⁶ → 10² cheaply → 10¹ expensively. The ceiling is set by the first stage; its metric is recall.
Primary sources
- C. Anderson. The Long Tail, Wired, 2004 — the piece that brought the term into common use.
- P. Covington, J. Adams, E. Sargin. Deep Neural Networks for YouTube Recommendations, RecSys 2016 — the canonical account of the two-stage funnel: candidate generation and ranking, and why exactly that way.
- G. Linden. Make Data Useful, Stanford, 2006 — the source of the observation about 100 ms and a percent of sales; it is also honestly visible there that this is one internal experiment.
- R. Kohavi, R. Longbotham et al. Online Controlled Experiments at Large Scale — how effects like that are measured and where people go wrong in measuring them.
- C. Doctorow. Enshittification, 2023 — the formulation of how a platform degrades step by step while staying locally rational.
- The numbers in this chapter:
_tools/longtail.pyin this repository.