Building a semantic search index

Compare lexical, dense, and fused rankings without pretending a top hit is an answer

systems
semantic search
retrieval
Learn how a small search index stores terms, vectors, metadata, and relevance checks for one fictional handbook.

A parent asked the handbook, “Where can my kid stay while I study at night?” The answer lived in passage H13, but the wording did not say child care.

This lesson uses a related search query, somewhere for my kid during night class. Under the lexical scoring used later in this lesson, which keeps stop words and does no stemming, H13 ranks second because it shares only the function words for and during; the class-related distractor H15 shares class. That rank does not come from the meaning of kid or night. If stop words were removed, H13 would receive no lexical score for this query.

Semantic search indexing prepares a searchable structure before the next query arrives. A lexical index stores terms and counts. A dense index stores one vector for each passage, using the same local embedding model for passages and queries. Both indexes can return a ranked list; neither can decide by itself that the top passage is relevant.

Note

The Riverton handbook in this lesson is an invented teaching fixture about fictional programs and policies.

TipWhat you will learn

This lesson shows how to:

  • build a lexical inverted index with explicit identifier tokenization;
  • score the index with a fixed BM25 formula;
  • mean-pool local MiniLM token vectors into one passage vector;
  • record index metadata so stale vectors are caught;
  • fuse lexical and dense ranks with reciprocal rank fusion; and
  • read recall and reciprocal rank without naming a winner.

Load the frozen handbook and judgments

The handbook, queries, and relevance judgments were written before this page ran any search code. The judgments cover every query against every passage. They are page-author reference labels, not ground truth.

suppressPackageStartupMessages({
  library(digest)
  library(dplyr)
  library(huggingfaceR)
  library(jsonlite)
  library(knitr)
  library(purrr)
  library(readr)
  library(reticulate)
  library(stringr)
  library(tibble)
  library(tidyr)
  library(tokenizers)
})

source("R/use-nlg.R")

hash_lines <- function(path) {
  digest(
    paste(read_lines(path), collapse = "\n"),
    algo = "sha256",
    serialize = FALSE
  )
}

handbook_path <- "data/riverton/riverton-handbook.csv"
judgments_path <- "data/riverton/riverton-search-judgments.csv"

handbook <- read_csv(
  handbook_path,
  na = character(),
  col_types = cols(
    passage_id = col_character(),
    topic = col_character(),
    text = col_character(),
    source = col_character(),
    author_note = col_character()
  )
)

judgments <- read_csv(
  judgments_path,
  na = character(),
  col_types = cols(
    query_id = col_character(),
    query = col_character(),
    probe_type = col_character(),
    passage_id = col_character(),
    relevant = col_integer(),
    judged_by = col_character()
  )
)

handbook_metadata <- read_csv(
  "data/riverton/riverton-handbook-metadata.csv",
  na = character(),
  col_types = cols(
    artifact = col_character(),
    description = col_character(),
    source = col_character(),
    license = col_character(),
    created_on = col_character(),
    rows = col_integer(),
    fingerprint = col_character()
  )
)

queries <- judgments |>
  distinct(query_id, query, probe_type) |>
  arrange(query_id)

miss_context <- handbook |>
  filter(passage_id %in% c("H13", "H15")) |>
  select(passage_id, topic, text)

judgment_summary <- judgments |>
  group_by(query_id, query, probe_type) |>
  summarise(
    relevant_passage = {
      relevant_ids <- passage_id[relevant == 1L]
      if (length(relevant_ids) == 0L) {
        "not applicable"
      } else {
        paste(relevant_ids, collapse = ", ")
      }
    },
    .groups = "drop"
  )

knitr::kable(
  miss_context,
  format = "html",
  escape = TRUE,
  col.names = c("Passage", "Topic", "Text"),
  caption = "The child-care passage and a nearby class-related distractor",
  row.names = FALSE
)
The child-care passage and a nearby class-related distractor
Passage Topic Text
H13 child care Free child care is available in Room 104 during evening classes for children aged 3 to 10.
H15 laptops Laptops are provided in class for Data Support Certificate students and may not be taken home.

The table above starts with H13 because it answers the parent’s question. H15 is a distractor about laptops and class. A search method that always returns a top row can still put a distractor first.

knitr::kable(
  judgment_summary,
  format = "html",
  escape = TRUE,
  col.names = c("Query", "Query text", "Probe type", "Relevant passage"),
  caption = "Author-written relevance judgments used for the search checks",
  row.names = FALSE
)
Author-written relevance judgments used for the search checks
Query Query text Probe type Relevant passage
S1 somewhere for my kid during night class vocabulary mismatch H13
S2 DSC-104 exact identifier with near misses H09
S3 money while I train vocabulary mismatch H08
S4 free ride to class vocabulary mismatch H05
S5 weekend forklift classes negated fact H11
S6 what should I bring to enroll paraphrase H07
S7 can I take the laptop home lexical overlap H15
S8 cafeteria lunch menu out of scope not applicable

Build terms for a lexical inverted index

