https://pressthink.org/j/rosen-archive/frontend/utils/rrf.js?v=3.8.36

1/**
2 * Reciprocal Rank Fusion for hybrid recall (issue #279, the fusion core).
3 *
4 * #279 merges two ranked result lists -- the lexical leg (#276 MiniSearch BM25,
5 * or today's substring filter) and the semantic leg (#278/#396 BGE cosine) --
6 * into one ranking. RRF is the right merge because BM25 scores and cosine
7 * similarities are on different, uncalibrated scales and there is no labeled-query
8 * set to tune a weighted blend against, so the raw scores are not comparable. RRF
9 * throws the scores away and fuses on RANK alone, which makes it indifferent to
10 * the int8 quantization of the stored article vectors as well: the dequantized
11 * cosine is approximate, but the ordering it induces is the only thing RRF reads.
12 *
13 * The fused score of a candidate is the sum, over the lists it appears in, of
14 * 1 / (k + rank), where rank is its 1-indexed position in that list and k is a
15 * smoothing constant (60, from Cormack et al. 2009 and the value #279 specifies).
16 * A candidate absent from a list contributes NOTHING from that list -- the term
17 * is omitted, not added as 1 / (k + infinity). The fused candidate set is the
18 * UNION of the input lists, not their intersection.
19 *
20 * Provenance falls out for free: label the lexical leg 'kw' and the semantic leg
21 * 'sem' and a hit's `sources` is exactly ['kw'], ['sem'], or ['kw', 'sem'], so
22 * `chipFor(sources)` ('kw', 'sem', 'kw·sem') is the result-chip badge #279
23 * wants with no separate tagging pass.
24 *
25 * Pure and side-effect free: rank lists in -> fused ranking out. It was built
26 * first, before its two legs existed, and lived under data/lib/ while it was
27 * inert. It now runs in the browser: App.js fuses the MiniSearch hit order with
28 * the semantic hit order here, so the module moved into frontend/utils/ where
29 * the deploy walk and the service-worker shell pick it up like any other
30 * runtime module. It has no build-time caller.
31 */
32
33// Smoothing constant. Larger k flattens the contribution of top ranks (so deep
34// agreement between lists matters more); smaller k sharpens the head. 60 is the
35// literature default and #279's choice.
36export const DEFAULT_RRF_K = 60;
37
38// Recommended leg labels. Using these makes chipFor() emit #279's result badges
39// directly. The fuser itself is label-agnostic, so other callers can use any
40// labels they like.
41export const LABEL_LEXICAL = 'kw';
42export const LABEL_SEMANTIC = 'sem';
43
44// Canonical provenance order so a hit's chip is stable no matter what order the
45// caller passed the lists in: the known legs lead (lexical, then semantic) and
46// any other labels follow alphabetically. Without this, sources would inherit
47// the caller's object-key order and a { sem, kw } call would render 'sem·kw'.
48const CHIP_PRECEDENCE = { [LABEL_LEXICAL]: 0, [LABEL_SEMANTIC]: 1 };
49function compareLabels(a, b) {
50  const pa = CHIP_PRECEDENCE[a] ?? 2;
51  const pb = CHIP_PRECEDENCE[b] ?? 2;
52  return pa - pb || (a < b ? -1 : a > b ? 1 : 0);
53}
54
55/**
56 * Render a hit's `sources` array as a result-chip badge. With the recommended
57 * leg labels this yields 'kw', 'sem', or 'kw·sem'. The middle dot is U+00B7,
58 * not an ASCII period, so it does not collide with a label that contains '.'.
59 *
60 * The input is canonicalized (lexical, then semantic, then alphabetical) before
61 * joining, so the badge is stable even for a caller that hand-builds `sources`
62 * in some other order -- reciprocalRankFusion already returns it sorted, but
63 * chipFor must not assume its one caller.
64 */
65export function chipFor(sources) {
66  return [...sources].sort(compareLabels).join('·');
67}
68
69/**
70 * Fuse one or more ranked id lists with Reciprocal Rank Fusion.
71 *
72 * @param {Object<string, string[]>} lists - label -> ordered array of ids, best
73 *   first. Example: { kw: ['a', 'b'], sem: ['b', 'c'] }. A label whose list is
74 *   empty is allowed and simply contributes nothing.
75 * @param {{ k?: number }} [opts] - k is the RRF smoothing constant (>= 0).
76 * @returns {Array<{ id: string, score: number, sources: string[], ranks: Object<string, number> }>}
77 *   Fused hits sorted by score descending. Ties break by id ascending so the
78 *   order is fully deterministic. `sources` lists the contributing labels in
79 *   canonical leg order (lexical, semantic, then any others alphabetically), so
80 *   the chip is stable regardless of the order the lists were passed in; `ranks`

81 *   carries the 1-indexed rank per contributing label.
82 *
83 * Within a single list the FIRST occurrence of an id wins its (best) rank;
84 * later duplicates are ignored rather than counted twice, so a malformed list
85 * cannot inflate a candidate's score. Ranks are dense over the unique ids, so a
86 * duplicate does not waste a rank slot and penalize the items after it. A
87 * non-array list value throws -- a shape bug should fail loudly at the seam,
88 * not silently rank nothing.
89 */
90export function reciprocalRankFusion(lists, { k = DEFAULT_RRF_K } = {}) {
91  if (!Number.isFinite(k) || k < 0) {
92    throw new Error(`reciprocalRankFusion: k must be a finite number >= 0, got ${k}`);
93  }
94
95  // id -> { id, score, sources, ranks }. A Map preserves first-seen order, but
96  // the final sort is what callers depend on, so insertion order is incidental.
97  const fused = new Map();
98
99  for (const label of Object.keys(lists)) {
100    const list = lists[label];
101    if (!Array.isArray(list)) {
102      throw new Error(`reciprocalRankFusion: list "${label}" must be an array`);
103    }
104    const seen = new Set();
105    let rank = 0; // dense 1-indexed rank over UNIQUE ids in this list
106    for (const id of list) {
107      if (seen.has(id)) continue; // first (best) rank wins; ignore later dupes
108      seen.add(id);
109
110      rank += 1;
111      const contribution = 1 / (k + rank);
112
113      let entry = fused.get(id);
114      if (!entry) {
115        entry = { id, score: 0, sources: [], ranks: {} };
116        fused.set(id, entry);
117      }
118      entry.score += contribution;
119      entry.sources.push(label);
120      entry.ranks[label] = rank;
121    }
122  }
123
124  const hits = [...fused.values()];
125  for (const hit of hits) hit.sources.sort(compareLabels);
126  return hits.sort(
127    (a, b) => b.score - a.score || (a.id < b.id ? -1 : a.id > b.id ? 1 : 0),
128  );
129}
130
131export default {
132  DEFAULT_RRF_K,
133  LABEL_LEXICAL,
134  LABEL_SEMANTIC,
135  chipFor,
136  reciprocalRankFusion,
137};