Skip to content

Commit 6bbc7a0

Browse files
authored
feat(tools): add dependency-free BM25 ranker (#1207)
* feat(tools): add dependency-free BM25 ranker * fix(tools): split underscores in BM25 tokenizer * fix: preserve Unicode letters and numbers in MCP search tokens * fix(tools): normalize Unicode in BM25 tokenizer * fix(knip): exclude unused BM25 ranker from production check * test(tools): strengthen BM25 ranking and Unicode assertions
1 parent a15ba8c commit 6bbc7a0

4 files changed

Lines changed: 212 additions & 0 deletions

File tree

‎knip.json‎

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -27,6 +27,8 @@
2727
"!utils/WorkspacePathResolver.ts!",
2828
"!test-utils/**!",
2929
"!utils/versionToken.ts!",
30+
"!services/tools/Bm25Ranker.ts!",
31+
"!services/tools/types.ts!",
3032
"!core/tools/helpers/toolResultFormatting.ts!"
3133
],
3234
"ignoreDependencies": [

‎src/services/tools/Bm25Ranker.ts‎

Lines changed: 105 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,105 @@
1+
import { Ranker, ToolDoc } from "./types"
2+
3+
type IndexedDocument = {
4+
item: ToolDoc
5+
termFrequencies: Map<string, number>
6+
length: number
7+
index: number
8+
}
9+
10+
export class Bm25Ranker implements Ranker {
11+
private readonly k1 = 1.5
12+
private readonly b = 0.75
13+
private indexedItems: ToolDoc[] | undefined
14+
private documents: IndexedDocument[] = []
15+
private documentFrequency = new Map<string, number>()
16+
private averageDocumentLength = 0
17+
18+
rank(query: string, items: ToolDoc[], k: number): ToolDoc[] {
19+
const queryTerms = tokenize(query)
20+
21+
if (queryTerms.length === 0 || items.length === 0 || k <= 0) {
22+
return []
23+
}
24+
25+
this.ensureIndex(items)
26+
27+
const scores = this.documents
28+
.map((document) => ({
29+
document,
30+
score: this.score(document, new Set(queryTerms)),
31+
}))
32+
.filter(({ score }) => score > 0)
33+
34+
scores.sort((left, right) => right.score - left.score || left.document.index - right.document.index)
35+
36+
return scores.slice(0, k).map(({ document }) => document.item)
37+
}
38+
39+
private ensureIndex(items: ToolDoc[]): void {
40+
if (this.indexedItems === items) {
41+
return
42+
}
43+
44+
this.indexedItems = items
45+
this.documentFrequency = new Map<string, number>()
46+
this.documents = items.map((item, index) => {
47+
const termFrequencies = countTerms(item)
48+
49+
for (const term of termFrequencies.keys()) {
50+
this.documentFrequency.set(term, (this.documentFrequency.get(term) ?? 0) + 1)
51+
}
52+
53+
return {
54+
item,
55+
termFrequencies,
56+
length: Array.from(termFrequencies.values()).reduce((total, count) => total + count, 0),
57+
index,
58+
}
59+
})
60+
this.averageDocumentLength =
61+
this.documents.reduce((total, document) => total + document.length, 0) / this.documents.length
62+
}
63+
64+
private score(document: IndexedDocument, queryTerms: Set<string>): number {
65+
let score = 0
66+
const documentCount = this.documents.length
67+
68+
for (const term of queryTerms) {
69+
const termFrequency = document.termFrequencies.get(term)
70+
71+
if (!termFrequency) {
72+
continue
73+
}
74+
75+
const documentFrequency = this.documentFrequency.get(term) ?? 0
76+
const inverseDocumentFrequency = Math.log(
77+
1 + (documentCount - documentFrequency + 0.5) / (documentFrequency + 0.5),
78+
)
79+
const normalization = this.k1 * (1 - this.b + this.b * (document.length / this.averageDocumentLength))
80+
81+
score += inverseDocumentFrequency * ((termFrequency * (this.k1 + 1)) / (termFrequency + normalization))
82+
}
83+
84+
return score
85+
}
86+
}
87+
88+
function tokenize(value: string): string[] {
89+
return value
90+
.normalize("NFC")
91+
.toLowerCase()
92+
.split(/[^\p{L}\p{M}\p{N}]+/u)
93+
.filter(Boolean)
94+
}
95+
96+
function countTerms(item: ToolDoc): Map<string, number> {
97+
const frequencies = new Map<string, number>()
98+
const text = `${item.serverName} ${item.toolName} ${item.description}`
99+
100+
for (const term of tokenize(text)) {
101+
frequencies.set(term, (frequencies.get(term) ?? 0) + 1)
102+
}
103+
104+
return frequencies
105+
}
Lines changed: 96 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,96 @@
1+
import { describe, expect, it } from "vitest"
2+
import { Bm25Ranker } from "../Bm25Ranker"
3+
import { ToolDoc } from "../types"
4+
5+
const tool = (serverName: string, toolName: string, description: string): ToolDoc => ({
6+
serverName,
7+
toolName,
8+
description,
9+
})
10+
11+
describe("Bm25Ranker", () => {
12+
it("ranks matching MCP tools by BM25 relevance", () => {
13+
const items = [
14+
tool("postgres", "query", "Send data and query a Postgres database"),
15+
tool("jira", "createIssue", "Send messages and create Jira issues"),
16+
tool("slack", "postMessage", "Send a Slack message"),
17+
]
18+
19+
expect(new Bm25Ranker().rank("send slack message", items, 3)).toEqual([items[2], items[1], items[0]])
20+
})
21+
22+
it("returns an empty result for empty queries, empty items, and no matches", () => {
23+
const ranker = new Bm25Ranker()
24+
const items = [tool("slack", "postMessage", "Send a message")]
25+
26+
expect(ranker.rank(" ", items, 10)).toEqual([])
27+
expect(ranker.rank("message", [], 10)).toEqual([])
28+
expect(ranker.rank("unrelated", items, 10)).toEqual([])
29+
})
30+
31+
it("truncates results to the requested top-k", () => {
32+
const items = [
33+
tool("one", "search", "Search records"),
34+
tool("two", "search", "Search records"),
35+
tool("three", "search", "Search records"),
36+
]
37+
38+
expect(new Bm25Ranker().rank("search", items, 2)).toEqual(items.slice(0, 2))
39+
expect(new Bm25Ranker().rank("search", items, 0)).toEqual([])
40+
})
41+
42+
it("preserves input order for equal scores", () => {
43+
const items = [tool("first", "lookup", "Find a record"), tool("second", "lookup", "Find a record")]
44+
45+
expect(new Bm25Ranker().rank("record", items, 10)).toEqual(items)
46+
})
47+
48+
it("tokenizes case-insensitively around punctuation", () => {
49+
const matching = tool("Slack-Server", "POST.Message", "Send a message")
50+
const nonMatching = tool("calendar", "createEvent", "Create a calendar event")
51+
52+
expect(new Bm25Ranker().rank("SLACK post message", [nonMatching, matching], 10)).toEqual([matching])
53+
})
54+
55+
it("splits underscore-separated tool names into separate terms", () => {
56+
const matching = tool("github", "create_issue", "Open a ticket")
57+
const nonMatching = tool("calendar", "list_events", "Show upcoming events")
58+
59+
expect(new Bm25Ranker().rank("create issue", [nonMatching, matching], 10)).toEqual([matching])
60+
})
61+
62+
it("preserves Unicode letters and numbers in tokens", () => {
63+
const russian = tool("погода-сервер", "прогноз", "Прогноз погоды")
64+
const arabic = tool("أدوات", "مقياس", "يدعم ٣ بروتوكولات")
65+
66+
expect(new Bm25Ranker().rank("погода", [arabic, russian], 10)).toEqual([russian])
67+
expect(new Bm25Ranker().rank("٣", [russian, arabic], 10)).toEqual([arabic])
68+
})
69+
70+
it("matches composed and decomposed forms of the same accented character", () => {
71+
const decomposed = tool("café", "menu", "Liste du café")
72+
const composed = tool("café", "menu", "Menu")
73+
const other = tool("calendar", "events", "Show events")
74+
75+
expect(new Bm25Ranker().rank("café", [other, decomposed], 10)).toEqual([decomposed])
76+
expect(new Bm25Ranker().rank("café", [other, composed], 10)).toEqual([composed])
77+
})
78+
79+
it("handles tools with empty descriptions", () => {
80+
const item = tool("GitHub", "listRepos", "")
81+
82+
expect(new Bm25Ranker().rank("github repos", [item], 10)).toEqual([item])
83+
})
84+
85+
it("rebuilds only when the items array reference changes", () => {
86+
const items = [tool("slack", "send", "Send a message")]
87+
const ranker = new Bm25Ranker()
88+
89+
ranker.rank("send", items, 10)
90+
items.push(tool("jira", "create", "Create an issue"))
91+
expect(ranker.rank("issue", items, 10)).toEqual([])
92+
93+
const newItems = items.slice()
94+
expect(ranker.rank("issue", newItems, 10)).toEqual([newItems[1]])
95+
})
96+
})

‎src/services/tools/types.ts‎

Lines changed: 9 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,9 @@
1+
export type ToolDoc = {
2+
serverName: string
3+
toolName: string
4+
description: string
5+
}
6+
7+
export interface Ranker {
8+
rank(query: string, items: ToolDoc[], k: number): ToolDoc[]
9+
}

0 commit comments

Comments
 (0)