An inverted index stores, for each term, the passages that contain it. The tokenizer matters. A common word tokenizer splits DSC-104 into dsc and 104; that makes it share 104 with Room 104. This lesson keeps course-like identifiers as one term with the pattern [a-z]+-\d+|[a-z]+|\d+. It lowercases text, keeps stop words, and does no stemming, so class and classes remain different terms.

tokenize_index_terms <- function(text) {
  str_extract_all(
    str_to_lower(text, locale = "en"),
    "[a-z]+-\\d+|[a-z]+|\\d+"
  )
}

identifier_example <- tibble(
  text = c("Course DSC-104 meets in Room 104."),
  common_word_tokens = list(tokenizers::tokenize_words(text)[[1]]),
  index_terms = list(tokenize_index_terms(text)[[1]])
) |>
  summarise(
    text = first(text),
    common_word_tokens = map_chr(common_word_tokens, paste, collapse = ", "),
    index_terms = map_chr(index_terms, paste, collapse = ", ")
  )

passage_terms <- handbook |>
  transmute(
    passage_id,
    term = tokenize_index_terms(text)
  ) |>
  unnest_longer(term, values_to = "term")

posting_preview <- passage_terms |>
  filter(term %in% c("dsc-104", "104", "dsc-105")) |>
  count(term, passage_id, name = "count") |>
  arrange(term, passage_id)

knitr::kable(
  identifier_example,
  format = "html",
  escape = TRUE,
  col.names = c("Example text", "Common word tokens", "Index terms"),
  caption = "Explicit tokenization keeps an identifier together",
  row.names = FALSE
)
Explicit tokenization keeps an identifier together
Example text Common word tokens Index terms
Course DSC-104 meets in Room 104. course, dsc, 104, meets, in, room, 104 course, dsc-104, meets, in, room, 104 
knitr::kable(
  posting_preview,
  col.names = c("Term", "Passage", "Count"),
  caption = "Identifier and room-number postings under the lesson tokenizer",
  row.names = FALSE
)
Identifier and room-number postings under the lesson tokenizer
Term Passage Count
104 H13 1
dsc-104 H09 1
dsc-105 H10 1

These index terms are what the scoring formula in the next section counts. If a system needs exact course-code search, dsc-104 must be a term, not an accident of two smaller terms.

Score query terms with BM25

BM25 gives more weight to rare query terms, discounts long passages, and lets repeated terms help less each time. This lesson uses Lucene’s positive idf form, with k1 = 1.2 and b = 0.75, fixed before any query runs.

k1 <- 1.2
b <- 0.75
document_count <- nrow(handbook)

passage_lengths <- passage_terms |>
  count(passage_id, name = "dl")
average_length <- mean(passage_lengths$dl)

document_frequency <- passage_terms |>
  distinct(passage_id, term) |>
  count(term, name = "df") |>
  mutate(
    idf = log(1 + (document_count - df + 0.5) / (df + 0.5))
  )

postings <- passage_terms |>
  count(passage_id, term, name = "tf") |>
  left_join(passage_lengths, by = join_by(passage_id)) |>
  left_join(document_frequency, by = join_by(term)) |>
  mutate(
    bm25_weight = idf *
      (tf * (k1 + 1)) /
      (tf + k1 * (1 - b + b * dl / average_length))
  )

rank_bm25 <- function(query_id, query) {
  query_terms <- tibble(term = tokenize_index_terms(query)[[1]]) |>
    count(term, name = "query_tf")

  postings |>
    inner_join(query_terms, by = join_by(term)) |>
    group_by(passage_id) |>
    summarise(score = sum(bm25_weight * query_tf), .groups = "drop") |>
    filter(score > 0) |>
    arrange(desc(score), passage_id) |>
    mutate(query_id = query_id, rank = row_number())
}

bm25_ranks <- pmap_dfr(
  list(queries$query_id, queries$query),
  rank_bm25
)

default_passage_terms <- handbook |>
  transmute(
    passage_id,
    term = tokenizers::tokenize_words(text)
  ) |>
  unnest_longer(term, values_to = "term")

default_lengths <- default_passage_terms |>
  count(passage_id, name = "dl")
default_average_length <- mean(default_lengths$dl)
default_document_frequency <- default_passage_terms |>
  distinct(passage_id, term) |>
  count(term, name = "df") |>
  mutate(
    idf = log(1 + (document_count - df + 0.5) / (df + 0.5))
  )
default_postings <- default_passage_terms |>
  count(passage_id, term, name = "tf") |>
  left_join(default_lengths, by = join_by(passage_id)) |>
  left_join(default_document_frequency, by = join_by(term)) |>
  mutate(
    bm25_weight = idf *
      (tf * (k1 + 1)) /
      (tf + k1 * (1 - b + b * dl / default_average_length))
  )
default_s2_terms <- tibble(
  term = tokenizers::tokenize_words("DSC-104")[[1]]
) |>
  count(term, name = "query_tf")
