Kosh Adaptive Search Algorithm

Kosh provides a custom Adaptive Search Algorithm designed to return the most relevant credential based on how users naturally search — by label, by username, or by abbreviation. It combines Damerau-Levenshtein fuzzy string matching, ordered subsequence matching, and usage metrics (recency and frequency) in a single multiplicative scoring pipeline.

The search system ranks all credentials in the vault using four feature classes:

Feature	Description	Weight
String match (label)	Fuzzy match between queryLabel and credential label	0.60
String match (user)	Fuzzy match between queryUser and credential username	0.20
Recency	Usage multiplier: how recently the credential was accessed	0.12
Frequency	Usage multiplier: how often the credential has been accessed	0.05

After computing the score, all credentials are sorted descending, and the best match is selected if it clears a minimum threshold (0.2).

The system is deterministic, fast, and independent of database indexing behavior.

1. Query Modes

Single-argument search

kosh search git
# or shorthand
kosh git

• The argument is treated as the label query.
• The algorithm compares it against:
  • label
  • user (also considered, but with lower weighting)

Note: empty or whitespace-only queries evaluate to a score of 0.

Two-argument search

kosh search github personal

• First argument → label query
• Second argument → user query

This allows structured filtering such as targeting specific accounts under the same label (github work, github personal, etc.).

Interactive search

kosh search
# or shorthand
kosh

With no arguments the vault is re-scored on every keystroke and the top matches are presented for selection.

2. Scoring Model

Usage metrics modulate the match score instead of competing with it. This guarantees that a bad match multiplied by heavy usage remains a bad match; usage metrics primarily serve to break ties between similarly strong string matches.

TOTAL_SCORE = (LABEL_WEIGHT * labelScore + USER_WEIGHT * userScore) × (1 + RECENCY_WEIGHT * recencyScore + FREQUENCY_WEIGHT * frequencyScore)

Where each component is a normalized value ∈ [0, MAX_STRING_SCORE].

Because the second factor is always ≥ 1, recency and frequency can only scale a match up — they can never promote a weaker match above a stronger one.

How much can usage actually move a result?

The multiplier is bounded. Recency maxes out at 1.0 and frequency at 0.507 once the access count reaches the 2,000 reset threshold, so:

max multiplier = 1 + (0.12 × 1.0) + (0.05 × 0.507) = 1.145

Usage can lift a score by at most about 15%. That single number is what makes the ordering predictable — the gap between a good match and a mediocre one is almost always wider than 15%:

Credential	Match	Usage	Final score
Strong match, never used	0.9	multiplier 1.000	0.540
Weak match, used constantly	0.5	multiplier 1.145	0.344

The heavily used credential loses, and would keep losing however much more it were used.

This changed in v0.3.0

Scores used to be additive:

TOTAL_SCORE = labelScore + userScore + recencyScore + frequencyScore    ← old, v0.2.3

Under that formula recency and frequency could outvote the match itself, so a credential you used constantly could rank above one that actually matched what you typed. Describing the four weights as percentage shares of a single total no longer reflects how ranking works.

Tuning constants

Constant	Value
LABEL_WEIGHT	0.60
USER_WEIGHT	0.20
RECENCY_WEIGHT	0.12
FREQUENCY_WEIGHT	0.05
PREFIX_BOOST	0.8
SUBSTR_BOOST	0.5
SUBSEQ_BOOST	0.4
MAX_STRING_SCORE	1.0
MIN_SCORE_THRESHOLD	0.2
AccessCountResetThreshold	2,000

3. String Matching

Fuzzy Match Score

For each of the label and user fields, the query and target are case-folded and whitespace-trimmed inside the scoring function — so matching is reliably insensitive to case and surrounding whitespace on both sides:

labelScore = stringScore(queryLabel, label)
userScore  = stringScore(queryUser, user)

stringScore() evaluates relevance using a strict five-tier hierarchy:

1. Exact match
2. Prefix match
3. Substring match
4. Ordered subsequence match (abbreviations)
5. Fuzzy edit-distance (typos)

This ordering is guaranteed for every input, and is enforced by tests.

Damerau-Levenshtein Distance

Base string similarity is calculated using the Damerau-Levenshtein distance, which accurately treats two adjacent transposed characters as a single mistake rather than two:

similarity = 1 − distance(query, target) / max(len(query), len(target))

Query	Target	Levenshtein	Damerau-Levenshtein
crat	cart	2 edits	1 edit
recieve	receive	2 edits	1 edit
githbu	github	2 edits	1 edit

• kosh crat → matches cart
• kosh recieve → matches receive

The transposition rule is deliberately narrow: swapping two non-adjacent characters still costs two edits. A distance of zero short-circuits to a similarity of 1.0, which also means two empty strings are treated as a perfect match instead of producing NaN.

Asymptotic Boosts

Instead of flat score additions, Kosh uses asymptotic boosts to ensure scores never exceed 1.0. This is what enforces the strict matching hierarchy. The boost formula is:

