Code graph and memory for your coding agents, in one Rust program. For Claude Code, Codex, Cursor and any MCP client.
Rust agent-memoryai-agentsclaude-codecode-analysiscode-graphcode-intelligencecode-searchcodexcoding-agentscontext-engineeringcursordeveloper-toolsgraphragknowledge-graphlocal-firstmcpmcp-servermodel-context-protocolrusttree-sitter
//! Graphiti RRF adaptation; Graphicle BM25 and evidence-set scheduling. See
//! NOTICE.md for upstream provenance and changes.
//!
//! Portions adapted from Graphiti (<https://github.com/getzep/graphiti>), Copyright 2024, Zep Software, Inc., Apache-2.0; changes are described in NOTICE.md.
use crate::{Result, cache, text};
use serde_json::{Value, json};
use std::collections::{BTreeMap, BTreeSet};
/// Most reviewed memories one recall ranks; the most recently updated are kept.
pub const MAX_RECALL_MEMORIES: usize = 20_000;
/// Most rows [`rank`] accepts: a full passage catalogue plus the recall
/// memories, so no in-bounds store fails recall.
pub const MAX_ROWS: usize = crate::ingest::MAX_PASSAGES + MAX_RECALL_MEMORIES;
/// Most sources one [`rank`] call selects (a reranker's candidate pool).
pub const MAX_RANK_LIMIT: usize = 60;
/// Most candidates [`rank`] keeps after fusion and the relationship lift,
/// best first, ties by identity: selection reads no others.
pub const MAX_FUSED: usize = 400;
/// Most candidates a call may ask [`rank`] to keep instead (`fused_cap`):
/// a long ranking for a caller that fills a large context window.
pub const MAX_FUSED_CAP: usize = 4000;
/// Counting and listing questions need every instance, not the best one.
fn aggregate_question(lowercase: &str) -> bool {
static RX: std::sync::OnceLock<regex::Regex> = std::sync::OnceLock::new();
RX.get_or_init(|| {
regex::Regex::new(
r"\b(how many|how much|in total|total|altogether|combined|list|all the|every)\b",
)
.unwrap()
})
.is_match(lowercase)
}
/// Labels that open a turn in a `role: text` transcript.
pub(crate) const SPEAKER_ROLES: &[&str] = &[
"user",
"assistant",
"system",
"tool",
"human",
"ai",
"bot",
"model",
"function",
"developer",
];
/// Which side of a chat a question asks about, for `"speaker": "auto"`:
/// `assistant` when it names something the assistant said ("what did you
/// recommend", "you told me", "your last answer"), `none` when it only
/// points at an earlier conversation ("our previous chat", "we talked
/// about") and `user` otherwise, since a user's facts live in their own
/// turns. Keying every question on user turns costs the questions about
/// what the assistant said.
pub fn auto_speaker(question: &str) -> &'static str {
static RX: std::sync::OnceLock<[regex::Regex; 2]> = std::sync::OnceLock::new();
let [assistant, shared] = RX.get_or_init(|| {
[
regex::Regex::new(
r"(?i)\byou(?:['’](?:d|ve))?(?:\s+\w+){0,3}?\s+(?:said|told|mentioned|recommended|suggested|gave|provided|listed|shared|wrote|explained|described|came up with|named|offered|showed|taught|helped|created|made|generated|proposed|put together|compiled|included)\b|\bdid\s+you\s+(?:say|tell|mention|recommend|suggest|give|provide|list|share|write|explain|describe|name|offer|show|propose|include)\b|\byour\s+(?:previous|earlier|last)\s+(?:answer|response|reply|suggestion|recommendation|advice|list)\b",
)
.unwrap(),
regex::Regex::new(
r"(?i)\b(?:our|the|that)\s+(?:previous|earlier|last|past)\s+(?:chat|conversation|discussion)s?\b|\bwe\s+(?:talked|discussed|chatted|spoke|went over|covered)\b",
)
.unwrap(),
]
});
if assistant.is_match(question) {
"assistant"
} else if shared.is_match(question) {
"none"
} else {
"user"
}
}
/// The `speaker` option: `true` keys the speaker arm on user turns,
/// `{"keep": [roles]}` on the turns of up to 8 roles and `"auto"` on the
/// side `auto_speaker` reads from the question; absent or `false` adds no
/// arm.
fn speaker_roles(value: &Value, question: &str) -> Result<Option<BTreeSet<String>>> {
match value {
Value::Null | Value::Bool(false) => Ok(None),
Value::Bool(true) => Ok(Some(BTreeSet::from(["user".to_owned()]))),
Value::String(mode) if mode == "auto" => Ok(match auto_speaker(question) {
"none" => None,
side => Some(BTreeSet::from([side.to_owned()])),
}),
Value::Object(object) => {
if object.keys().any(|k| k != "keep") {
return Err("speaker accepts only keep".into());
}
let keep = object
.get("keep")
.and_then(Value::as_array)
.filter(|roles| (1..=8).contains(&roles.len()))
.ok_or("speaker.keep must list 1 to 8 roles")?;
let mut roles = BTreeSet::new();
for role in keep {
let role = role
.as_str()
.map(|r| r.trim().to_lowercase())
.filter(|r| !r.is_empty() && r.len() <= 40 && !r.contains([':', '\n', '\r']))
.ok_or("speaker roles must be short labels without colons")?;
roles.insert(role);
}
Ok(Some(roles))
}
_ => Err("speaker must be a boolean, \"auto\" or {\"keep\": [roles]}".into()),
}
}
/// The words of the turns spoken by `keep` in a `role: text` transcript.
/// LongMemEval's reference retrievers (xiaowu0162/LongMemEval@9e0b455f:
/// `process_item_flat_index` in `src/retrieval/run_retrieval.py`; MIT) key
/// sessions and turns on the user's side only; long assistant replies dilute
/// the user's own facts. A turn runs from its `label:` line to the next one,
/// where a label is a kept role, a standard chat role or, when a kept role
/// is a person's name, any name of up to three capitalized words. Text before
/// the first turn is not attributed.
pub fn speaker_text(text: &str, keep: &BTreeSet<String>) -> String {
let named = keep.iter().any(|r| !SPEAKER_ROLES.contains(&r.as_str()));
let is_name = |label: &str| {
let words: Vec<&str> = label.split_whitespace().collect();
(1..=3).contains(&words.len())
&& words.iter().all(|w| {
w.chars().next().is_some_and(char::is_uppercase)
&& w.chars().all(|c| c.is_alphabetic() || "'.-".contains(c))
})
};
let mut spoken = String::new();
let mut keeping = false;
for line in text.lines() {
let mut content = line;
if let Some((raw, rest)) = line.split_once(':') {
let label = raw.trim().to_lowercase();
if keep.contains(&label)
|| SPEAKER_ROLES.contains(&label.as_str())
|| (named && is_name(raw.trim()))
{
keeping = keep.contains(&label);
content = rest;
}
}
if keeping {
spoken.push_str(content);
spoken.push('\n');
}
}
spoken
}
/// Most caller `abstractions` per row, and bytes in each (read by
/// `key_expansion: "merge"`).
const MAX_ABSTRACTIONS: usize = 32;
const MAX_ABSTRACTION_BYTES: usize = 1000;
/// A row's caller `abstractions`, blank ones skipped: at most 32 strings of
/// at most 1,000 bytes each.
fn abstractions(row: &Value) -> Result<Vec<&str>> {
let Some(value) = row.get("abstractions").filter(|v| !v.is_null()) else {
return Ok(Vec::new());
};
let items = value
.as_array()
.filter(|items| items.len() <= MAX_ABSTRACTIONS)
.ok_or("abstractions must be an array of at most 32 strings")?;
let mut given = Vec::with_capacity(items.len());
for item in items {
let unit = item
.as_str()
.filter(|unit| unit.len() <= MAX_ABSTRACTION_BYTES)
.ok_or("Each abstraction must be a string of at most 1000 bytes")?;
if !unit.trim().is_empty() {
given.push(unit);
}
}
Ok(given)
}
pub fn rrf(rankings: &[Vec<String>], constant: f64, min_score: f64) -> Result<Vec<(String, f64)>> {
rrf_weighted(rankings, &vec![1.0; rankings.len()], constant, min_score)
}
/// RRF with a weight per ranking: Σ_r w_r / (k + rank_r) (Memora, memind).
/// A zero weight disables an arm, including its candidate membership.
pub fn rrf_weighted(
rankings: &[Vec<String>],
weights: &[f64],
constant: f64,
min_score: f64,
) -> Result<Vec<(String, f64)>> {
if !constant.is_finite()
|| constant <= 0.0
|| !min_score.is_finite()
|| weights.len() != rankings.len()
|| weights.iter().any(|w| !w.is_finite() || *w < 0.0)
{
return Err("Invalid RRF parameters".into());
}
let mut scores = std::collections::HashMap::<&str, f64>::new();
for (ranking, weight) in rankings.iter().zip(weights) {
if *weight == 0.0 {
continue;
}
for (i, id) in ranking.iter().enumerate() {
*scores.entry(id.as_str()).or_default() += weight / (i as f64 + constant);
}
}
let mut result: Vec<_> = scores
.into_iter()
.filter(|(_, v)| *v >= min_score)
.map(|(id, score)| (id.to_owned(), score))
.collect();
result.sort_by(|a, b| b.1.total_cmp(&a.1).then(a.0.cmp(&b.0)));
Ok(result)
}
/// Most `query_variants` one [`rank`] call accepts.
pub const MAX_QUERY_VARIANTS: usize = 8;
/// Longest query variant text, in bytes.
pub const MAX_QUERY_VARIANT_BYTES: usize = 4000;
/// Variant kinds: `query` (a rephrased question), `keyword` (a short keyword
/// query) and `passage` (a hypothetical answer passage, HyDE / query2doc).
pub const QUERY_VARIANT_KINDS: [&str; 3] = ["query", "keyword", "passage"];
/// One caller query variant, fused by [`rank`] as one more lexical arm. Onyx
/// multi-query search fuses an LLM rephrase, keyword queries and the original
/// question by weighted RRF; RAG-Fusion does the same with plain rephrasings,
/// and HyDE / query2doc search with a hypothetical answer passage.
#[derive(Clone, Debug, PartialEq)]
pub struct QueryVariant {
pub text: String,
pub weight: f64,
pub kind: &'static str,
}
/// Parses `query_variants`: an array of `{text, weight?, kind?}` (weight 0–4,
/// default 1; kind default `query`). Duplicates of one kind, compared
/// case-insensitively, merge and add their weights (Onyx
/// `deduplicate_queries`), capped at 4.
pub fn query_variants(value: &Value) -> Result<Vec<QueryVariant>> {
let items = match value {
Value::Null => return Ok(Vec::new()),
Value::Array(items) => items,
_ => return Err("query_variants must be an array".into()),
};
if items.len() > MAX_QUERY_VARIANTS {
return Err(format!("At most {MAX_QUERY_VARIANTS} query variants").into());
}
let mut variants: Vec<QueryVariant> = Vec::new();
for item in items {
let fields = item.as_object().ok_or("Query variants must be objects")?;
if fields
.keys()
.any(|key| !["text", "weight", "kind"].contains(&key.as_str()))
{
return Err("Query variant fields are text, weight and kind".into());
}
let text = fields
.get("text")
.and_then(Value::as_str)
.map(str::trim)
.filter(|text| !text.is_empty() && text.len() <= MAX_QUERY_VARIANT_BYTES)
.ok_or("Query variant text must be 1 to 4000 bytes")?;
let weight = match fields.get("weight") {
None | Some(Value::Null) => 1.0,
Some(value) => value
.as_f64()
.filter(|weight| (0.0..=4.0).contains(weight))
.ok_or("Query variant weights must be between 0 and 4")?,
};
let kind = match fields.get("kind") {
None | Some(Value::Null) => "query",
Some(value) => value
.as_str()
.and_then(|kind| QUERY_VARIANT_KINDS.into_iter().find(|k| *k == kind))
.ok_or("Query variant kind must be query, keyword or passage")?,
};
let folded = text.to_lowercase();
if let Some(seen) = variants
.iter_mut()
.find(|seen| seen.kind == kind && seen.text.to_lowercase() == folded)
{
seen.weight = (seen.weight + weight).min(4.0);
} else {
variants.push(QueryVariant {
text: text.to_owned(),
weight,
kind,
});
}
}
Ok(variants)
}
/// BM25 (k1 1.2, b 0.75, Lucene idf) of every row for `bag`, best first, ties
/// by identity; rows sharing no term are left out.
fn bm25_rank(
rows: &[Value],
features: &[std::sync::Arc<cache::Features>],
bag: &BTreeSet<String>,
average: f64,
) -> Vec<(String, f64)> {
let n = features.len() as f64;
let weights: Vec<(&String, f64)> = bag
.iter()
.map(|term| {
let df = features
.iter()
.filter(|f| f.words.contains_key(term))
.count() as f64;
(term, (1.0 + (n - df + 0.5) / (df + 0.5)).ln())
})
.collect();
let mut ranked: Vec<(String, f64)> = features
.iter()
.enumerate()
.filter_map(|(i, feature)| {
let mut score = 0.0;
for &(term, idf) in &weights {
let tf = feature.words.get(term) as f64;
if tf > 0.0 {
score += idf * tf * 2.2
/ (tf + 1.2 * (0.25 + 0.75 * feature.length as f64 / average));
}
}
(score > 0.0).then(|| (rows[i]["identity"].as_str().unwrap_or("").to_owned(), score))
})
.collect();
ranked.sort_by(|a, b| b.1.total_cmp(&a.1).then(a.0.cmp(&b.0)));
ranked
}
/// The words `rank` scores a question by: [`text::words`] without its stop
/// words, each once.
pub fn terms(value: &str) -> BTreeSet<String> {
const STOP: &[&str] = &[
"a", "an", "the", "to", "of", "in", "is", "are", "how", "what", "we", "do", "does", "can",
"for", "and", "with", "this", "that", "should",
];
text::words(value)
.into_iter()
.filter(|x| !STOP.contains(&x.as_str()))
.collect()
}
pub fn unresolved_needs(needs: &[String], documents: &[String]) -> Vec<String> {
let available: BTreeSet<_> = documents.iter().flat_map(|x| terms(x)).collect();
needs
.iter()
.filter(|need| {
let required = terms(need);
required.is_empty() || required.intersection(&available).count() * 2 < required.len()
})
.cloned()
.collect()
}
pub fn rank(request: &Value) -> Result<Value> {
// An unsupported option is refused, or at an inert value ignored, first.
crate::archived::check(request)?;
let rows = request
.get("rows")
.and_then(Value::as_array)
.ok_or("Expected source rows")?;
let question = crate::string(request, "question")?;
let scope = crate::string(request, "scope")?;
let limit = request.get("limit").and_then(Value::as_u64).unwrap_or(6) as usize;
if rows.len() > MAX_ROWS
|| scope.len() > 500
|| question.len() > 16000
|| !(1..=MAX_RANK_LIMIT).contains(&limit)
{
return Err("Retrieval limits exceeded".into());
}
let mut q = terms(question);
if let Some(needs) = request.get("needs").and_then(Value::as_array) {
if needs.len() > 20 {
return Err("At most 20 evidence needs".into());
}
for need in needs {
q.extend(terms(
need.as_str().ok_or("Evidence needs must be strings")?,
));
}
}
let mut ids = BTreeMap::new();
let requested_mode = request
.get("mode")
.and_then(Value::as_str)
.unwrap_or("auto");
let mode = match requested_mode {
"auto"
if q.iter()
.any(|t| ["procedure", "steps", "repeat", "lesson"].contains(&t.as_str())) =>
{
"procedures"
}
"auto"
if q.iter().any(|t| {
["import", "calls", "impact", "relationship", "dependencies"].contains(&t.as_str())
}) =>
{
"relationships"
}
"auto" => "balanced",
"balanced" | "procedures" | "relationships" => requested_mode,
_ => return Err("Unsupported memory query mode".into()),
};
// Opt-in Porter stemming of query and candidate words (Lucene/Anserini
// English BM25; Mem0's lemmatized BM25). Mode detection above keeps the
// surface words.
let stem = match request.get("stem") {
None | Some(Value::Null) => false,
Some(Value::Bool(value)) => *value,
Some(_) => return Err("stem must be a boolean".into()),
};
let mut stemmer = crate::stem::Stemmer::default();
if stem {
q = q.iter().map(|t| stemmer.stem(t)).collect();
}
let speaker_option = request.get("speaker").unwrap_or(&Value::Null);
let auto_side = (speaker_option.as_str() == Some("auto")).then(|| auto_speaker(question));
let speaker = speaker_roles(speaker_option, question)?;
// Opt-in `key_expansion: "merge"`: LongMemEval's key expansion
// (xiaowu0162/LongMemEval@9e0b455f: `resolve_expansion`, join mode
// `merge`, in `src/retrieval/index_expansion_utils.py`; MIT). A row's
// lexical key is its `abstractions`, then its title and text (K = V +
// fact), so a fact extracted from a passage also finds the passage. Its
// evidence is still the text alone.
let merge_keys = match request.get("key_expansion") {
None | Some(Value::Null) | Some(Value::Bool(false)) => false,
Some(Value::String(mode)) if mode == "merge" => true,
Some(_) => return Err("key_expansion must be \"merge\" or false".into()),
};
let mut keyed_rows = 0;
let mut contents = Vec::with_capacity(rows.len());
for (i, row) in rows.iter().enumerate() {
let id = crate::string(row, "identity")?;
if ids.insert(id.to_owned(), i).is_some() {
return Err("Candidate identities must be unique".into());
}
let title = crate::string(row, "title")?;
let body = crate::string(row, "text")?;
let mut content = String::new();
if merge_keys {
let keys = abstractions(row)?;
keyed_rows += usize::from(!keys.is_empty());
for key in keys {
content.push_str(key);
content.push(' ');
}
}
content.push_str(title);
content.push(' ');
content.push_str(body);
contents.push(content);
}
// Features depend only on the text, so the rows' are computed side by
// side (a command-line process starts with an empty cache) and kept in
// row order.
let features = cache::par_map(
&contents,
crate::stem::Stemmer::default,
|stemmer, content| {
if stem {
cache::stemmed_features(scope, content, stemmer)
} else {
cache::features(scope, content)
}
},
)
.into_iter()
.collect::<Result<Vec<_>>>()?;
drop(contents);
let average = (features.iter().map(|x| x.length).sum::<usize>() as f64
/ (rows.len().max(1) as f64))
.max(1.0);
let question_lowercase = question.to_lowercase();
// A caller that holds a passage index gives the lexical order of its
// whole catalogue (`lexical_ranked`: [identity, score] pairs, best
// first, at least its first 200), scored as below over every passage,
// and sends only the rows it ranks; otherwise the rows are scored here.
let lexical: Vec<(String, f64)> = match request.get("lexical_ranked") {
Some(given) if !given.is_null() => {
let list = given
.as_array()
.ok_or("lexical_ranked must list [identity, score] pairs")?;
let mut lexical = Vec::with_capacity(list.len());
for pair in list {
let (Some(id), Some(score)) = (
pair.get(0).and_then(Value::as_str),
pair.get(1).and_then(Value::as_f64),
) else {
return Err("lexical_ranked must list [identity, score] pairs".into());
};
if !ids.contains_key(id) || !score.is_finite() || score <= 0.0 {
return Err("lexical_ranked names a row that was not sent".into());
}
lexical.push((id.to_owned(), score));
}
lexical
}
_ => {
let term_weights: Vec<_> = q
.iter()
.map(|t| {
let frequency =
features.iter().filter(|x| x.words.contains_key(t)).count() as f64;
let idf =
(1.0 + (rows.len() as f64 - frequency + 0.5) / (frequency + 0.5)).ln();
(t, idf)
})
.collect();
let mut lexical = Vec::new();
for (i, row) in rows.iter().enumerate() {
let feature = &features[i];
let mut score = 0.0;
for &(term, idf) in &term_weights {
let tf = feature.words.get(term) as f64;
if tf > 0.0 {
score += idf * tf * 2.2
/ (tf + 1.2 * (0.25 + 0.75 * feature.length as f64 / average));
}
}
let title = row["title"].as_str().unwrap_or("").to_lowercase();
if !title.is_empty() && question_lowercase.contains(&title) {
score += 5.0;
}
if score > 0.0 {
lexical.push((row["identity"].as_str().unwrap().to_owned(), score));
}
}
lexical.sort_by(|a, b| b.1.total_cmp(&a.1).then(a.0.cmp(&b.0)));
lexical
}
};
let mut rankings = vec![
lexical
.iter()
.take(200)
.map(|(id, _)| id.clone())
.collect::<Vec<_>>(),
];
let mut names = vec!["lexical".to_owned()];
// Opt-in `speaker`: BM25 over the kept speakers' turns only, fused as one
// more arm beside the whole-passage ranking.
let mut speaker_report = auto_side.map_or(json!(null), |side| json!({"auto": side}));
// The speaker arm of a caller's passage index (`speaker_ranked`: the
// roles it kept, the ranking and its `rows` and `ranked` counts over the
// whole catalogue), used when it kept the roles chosen here.
let given_speaker = match request.get("speaker_ranked") {
Some(given) if !given.is_null() => Some(given_speaker(given, &ids)?),
_ => None,
};
if let Some(keep) = &speaker
&& let Some(given) = given_speaker.as_ref().filter(|given| &given.keep == keep)
{
let ranking = &given.ranking;
speaker_report = json!({"keep":keep,"rows":given.rows,"ranked":given.ranked});
if let Some(side) = auto_side {
speaker_report["auto"] = json!(side);
}
if !ranking.is_empty() {
rankings.push(ranking.iter().take(200).cloned().collect());
names.push("speaker".to_owned());
}
} else if let Some(keep) = &speaker {
let mut bags = Vec::new();
let spoken = cache::par_map(rows, crate::stem::Stemmer::default, |stemmer, row| {
let spoken = speaker_text(row["text"].as_str().unwrap_or(""), keep);
if stem {
cache::stemmed_features(scope, &spoken, stemmer)
} else {
cache::features(scope, &spoken)
}
});
for (i, feature) in spoken.into_iter().enumerate() {
let feature = feature?;
if feature.length > 0 {
bags.push((i, feature));
}
}
let n = bags.len() as f64;
let average =
(bags.iter().map(|(_, f)| f.length).sum::<usize>() as f64 / n.max(1.0)).max(1.0);
let idf: Vec<(&String, f64)> = q
.iter()
.map(|t| {
let df = bags.iter().filter(|(_, f)| f.words.contains_key(t)).count() as f64;
(t, (1.0 + (n - df + 0.5) / (df + 0.5)).ln())
})
.collect();
let mut spoken_rank: Vec<(String, f64)> = bags
.iter()
.filter_map(|(i, feature)| {
let score: f64 = idf
.iter()
.map(|&(term, idf)| {
let tf = feature.words.get(term) as f64;
idf * tf * 2.2
/ (tf + 1.2 * (0.25 + 0.75 * feature.length as f64 / average))
})
.sum();
(score > 0.0).then(|| (rows[*i]["identity"].as_str().unwrap().to_owned(), score))
})
.collect();
spoken_rank.sort_by(|a, b| b.1.total_cmp(&a.1).then(a.0.cmp(&b.0)));
speaker_report = json!({"keep":keep,"rows":bags.len(),"ranked":spoken_rank.len()});
if let Some(side) = auto_side {
speaker_report["auto"] = json!(side);
}
if !spoken_rank.is_empty() {
rankings.push(
spoken_rank
.into_iter()
.take(200)
.map(|(id, _)| id)
.collect(),
);
names.push("speaker".to_owned());
}
}
// Opt-in `query_variants`: each variant ranks the same candidates by BM25
// (stemmed like the question) and fuses as arm `lexical_q1`, `lexical_q2`,
// … weighted by its `weight` unless `arm_weights` names that arm.
let variants = query_variants(request.get("query_variants").unwrap_or(&Value::Null))?;
let mut variant_report = Vec::new();
let mut variant_weights = Vec::new();
for (i, variant) in variants.iter().enumerate() {
let mut bag = terms(&variant.text);
if stem {
bag = bag.iter().map(|t| stemmer.stem(t)).collect();
}
let ranked = bm25_rank(rows, &features, &bag, average);
let arm = format!("lexical_q{}", i + 1);
variant_report.push(
json!({"arm":arm,"kind":variant.kind,"weight":variant.weight,
"terms":bag.len(),"ranked":ranked.len()}),
);
if !ranked.is_empty() {
rankings.push(ranked.into_iter().take(200).map(|(id, _)| id).collect());
names.push(arm.clone());
variant_weights.push((arm, variant.weight));
}
}
if let Some(external) = request.get("rankings").and_then(Value::as_object) {
for (name, ranking) in external {
let items = ranking.as_array().ok_or("Ranking must be an array")?;
let mut seen = BTreeSet::new();
let mut list = Vec::new();
for id in items.iter().take(200).filter_map(Value::as_str) {
if ids.contains_key(id) && seen.insert(id) {
list.push(id.to_owned());
}
}
rankings.push(list);
names.push(name.clone());
}
}
// Arm weights and the RRF constant are opt-in; unset, every arm counts 1
// and k is 61, as before.
let rrf_k = request.get("rrf_k").and_then(Value::as_f64).unwrap_or(61.0);
if !(1.0..=1000.0).contains(&rrf_k) {
return Err("rrf_k must be between 1 and 1000".into());
}
let mut arm_weights = match request.get("arm_weights") {
None | Some(Value::Null) => serde_json::Map::new(),
Some(Value::Object(map)) => map.clone(),
Some(_) => return Err("arm_weights must map arm names to weights".into()),
};
for (arm, weight) in variant_weights {
arm_weights.entry(arm).or_insert(json!(weight));
}
// A caller's dense ranking for variant i (`rankings.semantic_q{i}`) counts
// the variant's weight times the `semantic` arm's unless named here.
let semantic = arm_weights
.get("semantic")
.and_then(Value::as_f64)
.unwrap_or(1.0);
for (i, variant) in variants.iter().enumerate() {
let arm = format!("semantic_q{}", i + 1);
if names.contains(&arm) {
let weight = (variant.weight * semantic).min(4.0);
arm_weights.entry(arm.clone()).or_insert(json!(weight));
variant_report[i]["dense"] = json!(arm);
}
}
let weight_of = |name: &str| -> Result<f64> {
match arm_weights.get(name) {
None => Ok(1.0),
Some(v) => v
.as_f64()
.filter(|w| (0.0..=4.0).contains(w))
.ok_or_else(|| "Arm weights must be between 0 and 4".into()),
}
};
let weights = names
.iter()
.map(|n| weight_of(n))
.collect::<Result<Vec<_>>>()?;
// Opt-in `origin_prior`: a weight between 0 and 1 per origin (the
// runtime's code-first prior gives a code question's documentation and
// test files less than their source). Every fused score of the origin's
// rows, and every score the relationship lift gives them, is multiplied
// by it before the order is taken, so selection and packing see it.
let priors = origin_priors(request)?;
let prior = |i: usize| -> f64 {
rows[i]
.get("origin")
.and_then(Value::as_str)
.and_then(|origin| priors.get(origin))
.copied()
.unwrap_or(1.0)
};
let mut scores: BTreeMap<String, f64> = rrf_weighted(&rankings, &weights, rrf_k, 0.0)?
.into_iter()
.map(|(id, score)| {
let weight = ids.get(&id).map_or(1.0, |&i| prior(i));
(id, score * weight)
})
.collect();
let mut reasons: BTreeMap<String, Vec<String>> = BTreeMap::new();
for ((name, ranking), weight) in names.iter().zip(&rankings).zip(&weights) {
if *weight == 0.0 {
continue;
}
for id in ranking {
reasons.entry(id.clone()).or_default().push(name.clone());
}
}
let global = request
.get("global_notes")
.and_then(Value::as_array)
.map(Vec::as_slice)
.unwrap_or(&[]);
for id in global.iter().filter_map(Value::as_str) {
if ids.contains_key(id) {
scores.entry(id.to_owned()).or_insert(0.001);
reasons
.entry(id.to_owned())
.or_default()
.push("global_reviewed_decision".into());
}
}
for (id, score) in &mut scores {
let row = &rows[ids[id]];
let kind = row
.get("memory")
.and_then(|x| x.get("kind"))
.and_then(Value::as_str)
.unwrap_or("");
if mode == "procedures" && ["procedure", "lesson"].contains(&kind) {
*score *= 1.3;
reasons
.entry(id.clone())
.or_default()
.push(format!("query_mode:{mode}"));
}
}
let mut base: Vec<_> = scores.iter().map(|(k, v)| (k.clone(), *v)).collect();
base.sort_by(|a, b| b.1.total_cmp(&a.1).then(a.0.cmp(&b.0)));
let received = request
.get("edges")
.and_then(Value::as_array)
.map(Vec::as_slice)
.unwrap_or(&[]);
let mut frontier: BTreeSet<String> = base
.iter()
.take(4)
.filter_map(|(id, _)| {
rows[*ids.get(id)?]
.get("source")?
.get("path")?
.as_str()
.map(str::to_owned)
})
.collect();
let hops = if mode == "relationships" { 2 } else { 1 };
let top = base.first().map(|(_, s)| *s).unwrap_or(0.0);
// A caller that sends only the relationship edges the lift reads asks
// for the files it starts from (`report_frontier`): the paths of the four
// best fused passages, before any edge is read, with what the lift
// scores their neighbours' passages by (the best fused score, `top`, and
// the question's terms), so that it can send only the passages that can
// be among the [`MAX_FUSED`] kept.
let frontier_report = (request.get("report_frontier") == Some(&json!(true)))
.then(|| json!({"paths":frontier,"hops":hops,"top":top,"terms":q}));
let (bounded, static_edges) = bound_static_edges(received, &frontier, hops);
let edges: &[Value] = bounded.as_deref().unwrap_or(received);
let mut visited = frontier.clone();
for hop in 1..=hops {
let mut next = BTreeSet::new();
for edge in edges {
let a = edge.get("source").and_then(Value::as_str).unwrap_or("");
let b = edge.get("target").and_then(Value::as_str).unwrap_or("");
if frontier.contains(a) && !visited.contains(b) {
next.insert(b.to_owned());
}
if frontier.contains(b) && !visited.contains(a) {
next.insert(a.to_owned());
}
}
for (i, row) in rows.iter().enumerate() {
let path = row
.get("source")
.and_then(|x| x.get("path"))
.and_then(Value::as_str)
.unwrap_or("");
if next.contains(path) {
let id = row["identity"].as_str().unwrap();
// Prefer a passage with query evidence within the related file.
let overlap = q
.iter()
.filter(|t| features[i].words.contains_key(t))
.count() as f64
/ q.len().max(1) as f64;
let score = top * (0.45 + 0.15 * overlap) / (hop as f64) * prior(i);
let entry = scores.entry(id.to_owned()).or_default();
*entry = entry.max(score);
reasons
.entry(id.to_owned())
.or_default()
.push(format!("static_relationship:{hop}"));
}
}
visited.extend(next.iter().cloned());
frontier = next;
}
let mut remaining: Vec<_> = scores.into_iter().collect();
remaining.sort_by(|a, b| b.1.total_cmp(&a.1).then(a.0.cmp(&b.0)));
let fused_cap = request
.get("fused_cap")
.and_then(Value::as_u64)
.map_or(MAX_FUSED, |cap| {
(cap as usize).clamp(MAX_FUSED, MAX_FUSED_CAP)
});
remaining.truncate(fused_cap);
// Diagnostics: the fused order before selection (for recall harnesses).
let debug_fused = request
.get("debug_fused")
.and_then(Value::as_u64)
.unwrap_or(0)
.min(fused_cap as u64) as usize;
let fused: Vec<String> = remaining
.iter()
.filter(|(id, _)| rows[ids[id]]["kind"] != "memory")
.take(debug_fused)
.map(|(id, _)| id.clone())
.collect();
// Evidence strength (Tiermem's router features, memind's strong signal):
// weak when the best passages cover little of the question, or the best
// lexical score is low and barely above the next.
let squash = |x: f64| x / (1.0 + x);
let s1 = lexical.first().map_or(0.0, |x| squash(x.1));
let s2 = lexical.get(1).map_or(0.0, |x| squash(x.1));
let top3: Vec<usize> = remaining
.iter()
.map(|(id, _)| ids[id])
.filter(|&i| rows[i]["kind"] != "memory")
.take(3)
.collect();
let question_coverage = if q.is_empty() {
1.0
} else {
q.iter()
.filter(|t| top3.iter().any(|&i| features[i].words.contains_key(t)))
.count() as f64
/ q.len() as f64
};
let weak = question_coverage < 0.5 || (s1 < 0.85 && s1 - s2 < 0.15);
let aggregate = aggregate_question(&question_lowercase);
// Per-origin quotas (LightRAG's linear gradient): the origin with the best
// candidate may give `max` sources, later ones down to `min`; leftover
// slots go one at a time to the earliest origins. Unset: 2 per origin.
let quota = match request.get("origin_quota") {
None | Some(Value::Null) => None,
Some(v) => {
let bound = |key: &str, default: u64| {
v.get(key)
.and_then(Value::as_u64)
.unwrap_or(default)
.clamp(1, 10) as usize
};
let (max, min) = (bound("max", 3), bound("min", 1));
Some((max.max(min), min.min(max)))
}
};
let mut origin_order: BTreeMap<String, usize> = BTreeMap::new();
for (id, _) in &remaining {
let row = &rows[ids[id]];
if row["kind"] != "memory" {
let origin = row["origin"].as_str().unwrap_or("").to_owned();
let next = origin_order.len();
origin_order.entry(origin).or_insert(next);
}
}
let origin_count = origin_order.len();
let cap_of = |origin: &str| -> usize {
match quota {
None => 2,
Some((max, min)) => {
let i = origin_order.get(origin).copied().unwrap_or(origin_count);
if origin_count <= 1 {
max
} else {
let span = (max - min) as f64 * i.min(origin_count - 1) as f64
/ (origin_count - 1) as f64;
((max as f64 - span).round() as usize).clamp(min, max)
}
}
}
};
let maximum = remaining.first().map(|x| x.1).unwrap_or(1.0).max(1e-12);
let needs: Vec<String> = request
.get("needs")
.and_then(Value::as_array)
.map(|x| {
x.iter()
.filter_map(Value::as_str)
.take(20)
.map(str::to_owned)
.collect()
})
.unwrap_or_default();
let need_terms: Vec<BTreeSet<String>> = needs
.iter()
.map(|x| {
let set = terms(x);
if stem {
set.iter().map(|t| stemmer.stem(t)).collect()
} else {
set
}
})
.collect();
let mut covered = BTreeSet::new();
let mut covered_terms = BTreeSet::new();
let mut selected: Vec<usize> = Vec::new();
// Each candidate/selected pair is invariant during this request. Advance
// its maximum only across newly selected rows, preserving score and tie
// order without recomputing all earlier pairs on every selection.
let mut redundancy = vec![(0usize, 0.0_f64); rows.len()];
let mut sources = Vec::new();
let mut memories = Vec::new();
let mut origins: BTreeMap<String, usize> = BTreeMap::new();
let mut content_seen = BTreeSet::new();
while !remaining.is_empty() {
let mut best = None;
for (position, (id, score)) in remaining.iter().enumerate() {
let i = ids[id];
let row = &rows[i];
let memory = row["kind"] == "memory";
let origin = crate::string(row, "origin")?;
if (memory && memories.len() >= 12)
|| (!memory
&& (sources.len() >= limit
|| *origins.get(origin).unwrap_or(&0) >= cap_of(origin)))
{
continue;
}
let novelty = q
.iter()
.filter(|t| features[i].words.contains_key(t) && !covered_terms.contains(*t))
.count() as f64
/ q.len().max(1) as f64;
let new_needs = need_terms
.iter()
.enumerate()
.filter(|(n, t)| {
!covered.contains(n)
&& !t.is_empty()
&& t.iter()
.filter(|x| features[i].words.contains_key(x))
.count()
* 2
>= t.len()
})
.count() as f64;
let (compared, maximum_similarity) = &mut redundancy[i];
let new_maximum = selected[*compared..]
.iter()
.map(|j| {
let a = &features[i].words;
let b = &features[*j].words;
let common = a.common(b) as f64;
common / (a.len() + b.len()).max(1) as f64 * 2.0
})
.fold(*maximum_similarity, f64::max);
*compared = selected.len();
*maximum_similarity = new_maximum;
let utility = score / maximum + 0.2 * novelty + 0.15 * new_needs - 0.2 * new_maximum;
if best
.as_ref()
.is_none_or(|(_, u): &(usize, f64)| utility > *u)
{
best = Some((position, utility));
}
}
let best = best.map(|(position, _)| position).or_else(|| {
// Leftover polling: with quotas, unfilled source slots go to the
// remaining candidate of the earliest origin.
if quota.is_none() || sources.len() >= limit {
return None;
}
remaining
.iter()
.enumerate()
.filter(|(_, (id, _))| rows[ids[id]]["kind"] != "memory")
.min_by_key(|(position, (id, _))| {
let origin = rows[ids[id]]["origin"].as_str().unwrap_or("");
(
origin_order.get(origin).copied().unwrap_or(usize::MAX),
*position,
)
})
.map(|(position, _)| position)
});
let Some(position) = best else {
break;
};
let (id, _) = remaining.remove(position);
let i = ids[&id];
let row = &rows[i];
let body = crate::string(row, "text")?;
let content_hash = text::sha256(body.as_bytes());
if !content_seen.insert(content_hash) {
continue;
}
for (n, t) in need_terms.iter().enumerate() {
if !t.is_empty()
&& t.iter()
.filter(|x| features[i].words.contains_key(x))
.count()
* 2
>= t.len()
{
covered.insert(n);
}
}
covered_terms.extend(
q.iter()
.filter(|t| features[i].words.contains_key(t))
.cloned(),
);
if row["kind"] == "memory" {
memories.push(id);
} else {
*origins
.entry(row["origin"].as_str().unwrap_or("").to_owned())
.or_default() += 1;
sources.push(id);
}
selected.push(i);
}
let unresolved: Vec<_> = needs
.iter()
.enumerate()
.filter(|(i, _)| !covered.contains(i))
.map(|(_, x)| x)
.collect();
let mut output = json!({"sources":sources,"memories":memories,"reasons":reasons,"unresolved_needs":unresolved,"mode":mode,
"relationship_hops":hops,"decisions":selected.len(),
"need_assessment":"lexical candidate coverage, not semantic sufficiency","complete_evidence_guaranteed":false,
"strategy":"hybrid_rrf_graph_sequential_diversity","network_requests":0,"cache":cache::stats()?,
"evidence_strength":{"s1":s1,"s2":s2,"question_coverage":question_coverage,"weak":weak,"aggregate":aggregate,
"limit":limit}});
if debug_fused > 0 {
output["fused"] = json!(fused);
}
if quota.is_some() {
output["origin_quota"] = json!({"origins":origin_count});
}
if !priors.is_empty() {
output["origin_prior"] = json!({"origins":priors.len()});
}
if stem {
output["stemmer"] = json!("porter");
}
if merge_keys {
output["key_expansion"] = json!({"mode":"merge","rows":keyed_rows});
}
if !speaker_report.is_null() {
output["speaker"] = speaker_report;
}
if !variant_report.is_empty() {
output["query_variants"] = json!(variant_report);
}
if !static_edges.is_null() {
output["static_edges"] = static_edges;
}
if let Some(frontier) = frontier_report {
output["frontier"] = frontier;
}
// Diagnostics for comparing two callers' inputs (`debug_rankings`): each
// fused ranking, by arm.
if request.get("debug_rankings") == Some(&json!(true)) {
output["rankings_debug"] = json!(
names
.iter()
.zip(&rankings)
.map(|(name, list)| (name.clone(), json!(list)))
.collect::<serde_json::Map<_, _>>()
);
}
Ok(output)
}
/// A caller's speaker arm (`speaker_ranked`, see [`rank`]).
struct GivenSpeaker {
keep: BTreeSet<String>,
ranking: Vec<String>,
rows: u64,
ranked: u64,
}
fn given_speaker(given: &Value, ids: &BTreeMap<String, usize>) -> Result<GivenSpeaker> {
const REFUSED: &str = "speaker_ranked must give keep, ranking, rows and ranked";
let mut keep = BTreeSet::new();
for role in given.get("keep").and_then(Value::as_array).ok_or(REFUSED)? {
keep.insert(role.as_str().ok_or(REFUSED)?.to_owned());
}
let mut ranking = Vec::new();
for id in given
.get("ranking")
.and_then(Value::as_array)
.ok_or(REFUSED)?
{
match id.as_str() {
Some(id) if ids.contains_key(id) => ranking.push(id.to_owned()),
_ => return Err("speaker_ranked names a row that was not sent".into()),
}
}
let count = |key: &str| given.get(key).and_then(Value::as_u64).ok_or(REFUSED);
Ok(GivenSpeaker {
keep,
ranking,
rows: count("rows")?,
ranked: count("ranked")?,
})
}
/// The request's `origin_prior`: origin → weight, each between 0 and 1;
/// absent or `null`, none. At most [`MAX_ROWS`] origins.
fn origin_priors(request: &Value) -> Result<BTreeMap<String, f64>> {
let Some(value) = request.get("origin_prior").filter(|v| !v.is_null()) else {
return Ok(BTreeMap::new());
};
let refused = || "origin_prior must map origins to weights between 0 and 1".into();
let entries = value
.as_object()
.filter(|entries| entries.len() <= MAX_ROWS)
.ok_or_else(refused)?;
entries
.iter()
.map(|(origin, weight)| {
weight
.as_f64()
.filter(|w| (0.0..=1.0).contains(w))
.map(|w| (origin.clone(), w))
.ok_or_else(refused)
})
.collect()
}
/// Most static relationship edges [`rank`] reads.
pub const MAX_STATIC_EDGES: usize = 50_000;
/// Within [`MAX_STATIC_EDGES`], the edges as given (`None`) and no report.
/// Past it they are folded to one per (source file, target
/// file, kind), which leaves the relationship lift unchanged because it reads
/// file pairs only. If the distinct pairs alone still exceed the bound, the
/// pairs the lift reads are kept first: those touching `frontier` (the files
/// of the top-ranked passages) and, with `hops` above 1, the files the lift
/// reaches before its last hop. The rest fill the bound in input order. The
/// report says what happened: `aggregated`, `capped`, and `lift_complete`
/// (every pair the lift reads was kept, so it lifts exactly what the whole
/// list would). Past the bound `rank` used to fail the request.
pub fn bound_static_edges(
edges: &[Value],
frontier: &BTreeSet<String>,
hops: usize,
) -> (Option<Vec<Value>>, Value) {
if edges.len() <= MAX_STATIC_EDGES {
return (None, Value::Null);
}
fn field<'a>(edge: &'a Value, key: &str) -> &'a str {
edge.get(key).and_then(Value::as_str).unwrap_or("")
}
let mut seen = BTreeSet::new();
let mut folded: Vec<(&str, &str, &str)> = Vec::new();
for edge in edges {
let key = (
field(edge, "source"),
field(edge, "target"),
field(edge, "kind"),
);
if seen.insert(key) {
folded.push(key);
}
}
let distinct = folded.len();
let mut lift_complete = true;
if distinct > MAX_STATIC_EDGES {
// The files whose pairs the lift reads: the frontier, then the files
// each hop but the last newly reaches.
let mut near: BTreeSet<&str> = frontier.iter().map(String::as_str).collect();
let mut current = near.clone();
for _ in 1..hops {
let mut next = BTreeSet::new();
for (a, b, _) in &folded {
if current.contains(a) && !near.contains(b) {
next.insert(*b);
}
if current.contains(b) && !near.contains(a) {
next.insert(*a);
}
}
near.extend(next.iter().copied());
current = next;
}
let (mut kept, rest): (Vec<_>, Vec<_>) = folded
.into_iter()
.partition(|(a, b, _)| near.contains(a) || near.contains(b));
lift_complete = kept.len() <= MAX_STATIC_EDGES;
kept.extend(rest);
kept.truncate(MAX_STATIC_EDGES);
folded = kept;
}
let used: Vec<Value> = folded
.iter()
.map(|(source, target, kind)| json!({"source":source,"target":target,"kind":kind}))
.collect();
let report = json!({"received":edges.len(),"distinct":distinct,"used":used.len(),
"bound":MAX_STATIC_EDGES,"aggregated":true,"capped":distinct > MAX_STATIC_EDGES,
"lift_complete":lift_complete});
(Some(used), report)
}