Skip to main content

cortex_context/
ranking.rs

1//! Deterministic retrieval rankers: cosine similarity, lexical BM25,
2//! reciprocal-rank fusion, and structural graph boosting.
3//!
4//! Every function here is pure and parameter-pinned, and none of them calls
5//! a model — embedding vectors come from the caller. Because the parameters
6//! are fixed and versioned by [`RANKING_VERSION`], two runs over the same
7//! inputs produce the same ranking, which makes these rankings measurable
8//! against a fixture set before you let them influence anything.
9
10use std::collections::{BTreeMap, BTreeSet, HashMap};
11
12/// Identifies the pinned ranking parameters, so a measured result can be
13/// attributed to the exact algorithm that produced it.
14pub const RANKING_VERSION: &str = "retrieval-ranking-v2";
15/// Identity of the retrieval fixture set this ranking is measured against.
16pub const RANKING_FIXTURE_SET: &str = "retrieval-fixtures-v1";
17/// Production graph features: file spans and split siblings, not fixture pairs.
18pub const ADJACENCY_KIND: &str = "evidence_spans";
19const BM25_K1: f64 = 1.2;
20const BM25_B: f64 = 0.75;
21const RRF_K: f64 = 60.0;
22/// A doc gets a neighbor bonus only from fused top-`TOP_M` documents.
23const GRAPH_TOP_M: usize = 3;
24/// A neighbor of a top document is treated as ranked just behind it — it can
25/// overtake unrelated mid-ranked documents but never its benefactor.
26const GRAPH_RANK_PENALTY: f64 = 1.5;
27
28/// Why a cosine comparison cannot be trusted.
29#[derive(Debug, Clone, PartialEq, Eq)]
30pub enum RankingError {
31    EmptyVector,
32    EmptyCorpus,
33    DimensionMismatch { left: usize, right: usize },
34    ExpectedDimension { expected: usize, actual: usize },
35    DigestMismatch,
36    NonFinite,
37    Unnormalized,
38}
39
40impl std::fmt::Display for RankingError {
41    fn fmt(&self, formatter: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
42        match self {
43            Self::EmptyVector => formatter.write_str("embedding vector is empty"),
44            Self::EmptyCorpus => formatter.write_str("embedding corpus is empty"),
45            Self::DimensionMismatch { left, right } => {
46                write!(formatter, "embedding dimensions differ: {left} vs {right}")
47            }
48            Self::ExpectedDimension { expected, actual } => {
49                write!(
50                    formatter,
51                    "embedding dimension {actual} does not match model digest ({expected})"
52                )
53            }
54            Self::DigestMismatch => formatter.write_str("embedding model digest does not match"),
55            Self::NonFinite => formatter.write_str("embedding contains NaN or Infinity"),
56            Self::Unnormalized => formatter.write_str("embedding is not unit-length"),
57        }
58    }
59}
60
61impl std::error::Error for RankingError {}
62
63/// Identity a caller must present before mixing two embedding vectors.
64#[derive(Debug, Clone, Copy, PartialEq, Eq)]
65pub struct CosineSpec<'a> {
66    pub expected_dim: Option<usize>,
67    pub model_digest: Option<&'a str>,
68    pub observed_digest: Option<&'a str>,
69    pub require_unit: bool,
70}
71
72/// Cosine similarity computed in f64; zero vectors compare as 0.
73///
74/// # Errors
75///
76/// Empty, unequal, non-finite, digest-mismatched, or (when requested)
77/// unnormalized vectors. `expected_dim` is the model digest's advertised width.
78pub fn cosine_similarity(
79    a: &[f32],
80    b: &[f32],
81    expected_dim: Option<usize>,
82) -> Result<f64, RankingError> {
83    cosine_checked(
84        a,
85        b,
86        &CosineSpec {
87            expected_dim,
88            model_digest: None,
89            observed_digest: None,
90            require_unit: false,
91        },
92    )
93}
94
95/// Same as [`cosine_similarity`], with digest and unit-norm checks.
96pub fn cosine_checked(a: &[f32], b: &[f32], spec: &CosineSpec<'_>) -> Result<f64, RankingError> {
97    if a.is_empty() || b.is_empty() {
98        return Err(RankingError::EmptyVector);
99    }
100    if a.len() != b.len() {
101        return Err(RankingError::DimensionMismatch {
102            left: a.len(),
103            right: b.len(),
104        });
105    }
106    if let Some(expected) = spec.expected_dim
107        && a.len() != expected
108    {
109        return Err(RankingError::ExpectedDimension {
110            expected,
111            actual: a.len(),
112        });
113    }
114    if let (Some(expected), Some(observed)) = (spec.model_digest, spec.observed_digest)
115        && expected != observed
116    {
117        return Err(RankingError::DigestMismatch);
118    }
119    let mut dot = 0.0_f64;
120    let mut norm_a = 0.0_f64;
121    let mut norm_b = 0.0_f64;
122    for (x, y) in a.iter().zip(b.iter()) {
123        if !x.is_finite() || !y.is_finite() {
124            return Err(RankingError::NonFinite);
125        }
126        dot += f64::from(*x) * f64::from(*y);
127        norm_a += f64::from(*x) * f64::from(*x);
128        norm_b += f64::from(*y) * f64::from(*y);
129    }
130    if spec.require_unit {
131        let len_a = norm_a.sqrt();
132        let len_b = norm_b.sqrt();
133        if (len_a - 1.0).abs() > 1e-3 || (len_b - 1.0).abs() > 1e-3 {
134            return Err(RankingError::Unnormalized);
135        }
136    }
137    if norm_a == 0.0 || norm_b == 0.0 {
138        Ok(0.0)
139    } else {
140        Ok(dot / (norm_a.sqrt() * norm_b.sqrt()))
141    }
142}
143
144/// Corpus indices ranked by descending similarity; ties break by index for
145/// determinism.
146///
147/// # Errors
148///
149/// Any pair that [`cosine_similarity`] rejects.
150pub fn rank_by_similarity(query: &[f32], corpus: &[Vec<f32>]) -> Result<Vec<usize>, RankingError> {
151    if corpus.is_empty() {
152        return Err(RankingError::EmptyCorpus);
153    }
154    let mut scores = Vec::with_capacity(corpus.len());
155    for vector in corpus {
156        scores.push(cosine_similarity(query, vector, None)?);
157    }
158    Ok(rank_by_scores(&scores))
159}
160
161/// Lowercased alphanumeric tokens.
162#[must_use]
163pub fn tokenize(text: &str) -> Vec<String> {
164    text.chars()
165        .map(|ch| {
166            if ch.is_alphanumeric() {
167                ch.to_ascii_lowercase()
168            } else {
169                ' '
170            }
171        })
172        .collect::<String>()
173        .split_whitespace()
174        .map(str::to_owned)
175        .collect()
176}
177
178/// BM25 index over a fixed corpus.
179pub struct Bm25Index {
180    documents: Vec<HashMap<String, usize>>,
181    lengths: Vec<usize>,
182    average_length: f64,
183    document_frequency: HashMap<String, usize>,
184}
185
186impl Bm25Index {
187    #[must_use]
188    pub fn build(corpus: &[String]) -> Self {
189        let mut documents = Vec::with_capacity(corpus.len());
190        let mut lengths = Vec::with_capacity(corpus.len());
191        let mut document_frequency: HashMap<String, usize> = HashMap::new();
192        for text in corpus {
193            let tokens = tokenize(text);
194            lengths.push(tokens.len());
195            let mut frequencies: HashMap<String, usize> = HashMap::new();
196            for token in tokens {
197                *frequencies.entry(token).or_insert(0) += 1;
198            }
199            for term in frequencies.keys() {
200                *document_frequency.entry(term.clone()).or_insert(0) += 1;
201            }
202            documents.push(frequencies);
203        }
204        let average_length = if lengths.is_empty() {
205            0.0
206        } else {
207            lengths.iter().map(|length| to_f64(*length)).sum::<f64>() / to_f64(lengths.len())
208        };
209        Self {
210            documents,
211            lengths,
212            average_length,
213            document_frequency,
214        }
215    }
216
217    /// BM25 score of one document for a tokenized query.
218    #[must_use]
219    pub fn score(&self, query_tokens: &[String], document: usize) -> f64 {
220        let Some(frequencies) = self.documents.get(document) else {
221            return 0.0;
222        };
223        let total = to_f64(self.documents.len());
224        let length = to_f64(self.lengths[document]);
225        let mut score = 0.0;
226        for term in query_tokens {
227            let Some(term_frequency) = frequencies.get(term) else {
228                continue;
229            };
230            let document_frequency = to_f64(*self.document_frequency.get(term).unwrap_or(&0));
231            let idf = ((total - document_frequency + 0.5) / (document_frequency + 0.5) + 1.0).ln();
232            let tf = to_f64(*term_frequency);
233            let denominator =
234                tf + BM25_K1 * (1.0 - BM25_B + BM25_B * length / self.average_length.max(1.0));
235            score += idf * (tf * (BM25_K1 + 1.0)) / denominator;
236        }
237        score
238    }
239
240    /// Corpus indices ranked by descending BM25 score; ties break by index.
241    #[must_use]
242    pub fn rank(&self, query: &str) -> Vec<usize> {
243        let tokens = tokenize(query);
244        rank_by_scores(
245            &(0..self.documents.len())
246                .map(|document| self.score(&tokens, document))
247                .collect::<Vec<_>>(),
248        )
249    }
250}
251
252/// Reciprocal-rank fusion of several rankings over the same corpus.
253#[must_use]
254pub fn rrf_fuse(rankings: &[&[usize]], corpus_len: usize) -> Vec<usize> {
255    let mut scores = vec![0.0_f64; corpus_len];
256    for ranking in rankings {
257        for (rank, document) in ranking.iter().enumerate() {
258            if let Some(score) = scores.get_mut(*document) {
259                *score += 1.0 / (RRF_K + to_f64(rank + 1));
260            }
261        }
262    }
263    rank_by_scores(&scores)
264}
265
266/// Re-rank a fused ranking with a structural neighbor lift in rank space:
267/// a document related to one of the fused top-`GRAPH_TOP_M` documents is
268/// treated as ranked `GRAPH_RANK_PENALTY` behind its best benefactor. It can
269/// overtake unrelated mid-ranked documents but never the benefactor itself.
270#[must_use]
271pub fn graph_boost(fused: &[usize], adjacency: &BTreeMap<usize, BTreeSet<usize>>) -> Vec<usize> {
272    let mut rank_of = vec![usize::MAX; fused.len()];
273    for (rank, document) in fused.iter().enumerate() {
274        if let Some(slot) = rank_of.get_mut(*document) {
275            *slot = rank;
276        }
277    }
278    let mut scores = vec![0.0_f64; fused.len()];
279    for (rank, document) in fused.iter().enumerate() {
280        let own_rank = to_f64(rank + 1);
281        let best_benefactor = adjacency
282            .get(document)
283            .into_iter()
284            .flatten()
285            .filter_map(|neighbor| rank_of.get(*neighbor).copied())
286            .filter(|neighbor_rank| *neighbor_rank < GRAPH_TOP_M)
287            .min();
288        let effective_rank = best_benefactor.map_or(own_rank, |benefactor_rank| {
289            own_rank.min(to_f64(benefactor_rank + 1) + GRAPH_RANK_PENALTY)
290        });
291        scores[*document] = 1.0 / (RRF_K + effective_rank);
292    }
293    rank_by_scores(&scores)
294}
295
296/// Symmetric adjacency over corpus indices from declared related pairs;
297/// malformed or unknown entries are ignored.
298#[must_use]
299pub fn build_adjacency(ids: &[&str], related: &[Vec<String>]) -> BTreeMap<usize, BTreeSet<usize>> {
300    let index_of: HashMap<&str, usize> = ids
301        .iter()
302        .enumerate()
303        .map(|(index, id)| (*id, index))
304        .collect();
305    let mut adjacency: BTreeMap<usize, BTreeSet<usize>> = BTreeMap::new();
306    for pair in related {
307        let (Some(first), Some(second)) = (pair.first(), pair.get(1)) else {
308            continue;
309        };
310        if let (Some(&left), Some(&right)) =
311            (index_of.get(first.as_str()), index_of.get(second.as_str()))
312        {
313            adjacency.entry(left).or_default().insert(right);
314            adjacency.entry(right).or_default().insert(left);
315        }
316    }
317    adjacency
318}
319
320/// One evidence fragment for production adjacency extraction.
321pub struct EvidenceLink<'a> {
322    pub id: &'a str,
323    pub source: &'a str,
324    pub content: &'a str,
325}
326
327/// Structural pairs from evidence: split siblings and the same source file.
328///
329/// This is the production stand-in for eval's declared `related` pairs. It
330/// is intentionally conservative: prefix-sharing split parts, and fragments
331/// that name the same source path. It does not invent crate-level edges.
332#[must_use]
333pub fn evidence_adjacency(items: &[EvidenceLink<'_>]) -> Vec<Vec<String>> {
334    let mut pairs = Vec::new();
335    for (left_index, left) in items.iter().enumerate() {
336        for right in items.iter().skip(left_index + 1) {
337            if parent_id(left.id) == parent_id(right.id)
338                || same_source_file(left.source, right.source)
339            {
340                pairs.push(vec![left.id.to_owned(), right.id.to_owned()]);
341            }
342        }
343    }
344    pairs
345}
346
347/// `WX-VERIFY-2` → `WX-VERIFY`; ids without a trailing `-<digits>` stay as-is.
348#[must_use]
349pub fn parent_id(id: &str) -> &str {
350    if let Some(position) = id.rfind('-') {
351        let suffix = &id[position + 1..];
352        if !suffix.is_empty() && suffix.chars().all(|character| character.is_ascii_digit()) {
353            return &id[..position];
354        }
355    }
356    id
357}
358
359fn same_source_file(left: &str, right: &str) -> bool {
360    match (source_file(left), source_file(right)) {
361        (Some(left), Some(right)) => left == right,
362        _ => false,
363    }
364}
365
366fn source_file(source: &str) -> Option<&str> {
367    source.split([',', ' ', ';']).find_map(|part| {
368        let trimmed = part.trim();
369        let path = trimmed.split_once(':').map_or(trimmed, |(path, _)| path);
370        path.contains('.')
371            .then_some(path)
372            .filter(|value| value.contains('/') || value.contains('\\'))
373    })
374}
375
376/// The `hybrid_graph` pipeline: cosine + BM25 RRF, then structural boost.
377///
378/// Eval and production must call this with the same adjacency extractor.
379pub fn rank_hybrid_graph(
380    query: &[f32],
381    corpus: &[Vec<f32>],
382    corpus_texts: &[String],
383    query_text: &str,
384    corpus_ids: &[&str],
385    related: &[Vec<String>],
386) -> Result<Vec<usize>, RankingError> {
387    let embedding = rank_by_similarity(query, corpus)?;
388    let lexical = Bm25Index::build(corpus_texts).rank(query_text);
389    let fused = rrf_fuse(
390        &[embedding.as_slice(), lexical.as_slice()],
391        corpus_texts.len(),
392    );
393    Ok(graph_boost(&fused, &build_adjacency(corpus_ids, related)))
394}
395
396fn rank_by_scores(scores: &[f64]) -> Vec<usize> {
397    let mut ranked: Vec<usize> = (0..scores.len()).collect();
398    ranked.sort_by(|left, right| {
399        scores[*right]
400            .partial_cmp(&scores[*left])
401            .unwrap_or(std::cmp::Ordering::Equal)
402            .then(left.cmp(right))
403    });
404    ranked
405}
406
407fn to_f64(value: usize) -> f64 {
408    f64::from(u32::try_from(value).unwrap_or(u32::MAX))
409}
410
411#[cfg(test)]
412#[path = "ranking_tests.rs"]
413mod tests;