# Search Concepts

This page explains the algorithms and theory behind `@coda/search`. You do not need to read this to use the library, but it helps when [tuning parameters](tuning.md) or [extending the pipeline](extending.md).

---

## BM25 Keyword Scoring

BM25 (Best Matching 25, also called Okapi BM25) is the standard baseline for text retrieval. It ranks documents by how well their terms match the query, accounting for three factors:

1. **Term frequency (TF)** -- terms that appear more often in a document increase its score, but with diminishing returns (saturation controlled by [`k1`](tuning.md#parameters)).
2. **Inverse document frequency (IDF)** -- rare terms contribute more to relevance than common ones.
3. **Document length normalization** -- longer documents are penalized so they do not dominate simply by containing more words. The [`b`](tuning.md#parameters) parameter controls how aggressively length is normalized (0 = no normalization, 1 = full normalization).

Default parameters: `k1 = 1.2`, `b = 0.75` (standard TREC values).

### Tokenization pipeline

Applied identically to queries and document text at index time:

1. **camelCase splitting** -- `getUserById` becomes `get`, `user`, `by`, `id`
2. **Lowercase** -- normalizes all tokens
3. **Stop word filter** -- removes common English stop words (`a`, `the`, `is`, ...)
4. **Porter stemming** -- `contracts` becomes `contract`, `running` becomes `run`

This ensures that a query for "contract" matches documents containing "contracts" or "contracting".

### Dual-level keyword weighting

Keyword scoring is split into two independent signals that are later combined via [RRF score fusion](#rrf-score-fusion):

- **`keyword`** -- raw query tokens (specific/low-level, e.g., `artist_id`)
- **`keyword_expanded`** -- glossary-expanded tokens only (conceptual/high-level, e.g., `royalties` when the query mentions `payments`)

[`KeywordStage`](pipeline.md#built-in-stages) `.rank()` is called twice with different token sets, and both signals enter [fusion](pipeline.md#phase-4-score-fusion) independently. This gives specific entity matches stronger ranking power while still surfacing conceptually related items through [glossary expansion](#glossary-matching).

### Prefix fallback via trie

When exact keyword results are sparse, a `StringTrie` index catches partial matches via prefix lookup. This handles cases where the user types a truncated term (e.g., `"artist"` matching `"artist_id"`, `"artist_name"`).

---

## HNSW Vector Search

HNSW (Hierarchical Navigable Small World) is an approximate nearest-neighbor algorithm that builds a multi-layer proximity graph. At each layer, a node is connected to its [`m`](tuning.md#efsearch-hnsw-recall-vs-latency) nearest neighbors. Queries start at the top layer and greedily descend, maintaining a candidate set of size [`efSearch`](tuning.md#efsearch-hnsw-recall-vs-latency) at each layer.

### Key parameters

| Parameter        | Range  | Higher value                             | Lower value                             |
| ---------------- | ------ | ---------------------------------------- | --------------------------------------- |
| `m`              | 4–64   | Better recall, more memory, slower build | Worse recall, less memory, faster build |
| `efConstruction` | 50–500 | Better recall, slower insert             | Worse recall, faster insert             |
| `efSearch`       | 10–500 | Better recall, slower query              | Worse recall, faster query              |

- **`m`** — bi-directional links per node. Controls graph connectivity. Values below 8 produce sparse graphs with poor recall; values above 32 waste memory for marginal recall gains.
- **`efConstruction`** — search width during insertion. Higher values find better neighbors but slow down index builds. Should be at least `2 * m`.
- **`efSearch`** — candidate list size during query traversal. Higher values improve recall at the cost of query latency.
- **Cosine similarity** — vectors are normalized at embed time; dot product of normalized vectors approximates cosine similarity.

### Recommended defaults by corpus size

| Corpus size | `m` | `efConstruction` | `efSearch` | Notes                               |
| ----------- | --- | ---------------- | ---------- | ----------------------------------- |
| < 1,000     | 8   | 100              | 30         | Small corpus; brute-force also fine |
| 1K–10K      | 16  | 200              | 50         | Default. Good balance.              |
| 10K–100K    | 16  | 200              | 100        | Increase efSearch for recall        |
| 100K–1M     | 24  | 300              | 150        | Higher m for denser graph           |
| > 1M        | 32  | 400              | 200        | Consider sharding at this scale     |

### Uint8 quantization

`QuantizedHnswIndex` stores uint8-quantized vectors in the HNSW graph while retaining exact float32 vectors internally for snapshot fidelity. This reduces memory by 4x at the cost of minor precision loss.

**Process:**

1. Compute per-vector min and scale (range = max - min)
2. Map float values linearly to the uint8 range `[0, 255]`
3. Store the quantized bytes along with min/scale for reconstruction during dot product

**Accuracy:** Mean error is less than 5% at 1024 dimensions, well within acceptable bounds for approximate nearest-neighbor search. Exact float32 vectors are retained so quantization error does not compound across index restarts.

### Query embedding cache and in-flight dedup

[`VectorStage`](pipeline.md#built-in-stages) owns an LRU query cache (configurable capacity, default 64) and deduplicates concurrent embedding requests for the same query string. This avoids redundant model calls when multiple requests arrive for the same or recently-seen query.

---

## Glossary Matching

Domain glossary entries inject curated knowledge into the search pipeline. When the query contains a glossary term, the corresponding target identifiers are boosted in the result set.

### Matching rules

- **Word-boundary** -- terms match on word boundaries, not arbitrary substrings
- **Case-insensitive** -- `"Royalties"` matches `"royalties"`
- **Fuzzy** -- up to edit distance 2 (Levenshtein) for typo tolerance

### GlossaryEntry format

```ts
interface GlossaryEntry {
  terms: string[]; // Trigger terms (word-boundary, fuzzy matched)
  targets: string[]; // Primary identifiers -- boost weight 1.0
  related?: string[]; // Secondary identifiers -- boost weight 0.5
  context?: string; // Appended to document text at index time
  domain?: string; // Grouping label (informational)
  priority?: number; // Boost multiplier (default 1, higher = stronger)
}
```

Priority scales the base boost as a multiplier: an entry with `priority: 2` produces twice the boost of a `priority: 1` entry. The default (when omitted) is `1`. Setting `priority: 0` means the entry triggers query expansion but contributes no ranking boost — useful for synonym injection without direct result boosting. Negative values are invalid and treated as `1`.

### Expansion vs ranking

Glossary integration is split into two components:

- **`GlossaryExpander`** (a [`QueryExpander`](pipeline.md#phase-1-query-expansion)) -- runs before ranking stages. Produces `expansionTokens` (glossary-added synonyms) that flow into the `keyword_expanded` signal.
- **`GlossaryMatchStage`** (a [`SearchStage`](pipeline.md#phase-2-ranking-stages)) -- runs during ranking. Boosts documents whose IDs match glossary targets directly.

Glossary terms can also be injected into document text at index build time (via the `context` field), enriching both the BM25 and vector indexes with domain vocabulary.

---

## RRF Score Fusion

Reciprocal Rank Fusion (Cormack et al., 2009) combines multiple ranked lists without requiring training data or labeled relevance judgments.

### Formula

```
score(doc) = SUM over signals i:  1 / (k + rank_i(doc))
```

Where `rank_i` is the 1-based position in signal `i`'s list and [`k` defaults to 25](tuning.md#rrfk-rank-weighting). Documents appearing in multiple signals naturally score higher. The fused scores are passed to a [top-K selection](pipeline.md#top-k-selection) algorithm with keyset pagination support.

### Why k=25 (not k=60)

The original RRF paper recommends `k = 60` for homogeneous fusion -- combining many retrieval runs of the same type (e.g., multiple TREC keyword systems). For heterogeneous fusion of 3-5 distinct signals (vector + keyword + glossary), `k = 25` better rewards items that rank highly in multiple signals. This is the standard default in hybrid dense+sparse pipelines (Weaviate, BEIR benchmarks).

### NamedSignal[] -- extensible, not hardcoded

Fusion accepts N named signals via [`NamedSignal[]`](pipeline.md#phase-4-score-fusion) (each carrying a `name` and a ranked `entries` list), rather than a hardcoded 3-field interface. This makes it straightforward to add or remove signals without changing the fusion API.

### Alternative: WeightedSumFusion

For cases where you want explicit control over signal importance, `WeightedSumFusion` normalizes each signal's scores to `[0, 1]` and computes a weighted sum. This requires choosing weights (e.g., keyword: 0.4, vector: 0.4, glossary: 0.2) but gives direct control over each signal's contribution.

---

## Graph Signals

Graph signals leverage relationship structure (e.g., foreign keys, type hierarchies) to boost documents that are structurally important or close to already-matched results.

### DegreeSignal (static)

Computes node importance by in-degree + out-degree in the schema graph, normalized to `[0, 1]`. Highly-connected nodes (hubs) -- such as a type returned by many query fields, or a table referenced by many foreign key columns -- receive a ranking boost.

`DegreeSignal` is a [`StaticSignal`](pipeline.md#staticsignal): it is computed once and cached until `invalidateStaticSignals()` is called (typically after a data refresh rebuilds the graph).

### AdamicAdarSignal (static)

Computes neighbor specificity using the Adamic-Adar index (2003). For each node, sums `1 / log(degree(neighbor))` across all neighbors. Nodes connected to low-degree (rare, niche) neighbors score higher than nodes connected only to high-degree hubs. This complements DegreeSignal -- where DegreeSignal favors hubs, AdamicAdarSignal favors nodes in specific, well-defined relationships.

### BetweennessSignal (static)

Computes betweenness centrality via Brandes' algorithm (O(V×E) for unweighted graphs). Nodes that sit on many shortest paths between other node pairs score higher -- these are "bridge" tables connecting otherwise separate domains (e.g., CONTRACT linking the ARTIST domain to the ROYALTY domain). Treats the graph as undirected.

### ColumnDensitySignal (static, no graph required)

Computes a ranking signal from document field density. Documents with more keyword fields (columns, properties) score higher, capturing the fact-table-vs-lookup-table distinction -- data-rich tables with many columns are typically more important than small lookup tables. Unlike the other signals, this does not require a graph.

### ProximitySignal (query-time)

Runs multi-source BFS from the top-ranked candidates (as anchor nodes) and boosts nearby graph neighbors. This captures the intuition that items close to already-matched results are likely relevant.

`ProximitySignal` is a [`QuerySignal`](pipeline.md#querysignal): it is computed fresh on every search call using the top candidates as starting points.

### Static vs query-time

| Type                                     | When computed  | Cached | Examples                                                               |
| ---------------------------------------- | -------------- | ------ | ---------------------------------------------------------------------- |
| [StaticSignal](pipeline.md#staticsignal) | On data change | Yes    | DegreeSignal, AdamicAdarSignal, BetweennessSignal, ColumnDensitySignal |
| [QuerySignal](pipeline.md#querysignal)   | Every search   | No     | ProximitySignal                                                        |

Static signals are cheap per query (cached). Query signals are more expensive but can incorporate query-specific context. See [extending signals](extending.md#custom-staticsignal) for how to implement custom signals.