default_s2_preview <- default_postings |>
  inner_join(default_s2_terms, by = join_by(term)) |>
  group_by(passage_id) |>
  summarise(score = sum(bm25_weight * query_tf), .groups = "drop") |>
  filter(score > 0) |>
  left_join(handbook |> select(passage_id, topic), by = join_by(passage_id)) |>
  arrange(desc(score), passage_id) |>
  mutate(rank = row_number()) |>
  slice_head(n = 3) |>
  select(passage_id, topic, rank, score)

bm25_preview <- bm25_ranks |>
  filter(query_id %in% c("S1", "S2")) |>
  slice_min(rank, n = 3, by = query_id) |>
  left_join(
    handbook |> select(passage_id, topic),
    by = join_by(passage_id)
  ) |>
  select(query_id, rank, passage_id, topic, score)

top_margin <- function(ranks, query) {
  scores <- ranks |>
    filter(query_id == query) |>
    arrange(rank) |>
    pull(score)
  if (length(scores) < 2L) {
    return(Inf)
  }
  scores[[1]] - scores[[2]]
}

knitr::kable(
  bm25_preview |>
    mutate(score = round(score, 3)),
  col.names = c("Query", "Rank", "Passage", "Topic", "BM25 score"),
  caption = "BM25 top passages for the child-care and course-code probes",
  row.names = FALSE
)
BM25 top passages for the child-care and course-code probes
Query Rank Passage Topic BM25 score
S1 1 H15 laptops 3.648
S1 2 H13 child care 3.565
S1 3 H14 deadline 1.355
S2 1 H09 course codes 2.252 
knitr::kable(
  default_s2_preview |>
    mutate(score = round(score, 3)),
  col.names = c("Passage", "Topic", "Default-tokenizer rank", "BM25 score"),
  caption = "Default word splitting keeps the right course-code passage first but fills the rest of the top three with partial matches",
  row.names = FALSE
)
Default word splitting keeps the right course-code passage first but fills the rest of the top three with partial matches
Passage Topic Default-tokenizer rank BM25 score
H09 course codes 1 3.407
H13 child care 2 1.935
H10 refresher workshop 3 1.704

BM25 handles DSC-104 cleanly because the tokenizer kept the identifier. With default word splitting, the right passage still stays first in this render, but Room 104 and DSC-105 become partial matches that fill the rest of the top three. BM25 still struggles when the query says “money while I train” and the passage says “training stipend.”

Make dense passage vectors

The dense index uses the pinned sentence-transformers/all-MiniLM-L6-v2 model. The local Hugging Face feature-extraction pipeline returns one vector per word piece. For each text, this lesson averages those vectors, then scales the result to length 1.

The model’s own files say the sentence-transformer wrapper uses mean pooling and a normalization module. The model card says sentence-transformers truncates inputs longer than 256 word pieces by default and that training used sequences of at most 128 tokens. The page applies the model’s pooling steps one text at a time, so the pipeline output has no padding tokens (filler tokens that a batch adds so every text in it has the same length); the helper is valid only for that one-text call pattern.

The model manifest records an Apache-2.0 license. This lesson uses English (en) handbook text and does not claim the same behavior for other languages or domains.

embedder <- load_nlg_pipeline(
  "minilm_l6_v2",
  "feature-extraction"
)

model_dir <- file.path(
  "data-raw",
  ".cache",
  "nlg-models",
  embedder$metadata$local_directory
)
modules_config <- fromJSON(file.path(model_dir, "modules.json"))
pooling_config <- fromJSON(file.path(model_dir, "1_Pooling", "config.json"))
sentence_config <- fromJSON(file.path(model_dir, "sentence_bert_config.json"))
bert_config <- fromJSON(file.path(model_dir, "config.json"))
tokenizer_config <- fromJSON(file.path(model_dir, "tokenizer_config.json"))

extract_token_matrix <- function(feature_item) {
  item <- feature_item
  if (
    length(item) == 1L &&
      is.list(item[[1]]) &&
      !is.numeric(item[[1]])
  ) {
    item <- item[[1]]
  }
  do.call(rbind, item)
}

mean_pool_l2 <- function(feature_item) {
  token_matrix <- extract_token_matrix(feature_item)
  vector <- colMeans(token_matrix)
  vector / sqrt(sum(vector^2))
}

embed_one_text <- function(text) {
  output <- embedder$pipeline(text)
  mean_pool_l2(output[[1]])
}

token_counts <- tibble(
  passage_id = handbook$passage_id,
  model_tokens = map_int(
    handbook$text,
    \(text) nlg_token_count(embedder$tokenizer, text)
  )
)

stopifnot(max(token_counts$model_tokens) <= 256L)

first_output <- embedder$pipeline(handbook$text[[1]])
first_attention <- embedder$tokenizer(
  handbook$text[[1]],
  add_special_tokens = TRUE,
  return_attention_mask = TRUE
)$attention_mask

passage_embeddings <- map(handbook$text, embed_one_text)
embedding_matrix <- do.call(rbind, passage_embeddings)
rownames(embedding_matrix) <- handbook$passage_id

