Semantic search
from scratch.

Ten sentences, ranked by brute force.

Embeddings, visually ends with a working search engine: embed ten hard-coded sentences, embed the query, compute cosine similarity against all ten, sort. That is genuinely the whole idea, and for ten sentences it is also the whole system.

Then you point it at a real corpus and every one of those simplifications turns into a decision you have to make. Your documents are not sentences — they are 40-page PDFs that have to be cut up somehow. There are not ten of them, there are a hundred thousand, and an O(n) scan per keystroke stops being free. And your users do not type tidy paraphrases; they type E020, and M8100, and “lever goes soft after a while”.

The five gaps this page closes

1. Chunking. A document is not a unit of retrieval. Cutting it up badly loses the answer before search even begins — and it is the single highest-leverage decision in the pipeline.
2. What a vector store actually holds. Vectors are the least interesting part of it.
3. When brute force stops working — and the honest answer to “do I need a vector database?”, which is usually no.
4. Hybrid search. Embeddings cannot retrieve a part number. Keyword search cannot retrieve a paraphrase. You need both, and a principled way to merge two ranked lists that have no comparable scores.
5. Reranking and RAG. Cheap-and-approximate first, expensive-and-precise second; then paste the winners into a prompt.

The least glamorous decision, and the one that decides everything.

An embedding model turns a passage into one fixed-length vector. Give it a whole page and you get the average of every idea on that page — a vector that is a little bit about everything and precisely about nothing. Give it a fragment and you get a sharp vector that may not contain the answer at all.

Below is a real support article and a real question. Move the sliders and watch what survives. The dashed green outline marks the span that actually answers the question; alternating bright and faint bands show the chunk boundaries; amber shows text that appears in two chunks because of overlap.

The three failure modes, in one sentence each

• Too large — the answer is in there, but it is 23 words out of 100. The chunk’s vector is dominated by rim tape and valve cores, so the chunk ranks lower for the sealant question than it deserves to, and the language model has to find the needle itself.
• Too small — the answer is 23 words long and a 16-word chunk physically cannot hold it. No retrieval strategy on earth recovers a fact that was destroyed at ingest time.
• The boundary — the worst one, because it is invisible. With 40-word chunks and no overlap the answer straddles a cut. Both halves score mediocrely, neither is complete, and nothing in your logs tells you this happened.

Fixed-size word windows are the crudest strategy and the right default. Better ones split on structure — Markdown headings, HTML sections, function definitions — so a chunk is a thing that means something on its own. Whatever you pick, store the source document id and the ordinal with each chunk, because you will want to show the user where an answer came from and to stitch neighbouring chunks back together at read time.

Vectors, metadata, and an index over the vectors.

A vector database is not exotic. It is a table of rows with a float array column and a specialised index on that column. If you can picture Postgres with an extra index type, you have the right picture — which is exactly why pgvector exists and is usually enough.

Three things live in a row, and only one of them is the embedding:

• The vector — 384 float32s here, 1536 for OpenAI’s text-embedding-3-small. 1.5 KB and 6 KB per chunk respectively.
• The payload and metadata — the chunk text itself (you need it back to show the user and to feed a language model), plus source id, ordinal, timestamps, tenant, permissions. Filtering on metadata is what turns a demo into a product.
• The index — a structure that answers “nearest neighbours of this vector” without touching every row. This is the only genuinely new machinery, and §4 is about when you actually need it.

final case class Chunk(
    id:       String,
    docId:    String,
    ordinal:  Int,
    text:     String,
    metadata: Map[String, String]
)

final case class Indexed(chunk: Chunk, vector: Array[Float])

trait VectorStore:
  def upsert(batch: Seq[Indexed]): Unit
  def search(query: Array[Float], k: Int, filter: Map[String, String] = Map.empty)
      : Seq[(Chunk, Float)]

/** Ingest is three steps and a batch size. The batch size is not decoration —
  * embedding one string at a time is the classic way to make ingest 40x slower. */
def ingest(
    docs:  Seq[Document],
    store: VectorStore,
    embed: Seq[String] => Seq[Array[Float]]
): Unit =
  docs
    .flatMap(chunk(size = 40, overlap = 8))
    .grouped(64)
    .foreach: batch =>
      val vectors = embed(batch.map(_.text))
      store.upsert(batch.lazyZip(vectors).map(Indexed.apply))

You almost certainly do not need a vector index.

Exact search is a dot product per document, and dot products are the thing computers are best at. The interesting question is not “is O(n) slow?” but “at what n does it start to matter for my latency budget?”

Cost model, not a benchmark: 384 float32 dimensions = 1 536 bytes per vector, streamed from RAM at ~10 GB/s on one core, which is where a normalised dot product is bottlenecked. Your numbers will differ by a factor of a few; the shape of the table will not.

What an ANN index buys, and what it costs

Approximate nearest neighbour search trades exactness for time. HNSW, the one you will meet in practice, builds a layered graph over the vectors: sparse long-range links at the top for coarse navigation, dense short-range links at the bottom for the final approach. A query greedily walks downhill from an entry point, so it touches a few hundred vectors instead of ten million — O(log n)-ish instead of O(n).

The cost is that it is approximate. Some true nearest neighbours are missed, and the knob that controls how many is a search-effort parameter (efSearch): raise it and recall climbs toward 100 % while latency climbs with it. The other costs are less discussed and bite harder — the graph must be held in memory alongside the vectors, building it is expensive, deletes are awkward, and metadata filtering interacts badly with graph traversal, because the neighbours you are allowed to return may not be reachable from the ones you are walking through.

Neither strategy is good enough. Together they are.

