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

Vector Search

Both backends use cosine similarity to find semantically similar content.

Memory Backend (HNSWLib)

Uses Hierarchical Navigable Small World graphs for approximate nearest neighbor search.

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

Score calculation:

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.

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:

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)

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

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:

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:

PgVector Backend: Single-Query Hybrid

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

WITH base_scores AS (
  SELECT
    id, text, embedding,
    1 - (embedding <=> query_embedding) AS vector_score,
    ts_rank(to_tsvector('english', text), query) AS keyword_score
  FROM arcana_chunks
),
normalized AS (
  SELECT *,
    (keyword_score - MIN(keyword_score) OVER ()) /
    NULLIF(MAX(keyword_score) OVER () - MIN(keyword_score) OVER (), 0)
    AS keyword_normalized
  FROM base_scores
)
SELECT *,
  (vector_weight * vector_score + keyword_weight * keyword_normalized) AS hybrid_score
FROM normalized
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.

Score normalization:

• Vector scores (cosine similarity) naturally range 0-1
• Keyword scores (ts_rank) vary widely based on document content
• The query normalizes keyword scores using min-max scaling within the result set

Configurable weights:

# 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:

%{
  id: "...",
  text: "...",
  score: 0.75,           # Combined hybrid score
  vector_score: 0.82,  # Cosine similarity
  keyword_score: 0.68   # Raw ts_rank score
}

Memory Backend: Reciprocal Rank Fusion (RRF)

For the memory backend (and other custom backends), hybrid search uses Reciprocal Rank Fusion 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:

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:

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"

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

Choosing the Right Mode

Backend Comparison