Similarity Search: A Practical Checkbook for Choosing the Right Matching Algorithm

Imagine you're building an agent router. A user types a query, and your job is to figure out which of your registered agents (each with a short text description) is the best fit — without calling an LLM to judge it. This is a similarity search problem, and the algorithm you pick can make the difference between a router that "just works" and one that silently sends every query to the wrong agent.

I'll be using one example so you can see exactly how each algorithm behaves on the same input.

Ex: a small agent registry — a set of agents, each with a short description — and one incoming client query. The job of the similarity algorithm is to score the query against every agent description and return the highest-scoring agent (argmax).

Client query: "I WANT TO SUMMARIZE THE DOCUMENT"

Agent registry:

Agent A → "summarize the doc"

Agent B → "generate doc string"

Agent C → "add to taskboard and events"

The correct agent here is obviously Agent A to a human reader — the value of the walkthrough below is seeing how much each algorithm agrees with that, and where a naive algorithm could get tripped up.

1. What Is Similarity Search?

Similarity search is the process of finding, from a collection of items, the ones that are most "alike" a given query — based on fuzzy logic rather than requiring an exact match. It's the backbone of recommendation engines, semantic search, record de-duplication, spell-checkers, and here agent/tool routing.

Broadly, every similarity search technique boils down to two things:

1. Represent the items being compared (turn text into tokens, characters, or vectors).
2. Score how close two representations are, using a distance metric (lower = more similar, e.g. edit distance) or a similarity score (higher = more similar, e.g. cosine similarity, Dice coefficient).

There are two major families of algorithms for step 2:

This article focuses mainly on the lexical/fuzzy matching family (since that's what you'd use when you explicitly don't want an LLM or embedding model to do the validation), but it also covers where embeddings fit in, so you know when to reach for them instead.

2. Step 1: Preprocessing (Before Any Similarity Algorithm)

Before comparing any two strings, you almost always want to normalize them. Comparing raw, unprocessed text tends to penalize semantically similar phrases just because of stop words, casing, or word inflections.

Using spaCy (en_core_web_sm), a typical preprocessing pipeline does:

• Tokenization — split text into individual tokens.
• Stop word removal (token.is_stop) — drop low-information words like "is", "the", "a".
• Punctuation removal (token.is_punct) — drop punctuation tokens.
• Lemmatization (token.lemma_) — reduce words to their dictionary/base form (e.g. "summarizes" → "summarize", "reads" → "read").
• Lowercasing — normalize case so "Document" and "document" aren't treated as different tokens.

Applying this to our running example:

Query: "I WANT TO SUMMARIZE THE DOCUMENT"

→ preprocessed: ['want', 'summarize', 'document']

Agent A: "summarize the doc"

→ preprocessed: ['summarize', 'doc']

Agent B: "generate doc string"

→ preprocessed: ['generate', 'doc', 'string']

Agent C: "add to taskboard and events"

→ preprocessed: ['add', 'taskboard', 'event']

Note: lemmatization normalizes "summarizes" → "summarize", but it does not turn "doc" into "document"; those are two genuinely different tokens. This is an issue that often comes with real agent descriptions (abbreviations, shorthand), and it's exactly why token-overlap methods alone aren't always enough.

Tip: Also consider stemming vs. lemmatization trade-offs, removing duplicate tokens, and optionally filtering by part-of-speech (keeping only nouns/verbs) if descriptions are noisy. This preprocessing makes the algorithm more accurate.

3. Step 2: The Similarity Algorithms

3.1 Token/Set-Based Algorithms

These treat text as a bag of tokens (sets) rather than character sequences. They're fast, interpretable, and great for short descriptions like agent metadata.

a) Sorensen–Dice Coefficient (often just called "Dice coefficient")

Also commonly referred to as the Sorensen–Dice coefficient (or Dice coefficient), close cousin of Jaccard similarity but weights overlap differently.

It measures token overlap between two sets, weighting the intersection twice:

Dice(A, B) = (2 × |A ∩ B|) / (|A| + |B|)

Example — scoring the query against all three agents:

Query tokens (Q): {want, summarize, document}

Agent A tokens: {summarize, doc}

Intersection = {summarize} → |Q ∩ A| = 1

Dice = (2 × 1) / (3 + 2) = 2/5 = 0.400

Agent B tokens: {generate, doc, string}

Intersection = {} → |Q ∩ B| = 0

Dice = 0.000

Agent C tokens: {add, taskboard, event}

Intersection = {} → |Q ∩ C| = 0

Dice = 0.000

Argmax → Agent A (0.400), and it's not close — Dice already separates the right agent from the other two cleanly, because "summarize" is a shared exact token.

• Strengths: Simple, fast, interpretable, works well on short text (like agent descriptions or tags).
• Weaknesses: Pure token overlap — "summarization" and "summarize" don't count as a match unless lemmatized first (this is why Step 1 matters so much).

b) Jaccard Similarity

Very similar to Dice, but divides by the union instead of the sum:

Jaccard(A, B) = |A ∩ B| / |A ∪ B|

