How Does a Search Engine Decide What to Show You?
Two pages both mention what you searched for. One goes first. The decision is made in about a tenth of a second, and it is mostly a question about who links to whom.
Nobody searches the web when you press enter
Junior level — plain language, no maths
The first thing to get straight is that a search engine does not go and look at the web when you type something. It could not possibly - the answer arrives in about two tenths of a second, which is not enough time to visit even one distant website, let alone a billion. Everything has been done in advance.
What happens in advance is crawling. A program starts at some page, reads it, writes down every word on it, then follows every link on that page to find more pages, and repeats - forever. The web is held together by links, so following links from a few starting points eventually reaches most of it.
What gets written down is an index, and it is built backwards from how you might expect. Instead of a list of pages and the words on them, it is a list of words and the pages containing them. Look up volcano and you immediately have every page that mentions it. That is the trick that makes the answer instant: the hard work happened last week.
Then comes the interesting part - ordering. Counting how often a page says volcano is a start, but anyone can type a word a thousand times, and in the early web people did exactly that. The idea that fixed it was to look at links: treat a link as a vote, and count votes from important pages as worth more than votes from nobody. Move the slider in the simulation and watch the shop page, which mentions volcanoes constantly and which nobody links to, slide down the list where it belongs.
Things worth knowing
- A crawler that finds a page with no links pointing at it from anywhere has no way to discover it. Pages like that are effectively invisible, which is why site owners submit sitemaps.
- An inverted index is the same structure as the index at the back of a book: not "page 47 contains these words" but "this word appears on pages 47, 112 and 340".
- Before link-based ranking, the top results for most queries were pages that had simply repeated the search term hundreds of times in white text on a white background.
Inverted indexes, TF-IDF and the random surfer
Student level — the core equations
The index is the foundation. For every term, the engine stores a posting list: the documents containing it, usually with positions so that phrase queries work. A query for two words becomes an intersection of two posting lists, which is fast because the lists are sorted and compressed. Everything else - ranking, snippets, filtering - operates on that structure.
Ranking by text alone uses TF-IDF, and both halves matter. Term frequency rewards a document for mentioning the word, usually with a damping function because the fiftieth mention adds less than the second. Inverse document frequency penalises words that appear everywhere: a match on the is worthless, a match on thermocline is highly informative, and the weight is \(\log(N/\text{df})\). The modern refinement is BM25, which adds length normalisation so that long documents cannot win simply by containing more words.
PageRank supplies the second half, and its definition is recursive in a way that sounds circular but is not: a page is important if important pages link to it. Model a surfer who clicks links at random and occasionally jumps to a random page instead - the damping factor \(d\), conventionally 0.85, is the probability of clicking rather than jumping. PageRank is the long-run fraction of time the surfer spends on each page, which is the principal eigenvector of the link matrix, computed by iterating until it stops moving.
The final score blends them, and the blend is where the judgement lives. Too much weight on text and keyword stuffing wins; too much on links and a popular page outranks a relevant one. Real systems add hundreds of further signals - freshness, click behaviour, page speed, and since 2019 neural language models that score the passage against the query's meaning rather than its words - but the two-part structure of relevance and authority is still visible underneath.
Key Formulas
| Term frequency | \(\text{tf}(t,d) = \dfrac{f_{t,d}}{\sum_{t'} f_{t',d}}\) | |
|---|---|---|
| Inverse doc frequency | \(\text{idf}(t) = \log \dfrac{N}{\text{df}(t)}\) | |
| TF-IDF score | \(\text{score} = \sum_{t \in q} \text{tf}(t,d)\cdot\text{idf}(t)\) | |
| PageRank | \(PR(p) = \dfrac{1-d}{N} + d\!\!\sum_{q \to p} \dfrac{PR(q)}{L(q)}\) | |
| Final blend | \(S = (1-w)\,\widehat{\text{tfidf}} + w\,\widehat{PR}\) | |
Things worth knowing
- IDF is why searching for a rare technical term works so much better than searching for a common one. The rare word carries nearly all the discriminating power of the query.
- The damping factor exists to stop the random surfer getting trapped. Without the occasional jump, all the rank would pool in pages that link to each other and out to nothing.
- BM25 was published in the 1990s and is still the default baseline in information retrieval research. Neural rankers are usually measured by how far they beat it.
Eigenvectors, index compression, and ranking after neural retrieval
Scholar level — full mathematical depth
01PageRank as a Markov chain
Write the web as a column-stochastic matrix \(M\) where \(M_{ij} = 1/L(j)\) if \(j\) links to \(i\). The damped operator \(G = dM + \frac{1-d}{N}\mathbf{1}\mathbf{1}^{\!\top}\) is stochastic, irreducible and aperiodic, so Perron-Frobenius guarantees a unique positive stationary vector - PageRank is its principal eigenvector. The power method converges at a rate governed by the second eigenvalue, which for the damped chain is bounded by \(d\); at \(d = 0.85\) that is roughly one decimal digit every dozen iterations, which is why fifty iterations sufficed on a web of billions of pages. Dangling nodes, which link to nothing, must be handled explicitly or probability mass leaks away.
02The index, and why compression is a ranking problem
Posting lists are stored as gaps between document identifiers rather than the identifiers themselves, then coded with variable-byte, Elias-Fano or SIMD-friendly schemes. Assigning document identifiers so that similar documents are numbered close together shrinks the gaps and therefore the index - which makes document ordering a compression decision with direct consequences for query latency. Query evaluation then uses dynamic pruning: WAND and block-max WAND skip whole blocks of a posting list whose best possible contribution cannot reach the current top-k threshold, which is what makes exhaustive scoring unnecessary.
03Learning to rank
Once there are hundreds of signals, hand-tuning stops. Learning-to-rank treats the ordering as a supervised problem over judged query-document pairs, and the useful objectives are listwise rather than pointwise, because the metric that matters - normalised discounted cumulative gain - depends on the whole ordering and is not differentiable. LambdaMART sidesteps that by defining gradients directly from the metric's change under a swap, and remained the production standard for years precisely because gradient-boosted trees handle heterogeneous, poorly scaled features better than networks do.
04Dense retrieval and the end of exact matching
Inverted indexes retrieve on lexical overlap, so a document that says car is invisible to a query for automobile. Dense retrieval encodes query and document into vectors with a transformer and retrieves by approximate nearest neighbour search over HNSW graphs, matching meaning rather than strings. It is usually paired with the lexical index in a hybrid, because dense retrieval is weak exactly where sparse retrieval is strong: rare entity names, identifiers, and terms the encoder never saw in training. The final stage is a cross-encoder that reads query and candidate jointly - far too expensive for retrieval, affordable for reranking the top hundred.
05An adversarial system
Uniquely among ranking problems, the documents are written by parties who know the ranking function and profit from beating it. This changes the engineering: signals must be costly to forge, which is why links from trusted sources outweigh links a page can create for itself, and why click signals are heavily denoised. It also explains why ranking details are not published. The arrival of generated text at scale sharpens the problem - the cheap signals of effort that ranking quietly relied on for two decades no longer separate the careful from the automatic.
Key Formulas
| Google matrix | \(G = dM + \dfrac{1-d}{N}\mathbf{1}\mathbf{1}^{\!\top}\) | |
|---|---|---|
| Stationary vector | \(\pi = G\pi,\qquad \|\pi\|_1 = 1\) | |
| Convergence | \(\|\pi_k - \pi\| \le C\,d^{\,k}\) | |
| BM25 | \(\sum_{t \in q}\text{idf}(t)\dfrac{f_{t,d}(k_1+1)}{f_{t,d}+k_1\left(1-b+b\frac{|d|}{\overline{|d|}}\right)}\) | |
| nDCG | \(\text{nDCG}_k = \dfrac{1}{Z_k}\sum_{i=1}^{k}\dfrac{2^{r_i}-1}{\log_2(i+1)}\) | |
Things worth knowing
- PageRank's convergence rate is bounded by the damping factor, so d = 0.85 gives about a factor of 10 error reduction every 13 iterations, independent of how large the web is.
- Block-max WAND lets an engine score a small fraction of the matching documents and still return a provably correct top-k. The saving comes from bounding what a block could contribute before looking inside it.
- Hybrid retrieval beats either half alone on almost every benchmark, because lexical and dense methods fail on disjoint queries - exact identifiers for one, paraphrases for the other.