plutolab/kosh

Fork 0

High frequency credentials dominate the search even when the label or user text is not at all close to the search query. #15

New issue

Closed

opened 2026-06-18 17:36:37 +00:00 by kashish · 2 comments

kashish commented

2026-06-18 17:36:37 +00:00

Owner

Credentials that are used very often end dominating other credentials and show up in the search result even when they don't have any text or part of text even close to the search query.

The string scoring should have a higher bias, frequency scoring should also flatten out faster and harder to prevent frequency dominance in search results.

Actual Example

Kashish ❯ kosh labplutogl kas
[→] query labplutogl kas [search.go:51]
[→] time for search 0s [search.go:86]
[→] result score 0.499664 [search.go:62]
[✓] found credential - yelo_analytics_db (kashish.sahu)
[?] enter master password:

labplutogl is no where near related to yelo_analytics_db yet it surfaced because it has a relatively high access count.

Access Count

Kashish ❯ kosh list
[•] filters: none

ID   LABEL              USER               CREATED AT           UPDATED AT           ACCESSED AT          ACCESS COUNT
────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────
...
8    yelo_analytics_db  kashish.sahu       2025-11-24 02:25:51  2026-06-18 10:37:52  2026-06-18 10:37:52  126
...
19   plutolab_git       kashish            2025-12-14 23:30:16  2026-06-15 11:24:18  2026-06-15 11:24:18  11
...

Credentials that are used very often end dominating other credentials and show up in the search result even when they don't have any text or part of text even close to the search query. The string scoring should have a higher bias, frequency scoring should also flatten out faster and harder to prevent frequency dominance in search results. ### Actual Example ```bash Kashish ❯ kosh labplutogl kas [→] query labplutogl kas [search.go:51] [→] time for search 0s [search.go:86] [→] result score 0.499664 [search.go:62] [✓] found credential - yelo_analytics_db (kashish.sahu) [?] enter master password: ``` `labplutogl` is no where near related to `yelo_analytics_db` yet it surfaced because it has a relatively high access count. ### Access Count ```bash Kashish ❯ kosh list [•] filters: none ID LABEL USER CREATED AT UPDATED AT ACCESSED AT ACCESS COUNT ──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────── ... 8 yelo_analytics_db kashish.sahu 2025-11-24 02:25:51 2026-06-18 10:37:52 2026-06-18 10:37:52 126 ... 19 plutolab_git kashish 2025-12-14 23:30:16 2026-06-15 11:24:18 2026-06-15 11:24:18 11 ... ```

kashish self-assigned this

2026-06-18 17:36:53 +00:00

kashish commented

2026-06-19 10:16:17 +00:00

Author

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.

Proposed 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. --- ### **Proposed 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.

image.png

415 KiB

Screenshot 2026-06-18 232501.png

130 KiB

kashish added the

bug

label

2026-06-19 15:39:06 +00:00

kashish commented

2026-06-19 15:40:06 +00:00

Author

Owner