Worked example (same registry):

Agent A: |Q ∩ A| = 1, |Q ∪ A| = {want, summarize, document, doc} = 4 → Jaccard = 1/4 = 0.250

Agent B: |Q ∩ B| = 0 → Jaccard = 0.000

Agent C: |Q ∩ C| = 0 → Jaccard = 0.000

Argmax → Agent A (0.250) — same winner as Dice, just a lower absolute score, which is expected (Jaccard is always ≤ Dice for the same sets).

• Strengths: Same as Dice — simple, fast, great for short token sets; also very common for comparing tag sets, categories, or tokenized n-grams.
• Weaknesses: Same as Dice; Jaccard scores are always ≤ Dice scores for the same sets, so if you're setting a similarity threshold, remember the two are not interchangeable numerically.

Dice vs Jaccard — does it matter? Not for ranking: Dice is a rescaling of Jaccard. If you're just picking the best match, either works identically. They only diverge if you set a fixed similarity threshold: Dice scores run higher for the same overlap (it divides by set-size sum, not union). In practice, Jaccard is the more standard "set similarity" metric (used in MinHash/LSH); Dice is more common in NLP/IR text-matching contexts.

3.2 Character-Based (Edit Distance) Algorithms

These compare strings character by character, which makes them excellent at catching typos, spelling variants, and morphological similarity that token-overlap methods miss entirely.

c) Jaro-Winkler Similarity

Jaro-Winkler measures character-level similarity, factoring in matching characters and transpositions (Jaro distance), then boosts the score if the two strings share a common prefix (the "Winkler" adjustment). It's especially good for short strings like names, or single-word comparisons.

For each agent, take the best (max) score across every query-token × description-token pair. Running this for real (jellyfish.jaro_winkler_similarity) on our registry:

Agent A: best pair = ("summarize", "summarize") → 1.000 ← exact token match

Agent B: best pair = ("document", "doc") → 0.854 ← shares "doc" prefix

Agent C: best pair = ("document", "event") → 0.658

Argmax → Agent A (1.000) — still correct, but look closely at Agent B: 0.854, a high score for the wrong agent. This is Jaro-Winkler's prefix bonus working against you — "document" and "doc" share a full prefix, so the algorithm rates them as very similar even though "doc" here means something closer to "docstring," not "the document." Jaro-Winkler alone can almost route a query to the wrong agent, purely because of how it weights shared prefixes.

This is why its adviced to ensemble a token-based method with a character-based one — Dice/Jaccard would have flagged Agent B as 0.0, catching what Jaro-Winkler alone missed.

• Strengths: Catches near-misses that token overlap can't — e.g. "summarize" vs "summarizing" vs "summarization" score highly even without lemmatization, because they share long common prefixes. Very fast on short strings.
• Weaknesses: Designed for comparing single words/short strings, not full sentences — comparing two long sentences directly with Jaro-Winkler gives poor results (this is why, in the example above, you compare token-by-token and take the max/average, rather than jamming the whole preprocessed phrase into one string). Sensitive to prefix but not to characters later in the word.

d) Levenshtein Distance (Edit Distance)

Levenshtein distance is the minimum number of single-character edits — insertions, deletions, or substitutions — needed to turn one string into another. It's the most well-known "edit distance" metric and the basis for many spell-checkers.

Levenshtein("summarize", "summarization")

To turn edit distance into a similarity score (0 to 1, comparable with the other algorithms), normalize by the longer string's length:

similarity = 1 — (edit_distance / max(len(s1), len(s2)))

Running this (best token-pair match per agent, via rapidfuzz) on our registry:

Agent A: best pair = ("summarize", "summarize") → distance 0 → similarity 1.000

Agent B: best pair = ("document", "doc") → distance 5 → similarity 0.375

Agent C: best pair = ("want", "event") → distance 3 → similarity 0.400

Argmax → Agent A (1.000), and notice Levenshtein does not fall into the same trap as Jaro-Winkler: "document" vs "doc" only scores 0.375 here, because Levenshtein counts the 5 missing characters directly rather than rewarding the shared prefix the way Jaro-Winkler's boost does. This is a useful, concrete illustration of why the two character-based algorithms aren't interchangeable — they can disagree on the same pair of strings.

• Strengths: The gold standard for catching typos and minor spelling variations ("summarize" vs "sumarize"); intuitive and well understood; many fast implementations exist (python-Levenshtein, jellyfish, rapidfuzz).
• Weaknesses: Like Jaro-Winkler, it's built for word/short-string comparison, not sentences — apply it token-by-token (take best match) rather than on whole descriptions. It's also case-sensitive and order-sensitive: "document summary" vs "summary document" would score worse than you might expect, even though the meaning is identical.
• Variant to know: Damerau-Levenshtein extends Levenshtein by also treating adjacent character transpositions (e.g. "the" ↔ "teh") as a single edit instead of two — useful if your queries come from human typing where swapped letters are common.

e) Bitap Algorithm (Shift-Or / Baeza-Yates–Gonnet)

