nx_bm25_lib.nx source
↩ module page · 232 lines · 8461 B
1// nx_bm25_lib.nx -- BM25 lexical retrieval + RECIPROCAL RANK FUSION, in pure integer fixed point.
2//
3// WHY THIS, WHY NOW (July 2026 SOTA, researched): every credible legal-retrieval stack this year is
4// HYBRID -- a dense vector retriever AND BM25, fused with Reciprocal Rank Fusion, then reranked by a
5// cross-encoder. Neither leg alone wins: vectors catch paraphrase, BM25 catches the exact defined term
6// ("Force Majeure Event", a party name, a section cross-reference) that an embedder blurs away. In
7// contracts the exact term is very often the whole question, which is why the lexical leg never gets
8// dropped even in fully neural stacks.
9//
10// This builds the leg that needs NO MODEL, plus the fusion that any future embedder plugs straight into.
11// The banked house order is embedder -> cross-encoder -> grep-tools -> graph LAST; BM25+RRF is the
12// skeleton those slot into, and it is useful on its own from day one.
13//
14// u2605NO FLOAT. BM25 needs a logarithm and a saturating ratio, both normally float. Everything here is
15// integer fixed point in MILLI units (1000 = 1.0), including a bit-position natural log with linear
16// interpolation of the mantissa. Ranking only needs ORDER preservation, and integer fixed point
17// preserves order exactly while staying reproducible bit-for-bit across machines -- a float BM25 can
18// reorder two near-tied clauses depending on FMA and compile flags, which makes a retrieval regression
19// impossible to reproduce. Determinism is worth more here than the third decimal place.
20//
21// u2605IDF IS THE HALF PEOPLE DROP. Scoring on raw term frequency ranks a clause highly for containing
22// "the" fifty times. IDF is what makes a rare defined term outweigh filler, and BM25's length
23// normalisation (b) is what stops a long clause winning purely by being long. Both are load-bearing.
24//
25// Parameters are DATA (rule 11): k1 and b as named constants in milli, the standard 1.2 / 0.75.
26// license_tier: ORIGINAL LIB.
27
28import "nx_clause_lib.nx"
29
30const BM_K1_MILLI: i64 = 1200
31const BM_B_MILLI: i64 = 750
32const BM_RRF_K: i64 = 60
33const BM_NO_DOC: i64 = 0 - 1
34const BM_LOG2_1000: i64 = 9953
35
36// ---- integer logarithm, milli units ----
37
38// floor(log2(x)) for x >= 1
39func bm_log2_floor(x: i64) -> i64 {
40 if x < 1 { return 0 }
41 var n: i64 = 0
42 var v: i64 = x
43 while v > 1 {
44 v = v / 2
45 n = n + 1
46 }
47 return n
48}
49
50// log2(x) * 1000, with the mantissa linearly interpolated. Exact at powers of two.
51func bm_log2_milli(x: i64) -> i64 {
52 if x < 1 { return 0 }
53 let n: i64 = bm_log2_floor(x)
54 var p: i64 = 1
55 var i: i64 = 0
56 while i < n {
57 p = p * 2
58 i = i + 1
59 }
60 let frac: i64 = ((x - p) * 1000) / p
61 return (n * 1000) + frac
62}
63
64// ln(x) * 1000 = log2(x) * ln(2), ln(2) ~ 0.693147
65func bm_ln_milli(x: i64) -> i64 {
66 return (bm_log2_milli(x) * 693) / 1000
67}
68
69// u2605ln of a value ALREADY IN MILLI, without truncating it to an integer first.
70// The obvious shortcut -- bm_ln_milli(x_milli / 1000) -- silently collapses EVERY ratio between 1.0 and
71// 2.0 to ln(1) = 0. In BM25 that is not a rounding nit: it zeroes the idf of every term appearing in
72// more than about half the corpus, which makes those terms free and unrankable. Caught by the gate.
73// BM_LOG2_1000 is this function's OWN log2(1000), not the mathematical one, so that ln(1.000) is
74// exactly 0 -- the identity has to hold in the arithmetic actually used, not in real numbers.
75func bm_ln_of_milli(x_milli: i64) -> i64 {
76 if x_milli <= 1000 { return 0 }
77 let l2: i64 = bm_log2_milli(x_milli) - BM_LOG2_1000
78 if l2 <= 0 { return 0 }
79 return (l2 * 693) / 1000
80}
81
82// ---- corpus statistics ----
83
84func bm_doclen(doc: *u8) -> i64 {
85 return cl_word_count(doc)
86}
87
88// term frequency: how many times `term` occurs in `doc` (whole-word, case-insensitive)
89func bm_tf(doc: *u8, term: *u8) -> i64 {
90 let w: *u8 = sys_mmap(CL_WORDBUF)
91 var i: i64 = 0
92 var n: i64 = 0
93 while 1 == 1 {
94 let nx: i64 = cl_word_at(doc, i, w)
95 if w[0] == (0 as u8) { return n }
96 if mt_streq(w, term) == 1 { n = n + 1 }
97 i = nx
98 }
99 return n
100}
101
102// document frequency: how many docs in the corpus contain `term` at least once
103func bm_df(lib: *i64, n: i64, term: *u8) -> i64 {
104 var c: i64 = 0
105 var i: i64 = 0
106 while i < n {
107 if cl_has_word(lib[i] as *u8, term) == 1 { c = c + 1 }
108 i = i + 1
109 }
110 return c
111}
112
113func bm_avgdl(lib: *i64, n: i64) -> i64 {
114 if n <= 0 { return 0 }
115 var t: i64 = 0
116 var i: i64 = 0
117 while i < n {
118 t = t + bm_doclen(lib[i] as *u8)
119 i = i + 1
120 }
121 return t / n
122}
123
124// u2605IDF, milli units: ln(1 + (N - df + 0.5)/(df + 0.5)). Scaled by 2 inside to keep the halves integral.
125// A term in EVERY doc scores near zero; a term in ONE doc of many scores high. Never negative.
126func bm_idf_milli(ndocs: i64, df: i64) -> i64 {
127 if ndocs <= 0 { return 0 }
128 if df < 0 { return 0 }
129 let num: i64 = (2 * (ndocs - df)) + 1
130 let den: i64 = (2 * df) + 1
131 if den <= 0 { return 0 }
132 // 1 + num/den, in milli
133 let ratio_milli: i64 = 1000 + ((num * 1000) / den)
134 if ratio_milli < 1000 { return 0 }
135 return bm_ln_of_milli(ratio_milli)
136}
137
138// u2605the per-term BM25 contribution in milli units, with saturation and length normalisation.
139func bm_term_score_milli(doc: *u8, term: *u8, lib: *i64, n: i64, avgdl: i64) -> i64 {
140 let tf: i64 = bm_tf(doc, term)
141 if tf <= 0 { return 0 }
142 let idf: i64 = bm_idf_milli(n, bm_df(lib, n, term))
143 if idf <= 0 { return 0 }
144 var norm: i64 = 1000
145 if avgdl > 0 {
146 norm = (1000 - BM_B_MILLI) + ((BM_B_MILLI * bm_doclen(doc)) / avgdl)
147 }
148 let numer: i64 = tf * (BM_K1_MILLI + 1000)
149 let denom: i64 = (tf * 1000) + ((BM_K1_MILLI * norm) / 1000)
150 if denom <= 0 { return 0 }
151 return (idf * numer) / denom
152}
153
154// full BM25 for a query against one document
155func bm_score_milli(doc: *u8, query: *u8, lib: *i64, n: i64) -> i64 {
156 let avgdl: i64 = bm_avgdl(lib, n)
157 let w: *u8 = sys_mmap(CL_WORDBUF)
158 var i: i64 = 0
159 var s: i64 = 0
160 while 1 == 1 {
161 let nx: i64 = cl_word_at(query, i, w)
162 if w[0] == (0 as u8) { return s }
163 s = s + bm_term_score_milli(doc, w, lib, n, avgdl)
164 i = nx
165 }
166 return s
167}
168
169// index of the best-scoring document, or BM_NO_DOC when nothing scores above zero.
170func bm_best(query: *u8, lib: *i64, n: i64) -> i64 {
171 if n <= 0 { return BM_NO_DOC }
172 var best: i64 = BM_NO_DOC
173 var bs: i64 = 0
174 var i: i64 = 0
175 while i < n {
176 let s: i64 = bm_score_milli(lib[i] as *u8, query, lib, n)
177 if s > bs {
178 bs = s
179 best = i
180 }
181 i = i + 1
182 }
183 return best
184}
185
186// 1-based rank of document `idx` for this query (1 = best). 0 when it scores nothing.
187func bm_rank_of(query: *u8, lib: *i64, n: i64, idx: i64) -> i64 {
188 if idx < 0 { return 0 }
189 if idx >= n { return 0 }
190 let mine: i64 = bm_score_milli(lib[idx] as *u8, query, lib, n)
191 if mine <= 0 { return 0 }
192 var better: i64 = 0
193 var i: i64 = 0
194 while i < n {
195 if i != idx {
196 if bm_score_milli(lib[i] as *u8, query, lib, n) > mine { better = better + 1 }
197 }
198 i = i + 1
199 }
200 return better + 1
201}
202
203// ---- RECIPROCAL RANK FUSION ----
204
205// u2605RRF combines rankings, NOT scores -- which is the entire point. BM25 scores and cosine similarities
206// live on incomparable scales; normalising them against each other is guesswork that shifts whenever
207// either retriever changes. Ranks are comparable by construction. A document ranked 1 by either leg
208// scores strongly; one ranked mid-pack by both does not. Rank 0 means "unranked by that leg" and
209// contributes nothing rather than contributing a fabricated worst-case.
210func bm_rrf_milli(rank_a: i64, rank_b: i64) -> i64 {
211 var s: i64 = 0
212 if rank_a > 0 { s = s + (1000 / (BM_RRF_K + rank_a)) }
213 if rank_b > 0 { s = s + (1000 / (BM_RRF_K + rank_b)) }
214 return s
215}
216
217// fuse two ranking legs over n documents; ranks_a / ranks_b are arrays of 1-based ranks (0 = unranked).
218func bm_rrf_best(ranks_a: *i64, ranks_b: *i64, n: i64) -> i64 {
219 if n <= 0 { return BM_NO_DOC }
220 var best: i64 = BM_NO_DOC
221 var bs: i64 = 0
222 var i: i64 = 0
223 while i < n {
224 let s: i64 = bm_rrf_milli(ranks_a[i], ranks_b[i])
225 if s > bs {
226 bs = s
227 best = i
228 }
229 i = i + 1
230 }
231 return best
232}