dense_metadata <- tibble(
  field = c(
    "model",
    "revision",
    "pooling",
    "normalization",
    "prefix",
    "runtime length checked here",
    "training sequence length on model card",
    "casing",
    "dimension"
  ),
  value = c(
    embedder$metadata$model_id,
    embedder$metadata$revision,
    "mean over returned token vectors",
    "L2 unit length",
    "none",
    as.character(sentence_config$max_seq_length),
    "at most 128 tokens",
    paste0("uncased: ", tokenizer_config$do_lower_case),
    as.character(ncol(embedding_matrix))
  )
)

knitr::kable(
  dense_metadata,
  col.names = c("Metadata field", "Recorded value"),
  caption = "Dense index metadata that must match at query time",
  row.names = FALSE
)
Dense index metadata that must match at query time
Metadata field Recorded value
model sentence-transformers/all-MiniLM-L6-v2
revision 1110a243fdf4706b3f48f1d95db1a4f5529b4d41
pooling mean over returned token vectors
normalization L2 unit length
prefix none
runtime length checked here 256
training sequence length on model card at most 128 tokens
casing uncased: TRUE
dimension 384 
knitr::kable(
  token_counts |>
    arrange(desc(model_tokens)) |>
    slice_head(n = 5),
  col.names = c("Passage", "Word-piece tokens"),
  caption = "Longest handbook passages remain inside the 256-word-piece runtime limit",
  row.names = FALSE
)
Longest handbook passages remain inside the 256-word-piece runtime limit
Passage Word-piece tokens
H02 36
H10 35
H09 32
H08 31
H06 30

All passages are short enough to embed without truncation. The lesson embeds one text at a time, so the pooling helper never averages padding tokens.

Record stale-index checks

An index is tied to its passages and model conventions. The embedding dimension alone cannot detect a swap: several small English embedding models can produce 384-dimensional vectors. The safer record includes model revision, pooling, prefixes, tokenizer behavior, library versions, lexical settings, and passage fingerprints.

passage_fingerprints <- handbook |>
  transmute(
    passage_id,
    passage_sha256 = map_chr(
      text,
      \(value) digest(value, algo = "sha256", serialize = FALSE)
    )
  )

handbook_fingerprint <- hash_lines(handbook_path)

index_record <- tibble(
  key = c(
    "model_id",
    "revision",
    "license",
    "pooling",
    "normalization",
    "query_prefix",
    "passage_prefix",
    "max_seq_length",
    "training_sequence_length",
    "tokenizer_casing",
    "lexical_token_pattern",
    "lexical_stop_words",
    "lexical_stemming",
    "bm25_idf",
    "bm25_k1",
    "bm25_b",
    "handbook_fingerprint",
    "passage_fingerprint_count",
    "similarity",
    "search_type",
    "huggingfaceR",
    "reticulate",
    "transformers",
    "torch",
    "python_tokenizers"
  ),
  value = c(
    embedder$metadata$model_id,
    embedder$metadata$revision,
    embedder$metadata$license,
    "mean pooling over real token vectors",
    "L2 normalization",
    "none",
    "none",
    as.character(sentence_config$max_seq_length),
    "at most 128 tokens",
    paste0("do_lower_case=", tokenizer_config$do_lower_case),
    "[a-z]+-\\d+|[a-z]+|\\d+",
    "kept",
    "none",
    "Lucene positive idf",
    as.character(k1),
    as.character(b),
    handbook_fingerprint,
    as.character(nrow(passage_fingerprints)),
    "cosine, computed as dot product of unit vectors",
    "exact scan over 15 passages",
    as.character(packageVersion("huggingfaceR")),
    as.character(packageVersion("reticulate")),
    as.character(reticulate::py_to_r(reticulate::import("transformers")$`__version__`)),
    as.character(reticulate::py_to_r(reticulate::import("torch")$`__version__`)),
    as.character(reticulate::py_to_r(reticulate::import("tokenizers")$`__version__`))
  )
)

metadata_matches <- function(record, model_id, revision, pooling) {
  expected <- c(model_id = model_id, revision = revision, pooling = pooling)
  actual <- record |>
    filter(key %in% names(expected)) |>
    select(key, value) |>
    deframe()
  identical(actual[names(expected)], expected)
}

metadata_check <- tibble(
  check = c("current model", "changed pooling example"),
  ok_to_query = c(
    metadata_matches(
      index_record,
      embedder$metadata$model_id,
      embedder$metadata$revision,
      "mean pooling over real token vectors"
    ),
    metadata_matches(
      index_record,
      embedder$metadata$model_id,
      embedder$metadata$revision,
      "CLS pooling"
    )
  )
)

edited_passage_check <- passage_fingerprints |>
  filter(passage_id == "H13") |>
  mutate(
    edited_sha256 = digest(
      paste0(
        handbook$text[handbook$passage_id == "H13"],
        " Extra sentence."
      ),
      algo = "sha256",
      serialize = FALSE
    ),
    fingerprint_matches = passage_sha256 == edited_sha256,
    action = if_else(
      fingerprint_matches,
      "reuse stored vector",
      "re-embed this passage"
    )
  )

