Lexical Search, Indexing, and Ranking

The stages can be measured and debugged independently.

A useful search system combines them according to the query and corpus.

The first column's claim — that exact term matching is strong for names and codes — has been measured, and the size of the advantage is the part worth carrying. A Princeton group built a benchmark for it out of Wikidata: 24 relations turned into templated questions, up to 1,000 sampled facts per relation. They called it EntityQuestions and published it in 2021.

On Natural Questions the dense retriever DPR reaches 80.1 top-20 accuracy against BM25's 64.5. That is the ordering everyone expects. On EntityQuestions the ordering inverts. BM25 scores 71.2, against 49.7 for DPR trained on NQ and 56.7 for DPR trained on four datasets. Sciavolino and colleagues state it without hedging: “DPR trained on NQ significantly underperforms BM25 on almost all sets of questions.” On the single relation “Where was [E] born?” BM25 takes 75.2 against DPR(NQ)'s 25.4, a gap of 49.8 points absolute.

A second lab reproduced the reversal on the same benchmark. Meta AI reports EntityQuestions Acc@20 of 56.6 for DPR against 70.8 for BM25, micro-averaged. Its abstract puts the shortfall in one clause: dense retrievers “still lag behind sparse methods such as BM25 in their ability to reliably match salient phrases and rare entities in the query”. Two independent runs, the same direction. On queries whose whole content is a rare name, literal token matching is not a fallback.

BM25-style ranking rewards query terms according to their document frequency, term occurrence, and a saturating treatment of repeated terms, while normalizing for document length. Those parameters are not a family of options a team picks from. In mainstream engines they are two fixed numbers, shipped as the default.

Apache Lucene's IndexSearcher carries one line under the comment `// the default Similarity`: `private static final Similarity defaultSimilarity = new BM25Similarity();`. The javadoc for that no-argument constructor reads “BM25 with these default values:” k1 = 1.2, b = 0.75, discountOverlaps = true. Elasticsearch is built on Lucene, and its index-settings reference lists “BM25 similarity (default)” with the same k1 = 1.2 and b = 0.75, and discount_overlaps true. Of the first constant, Elasticsearch's “Similarity settings” page says: “Controls non-linear term frequency normalization (saturation). The default value is 1.2.” Almost every lexical score a reader will ever be asked to explain was produced by those two untouched numbers.

A score has no universal probability meaning and is usually comparable only within a query and index configuration; product relevance can also require authority, freshness, permissions, and business rules.

One automatic expansion policy can damage the most valuable searches. The mix of intents is not a matter of designer intuition either. It has been counted on real logs, twice, by different people.

AltaVista's queries were counted two ways. An interstitial survey produced 3,190 valid returns between 26 June and 3 November 2001. Separately, 400 queries were inspected by hand, drawn from a random sample of 1,000 daily log queries. Navigational came out at 24.5% in the survey against 20% in the log. Informational at an estimated 39% against 48%. Transactional at more than 22% (estimated 36%) against 30%. Andrei Broder, who ran both counts at IBM Research, states in his 2002 introduction what the counting was for: “In fact as we show later, informational queries constitute less than 50% of web searches.” The class everyone designs for was under half.

Jansen and colleagues applied the same three categories to a different engine's log. Dogpile.com, 6 May 2005: 1,523,793 queries from 534,507 users. More than 80% came out informational, and about 10% each navigational and transactional. Their automatic classifier agreed with 400 manually coded queries 74% of the time. One taxonomy, two corpora, proportions that differ by tens of points. That is the argument for measuring your own log before choosing one analysis policy for all of it.

A disciplined lexical system is both a product and a benchmark for neural retrieval.

If no relevant document reaches the candidate set, a later reranker cannot rescue it; measure recall at several depths, then ranking quality such as reciprocal rank or discounted gain for queries with graded relevance.

The two numbers come apart far enough to see. Take the MS MARCO passage dev-small set of 6,980 queries and a plain BM25 first stage: Anserini, run as `-bm25 -bm25.k1 0.82 -bm25.b 0.68 -hits 1000`. A relevant passage lands somewhere inside the top 1,000 for 85.73% of queries. trec_eval prints `recall_1000 all 0.8573`, with map 0.1957. The same run's own top-10 ordering scores “MRR @10: 0.18741227770955546”.

One system, one index, one pass: recall_1000 is 0.8573 and MRR@10 is 0.1874. Baidu's RocketQA team lists the identical baseline from outside the group as “BM25 (anserini) (Yang et al., 2017) - 18.7 59.2 85.7” on MS MARCO Dev, and the leaderboard entry it matches, “BM25 (Lucene8, tuned)”, is dated 2019/06/26. Anserini's own documentation says which half it watches: “In many retrieval applications, average precision and recall@1000 are the two metrics we care about the most.” A reranker placed on that stage inherits 85.73% as its ceiling, and has most of the ordering left to win.

Aggregate metrics need slices for identifiers, languages, query length, freshness, permissions, and no-answer cases. Interaction logs are biased by current ranking and interface. So use controlled judgments and experiments too.

BEIR's authors had to pick a measure, and their reasoning is the part to copy. They rule out two families by name. “Decision support metrics such as Precision and Recall which are both rank unaware are not suitable”. “Binary rank-aware metrics such as MRR (Mean Reciprocal Rate) and MAP (Mean Average Precision) fail to evaluate tasks with graded relevance judgements”. They settle on normalised discounted cumulative gain. They “compute nDCG@10 for all datasets” with “the official TREC evaluation tool”. One metric, one stated reason, every dataset. That is what makes the table comparable at all.

Choose a real query with an unsatisfactory result. Trace normalization, tokens, expansions, filters, candidate postings, term statistics, field scores, and snippet selection.

Propose the smallest change that would recover the relevant document without damaging exact lookups or permissions. Add the case to a regression set.

Take the query from a log rather than from a colleague. MS MARCO, released in 2016, is built that way: “all questions are sampled from real anonymized user queries”. The passages “are extracted from real web documents using the most advanced version of the Bing search engine”, and the answers are human generated. The first release was “100,000 queries with their corresponding answers”. Queries of that kind are abbreviated, misspelled and ambiguous in ways a team writing its own test set never reproduces.

The same collection also shows how thin judged evidence is at that scale. The TREC 2019 Deep Learning Track overview states it in its abstract: “The passage retrieval task has a corpus of 8.8 million passages with 503 thousand training queries, for which we generate a reusable test set of 43 queries”. A second task covered 3.2 million documents with 367 thousand training queries; 15 groups submitted 75 runs. Forty-three judged queries is the reusable test set for a collection of 8.8 million passages.

Per query the judgments are thinner still. RocketQA's authors open with it: “Taking the MSMARCO dataset (Nguyen et al., 2016) as an example, each question has only 1.1 annotated positive passages on average, while there are 8.8M passages in the whole collection.” Before recording that your system missed the relevant document, check whether any relevant document was ever marked.