1use std::collections::{BTreeMap, BTreeSet, HashMap};
11
12pub const RANKING_VERSION: &str = "retrieval-ranking-v2";
15pub const RANKING_FIXTURE_SET: &str = "retrieval-fixtures-v1";
17pub const ADJACENCY_KIND: &str = "evidence_spans";
19const BM25_K1: f64 = 1.2;
20const BM25_B: f64 = 0.75;
21const RRF_K: f64 = 60.0;
22const GRAPH_TOP_M: usize = 3;
24const GRAPH_RANK_PENALTY: f64 = 1.5;
27
28#[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#[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
72pub 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
95pub 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
144pub 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#[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
178pub 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 #[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 #[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#[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#[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#[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
320pub struct EvidenceLink<'a> {
322 pub id: &'a str,
323 pub source: &'a str,
324 pub content: &'a str,
325}
326
327#[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#[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
376pub 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;