FIX: Search algorithm favours behaviour metrics over string similarity

kashish commented

2026-06-19 18:53:33 +00:00

Owner

Bug: Behavioral metrics are overpowering string matches & prefix inversion

Problem Statement: The current search algorithm suffers from two fundamental ranking flaws. First, "behavioral dominance" allows highly-used credentials to bypass the MIN_SCORE_THRESHOLD and surface over actual text matches strictly based on usage history. Second, an unbounded string scoring logic creates an "inversion zone" where partial prefix matches can mathematically outrank exact matches.

Here is the mathematical breakdown of the flaws and the proposed structural fixes.

1. Frequency Scoring is not flat enough

The logarithmic growth of our current frequency score scales too aggressively, allowing high-usage credentials to permanently dominate the ranking.

Current Formula:
f(x) = \frac{\log(x + 1)}{5.0}

f(200) = 1.06 \leftarrow Surpasses 1.0 at just 200 accesses, overpowering the base string score (which is theoretically bounded at 1.0).
f(2000) = 1.52

Proposed Formula:
g(x) = \frac{\log(x + 1)}{15.0}

g(200) = 0.35
g(2000) = 0.50 \leftarrow Stays comfortably within the desired bounds. It will never exceed 1.0 under realistic usage patterns.

Mathematical Outcome:
We achieve a 3\times flatter curve.
f'(x) = \frac{1}{5(x+1)}
g'(x) = \frac{1}{15(x+1)} = \boxed{f'(x) \times \frac{1}{3}}

2. The Additive Nature of the Combined Scoring

Currently, the final combined score places behavioral metrics on the same additive plane as the text match:

Score = (S_{\text{label}} \times 0.60) + (S_{\text{user}} \times 0.20) + (S_{\text{recency}} \times 0.12) + (S_{\text{frequency}} \times 0.05)

Because it is additive, a credential with massive behavioral scores can pass the visibility threshold even if it shares zero characters with the search query (e.g., Score = 0.0 + 0.25 = 0.25).

To fix this, we are switching to a multiplicative model where behavior acts as an amplifier to an existing text match, rather than an independent score provider:

Score = \text{StringScore} \times (1.0 + (S_{\text{recency}} \times 0.12) + (S_{\text{frequency}} \times 0.05))
(where \text{StringScore} = (S_{\text{label}} \times 0.60) + (S_{\text{user}} \times 0.20))

The base 1.0 ensures a perfect text match retains its core score, while the behavioral metrics act strictly as a percentage bonus. If the text match is 0.0, the final score mathematically collapses to 0.0.

3. The Prefix Inversion (Asymptotic Gap Closing)

Currently, PREFIX_BOOST = 1.0 and is added directly to the similarity score. A partial prefix match (e.g., searching "git" for "github") evaluates to S_{\text{sim}} + 1.0, which yields an unbounded score > 1.0. Because an exact match strictly returns 1.0, a partial prefix match will mathematically outrank a flawless exact match.

The Fix: Asymptotic Gap Closing
Instead of adding a flat integer and breaking the ceiling, the boost should close a percentage of the remaining gap to 1.0.

S_{\text{boosted}} = S_{\text{sim}} + ((1.0 - S_{\text{sim}}) \times \beta)
(where \beta = 0.80 for Prefix, and 0.40 for Substring)

Mathematical Rigour:

Preserves Ordinality: If S_1 > S_2, then S_1 + (1.0 - S_1)\beta > S_2 + (1.0 - S_2)\beta. The relative Levenshtein ranking is perfectly maintained; better partial matches still beat worse partial matches.
Protects Exact Matches Naturally: Because it only closes a percentage of the gap, \lim_{S \to 1} S_{\text{boosted}} = 1.0. The score approaches 1.0 asymptotically but never actually breaches it, guaranteeing exact matches remain the undisputed ceiling without requiring hacky hard-clamps.

Action Items