knitr::kable(
  index_record,
  format = "html",
  escape = TRUE,
  col.names = c("Index key", "Value"),
  caption = "Index metadata needed before reusing stored vectors",
  row.names = FALSE
)
Index metadata needed before reusing stored vectors
Index key Value
model_id sentence-transformers/all-MiniLM-L6-v2
revision 1110a243fdf4706b3f48f1d95db1a4f5529b4d41
license Apache-2.0
pooling mean pooling over real token vectors
normalization L2 normalization
query_prefix none
passage_prefix none
max_seq_length 256
training_sequence_length at most 128 tokens
tokenizer_casing do_lower_case=TRUE
lexical_token_pattern [a-z]+-\d+|[a-z]+|\d+
lexical_stop_words kept
lexical_stemming none
bm25_idf Lucene positive idf
bm25_k1 1.2
bm25_b 0.75
handbook_fingerprint e8f6bd47e297f4ecc489169f5ca6e2154a1d3316136bfb5f7be26dcc39725a64
passage_fingerprint_count 15
similarity cosine, computed as dot product of unit vectors
search_type exact scan over 15 passages
huggingfaceR 2.1.0
reticulate 1.46.0
transformers 4.57.6
torch 2.9.1+cpu
python_tokenizers 0.22.2 
knitr::kable(
  metadata_check,
  col.names = c("Check", "Safe to query"),
  caption = "A changed pooling convention fails closed before search",
  row.names = FALSE
)
A changed pooling convention fails closed before search
Check Safe to query
current model TRUE
changed pooling example FALSE 
knitr::kable(
  edited_passage_check |>
    select(passage_id, fingerprint_matches, action),
  col.names = c("Passage", "Fingerprint matches", "Index action"),
  caption = "A changed passage fingerprint triggers re-embedding for that passage",
  row.names = FALSE
)
A changed passage fingerprint triggers re-embedding for that passage
Passage Fingerprint matches Index action
H13 FALSE re-embed this passage

If a passage fingerprint changes, only that passage needs a new vector. If the model revision or pooling changes, the stored vectors cannot be mixed with new query vectors.

Rank queries with dense vectors and fusion

Dense search embeds the query with the same model and ranks passages by cosine similarity. The hybrid below uses reciprocal rank fusion, or RRF. It adds 1 / (k + rank) from each ranked list, with k = 60. RRF uses ranks because BM25 scores and cosine scores are on different scales.

query_token_counts <- tibble(
  query_id = queries$query_id,
  model_tokens = map_int(
    queries$query,
    \(text) nlg_token_count(embedder$tokenizer, text)
  )
)
stopifnot(max(query_token_counts$model_tokens) <= 256L)

query_embeddings <- map(queries$query, embed_one_text)
query_matrix <- do.call(rbind, query_embeddings)
rownames(query_matrix) <- queries$query_id

dense_scores <- query_matrix %*% t(embedding_matrix)

dense_ranks <- as_tibble(as.data.frame(dense_scores), rownames = "query_id") |>
  pivot_longer(
    -query_id,
    names_to = "passage_id",
    values_to = "score"
  ) |>
  arrange(query_id, desc(score), passage_id) |>
  group_by(query_id) |>
  mutate(rank = row_number()) |>
  ungroup()

rrf_k <- 60
rrf_ranks <- bind_rows(
  bm25_ranks |> transmute(query_id, passage_id, method = "BM25", rank),
  dense_ranks |> transmute(query_id, passage_id, method = "dense", rank)
) |>
  mutate(rrf_component = 1 / (rrf_k + rank)) |>
  group_by(query_id, passage_id) |>
  summarise(score = sum(rrf_component), .groups = "drop") |>
  arrange(query_id, desc(score), passage_id) |>
  group_by(query_id) |>
  mutate(rank = row_number()) |>
  ungroup()

top_hits <- bind_rows(
  bm25_ranks |> mutate(method = "BM25 lexical", score_type = "BM25"),
  dense_ranks |> mutate(method = "dense", score_type = "cosine"),
  rrf_ranks |> mutate(method = "RRF hybrid", score_type = "RRF")
) |>
  filter(rank == 1L) |>
  left_join(
    queries |> select(query_id, query),
    by = join_by(query_id)
  ) |>
  left_join(
    handbook |> select(passage_id, topic),
    by = join_by(passage_id)
  ) |>
  select(method, query_id, query, passage_id, topic, score_type, score)

bm25_no_match_rows <- queries |>
  filter(!query_id %in% unique(bm25_ranks$query_id)) |>
  transmute(
    method = "BM25 lexical",
    query_id,
    query,
    passage_id = "no lexical match",
    topic = "no lexical match",
    score_type = "BM25",
    score = NA_real_
  )

top_hits_display <- bind_rows(top_hits, bm25_no_match_rows) |>
  arrange(query_id, method)