Keyword search cannot retrieve a paraphrase. Vector search cannot retrieve a part number. This is not a tuning problem — the two failure modes are structural, and each is exactly where the other one is strong. Run both, then merge the ranked lists.

Pick a query. All three columns are computed live in your browser from the baked all-MiniLM-L6-v2 vectors and a real BM25 index over the same 26 documents.

BM25, properly

The keyword column is BM25 with k1 = 1.2 and b = 0.75, not term counting. Two ideas do all the work. Saturation: the tenth occurrence of a word tells you far less than the second, so term frequency is fed through f / (f + k1) rather than used raw. Length normalisation: a match inside a 40-word document is stronger evidence than the same match inside a 400-word one, and b controls how hard that is penalised. Multiply by inverse document frequency and a rare token like E020 outweighs fifty occurrences of brake.

final class Bm25(docs: Vector[Vector[String]], k1: Double = 1.2, b: Double = 0.75):
  private val n     = docs.size
  private val avgdl = docs.map(_.size).sum.toDouble / n
  private val df    = docs.flatMap(_.distinct).groupMapReduce(identity)(_ => 1)(_ + _)

  private def idf(term: String): Double =
    val d = df.getOrElse(term, 0)
    math.log(1 + (n - d + 0.5) / (d + 0.5))

  def score(query: Seq[String], doc: Int): Double =
    val tokens = docs(doc)
    val tf     = tokens.groupMapReduce(identity)(_ => 1)(_ + _)
    query.foldLeft(0.0): (acc, term) =>
      tf.getOrElse(term, 0) match
        case 0 => acc
        case f =>
          val norm = 1 - b + b * tokens.size / avgdl
          acc + idf(term) * (f * (k1 + 1)) / (f + k1 * norm)

Reciprocal Rank Fusion, and why not just add the scores

A BM25 score of 3.97 and a cosine similarity of 0.43 are not on the same scale, are not bounded the same way, and do not move together. Normalising them into a common range sounds reasonable and behaves badly: min-max normalisation makes every score depend on the worst result in the list, so adding one irrelevant document silently rescores everything else.

RRF sidesteps the problem by throwing the scores away and keeping only the ranks. Each list contributes 1 / (k + rank) with k = 60, and the contributions are summed. The large constant flattens the curve, so the difference between rank 1 and rank 2 is small (0.01639 vs 0.01613) while the difference between “appears in both lists” and “appears in one” is large. That is the whole trick: RRF rewards agreement between retrievers rather than confidence within one of them.

/** Reciprocal Rank Fusion. Input: one ranked id list per retriever,
  * already truncated to top-k. Output: one merged ranking.
  * Note what is missing — the retrievers' own scores never appear. */
def rrf(lists: Seq[Seq[String]], k: Int = 60): Seq[(String, Double)] =
  lists
    .flatMap(_.zipWithIndex.map((id, i) => id -> 1.0 / (k + i + 1)))
    .groupMapReduce(_._1)(_._2)(_ + _)
    .toSeq
    .sortBy(-_._2)

Retrieve 50 cheaply, then reorder 50 expensively.

Everything so far used a bi-encoder: the query and the document are embedded separately and compared with a dot product. That separation is what makes it fast — document vectors are computed once at ingest — and it is also what limits it. The document vector was produced without ever seeing the query.

A cross-encoder gives up the separation. It feeds the pair [query] [SEP] [document] through a transformer together and outputs one relevance score, so every attention layer can compare the two texts word by word. It is far more accurate and completely unusable as a search index: nothing can be precomputed, so scoring a 100 000-document corpus means 100 000 forward passes per query.

Hence the two-stage pattern. The bi-encoder narrows a hundred thousand candidates to fifty; the cross-encoder reorders those fifty. Below, both columns are real: all-MiniLM-L6-v2 on the left, ms-marco-MiniLM-L-6-v2 logits on the right, over the same corpus.

Retrieval-augmented generation is a string template.

RAG has an intimidating name and an anticlimactic implementation: retrieve the top few chunks, paste them into a prompt above the user’s question, send it to a language model. That is the entire architecture. Every hard part of it is in sections 2 to 6.

def buildPrompt(question: String, hits: Seq[Chunk]): String =
  val context = hits.zipWithIndex
    .map((c, i) => s"[${i + 1}] ${c.metadata("title")}\n${c.text}")
    .mkString("\n\n")

  s"""|Answer the question using only the context below.
      |Cite the numbered source you used. If the context does not
      |contain the answer, say that you do not know.
      |
      |Context:
      |$context
      |
      |Question: $question
      |Answer:""".stripMargin

Turning up k feels like it should help and mostly does not. More chunks means more tokens, more latency, more cost, and a longer haystack for the model to lose the needle in — the “lost in the middle” effect is real and well documented. Three to five good chunks beats twenty mediocre ones every time, which is another way of saying that RAG quality is retrieval quality.

A decision guide, by corpus size.

Almost every retrieval system is over-engineered in the index and under-engineered in the chunker. Start at the top of this list and only move down when something measurably hurts.

What to remember

1. Chunking decides the ceiling. Nothing downstream recovers an answer that was cut in half at ingest time.
2. Exact search is fine to about 100 k chunks. Approximate indexes solve a problem you probably do not have yet.
3. Keyword and vector search fail in opposite directions. Running both and fusing the ranks costs almost nothing and removes a whole category of failure.
4. RRF works because it ignores scores. Never sum a BM25 score and a cosine similarity.
5. A reranker is a precision tool with a real latency bill and a real distribution assumption — verify it helps on your queries.
6. RAG is retrieval plus string concatenation. If the answers are bad, the retrieval is bad.