Update frequencyScore divisor from 5.0 to 15.0.
Refactor ScoreQuery to use the multiplicative base structure.
Replace unbounded additive PREFIX_BOOST and SUBSTRING_BOOST with asymptotic gap-closing multipliers (0.80 and 0.40 respectively) in stringScore.
Add Unit Tests for search algorithm to prevent regression in future.

### **Bug: Behavioral metrics are overpowering string matches & prefix inversion** **Problem Statement:** The current search algorithm suffers from two fundamental ranking flaws. First, "behavioral dominance" allows highly-used credentials to bypass the `MIN_SCORE_THRESHOLD` and surface over actual text matches strictly based on usage history. Second, an unbounded string scoring logic creates an "inversion zone" where partial prefix matches can mathematically outrank exact matches. Here is the mathematical breakdown of the flaws and the proposed structural fixes. --- ### **1. Frequency Scoring is not flat enough** The logarithmic growth of our current frequency score scales too aggressively, allowing high-usage credentials to permanently dominate the ranking. **Current Formula:** $f(x) = \frac{\log(x + 1)}{5.0}$ * $f(200) = 1.06$ $\leftarrow$ *Surpasses 1.0 at just 200 accesses, overpowering the base string score (which is theoretically bounded at 1.0).* * $f(2000) = 1.52$ **Proposed Formula:** $g(x) = \frac{\log(x + 1)}{15.0}$ * $g(200) = 0.35$ * $g(2000) = 0.50$ $\leftarrow$ *Stays comfortably within the desired bounds. It will never exceed 1.0 under realistic usage patterns.* **Mathematical Outcome:** We achieve a $3\times$ flatter curve. $f'(x) = \frac{1}{5(x+1)}$ $g'(x) = \frac{1}{15(x+1)} = \boxed{f'(x) \times \frac{1}{3}}$ ![Screenshot 2026-06-18 232501](/attachments/7f75de00-94b5-4880-9bbe-5056522ec2cf) --- ### **2. The Additive Nature of the Combined Scoring** Currently, the final combined score places behavioral metrics on the same additive plane as the text match: $Score = (S_{\text{label}} \times 0.60) + (S_{\text{user}} \times 0.20) + (S_{\text{recency}} \times 0.12) + (S_{\text{frequency}} \times 0.05)$ Because it is additive, a credential with massive behavioral scores can pass the visibility threshold even if it shares zero characters with the search query (e.g., $Score = 0.0 + 0.25 = 0.25$). To fix this, we are switching to a **multiplicative model** where behavior acts as an amplifier to an existing text match, rather than an independent score provider: $Score = \text{StringScore} \times (1.0 + (S_{\text{recency}} \times 0.12) + (S_{\text{frequency}} \times 0.05))$ *(where $\text{StringScore} = (S_{\text{label}} \times 0.60) + (S_{\text{user}} \times 0.20)$)* The base $1.0$ ensures a perfect text match retains its core score, while the behavioral metrics act strictly as a percentage bonus. If the text match is $0.0$, the final score mathematically collapses to $0.0$. ![image](/attachments/e677639c-6970-4e1d-92cc-c3f4450a1553) --- ### **3. The Prefix Inversion (Asymptotic Gap Closing)** Currently, `PREFIX_BOOST = 1.0` and is added directly to the similarity score. A partial prefix match (e.g., searching "git" for "github") evaluates to $S_{\text{sim}} + 1.0$, which yields an unbounded score $> 1.0$. Because an exact match strictly returns $1.0$, a partial prefix match will mathematically outrank a flawless exact match. **The Fix: Asymptotic Gap Closing** Instead of adding a flat integer and breaking the ceiling, the boost should close a percentage of the remaining gap to $1.0$. $S_{\text{boosted}} = S_{\text{sim}} + ((1.0 - S_{\text{sim}}) \times \beta)$ *(where $\beta = 0.80$ for Prefix, and $0.40$ for Substring)* **Mathematical Rigour:** 1. **Preserves Ordinality:** If $S_1 > S_2$, then $S_1 + (1.0 - S_1)\beta > S_2 + (1.0 - S_2)\beta$. The relative Levenshtein ranking is perfectly maintained; better partial matches still beat worse partial matches. 2. **Protects Exact Matches Naturally:** Because it only closes a percentage of the gap, $\lim_{S \to 1} S_{\text{boosted}} = 1.0$. The score approaches $1.0$ asymptotically but never actually breaches it, guaranteeing exact matches remain the undisputed ceiling without requiring hacky hard-clamps. --- ### **Action Items** * [x] Update `frequencyScore` divisor from `5.0` to `15.0`. * [x] Refactor `ScoreQuery` to use the multiplicative base structure. * [x] Replace unbounded additive `PREFIX_BOOST` and `SUBSTRING_BOOST` with asymptotic gap-closing multipliers (`0.80` and `0.40` respectively) in `stringScore`. * [x] Add Unit Tests for search algorithm to prevent regression in future.