knitr::kable(
  top_hits_display |>
    mutate(score = if_else(is.na(score), "not applicable", sprintf("%.3f", score))),
  format = "html",
  escape = TRUE,
  col.names = c("Method", "Query", "Query text", "Top passage", "Top topic", "Score type", "Score"),
  caption = "Top passage per method; BM25 returns no lexical match for S3 and S8",
  row.names = FALSE
)
Top passage per method; BM25 returns no lexical match for S3 and S8
Method Query Query text Top passage Top topic Score type Score
BM25 lexical S1 somewhere for my kid during night class H15 laptops BM25 3.648
RRF hybrid S1 somewhere for my kid during night class H13 child care RRF 0.033
dense S1 somewhere for my kid during night class H13 child care cosine 0.362
BM25 lexical S2 DSC-104 H09 course codes BM25 2.252
RRF hybrid S2 DSC-104 H09 course codes RRF 0.033
dense S2 DSC-104 H09 course codes cosine 0.557
BM25 lexical S3 money while I train no lexical match no lexical match BM25 not applicable
RRF hybrid S3 money while I train H08 stipend RRF 0.016
dense S3 money while I train H08 stipend cosine 0.295
BM25 lexical S4 free ride to class H13 child care BM25 3.243
RRF hybrid S4 free ride to class H13 child care RRF 0.032
dense S4 free ride to class H11 forklift schedule cosine 0.460
BM25 lexical S5 weekend forklift classes H11 forklift schedule BM25 5.265
RRF hybrid S5 weekend forklift classes H11 forklift schedule RRF 0.033
dense S5 weekend forklift classes H11 forklift schedule cosine 0.789
BM25 lexical S6 what should I bring to enroll H07 enrollment documents BM25 3.659
RRF hybrid S6 what should I bring to enroll H07 enrollment documents RRF 0.033
dense S6 what should I bring to enroll H07 enrollment documents cosine 0.584
BM25 lexical S7 can I take the laptop home H15 laptops BM25 2.514
RRF hybrid S7 can I take the laptop home H15 laptops RRF 0.033
dense S7 can I take the laptop home H15 laptops cosine 0.582
BM25 lexical S8 cafeteria lunch menu no lexical match no lexical match BM25 not applicable
RRF hybrid S8 cafeteria lunch menu H02 contact RRF 0.016
dense S8 cafeteria lunch menu H02 contact cosine 0.244

S8 asks for a cafeteria lunch menu. The judgments say no passage is relevant. BM25 returns no lexical match after zero-score rows are excluded, while dense search and RRF still return a top passage. That is a property of similarity search, not evidence that the handbook contains a lunch-menu answer.

Evaluate the ranks query by query

The table below reports each method on each query. Recall at 1 asks whether the relevant passage appears first. Recall at 3 asks whether it appears in the first three. Because these probes have at most one relevant passage, recall at k is the same as success at k. Reciprocal rank is 1 / rank for the first relevant passage. S8 has no relevant passage, so these columns are not applicable.

evaluate_ranks <- function(ranks, method_name) {
  judgments |>
    left_join(
      ranks |> select(query_id, passage_id, rank, score),
      by = join_by(query_id, passage_id)
    ) |>
    group_by(query_id, query, probe_type) |>
    summarise(
      relevant_total = sum(relevant),
      relevant_rank = {
        relevant_ranks <- rank[relevant == 1L]
        relevant_ranks <- relevant_ranks[!is.na(relevant_ranks)]
        if (length(relevant_ranks) == 0L) {
          NA_integer_
        } else {
          min(relevant_ranks)
        }
      },
      top_passage = {
        scored_passages <- passage_id[!is.na(rank)]
        scored_ranks <- rank[!is.na(rank)]
        if (length(scored_ranks) == 0L) {
          NA_character_
        } else {
          scored_passages[which.min(scored_ranks)]
        }
      },
      top_score = {
        scored_scores <- score[!is.na(rank)]
        scored_ranks <- rank[!is.na(rank)]
        if (length(scored_ranks) == 0L) {
          NA_real_
        } else {
          scored_scores[which.min(scored_ranks)]
        }
      },
      recall_at_1 = {
        relevant_passages <- passage_id[relevant == 1L]
        top_passages <- passage_id[!is.na(rank) & rank <= 1L]
        if (length(relevant_passages) == 0L) {
          NA_real_
        } else {
          sum(relevant_passages %in% top_passages) /
            length(relevant_passages)
        }
      },
      recall_at_3 = {
        relevant_passages <- passage_id[relevant == 1L]
        top_passages <- passage_id[!is.na(rank) & rank <= 3L]
        if (length(relevant_passages) == 0L) {
          NA_real_
        } else {
          sum(relevant_passages %in% top_passages) /
            length(relevant_passages)
        }
      },
      reciprocal_rank = if_else(
        relevant_total == 0L,
        NA_real_,
        if_else(is.na(relevant_rank), 0, 1 / relevant_rank)
      ),
      .groups = "drop"
    ) |>
    mutate(method = method_name)
}

