How search engines rank: PageRank to BM25

I add “reddit” to about a third of my searches now. Not programming searches, those still mostly land on Stack Overflow or the docs, but anything where I want a human opinion: which dishwasher, whether a hiking trail is any good, what people think of a book. Without it I get ten pages that were all clearly written to rank, with a table of contents, an affiliate link in every paragraph and the actual answer somewhere under the fold.

So Dmitri Brereton’s Google Search Is Dying, which went up on Tuesday and has been all over Hacker News since, landed with me. His argument is that results are worse because the web Google indexes has filled up with content made to game it, and because Google has given more and more of the page to ads. He quotes Brin and Page’s original 1998 paper on the ads point, which I’d forgotten has a whole appendix on it: they wrote that “advertising funded search engines will be inherently biased towards the advertisers and away from the needs of the consumers.” It’s a good line to have on the record.

I don’t know enough about what goes on inside Google today to say whether he’s right about the causes. Nobody outside does. But I’ve built search into products a couple of times, and the classic ranking machinery is simple enough to explain in one post, and once you see it you can see why it’s so gameable. So here’s that.

Step one: the inverted index

You can’t scan every document for every query. What every search engine does instead, from Lucene to Google, is build an inverted index: for every word, the list of documents it appears in, usually with how many times and where.

A query for sqlite wal looks up two lists, intersects them (or unions them, for an OR query), and now you have a few candidates instead of a few billion documents. That’s the retrieval half of the problem. The ranking half is deciding which candidate goes first, and this is where it gets interesting.

Step two: how well does the text match?

The oldest useful answer is TF-IDF. Term frequency: a document that says “sqlite” six times is probably more about SQLite than one that says it once. Inverse document frequency: rare words carry more information than common ones, so a match on “wal” should count for more than a match on “the”. The usual IDF is the log of (number of documents / number of documents containing the word). Multiply the two, add up over the query terms, sort.

Let’s make up some numbers. Say we have 10,000 documents. “sqlite” appears in 120 of them, “wal” in 30. That gives

• IDF(sqlite) = ln(10,000 / 120) ≈ 4.42
• IDF(wal) = ln(10,000 / 30) ≈ 5.81

Now two candidate documents for sqlite wal:

• A is a short, focused 300-word post. It says “sqlite” 6 times and “wal” once.
• B is a 1,500-word mega-guide. It says “sqlite” 3 times and “wal” 4 times.

Plain TF-IDF scores A at 6 × 4.42 + 1 × 5.81 ≈ 32.3, and B at 3 × 4.42 + 4 × 5.81 ≈ 36.5. B wins. Which might be fine, but notice why it wins. It’s five times as long, so it had five times as many chances to say the words. And the count is linear: say “wal” forty times and you’d score ten times as much as saying it four times. You can see where the keyword-stuffed pages of the early 2000s came from.

BM25

BM25 is the fix for both of those, and it’s what Lucene, and so Elasticsearch and Solr, have used by default for years now. It came out of Stephen Robertson and colleagues’ work on probabilistic retrieval in the ’90s (the “BM” stands for “best matching”, and 25 is, as far as I know, just the number of the variant that worked). For each query term, the score is

IDF(t) × f × (k1 + 1) / (f + k1 × (1 − b + b × len / avg_len))

where f is how many times the term appears in the document, len is the document’s length and avg_len is the average. The usual defaults are k1 = 1.2 and b = 0.75. (Lucene’s IDF is a slightly smoothed version of the one above, ln(1 + (N − n + 0.5)/(n + 0.5)), which comes to 4.42 and 5.79 for our two words. Close enough that I’ll use those.)

Two things are going on in that fraction. First, it saturates. With an average-length document, a term that appears once contributes 1.0 × IDF, twice is 1.38, five times 1.77, ten times 1.96, and a hundred times 2.17. It can never go above k1 + 1 = 2.2, however many times you repeat it. Second, the b × len / avg_len part means long documents need more occurrences to get the same credit, because they had more room.

Redo A and B with an average length of 600 words. For A (300 words) the length factor is 1.2 × (0.25 + 0.75 × 0.5) = 0.75, so being short actually helps it a little. For B (1,500 words) it’s 1.2 × (0.25 + 0.75 × 2.5) = 2.55.

