use std::collections::HashMap;
use crate::types::ChunkId;
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum FusionSource {
Dense,
Sparse,
}
#[derive(Debug, Clone)]
pub struct FusionCandidate {
pub chunk_id: ChunkId,
pub source: FusionSource,
pub rank: usize,
pub source_score: f32,
}
#[derive(Debug, Clone)]
pub struct RrfConfig {
pub k: f32,
pub dense_weight: f32,
pub sparse_weight: f32,
}
impl Default for RrfConfig {
fn default() -> Self {
Self {
k: 60.0,
dense_weight: 1.0,
sparse_weight: 1.0,
}
}
}
#[derive(Debug, Clone)]
pub struct FusedResult {
pub chunk_id: ChunkId,
pub rrf_score: f32,
pub dense_rank: Option<usize>,
pub sparse_rank: Option<usize>,
}
struct FusionAccumulator {
rrf_score: f32,
dense_rank: Option<usize>,
sparse_rank: Option<usize>,
}
pub struct RrfFusion {
config: RrfConfig,
}
impl RrfFusion {
pub fn new(config: RrfConfig) -> Self {
Self { config }
}
pub fn default_config() -> Self {
Self::new(RrfConfig::default())
}
pub fn fuse(&self, candidates: Vec<FusionCandidate>) -> Vec<FusedResult> {
let mut accumulators: HashMap<ChunkId, FusionAccumulator> = HashMap::new();
for candidate in candidates {
let weight = match candidate.source {
FusionSource::Dense => self.config.dense_weight,
FusionSource::Sparse => self.config.sparse_weight,
};
let contribution = weight / (self.config.k + candidate.rank as f32);
let acc = accumulators
.entry(candidate.chunk_id.clone())
.or_insert_with(|| FusionAccumulator {
rrf_score: 0.0,
dense_rank: None,
sparse_rank: None,
});
acc.rrf_score += contribution;
match candidate.source {
FusionSource::Dense => acc.dense_rank = Some(candidate.rank),
FusionSource::Sparse => acc.sparse_rank = Some(candidate.rank),
}
}
let mut results: Vec<FusedResult> = accumulators
.into_iter()
.map(|(chunk_id, acc)| FusedResult {
chunk_id,
rrf_score: acc.rrf_score,
dense_rank: acc.dense_rank,
sparse_rank: acc.sparse_rank,
})
.collect();
results.sort_by(|a, b| {
b.rrf_score
.partial_cmp(&a.rrf_score)
.unwrap_or(std::cmp::Ordering::Equal)
.then_with(|| a.chunk_id.cmp(&b.chunk_id))
});
results
}
}
#[cfg(test)]
mod tests {
use super::*;
use uuid::Uuid;
fn make_chunk_id(seed: u8) -> ChunkId {
let bytes = [seed; 16];
ChunkId::from_uuid(Uuid::from_bytes(bytes))
}
#[test]
fn test_rrf_single_source() {
let fusion = RrfFusion::default_config();
let candidates = vec![
FusionCandidate {
chunk_id: make_chunk_id(1),
source: FusionSource::Dense,
rank: 1,
source_score: 0.9,
},
FusionCandidate {
chunk_id: make_chunk_id(2),
source: FusionSource::Dense,
rank: 2,
source_score: 0.8,
},
FusionCandidate {
chunk_id: make_chunk_id(3),
source: FusionSource::Dense,
rank: 3,
source_score: 0.7,
},
];
let results = fusion.fuse(candidates);
assert_eq!(results.len(), 3);
assert!(results[0].rrf_score > results[1].rrf_score);
assert!(results[1].rrf_score > results[2].rrf_score);
assert!(results[0].dense_rank.is_some());
assert!(results[0].sparse_rank.is_none());
}
#[test]
fn test_rrf_both_sources() {
let fusion = RrfFusion::default_config();
let candidates = vec![
FusionCandidate {
chunk_id: make_chunk_id(1), source: FusionSource::Dense,
rank: 1,
source_score: 0.9,
},
FusionCandidate {
chunk_id: make_chunk_id(2), source: FusionSource::Dense,
rank: 2,
source_score: 0.8,
},
FusionCandidate {
chunk_id: make_chunk_id(3), source: FusionSource::Dense,
rank: 3,
source_score: 0.7,
},
FusionCandidate {
chunk_id: make_chunk_id(1), source: FusionSource::Sparse,
rank: 3,
source_score: 5.0,
},
FusionCandidate {
chunk_id: make_chunk_id(2), source: FusionSource::Sparse,
rank: 1,
source_score: 8.0,
},
];
let results = fusion.fuse(candidates);
assert_eq!(results.len(), 3);
let b_result = results
.iter()
.find(|r| r.chunk_id == make_chunk_id(2))
.unwrap();
let a_result = results
.iter()
.find(|r| r.chunk_id == make_chunk_id(1))
.unwrap();
let c_result = results
.iter()
.find(|r| r.chunk_id == make_chunk_id(3))
.unwrap();
assert!(
b_result.rrf_score > a_result.rrf_score,
"B should rank higher than A"
);
assert!(
a_result.rrf_score > c_result.rrf_score,
"A should rank higher than C"
);
}
#[test]
fn test_rrf_deduplication() {
let fusion = RrfFusion::default_config();
let candidates = vec![
FusionCandidate {
chunk_id: make_chunk_id(1),
source: FusionSource::Dense,
rank: 1,
source_score: 0.9,
},
FusionCandidate {
chunk_id: make_chunk_id(1),
source: FusionSource::Sparse,
rank: 2,
source_score: 5.0,
},
];
let results = fusion.fuse(candidates);
assert_eq!(results.len(), 1);
assert_eq!(results[0].dense_rank, Some(1));
assert_eq!(results[0].sparse_rank, Some(2));
let expected = 1.0 / (60.0 + 1.0) + 1.0 / (60.0 + 2.0);
assert!((results[0].rrf_score - expected).abs() < 0.0001);
}
#[test]
fn test_rrf_equal_score_tie_break_is_deterministic() {
let fusion = RrfFusion::default_config();
let a = FusionCandidate {
chunk_id: make_chunk_id(9),
source: FusionSource::Dense,
rank: 4,
source_score: 0.5,
};
let b = FusionCandidate {
chunk_id: make_chunk_id(3),
source: FusionSource::Sparse,
rank: 4,
source_score: 7.0,
};
let forward = fusion.fuse(vec![a.clone(), b.clone()]);
let reverse = fusion.fuse(vec![b, a]);
assert_eq!(forward[0].rrf_score, forward[1].rrf_score);
let forward_ids: Vec<_> = forward.iter().map(|r| r.chunk_id.clone()).collect();
let reverse_ids: Vec<_> = reverse.iter().map(|r| r.chunk_id.clone()).collect();
assert_eq!(forward_ids, reverse_ids);
assert_eq!(forward_ids[0], make_chunk_id(3));
}
#[test]
fn test_rrf_weights() {
let config = RrfConfig {
k: 60.0,
dense_weight: 2.0,
sparse_weight: 1.0,
};
let fusion = RrfFusion::new(config);
let candidates = vec![
FusionCandidate {
chunk_id: make_chunk_id(1), source: FusionSource::Dense,
rank: 1,
source_score: 0.9,
},
FusionCandidate {
chunk_id: make_chunk_id(2), source: FusionSource::Sparse,
rank: 1,
source_score: 5.0,
},
];
let results = fusion.fuse(candidates);
let dense_result = results
.iter()
.find(|r| r.chunk_id == make_chunk_id(1))
.unwrap();
let sparse_result = results
.iter()
.find(|r| r.chunk_id == make_chunk_id(2))
.unwrap();
assert!(
dense_result.rrf_score > sparse_result.rrf_score,
"Dense should rank higher with 2x weight"
);
assert!(
(dense_result.rrf_score / sparse_result.rrf_score - 2.0).abs() < 0.0001,
"Dense score should be 2x sparse score"
);
}
}