rank_evaluation <- bind_rows(
  evaluate_ranks(bm25_ranks, "BM25 lexical"),
  evaluate_ranks(dense_ranks, "dense"),
  evaluate_ranks(rrf_ranks, "RRF hybrid")
) |>
  select(
    method,
    query_id,
    probe_type,
    relevant_rank,
    top_passage,
    recall_at_1,
    recall_at_3,
    reciprocal_rank
  ) |>
  arrange(query_id, method)

paired_summary <- rank_evaluation |>
  filter(!is.na(reciprocal_rank)) |>
  select(query_id, method, reciprocal_rank) |>
  pivot_wider(names_from = method, values_from = reciprocal_rank) |>
  mutate(
    across(
      c(`BM25 lexical`, dense, `RRF hybrid`),
      \(value) coalesce(value, 0)
    )
  ) |>
  summarise(
    dense_above_bm25 = sum(dense > `BM25 lexical`),
    tied = sum(dense == `BM25 lexical`),
    bm25_above_dense = sum(dense < `BM25 lexical`),
    rrf_above_dense = sum(`RRF hybrid` > dense),
    rrf_tied_dense = sum(`RRF hybrid` == dense),
    dense_above_rrf = sum(`RRF hybrid` < dense),
    rrf_above_bm25 = sum(`RRF hybrid` > `BM25 lexical`),
    rrf_tied_bm25 = sum(`RRF hybrid` == `BM25 lexical`),
    bm25_above_rrf = sum(`RRF hybrid` < `BM25 lexical`)
  )

miss_table <- rank_evaluation |>
  filter(
    is.na(relevant_rank) |
      recall_at_1 == 0 |
      recall_at_3 == 0
  ) |>
  mutate(
    recall_at_1 = if_else(is.na(recall_at_1), NA_real_, recall_at_1),
    recall_at_3 = if_else(is.na(recall_at_3), NA_real_, recall_at_3)
  )

display_metric <- function(value) {
  case_when(
    is.na(value) ~ "not applicable",
    TRUE ~ sprintf("%.3f", value)
  )
}

display_rank <- function(value, relevant_total) {
  case_when(
    relevant_total == 0L ~ "not applicable",
    is.na(value) ~ "not retrieved",
    TRUE ~ as.character(value)
  )
}

display_top <- function(value) {
  if_else(is.na(value), "no lexical match", value)
}

rank_evaluation_display <- rank_evaluation |>
  left_join(
    judgments |>
      group_by(query_id) |>
      summarise(relevant_total = sum(relevant), .groups = "drop"),
    by = join_by(query_id)
  ) |>
  mutate(
    relevant_rank = display_rank(relevant_rank, relevant_total),
    top_passage = case_when(
      relevant_total == 0L & method == "BM25 lexical" ~ "no lexical match",
      relevant_total == 0L ~ top_passage,
      TRUE ~ display_top(top_passage)
    ),
    recall_at_1 = display_metric(recall_at_1),
    recall_at_3 = display_metric(recall_at_3),
    reciprocal_rank = display_metric(reciprocal_rank)
  ) |>
  select(-relevant_total)

miss_table_display <- miss_table |>
  left_join(
    judgments |>
      group_by(query_id) |>
      summarise(relevant_total = sum(relevant), .groups = "drop"),
    by = join_by(query_id)
  ) |>
  mutate(
    relevant_rank = display_rank(relevant_rank, relevant_total),
    top_passage = case_when(
      relevant_total == 0L & method == "BM25 lexical" ~ "no lexical match",
      relevant_total == 0L ~ top_passage,
      TRUE ~ display_top(top_passage)
    ),
    recall_at_1 = display_metric(recall_at_1),
    recall_at_3 = display_metric(recall_at_3),
    reciprocal_rank = display_metric(reciprocal_rank)
  ) |>
  select(-relevant_total)

