# Search Algorithms

Arcana supports three search modes across two vector store backends. This guide explains how each algorithm works under the hood.

## Search Modes Overview

| Mode | Purpose | Memory Backend | PgVector Backend |
|------|---------|----------------|------------------|
| `:vector` | Find similar meaning | HNSWLib cosine similarity | pgvector HNSW index |
| `:keyword` | Find keyword matches | TF-IDF-like scoring | PostgreSQL tsvector |
| `:hybrid` | Combine both | Two queries + RRF | Single-query with weights |

## Vector Search

Both backends use cosine similarity to find semantically similar content.

### Memory Backend (HNSWLib)

Uses [Hierarchical Navigable Small World](https://arxiv.org/abs/1603.09320) graphs for approximate nearest neighbor search.

```
Query embedding → HNSWLib.Index.knn_query → Top-k neighbors by cosine distance
```

**Score calculation:**
```elixir
score = 1.0 - cosine_distance
```

Where `cosine_distance = 1 - cosine_similarity`. A score of 1.0 means identical vectors.

**Complexity:** O(log n) average case for k-NN queries.

### PgVector Backend

Uses PostgreSQL's pgvector extension with HNSW indexing.

```sql
SELECT *, 1 - (embedding <=> query_embedding) AS score
FROM arcana_chunks
ORDER BY embedding <=> query_embedding
LIMIT 10
```

The `<=>` operator computes cosine distance. The HNSW index makes this efficient even for millions of vectors.

## Keyword Search

### Memory Backend: TF-IDF-like Scoring

A simplified term-matching algorithm inspired by TF-IDF:

```elixir
def calculate_text_score(query_terms, document_text) do
  doc_terms = tokenize(document_text)
  matching = count_matching_terms(query_terms, doc_terms)

  # What fraction of query terms appear in the document
  term_ratio = matching / length(query_terms)

  # Penalize long documents (they match more by chance)
  length_factor = 1.0 / :math.log(length(doc_terms) + 1)

  term_ratio * length_factor
end
```

**Example:**

Query: `"elixir pattern matching"` (3 terms)

| Document | Matches | Term Ratio | Length | Length Factor | Score |
|----------|---------|------------|--------|---------------|-------|
| "Pattern matching in Elixir is powerful" | 3 | 1.0 | 6 | 0.51 | 0.51 |
| "Elixir is great" | 1 | 0.33 | 3 | 0.72 | 0.24 |
| "A very long document about many topics including elixir..." | 1 | 0.33 | 50 | 0.26 | 0.09 |

**Why "TF-IDF-like" not actual TF-IDF:**

| Feature | Real TF-IDF | Memory Backend |
|---------|-------------|----------------|
| Term frequency | Counts occurrences | Binary (present/absent) |
| Inverse document frequency | Corpus-wide statistics | No corpus index |
| Document length normalization | Yes | Yes (via log factor) |

The simplification avoids maintaining a persistent term index, which would add complexity to an in-memory store.

### PgVector Backend: PostgreSQL Full-Text Search

Uses PostgreSQL's battle-tested full-text search with `tsvector` and `tsquery`:

```sql
SELECT *,
  ts_rank(to_tsvector('english', text), to_tsquery('english', 'elixir & pattern & matching')) AS score
FROM arcana_chunks
WHERE to_tsvector('english', text) @@ to_tsquery('english', 'elixir & pattern & matching')
ORDER BY score DESC
```

**How it works:**

1. **`to_tsvector`**: Converts text to a searchable vector of lexemes (normalized word forms)
   - "running" → "run"
   - "patterns" → "pattern"
   - Removes stop words ("the", "is", "a")

2. **`to_tsquery`**: Converts query to search terms joined with `&` (AND)
   - `"elixir pattern matching"` → `'elixir' & 'pattern' & 'match'`

3. **`@@` operator**: Returns true if document matches query

4. **`ts_rank`**: Scores documents by:
   - Term frequency in document
   - Inverse document frequency (rarity)
   - Term proximity (how close terms appear)

**Advantages over Memory backend:**
- Stemming (matches "running" when searching "run")
- Stop word removal
- Proximity scoring
- Language-aware processing

## Hybrid Search

Hybrid mode combines vector and keyword search. The implementation differs by backend:

| Backend | Approach | Advantages |
|---------|----------|------------|
| PgVector | Single-query weighted combination | Better coverage, configurable weights |
| Memory | Two queries + RRF | Simple, rank-based fusion |

### PgVector Backend: Single-Query Hybrid

The pgvector backend uses a single SQL query that combines both scores:

```sql
WITH q AS (
  SELECT tsvector_to_array(to_tsvector('english', query_text)) AS lexemes
),
scored AS (
  SELECT
    id, text,
    1 - (embedding <=> query_embedding) AS vector_score,
    -- the share of the query's distinct lexemes the chunk contains;
    -- 0 for a stopword-only query, so the vector score still ranks
    COALESCE(
      (length(tsv) - length(ts_delete(tsv, q.lexemes)))::float
        / NULLIF(cardinality(q.lexemes), 0),
      0
    ) AS keyword_score
  FROM arcana_chunks, q,
    LATERAL (SELECT to_tsvector('english', text) AS tsv OFFSET 0) v
)
SELECT *,
  (vector_weight * vector_score + keyword_weight * keyword_score) AS hybrid_score
FROM scored
ORDER BY hybrid_score DESC
```

**Why single-query is better:**

With separate queries, items ranking moderately in both lists might be missed. For example:
- Vector search fetches top 20
- Keyword search fetches top 20
- An item ranking #15 in both could be highly relevant overall, but RRF only sees it at position 15

Single-query evaluates **all** chunks, so nothing is missed.

**Keyword coverage:**
- Vector scores (cosine similarity) range 0-1
- The keyword score is the share of the query's distinct terms (lexemes after stemming and stopword removal) that a chunk contains, also 0-1: three of four terms scores 0.75
- A chunk with only some of the terms still scores, so long queries keep a keyword signal
- Repeating a term doesn't raise the score, so a term-dense chunk can't outrank the chunk that carries more of the query
- Coverage is already comparable across queries, so there is no normalization step

**Configurable weights:**

```elixir
# Equal weight (default)
{:ok, results} = Arcana.search("query", repo: Repo, mode: :hybrid)

# Favor vector similarity
{:ok, results} = Arcana.search("query", repo: Repo, mode: :hybrid, vector_weight: 0.7, keyword_weight: 0.3)

# Favor keyword matches
{:ok, results} = Arcana.search("query", repo: Repo, mode: :hybrid, vector_weight: 0.3, keyword_weight: 0.7)
```

Results include individual scores for debugging:

```elixir
%{
  id: "...",
  text: "...",
  score: 0.75,           # Combined hybrid score
  vector_score: 0.82,  # Cosine similarity
  keyword_score: 0.75   # Share of query terms the chunk contains
}
```

### Memory Backend: Reciprocal Rank Fusion (RRF)

For the memory backend (and other custom backends), hybrid search uses [Reciprocal Rank Fusion](https://plg.uwaterloo.ca/~gvcormac/cormacksigir09-rrf.pdf) to combine results from separate queries.

**The Problem:**

Vector and keyword searches return scores on different scales:
- Vector: 0.0 to 1.0 (cosine similarity)
- Keyword: Unbounded (ts_rank or term matching)

Naively averaging scores would bias toward one method.

**The Solution: RRF**

RRF scores by **rank position**, not raw score:

```elixir
def rrf_score(rank, k \\ 60) do
  1.0 / (k + rank)
end
```

Where `k` is a constant (default 60) that prevents top-ranked items from dominating.

**Weights on this path:**

`:vector_weight` and `:keyword_weight` apply here too, scaling each side's
contribution. Canonical RRF is unweighted, and equal weights reproduce it
exactly, since scaling both sides by the same factor cannot reorder anything.
Only the ratio matters, so `{0.9, 0.1}` ranks identically to `{9, 1}` and the
weights are rescaled to put the larger one at `1.0` before use. That keeps the
absolute scores where they were before weighting existed, which is why the
default `0.5`/`0.5` produces plain unweighted RRF rather than every score
halved. This differs from pgvector, where the weights are absolute multipliers
that interact with `:threshold`.

**Algorithm:**

```elixir
def rrf_combine(vector_results, keyword_results, limit, k \\ 60, weights \\ {1.0, 1.0}) do
  # Rescaled so the larger weight is 1.0 - only the ratio affects ranking
  {vector_weight, keyword_weight} = normalize_weights!(weights)

  # Build rank maps
  vector_ranks = build_rank_map(vector_results)
  keyword_ranks = build_rank_map(keyword_results)

  # Combine all unique IDs
  all_ids = MapSet.union(Map.keys(vector_ranks), Map.keys(keyword_ranks))

  # Calculate RRF score for each
  all_ids
  |> Enum.map(fn id ->
    vector_rank = Map.get(vector_ranks, id, 1000)  # Default: low rank
    keyword_rank = Map.get(keyword_ranks, id, 1000)

    rrf_score =
      vector_weight / (k + vector_rank) + keyword_weight / (k + keyword_rank)

    {id, rrf_score}
  end)
  |> Enum.sort_by(&elem(&1, 1), :desc)
  |> Enum.take(limit)
end
```

**Example:**

Query: `"BEAM virtual machine"`

| Document | Vector Rank | Keyword Rank | Vector RRF | Keyword RRF | Combined |
|----------|---------------|---------------|--------------|--------------|----------|
| "Erlang runs on the BEAM VM" | 1 | 2 | 0.016 | 0.016 | 0.032 |
| "The BEAM virtual machine" | - | 1 | 0.001 | 0.016 | 0.017 |
| "The BEAM is Erlang's runtime" | 2 | - | 0.016 | 0.001 | 0.017 |

Documents appearing in **both** result sets get boosted to the top.

## Choosing the Right Mode

| Use Case | Recommended Mode |
|----------|------------------|
| Conceptual questions ("How does X work?") | `:vector` |
| Exact terms, names, codes | `:keyword` |
| General search, unknown query type | `:hybrid` |
| API/function lookup | `:keyword` |
| Finding related concepts | `:vector` |

## Backend Comparison

| Aspect | Memory | PgVector |
|--------|--------|----------|
| Setup | No database needed | Requires PostgreSQL + pgvector |
| Persistence | Lost on restart | Persisted |
| Vector search | HNSWLib (excellent) | pgvector HNSW (excellent) |
| Keyword search | Basic term matching | Full linguistic processing |
| Stemming | No | Yes |
| Stop words | No | Yes |
| Scale | < 100K vectors | Millions of vectors |
| Best for | Testing, small apps | Production |