{"_id":"@arclabs561/rank-fusion","name":"@arclabs561/rank-fusion","dist-tags":{"latest":"0.1.19"},"versions":{"0.1.19":{"name":"@arclabs561/rank-fusion","collaborators":["Arc <attobop@gmail.com>"],"description":"Rank fusion algorithms for hybrid search — RRF, ISR, CombMNZ, Borda, DBSF. Zero dependencies.","version":"0.1.19","license":"MIT OR Apache-2.0","repository":{"type":"git","url":"git+https://github.com/arclabs561/rank-fusion.git"},"main":"rank_fusion.js","types":"rank_fusion.d.ts","keywords":["vector-search","hybrid-search","rrf","rag","search"],"gitHead":"8d9f37a8895e0bf8416996e1bc75a85593e34a81","_id":"@arclabs561/rank-fusion@0.1.19","bugs":{"url":"https://github.com/arclabs561/rank-fusion/issues"},"homepage":"https://github.com/arclabs561/rank-fusion#readme","_nodeVersion":"20.19.5","_npmVersion":"11.6.4","dist":{"integrity":"sha512-i3OslgIARmKx0fwIPdkJjT5CCnsx4xoBXJaX3OW5t09ebyw8hJWofPAGUVSyU3u6MXq4ouxOQavoINyoogD2Xw==","shasum":"b4cd65fe4e1f63dc7d20db7f3d0c1f8882fa720f","tarball":"https://registry.npmjs.org/@arclabs561/rank-fusion/-/rank-fusion-0.1.19.tgz","fileCount":5,"unpackedSize":17389,"signatures":[{"keyid":"SHA256:DhQ8wR5APBvFHLF/+Tc+AYvPOdTpcIDqOhxsBHRwC7U","sig":"MEYCIQDorRsAUlZ1FwYi3tJpVGrh8BQeYAc1RaFt7KzbpXfT0AIhAOQq7VGoKD7SnRgV87FVP6KnNp25FLoj8GYvfyR1iypW"}]},"_npmUser":{"name":"arclabs561","email":"femtobop@gmail.com"},"directories":{},"maintainers":[{"name":"arclabs561","email":"femtobop@gmail.com"}],"_npmOperationalInternal":{"host":"s3://npm-registry-packages-npm-production","tmp":"tmp/rank-fusion_0.1.19_1764715301443_0.6020834042443932"},"_hasShrinkwrap":false}},"time":{"created":"2025-12-02T22:41:41.273Z","0.1.19":"2025-12-02T22:41:41.652Z","modified":"2025-12-02T22:41:42.061Z"},"maintainers":[{"name":"arclabs561","email":"femtobop@gmail.com"}],"description":"Rank fusion algorithms for hybrid search — RRF, ISR, CombMNZ, Borda, DBSF. Zero dependencies.","homepage":"https://github.com/arclabs561/rank-fusion#readme","keywords":["vector-search","hybrid-search","rrf","rag","search"],"repository":{"type":"git","url":"git+https://github.com/arclabs561/rank-fusion.git"},"bugs":{"url":"https://github.com/arclabs561/rank-fusion/issues"},"license":"MIT OR Apache-2.0","readme":"# rank-fusion\n\nCombine ranked lists from multiple retrievers. Provides RRF, CombMNZ, Borda, DBSF, RBC, Condorcet, and 10+ fusion algorithms with full explainability, hyperparameter optimization, and IR metrics. Zero dependencies.\n\n## Python Bindings\n\nFor Python users, see [`rank-fusion-python`](../rank-fusion-python/README.md).\n\n[![CI](https://github.com/arclabs561/rank-fusion/actions/workflows/ci.yml/badge.svg)](https://github.com/arclabs561/rank-fusion/actions)\n[![Crates.io](https://img.shields.io/crates/v/rank-fusion.svg)](https://crates.io/crates/rank-fusion)\n[![Docs](https://docs.rs/rank-fusion/badge.svg)](https://docs.rs/rank-fusion)\n\n```\ncargo add rank-fusion\n```\n\n## Why Rank Fusion?\n\nHybrid search combines multiple retrievers (BM25, dense embeddings, sparse vectors) to get the best of each. This requires merging their results.\n\n**Problem**: Different retrievers use incompatible score scales. BM25 might score 0-100, while dense embeddings score 0-1. Normalization is fragile and requires tuning.\n\n**RRF (Reciprocal Rank Fusion)**: Ignores scores and uses only rank positions. The formula `1/(k + rank)` ensures:\n- Top positions dominate (rank 0 gets 1/60 = 0.017, rank 5 gets 1/65 = 0.015)\n- Multiple list agreement is rewarded (documents appearing in both lists score higher)\n- No normalization needed (works with any score distribution)\n\n**Example**: Document \"d2\" appears at rank 0 in BM25 list and rank 1 in dense list:\n- RRF score = 1/(60+0) + 1/(60+1) = 0.0167 + 0.0164 = 0.0331\n- This beats \"d1\" (only in BM25 at rank 0: 0.0167) and \"d3\" (only in dense at rank 1: 0.0164)\n\nRRF finds consensus across retrievers. No normalization needed, works with any score distribution.\n\n## What This Is\n\nFusion algorithms for hybrid search:\n\n| Scenario | Algorithm |\n|----------|-----------|\n| BM25 + dense embeddings | `rrf` (rank-based) |\n| Variable-length lists | `rbc` (Rank-Biased Centroids) |\n| Multiple retrievers, different scales | `rrf_multi` |\n| Same-scale scores | `combsum`, `combmnz` |\n| Trust one retriever more | `weighted`, `rrf_weighted` |\n| Different distributions | `dbsf` (z-score) |\n| Robust to outliers | `condorcet`, `combmed` |\n| Baselines | `combmax`, `combanz` |\n\n**What this is NOT**: embedding generation, vector search, or scoring embeddings. See [rank-refine](https://crates.io/crates/rank-refine) for scoring embeddings.\n\n## Usage\n\n```rust\nuse rank_fusion::rrf;\n\nlet bm25 = vec![(\"d1\", 12.5), (\"d2\", 11.0)];\nlet dense = vec![(\"d2\", 0.9), (\"d3\", 0.8)];\n\nlet fused = rrf(&bm25, &dense);\n// [(\"d2\", 0.033), (\"d1\", 0.016), (\"d3\", 0.016)]\n```\n\n### Realistic Example\n\n```rust\nuse rank_fusion::rrf;\n\n// BM25 results (50 items, scores 0-100)\nlet bm25_results = vec![\n    (\"doc_123\", 87.5),\n    (\"doc_456\", 82.3),\n    (\"doc_789\", 78.1),\n    // ... 47 more results\n];\n\n// Dense embedding results (50 items, cosine similarity 0-1)\nlet dense_results = vec![\n    (\"doc_456\", 0.92),\n    (\"doc_123\", 0.88),\n    (\"doc_999\", 0.85),\n    // ... 47 more results\n];\n\n// RRF finds consensus: doc_456 appears high in both lists\nlet fused = rrf(&bm25_results, &dense_results);\n// doc_456 wins (rank 1 in BM25, rank 0 in dense)\n// doc_123 second (rank 0 in BM25, rank 1 in dense)\n// doc_789 third (rank 2 in BM25, not in dense top-50)\n```\n\n## API\n\n### Rank-based (ignores scores)\n\n| Function | Formula | Use |\n|----------|---------|-----|\n| `rrf(a, b)` | 1/(k + rank) | Different scales |\n| `isr(a, b)` | 1/√(k + rank) | Lower ranks matter more |\n| `borda(a, b)` | N - rank | Simple voting |\n| `rbc(a, b)` | (1-p)^rank / (1-p^N) | Variable-length lists |\n| `condorcet(a, b)` | Pairwise voting | Robust to outliers |\n\n### Score-based\n\n| Function | Formula | Use |\n|----------|---------|-----|\n| `combsum(a, b)` | Σ scores | Same scale |\n| `combmnz(a, b)` | sum × count | Reward overlap |\n| `dbsf(a, b)` | z-score | Different distributions |\n| `weighted(a, b, config)` | weighted sum | Custom weights |\n| `combmax(a, b)` | max(scores) | Baseline, favor high scores |\n| `combmed(a, b)` | median(scores) | Robust to outliers |\n| `combanz(a, b)` | mean(scores) | Average instead of sum |\n\n### Multi-list\n\nAll functions have `*_multi` variants:\n\n```rust\nuse rank_fusion::{rrf_multi, RrfConfig};\n\nlet lists = vec![&bm25[..], &dense[..], &sparse[..]];\nlet fused = rrf_multi(&lists, RrfConfig::default());\n```\n\n### Weighted RRF\n\n```rust\nuse rank_fusion::rrf_weighted;\n\nlet weights = [1.0, 2.0, 0.5];  // per-retriever\nlet fused = rrf_weighted(&lists, &weights, config)?;\n```\n\n### Explainability\n\nDebug and analyze fusion results with full provenance:\n\n```rust\nuse rank_fusion::explain::{rrf_explain, analyze_consensus, attribute_top_k, RetrieverId};\nuse rank_fusion::RrfConfig;\n\nlet bm25 = vec![(\"d1\", 12.5), (\"d2\", 11.0)];\nlet dense = vec![(\"d2\", 0.9), (\"d3\", 0.8)];\n\nlet retrievers = vec![\n    RetrieverId::new(\"bm25\"),\n    RetrieverId::new(\"dense\"),\n];\n\n// Get results with full provenance\nlet explained = rrf_explain(\n    &[&bm25[..], &dense[..]],\n    &retrievers,\n    RrfConfig::default(),\n);\n\n// Each result shows which retrievers contributed and how\nfor result in &explained {\n    println!(\"{}: score={:.6}, consensus={:.1}%\",\n        result.id, result.score,\n        result.explanation.consensus_score * 100.0);\n    for source in &result.explanation.sources {\n        println!(\"  {}: rank {}, contribution {:.6}\",\n            source.retriever_id,\n            source.original_rank.unwrap_or(999),\n            source.contribution);\n    }\n}\n\n// Analyze consensus patterns\nlet consensus = analyze_consensus(&explained);\nprintln!(\"High consensus: {:?}\", consensus.high_consensus);\nprintln!(\"Single source: {:?}\", consensus.single_source);\n\n// Attribute top-k to retrievers\nlet attribution = attribute_top_k(&explained, 5);\nfor (retriever, stats) in &attribution {\n    println!(\"{}: {} docs in top-5, {} unique\",\n        retriever, stats.top_k_count, stats.unique_docs);\n}\n```\n\nSee [`examples/explainability.rs`](examples/explainability.rs) for a complete example.\n\n## Formulas\n\n### Notation\n\n- $d$: Document identifier\n- $R$: Set of all retrievers\n- $r$: A single retriever (element of $R$)\n- $R_d$: Set of retrievers containing document $d$\n- $\\text{rank}_r(d)$: 0-indexed rank of document $d$ in retriever $r$ (top result = 0)\n- $s_r(d)$: Score of document $d$ from retriever $r$\n- $N$: Total number of documents in a list\n- $k$: Smoothing constant (default 60 for RRF)\n\n### RRF (Reciprocal Rank Fusion)\n\n**RRF (Reciprocal Rank Fusion)**: Ignores score magnitudes and uses only rank positions. Formula:\n\n$$\\text{RRF}(d) = \\sum_{r \\in R} \\frac{1}{k + \\text{rank}_r(d)}$$\n\nwhere $R$ is the set of retrievers, $k$ is a smoothing constant (default 60), and $\\text{rank}_r(d)$ is the 0-indexed rank of document $d$ in retriever $r$ (top result = 0). From Cormack et al. (2009).\n\n### Why k=60?\n\nThe k parameter controls how sharply top positions dominate. Cormack et al. (2009) tested k values from 1 to 100 and found k=60 balances:\n- Top position emphasis (rank 0 vs rank 5: 1.1x ratio)\n- Consensus across lists (lower k overweights single-list agreement)\n- Robustness across datasets\n\n**Sensitivity analysis**:\n\n| k | rank 0 | rank 5 | rank 10 | Ratio (0 vs 5) | Use Case |\n|---|--------|--------|---------|----------------|----------|\n| 10 | 0.100 | 0.067 | 0.050 | 1.5x | Top positions highly reliable |\n| 60 | 0.017 | 0.015 | 0.014 | 1.1x | Default for most scenarios |\n| 100 | 0.010 | 0.0095 | 0.0091 | 1.05x | Want uniform contribution |\n\n**When to tune**:\n- k=20-40: When top retrievers are highly reliable, want strong consensus\n- k=60: Default for most hybrid search scenarios\n- k=100+: When lower-ranked items are still valuable, want broad agreement\n\n**Visual example**:\n\n```\nBM25 list:        Dense list:\nrank 0: d1 (12.5)  rank 0: d2 (0.9)\nrank 1: d2 (11.0)  rank 1: d3 (0.8)\nrank 2: d3 (10.5)  rank 2: d1 (0.7)\n\nRRF scores (k=60):\nd1: 1/(60+0) + 1/(60+2) = 0.0167 + 0.0161 = 0.0328\nd2: 1/(60+1) + 1/(60+0) = 0.0164 + 0.0167 = 0.0331 (wins)\nd3: 1/(60+2) + 1/(60+1) = 0.0161 + 0.0164 = 0.0325\n\nFinal ranking: [d2, d1, d3]\n```\n\n**CombMNZ**: Rewards documents appearing in multiple lists (consensus). Multiplies the sum of scores by the number of lists containing the document:\n\n$$\\text{score}(d) = \\text{count}(d) \\times \\sum_r s_r(d)$$\n\n**Example**: Document \"d1\" appears in 2 lists with scores [0.8, 0.7], while \"d2\" appears in 1 list with score 0.9:\n- CombSUM: d1 = 0.8 + 0.7 = 1.5, d2 = 0.9 (d1 wins)\n- CombMNZ: d1 = 2 × 1.5 = 3.0, d2 = 1 × 0.9 = 0.9 (d1 wins by larger margin)\n\n**Borda Count**: Each position gets points equal to how many documents it beats. Formula:\n\n$$\\text{Borda}(d) = \\sum_{r \\in R} (N - \\text{rank}_r(d))$$\n\nwhere $N$ is the total number of documents in list $r$, and $\\text{rank}_r(d)$ is 0-indexed.\n\n**Example**: Two lists, each with 3 documents:\n```\nList 1: [d1, d2, d3]  (N=3)\nList 2: [d2, d1, d3]  (N=3)\n```\n\nBorda scores:\n- d1: (3-0) + (3-1) = 3 + 2 = 5\n- d2: (3-1) + (3-0) = 2 + 3 = 5 (tie)\n- d3: (3-2) + (3-2) = 1 + 1 = 2\n\nBoth d1 and d2 win, reflecting that they appear high in both lists.\n\n**DBSF (Distribution-Based Score Fusion)**: Normalizes scores using z-scores to handle different distributions:\n\n$$s' = \\text{clip}\\left(\\frac{s - \\mu}{\\sigma}, -3, 3\\right)$$\n\nwhere $\\mu$ and $\\sigma$ are the mean and standard deviation of scores from that retriever. Clipping to $[-3, 3]$ bounds outliers: 99.7% of values in a normal distribution fall within ±3σ. This prevents one extreme score from dominating.\n\n**Example**: Retriever A has scores [10, 12, 15, 18, 20] (mean=15, σ=4). Document with score 25 gets z-score (25-15)/4 = 2.5. Document with score 30 gets clipped to 3.0 (would be 3.75 without clipping).\n\n### Relationship Between Algorithms\n\n**CombMNZ vs CombSUM**: CombMNZ is CombSUM multiplied by consensus count:\n\n$$\\text{CombMNZ}(d) = \\text{count}(d) \\times \\text{CombSUM}(d)$$\n\n**ISR vs RRF**: ISR uses square root instead of linear reciprocal:\n\n$$\\text{ISR}(d) = \\sum_{r \\in R} \\frac{1}{\\sqrt{k + \\text{rank}_r(d)}}$$\n\nThis gives lower-ranked items more weight. Use ISR when you want to consider items beyond the top 10-20.\n\n**DBSF vs CombSUM**: DBSF is CombSUM with z-score normalization instead of min-max:\n\n$$\\text{DBSF}(d) = |R_d| \\cdot \\sum_{r \\in R_d} \\text{clip}\\left(\\frac{s_r(d) - \\mu_r}{\\sigma_r}, -3, 3\\right)$$\n\nUse DBSF when score distributions differ significantly between retrievers.\n\n## Benchmarks\n\nMeasured on Apple M3 Max with `cargo bench`:\n\n| Operation | Items | Time |\n|-----------|-------|------|\n| `rrf` | 100 | 13μs |\n| `rrf` | 1000 | 159μs |\n| `combsum` | 100 | 14μs |\n| `combmnz` | 100 | 13μs |\n| `borda` | 100 | 13μs |\n| `rrf_multi` (5 lists) | 100 | 38μs |\n\nThese timings are suitable for real-time fusion of 100-1000 item lists.\n\n## Vendoring\n\nThe code can be vendored if you prefer not to add a dependency:\n\n- `src/lib.rs` is self-contained (~2000 lines)\n- Zero dependencies\n- All algorithms in one file\n\n## Choosing a Fusion Method\n\nStart here: Do your retrievers use compatible score scales?\n\n```\n├─ No (BM25: 0-100, dense: 0-1) → Use rank-based\n│  ├─ Need strong consensus? → RRF (k=60)\n│  └─ Lower ranks still valuable? → ISR (k=1)\n│\n└─ Yes (both 0-1, both cosine similarity) → Use score-based\n   ├─ Want to reward overlap? → CombMNZ\n   ├─ Simple sum? → CombSUM\n   ├─ Different distributions? → DBSF (z-score normalization)\n   └─ Trust one retriever more? → Weighted\n```\n\n**When RRF underperforms**:\n\nRRF is typically 3-4% lower NDCG than CombSUM when score scales are compatible (OpenSearch BEIR benchmarks). Trade-off:\n- RRF: Robust to scale mismatches, no tuning needed\n- CombSUM: Better quality when scales match, requires normalization\n\n**Use RRF when**:\n- Score scales are unknown or incompatible\n- You want zero-configuration fusion\n- Robustness is more important than optimal quality\n\n**Use CombSUM when**:\n- Scores are on the same scale (both cosine, both BM25, etc.)\n- You can normalize reliably\n- Quality is more important than convenience\n\nSee [DESIGN.md](DESIGN.md) for algorithm details.\n\n## Explainability\n\nThe `explain` module provides variants of fusion functions that return full provenance information, showing:\n\n- **Which retrievers** contributed each document\n- **Original ranks and scores** from each retriever\n- **Contribution amounts** showing how much each source added to the final score\n- **Consensus scores** indicating how many retrievers agreed on each document\n\nThis is critical for debugging RAG pipelines: you can see if your expensive cross-encoder is actually helping, identify retriever disagreement patterns, and understand why certain documents ranked where they did.\n\n**Use cases:**\n- Debugging retrieval failures (\"Why did this relevant doc rank so low?\")\n- A/B testing retrievers (\"Is my new embedding model actually improving results?\")\n- Building user trust (\"This answer came 60% from our docs, 40% from community forum\")\n- Identifying index staleness or embedding drift\n\nSee [`examples/explainability.rs`](examples/explainability.rs) for a complete example.\n\n## Normalization\n\nScore normalization is now a first-class concern. Use `normalize_scores()` to explicitly control how scores are normalized before fusion:\n\n```rust\nuse rank_fusion::{normalize_scores, Normalization};\n\nlet scores = vec![(\"d1\", 10.0), (\"d2\", 5.0), (\"d3\", 0.0)];\n\n// Min-max normalization (default for CombSUM/CombMNZ)\nlet normalized = normalize_scores(&scores, Normalization::MinMax);\n\n// Z-score normalization (used by DBSF)\nlet z_normalized = normalize_scores(&scores, Normalization::ZScore);\n\n// Sum normalization (preserves relative magnitudes)\nlet sum_normalized = normalize_scores(&scores, Normalization::Sum);\n\n// Rank-based (ignores score magnitudes)\nlet rank_normalized = normalize_scores(&scores, Normalization::Rank);\n```\n\n## Runtime Strategy Selection\n\nUse the `FusionStrategy` enum for dynamic method selection:\n\n```rust\nuse rank_fusion::strategy::FusionStrategy;\n\n// Select method at runtime\nlet method = if use_scores {\n    FusionStrategy::combsum()\n} else {\n    FusionStrategy::rrf(60)\n};\n\nlet result = method.fuse(&[&list1[..], &list2[..]]);\nprintln!(\"Using method: {}\", method.name());\n```\n\n## Hyperparameter Optimization\n\nOptimize fusion parameters using ground truth (qrels):\n\n```rust\nuse rank_fusion::optimize::{optimize_fusion, OptimizeConfig, OptimizeMetric, ParamGrid};\nuse rank_fusion::FusionMethod;\n\n// Relevance judgments\nlet qrels = std::collections::HashMap::from([\n    (\"doc1\", 2), // highly relevant\n    (\"doc2\", 1), // relevant\n]);\n\n// Retrieval runs\nlet runs = vec![\n    vec![(\"doc1\", 0.9), (\"doc2\", 0.8)],\n    vec![(\"doc2\", 0.9), (\"doc1\", 0.7)],\n];\n\n// Optimize RRF k parameter\nlet config = OptimizeConfig {\n    method: FusionMethod::Rrf { k: 60 },\n    metric: OptimizeMetric::Ndcg { k: 10 },\n    param_grid: ParamGrid::RrfK {\n        values: vec![20, 40, 60, 100],\n    },\n};\n\nlet optimized = optimize_fusion(&qrels, &runs, config);\nprintln!(\"Best k: {}, NDCG@10: {:.4}\", optimized.best_params, optimized.best_score);\n```\n\n## Evaluation Metrics\n\nThe crate includes standard IR metrics for evaluation:\n\n```rust\nuse rank_fusion::{ndcg_at_k, mrr, recall_at_k};\n\nlet results = vec![(\"d1\", 1.0), (\"d2\", 0.9), (\"d3\", 0.8)];\nlet qrels = std::collections::HashMap::from([\n    (\"d1\", 2), // highly relevant\n    (\"d2\", 1), // relevant\n]);\n\nlet ndcg = ndcg_at_k(&results, &qrels, 10);\nlet reciprocal_rank = mrr(&results, &qrels);\nlet recall = recall_at_k(&results, &qrels, 10);\n```\n\n## See Also\n\n- [rank-refine](https://crates.io/crates/rank-refine): score with embeddings (cosine, MaxSim)\n- [DESIGN.md](DESIGN.md): algorithm details and edge cases\n\n## License\n\nMIT OR Apache-2.0\n","readmeFilename":"README.md","_rev":"1-bf262f7a822660a14e5a25405deb83a5"}