knitr::kable(
  rank_evaluation_display,
  col.names = c(
    "Method",
    "Query",
    "Probe type",
    "Relevant rank",
    "Top passage",
    "Recall at 1",
    "Recall at 3",
    "Reciprocal rank"
  ),
  caption = "Per-query retrieval results from exhaustive author-written judgments",
  row.names = FALSE
)
Per-query retrieval results from exhaustive author-written judgments
Method Query Probe type Relevant rank Top passage Recall at 1 Recall at 3 Reciprocal rank
BM25 lexical S1 vocabulary mismatch 2 H15 0.000 1.000 0.500
RRF hybrid S1 vocabulary mismatch 1 H13 1.000 1.000 1.000
dense S1 vocabulary mismatch 1 H13 1.000 1.000 1.000
BM25 lexical S2 exact identifier with near misses 1 H09 1.000 1.000 1.000
RRF hybrid S2 exact identifier with near misses 1 H09 1.000 1.000 1.000
dense S2 exact identifier with near misses 1 H09 1.000 1.000 1.000
BM25 lexical S3 vocabulary mismatch not retrieved no lexical match 0.000 0.000 0.000
RRF hybrid S3 vocabulary mismatch 1 H08 1.000 1.000 1.000
dense S3 vocabulary mismatch 1 H08 1.000 1.000 1.000
BM25 lexical S4 vocabulary mismatch not retrieved H13 0.000 0.000 0.000
RRF hybrid S4 vocabulary mismatch 10 H13 0.000 0.000 0.100
dense S4 vocabulary mismatch 4 H11 0.000 0.000 0.250
BM25 lexical S5 negated fact 1 H11 1.000 1.000 1.000
RRF hybrid S5 negated fact 1 H11 1.000 1.000 1.000
dense S5 negated fact 1 H11 1.000 1.000 1.000
BM25 lexical S6 paraphrase 1 H07 1.000 1.000 1.000
RRF hybrid S6 paraphrase 1 H07 1.000 1.000 1.000
dense S6 paraphrase 1 H07 1.000 1.000 1.000
BM25 lexical S7 lexical overlap 1 H15 1.000 1.000 1.000
RRF hybrid S7 lexical overlap 1 H15 1.000 1.000 1.000
dense S7 lexical overlap 1 H15 1.000 1.000 1.000
BM25 lexical S8 out of scope not applicable no lexical match not applicable not applicable not applicable
RRF hybrid S8 out of scope not applicable H02 not applicable not applicable not applicable
dense S8 out of scope not applicable H02 not applicable not applicable not applicable 
knitr::kable(
  miss_table_display,
  col.names = c(
    "Method",
    "Query",
    "Probe type",
    "Relevant rank",
    "Top passage",
    "Recall at 1",
    "Recall at 3",
    "Reciprocal rank"
  ),
  caption = "Every miss and every no-relevant-passage query remains visible",
  row.names = FALSE
)
Every miss and every no-relevant-passage query remains visible
Method Query Probe type Relevant rank Top passage Recall at 1 Recall at 3 Reciprocal rank
BM25 lexical S1 vocabulary mismatch 2 H15 0.000 1.000 0.500
BM25 lexical S3 vocabulary mismatch not retrieved no lexical match 0.000 0.000 0.000
BM25 lexical S4 vocabulary mismatch not retrieved H13 0.000 0.000 0.000
RRF hybrid S4 vocabulary mismatch 10 H13 0.000 0.000 0.100
dense S4 vocabulary mismatch 4 H11 0.000 0.000 0.250
BM25 lexical S8 out of scope not applicable no lexical match not applicable not applicable not applicable
RRF hybrid S8 out of scope not applicable H02 not applicable not applicable not applicable
dense S8 out of scope not applicable H02 not applicable not applicable not applicable 
knitr::kable(
  paired_summary,
  col.names = c(
    "Dense above BM25",
    "Dense-BM25 ties",
    "BM25 above dense",
    "RRF above dense",
    "RRF-dense ties",
    "Dense above RRF",
    "RRF above BM25",
    "RRF-BM25 ties",
    "BM25 above RRF"
  ),
  caption = "Paired reciprocal-rank counts on the seven judged queries",
  row.names = FALSE
)
Paired reciprocal-rank counts on the seven judged queries
Dense above BM25 Dense-BM25 ties BM25 above dense RRF above dense RRF-dense ties Dense above RRF RRF above BM25 RRF-BM25 ties BM25 above RRF
3 4 0 0 6 1 3 4 0

Dense search fixes the child-care wording mismatch in S1 and the stipend wording mismatch in S3. It misses the transit query at the top three. BM25 does well on identifiers and exact wording, but it has no nonzero score for some paraphrases. RRF helps S1 and S3 and keeps several exact hits, yet it still misses the transit query at the top three. For S4, dense ranks the relevant H05 at 4, while RRF ranks it at 10 because H05 appears only in the dense list and receives no BM25 rank contribution. These are paired demonstrations on seven author-written probes, not a benchmark.

Larger evaluations do not give one method a permanent crown. BEIR reported BM25 as a strong zero-shot baseline across varied retrieval tasks, while dense passage retrieval reported large gains on open-domain question answering; entity-question work found dense retrievers can miss questions about rarely seen named entities. One DSC-104 probe in a 15-passage handbook cannot show that dense search handles identifiers.

What approximate search would change

This lesson scans all 15 passage vectors exactly. A larger system may use approximate nearest neighbour search to avoid comparing a query with every vector. In that context, ANN recall means agreement with exact nearest-neighbour search. It is not the same as relevance recall, which asks whether a human-judged relevant passage was retrieved. A fast ANN index can match exact search well and still retrieve an irrelevant passage.

An index of private text is private data. Embeddings can leak information about their source text, so storing vectors does not anonymize the handbook or any real collection.

What to remember

  • A lexical index stores terms, counts, document frequency, and passage length.
  • Identifier tokenization has to be explicit before BM25 can match codes.
  • Dense search stores model-specific vectors, not free-standing meanings.
  • Query-time metadata must match the stored index metadata.
  • Similarity search returns a ranked row even when no relevant passage exists.
  • Recall from relevance judgments and ANN recall answer different questions.

The dense list rescued the child-care query, but the no-menu query showed why every search result still needs a relevance check.

Sources