kashish added 4 commits

2026-06-19 18:53:33 +00:00

CHANGE: reduce global credential access count reset threshold to 2000 for faster resets 605661f4fa

CHANGE: flatten the frequency score curve by a factor of 3 to reduce frequency score overflowing 1.0 b7a5e26fab

CHANGE: use multiplicative combined score instead a95762c3ba

Changed the final combined score calculation from a simple
additive expression to a multiplicative one.

It now uses the behaviour metrics as a support element on top
of the primary string score. So a credential with a very bad
string match won't show up in results just due to behavior metrics.

Now the system collapses to zero, for queries with near zero string
similarity score.

CHANGE: prefix and substring boost are now asymptotic 56c0696051

The previous behaviour of adding a flat boost to a query
just because it is a prefix or a substring would sometimes
cause them to surpass exact matches (which have a fixed score of 1.0).

Boosts now asymptotically close the gap between the current string
score and the theoretical maximum of 1.0, but never exceeding it.
Thus ensuring that exact matches always come up first.

kashish commented

2026-06-19 18:54:03 +00:00

Author

Owner

Fixes #15

kashish self-assigned this

2026-06-19 18:54:26 +00:00

kashish force-pushed fix/search_score_behavior_bias from 56c0696051 to e24793341f

2026-06-23 17:37:09 +00:00

Compare

kashish added 1 commit

2026-06-23 18:11:13 +00:00

TEST: add levenshtein implementation unit tests 2c9bae6892

kashish added 1 commit

2026-06-29 05:34:31 +00:00

ADD: search function unit tests & fixes ab32a4a763

kashish added 1 commit

2026-06-29 17:39:44 +00:00

ADD: frequency score tests and a new base recency score test 8fb58a21bf

kashish added 1 commit

2026-07-15 19:20:12 +00:00

Add string scoring behaviour test 04c543427c

kashish force-pushed fix/search_score_behavior_bias from 04c543427c to 54eae6f6e8

2026-07-17 18:49:31 +00:00

Compare

kashish changed title from ~~WIP: FIX: Search algorithm favours behaviour metrics over string similarity~~ to FIX: Search algorithm favours behaviour metrics over string similarity

2026-07-17 18:50:52 +00:00

kashish merged commit 8d82041959 into main

2026-07-17 18:52:46 +00:00

kashish referenced this pull request from a commit

2026-07-17 18:52:48 +00:00

Merge pull request 'FIX: Search algorithm favours behaviour metrics over string similarity' (#16) from fix/search_score_behavior_bias into main

Rows
Columns

FIX: Search algorithm favours behaviour metrics over string similarity #16

Bug: Behavioral metrics are overpowering string matches & prefix inversion

1. Frequency Scoring is not flat enough

2. The Additive Nature of the Combined Scoring

3. The Prefix Inversion (Asymptotic Gap Closing)

Action Items