• A: sqlite 6 × 2.2 / (6 + 0.75) = 1.96, times 4.42 ≈ 8.64. wal 1 × 2.2 / (1 + 0.75) = 1.26, times 5.79 ≈ 7.28. Total 15.9.
• B: sqlite 3 × 2.2 / (3 + 2.55) = 1.19, times 4.42 ≈ 5.26. wal 4 × 2.2 / (4 + 2.55) = 1.34, times 5.79 ≈ 7.78. Total 13.0.

Now the short, focused page wins, which matches my intuition about which of the two I’d want to read. Nothing magic happened, two knobs just turned “more words” from an advantage into roughly neutral.

When we rebuilt the search in our product on Elasticsearch a few years ago, BM25 out of the box was most of the way to good. The rest was field boosts (a match in a title counts more than a match in a comment) and a recency nudge. Inside a single company’s data, where nobody is writing documents to game your ranking, that gets you a long way. Which is exactly the assumption that doesn’t hold on the open web.

PageRank: what does everyone else think?

Text matching tells you a page is about your query. It doesn’t tell you whether it’s any good, and in 1998 the search engines that only did text matching were drowning in pages that repeated keywords in white text on a white background. Brin and Page’s idea was to use the structure of the web itself. A link from page X to page Y is a vote by X’s author that Y is worth reading, and a vote from a page that lots of people link to should count for more.

That’s circular, which is the fun part. The usual way to explain it is the random surfer. Someone starts on a random page and clicks a random link on it, over and over. Every so often, with probability 1 − d, they get bored and jump to a completely random page instead. A page’s PageRank is the fraction of time the surfer spends on it in the long run. With N pages, a damping factor d (0.85 in the paper) and L(X) the number of outgoing links on page X:

PR(Y) = (1 − d) / N  +  d × Σ PR(X) / L(X)    for every X that links to Y

(The original paper writes it without the division by N, so the ranks add up to N instead of 1. Same ordering either way.)

You compute it by starting everyone at 1/N and applying the formula over and over until the numbers stop moving. Here’s a web with four pages: A links to B and C, B links to C, C links to A, and D links to C.

After the first round C has jumped to 0.569, since three pages point at it, and A is still at 0.25. After the second, A shoots up to 0.521, because C now has a lot of rank and gives all of it to A. It sloshes back and forth like that for a while and settles at A 0.373, B 0.196, C 0.394, D 0.038. D gets exactly the 0.0375 floor that the random jump guarantees, since nothing links to it. And A, with one incoming link, ends up almost level with C, which has three, because its one link comes from the most important page on this little web and isn’t shared with anything else.

I last saw this in a linear algebra course during my math degree, and didn’t expect to meet it again at work. The converged vector is the principal eigenvector of the (damped) link matrix, and the repeat-until-it-stops loop is the power method. The damping factor is what guarantees it converges to one answer. Without it, a page with no outgoing links, or a little loop of pages pointing only at each other, can trap the surfer and soak up all the rank.

Putting them together

A real engine combines something like BM25 (on the body, the title, the URL and the anchor text of links pointing at the page, which was another of Brin and Page’s good ideas) with something like PageRank, plus hundreds of other signals, freshness, location, what people clicked last time they searched this. Google has said for years that PageRank is just one signal among many, and these days most of the combining is done by learned models instead of a formula someone wrote by hand. I can’t tell you how any of that works inside Google, and I’m suspicious of anyone outside who says they can.

But every piece I’ve described assumes good faith. BM25 assumes the words on the page were written to describe the page. PageRank assumes a link is an opinion. Both were true enough in 1998, and the reason they stopped being true is that ranking became worth a lot of money. Link farms showed up almost as soon as PageRank did. The modern version is subtler, a few thousand well-written, perfectly relevant pages per niche, each linking to the others, each with the right headings, each recommending whatever pays the best commission. BM25 can’t tell that a perfectly relevant page is insincere, and if those pages get linked to, PageRank can’t either.

That’s why “reddit” works, I think. A forum thread isn’t written to rank. It’s messy, it rambles, somebody’s wrong in the third reply and gets told so. It’s the closest thing left to the web these algorithms were designed for. Which also means it’ll get gamed next, if it isn’t already, and I don’t expect the trick to last.

What I’d like, and what I’m half tempted to build for myself, is a search I can point at a list of sites I trust: the blogs in my feed reader, a few forums, the docs I use. Over a few thousand sites, plain BM25 with no link analysis at all would probably beat what I get from the big engines for half my queries, because the hard part, deciding whose words to believe, would already be done.