score += (1.0 - score) * BOOST

Exactly one boost applies — the first tier that matches:

• Prefix Boost (0.8): applied if the target starts with the query.
• Substring Boost (0.5): applied if the target contains the query contiguously anywhere inside it.
• Ordered-Subsequence Boost (0.4): rewards queries whose characters appear in order within the target, even with gaps. This allows for very fast abbreviation matching:
  • kosh gpat → matches git_personal_access_token
  • kosh awsprod → matches aws_production_key
  • kosh dbpw → matches database_password

For the query git, the tiers resolve like this:

Target	Tier	Relative score
git	exact	highest
github	prefix
my-git-token	substring
g_i_t_lab	subsequence
gut	fuzzy	lowest

4. Recency Scoring

Recent credentials should rank higher among similar matches. Kosh uses a quick-decay function with a ~12h half-life:

recencyScore = 1 / (1 + hoursSinceLastAccess / 12)

Time since last use	Recency
just now	1.00
12 hours	0.50
1 day	0.33
1 week	0.07
never	0.00

The curve is steepest in the first few hours: half the score is gone after 12 hours and two thirds after a day. Past about three days it is flat and near zero, so an old credential contributes essentially nothing from recency no matter how much older it gets.

Properties:

• Zero for never-used items.
• Drops quickly with time.
• Ensures daily-use credentials rise automatically above similarly-named older items.
• A last-access timestamp in the future (clock skew) is clamped to “just now” rather than going negative.

5. Frequency Scoring

Frequently used credentials gain a slight edge. The curve is flattened logarithmically to prevent heavily used credentials from dominating the vault forever.

frequencyScore = log(accessCount + 1) / 15

Access count	Frequency
0	0.000
1	0.046
10	0.160
100	0.308
1,000	0.461
2,000	0.507

The two curves above show why the divisor changed. The old /5 curve crosses 1.0 at around 150 accesses and keeps climbing, at which point frequency alone outweighs every other signal combined. The current /15 curve is still rising at 200 accesses but has only reached 0.35 — enough to separate a well-used credential from a neglected one, never enough to decide the ranking by itself.

Properties:

• Fast growth early (1 → 2 → 3 → 5 uses).
• Flattens significantly due to the / 15 divisor — widened from / 5 in v0.3.0, where the score could previously exceed 1.0 and swamp every other signal.
• The baseline access count automatically resets after hitting the 2,000 threshold, ensuring long-term stability. This was lowered from 10,000, so the reset happens roughly five times sooner.

Each successful retrieval through kosh get or kosh search bumps the access count by 2.

6. Thresholding and Sorting

Only results with a total score ≥ 0.2 are considered. Everything below is discarded outright rather than shown as a weak match.

Sorting priority:

1. Higher score first
2. If tied → higher access count
3. If still tied → lexicographically smaller label

This enforces strict predictability of results.

7. Complexity

For N credentials:

O(N * L²) time,  O(L) space

Where L is the max label/user string length. The quadratic term is the Damerau-Levenshtein matrix, computed with a rolling three-row buffer rather than a full table, which keeps memory linear. Given typical vault sizes (tens–hundreds of entries with short labels), this is effectively instantaneous — fast enough to re-score the entire vault on every keystroke in interactive mode.

8. Example Flow

Search request:

kosh gpat

Algorithm executes:

1. Lowercase and trim the query gpat.
2. For each credential:
   • compute stringScore("gpat", label) — scores highly on git_personal_access_token due to the ordered-subsequence boost
   • compute stringScore("gpat", user)
   • compute recencyScore
   • compute frequencyScore
3. Combine scores using the multiplicative formula.
4. Discard results < threshold.
5. Sort remaining by score/frequency/label.
6. Return best match.

If the user accepts, the credential is:

• Decrypted using a Curve25519-derived key.
• Copied to the clipboard directly.
• Frequency +2.
• Updated accessed_at=now.

The clipboard write happens before the metadata update, so the secret reaches the clipboard even if the bookkeeping write is slow or fails.

9. Test Coverage

internal/search/search_test.go covers:

• Damerau-Levenshtein distance, including that non-adjacent swaps are not a single edit
• stringScore across all five tiers
• recencyScore and frequencyScore curves
• the boost hierarchy exact > prefix > substring > subsequence > fuzzy
• end-to-end ranking by frequency and by recency
• deterministic tie-breakers
• query composition — a user-only query matching by user, and a label+user query outscoring a label-only one

10. Why This Algorithm Works Well

• More intelligent than substring search: handles transposed typos (crat), partial queries, and deep abbreviations (awsprod).
• Match quality is king: a bad string match can never outrank a good string match, no matter how heavily you use the bad one.
• Respects human usage patterns: items you used recently appear first automatically among similar matches.
• Deterministic and predictable: same inputs → same outputs.
• No reliance on external libraries: fully implemented in Go for portability.