Bitap is a fast, bitwise implementation for finding whether a text contains a substring "approximately equal" to a pattern (it also relies on edit distance under the hood). It's the algorithm behind Unix's agrep. It shines when you need to search for a short pattern inside a longer text with a small number of allowed errors.

• When it's relevant to agent matching: less common for whole-sentence description matching, more useful if you're searching for a known keyword/phrase (with allowed typos) inside long documents or logs.
• Weaknesses: Performance degrades on very long patterns; you need to decide an "error budget" (max allowed edits) up front.

3.3 Sequence / Frequency-Based Algorithms

f) N-gram Similarity

Instead of comparing whole tokens, break each string into overlapping sequences of n characters (or words) and compare the sets/frequencies of those n-grams. For example, tri-grams (n=3) of "summarize":

sum, umm, mma, mar, ari, riz, ize

For example,

Comparing n-gram sets between "summarize" and "summarization" will show high overlap on the shared prefix's trigrams, even without any lemmatization step.

• Strengths: Robust to typos and word-order shuffles (unlike Levenshtein, which is order-sensitive at the character level, but unlike Dice/Jaccard on whole tokens, which requires an exact token match). Works well as a fallback when lemmatization isn't available. Used in many spell-checkers and search engines.
• Weaknesses: Choosing n matters — too small (n=2) and everything looks similar; too large (n=5+) and it behaves like exact matching. More computationally involved to set up than simple token overlap.

3.4 Vector / Embedding-Based Algorithms (for context — not "LLM validation," but still ML-based)

If lexical/fuzzy methods aren't accurate enough (e.g. the query says "condense this file" and the description says "summarize the document" — zero token or character overlap, but same meaning), the next tier up is embeddings + a distance metric. This does not require an LLM to "judge" the match — a lightweight sentence-embedding model (e.g. sentence-transformers) converts text to vectors, and then a plain distance metric ranks them:

For large agent registries (hundreds/thousands of agents), exact nearest-neighbor search becomes slow, so Approximate Nearest Neighbor (ANN) methods are used instead:

• HNSW (Hierarchical Navigable Small World) — graph-based, high recall, widely used in vector databases.
• LSH (Locality-Sensitive Hashing) — hashes similar vectors into the same buckets.
• k-d tree / ball tree — good for low-dimensional data, doesn't scale well to high-dimensional embeddings.

4. The Checkbook: Which Algorithm Should You Use?

You may use this as a quick decision checklist.

*** Are you matching short text against short text (e.g. query vs. agent description/tags)?** → Start with Dice/Sorensen or Jaccard on preprocessed tokens. Cheap, fast, explainable.

*** Do your queries/descriptions likely contain typos, abbreviations, or spelling variants?** → Add Levenshtein or Jaro-Winkler on the token level (best-match per token) to catch near-misses that pure token overlap would score as zero.

*** Do you need to detect a known phrase inside a longer block of text, allowing a few errors?** → Use Bitap (online, no index needed) if the corpus is small, or n-gram indexing if it's large.

*** Is your matching sensitive to human-typing style errors (adjacent letters swapped)?** → Use Damerau-Levenshtein instead of plain Levenshtein.

*** Do you expect queries and descriptions to differ in wording even though they mean the same thing** (e.g. "summarize" vs "condense" vs "give me the gist")? → Lexical/fuzzy methods will fail here — you need embeddings + cosine similarity.

*** Do you need a single robust score rather than picking one algorithm?** → Ensemble it. A common, effective pattern: compute Dice (token overlap) + best-pairwise Jaro-Winkler (character similarity), then combine them (e.g. weighted average or take the max), so you catch both exact keyword overlaps and near-miss spelling variants.

5. Putting It Together: Scoring the Full Registry End-to-End

Query: "I WANT TO SUMMARIZE THE DOCUMENT"

Three of the four algorithms give Agent A highest score, Jaro-Winkler alone gets Agent A right too, but with a much smaller safety margin (1.000 vs 0.854) — a sign it's the least reliable single signal to route on by itself for this kind of short-description matching.

Practical takeaway for routing agents: don't just take argmax of one algorithm's raw score. Compute at least one token-based score (Dice/Jaccard) and one character-based score (Levenshtein or Jaro-Winkler), combine them (e.g. average or weighted sum), and route to whichever agent wins the combined score — and consider flagging low-confidence cases (small gap between the top two agents) for a fallback (e.g. asking the user to clarify, or only then calling an LLM).

6. Summary

• Preprocessing (stop-word removal + lemmatization) is recommended
• Token-set methods (Dice, Jaccard) are the cheapest first pass for short text like agent descriptions.
• Character-based methods (Levenshtein, Jaro-Winkler, Damerau-Levenshtein) catch typos and near-miss spellings that token methods miss — apply them token-by-token, not on full sentences.
• N-gram and Bitap are useful when you need substring/typo-tolerant search, especially at scale.
• Embeddings + cosine similarity are the right tool when meaning matters more than wording, just a numeric vector comparison.
• When in doubt, ensemble two algorithms from different families (one token-based, one character-based) rather than relying on a single score.