car-memgine 0.48.0

//! Cost-aware knowledge cascade — U-Mem's *Evolve* escalation (arXiv 2602.22406).
//!
//! Applies *Towards Autonomous Memory Agents* to CAR — see
//! `docs/proposals/autonomous-memory-agents.md`. U-Mem's Evolve step acquires &
//! validates new knowledge by **escalating cost-aware**: try the cheap signal
//! first (the model's own reflection / a teacher), only escalate to
//! tool-verified research when that's not confident enough, and only escalate to
//! a human/expert (HITL) as a last resort — never paying for a costlier tier
//! than the confidence target requires, and never exceeding a cost budget.
//!
//! This module is the **pure decision core** for that cascade: given the current
//! confidence in a piece of knowledge and a [`CascadePolicy`] (the ordered tiers,
//! each with a relative cost and the confidence it can deliver, plus a target and
//! a budget), [`decide_cascade`] returns which tier to run — or that the answer
//! is already confident enough, or that the budget is exhausted before any tier
//! reaches the target.
//!
//! It is deterministic and side-effect-free: it does **not** run reflection, call
//! tools, or ask a human. The caller maps the chosen [`CascadeTier`] onto CAR's
//! existing machinery — `reflect()` for self, tool execution for tool-verified,
//! and the durable HITL `ApprovalLedger` (`car-policy`) for the expert tier.
//! That keeps the policy testable in isolation, exactly like
//! [`crate::utility`]'s ranking core.

use serde::{Deserialize, Serialize};

/// The escalation tiers, cheapest first. The names mirror U-Mem's cascade:
/// self/teacher → tool-verified → expert/HITL.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, Serialize, Deserialize)]
#[serde(rename_all = "snake_case")]
pub enum CascadeTier {
    /// Cheapest: the model's own reflection / a teacher signal (`reflect()`).
    SelfReflect,
    /// Medium: tool-verified research (tool execution).
    ToolVerify,
    /// Costliest, last resort: human/expert feedback via the HITL approval ledger.
    HumanExpert,
}

/// One tier the cascade may escalate to: which [`CascadeTier`] it is, its
/// relative `cost`, and the `expected_confidence` in `[0,1]` it can deliver.
#[derive(Debug, Clone, Copy, PartialEq, Serialize, Deserialize)]
pub struct TierSpec {
    pub tier: CascadeTier,
    /// Relative cost to run this tier (any positive unit — tokens, latency, $).
    pub cost: f64,
    /// Confidence in `[0,1]` this tier is expected to deliver if run.
    pub expected_confidence: f64,
}

/// The cascade policy: the ordered tiers (cheapest → costliest), the
/// `confidence_target` at or above which escalation stops, and the total cost
/// `budget` across all tiers tried.
#[derive(Debug, Clone, Serialize, Deserialize)]
pub struct CascadePolicy {
    /// Stop escalating once confidence reaches this. Clamped to `[0,1]`.
    pub confidence_target: f64,
    /// Total cost budget across the cascade. A tier is only run if the
    /// *cumulative* cost of trying it (plus everything cheaper already tried)
    /// stays within this.
    pub budget: f64,
    /// Tiers in escalation order, cheapest first. The cascade walks them in the
    /// given order — it does not re-sort, so the caller controls the ordering.
    pub tiers: Vec<TierSpec>,
}

/// The cascade's decision.
#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
#[serde(tag = "decision", rename_all = "snake_case")]
pub enum CascadeOutcome {
    /// Current confidence already meets the target — escalate to nothing, spend
    /// nothing. The autonomous "don't pay to re-learn what you already know".
    AlreadyConfident { confidence: f64 },
    /// A tier reaches the target within budget. `tier` is the one to run;
    /// `confidence` is what it delivers; `cost_spent` is the cumulative cost of
    /// this tier plus every cheaper tier tried before it.
    Accept {
        tier: CascadeTier,
        confidence: f64,
        cost_spent: f64,
    },
    /// No tier reaches the target within budget. `best_tier` is the most
    /// confident tier reachable within budget (or `None` if even the cheapest
    /// tier is unaffordable); `confidence` is the best confidence achieved
    /// (falling back to the starting confidence); `cost_spent` is what reaching
    /// that best tier costs.
    Exhausted {
        best_tier: Option<CascadeTier>,
        confidence: f64,
        cost_spent: f64,
    },
}

/// Decide the cost-aware cascade. Walks `policy.tiers` in order (cheapest first),
/// accumulating cost; the first tier that meets `confidence_target` within
/// `budget` is [`CascadeOutcome::Accept`]. If the starting confidence already
/// meets the target it's [`CascadeOutcome::AlreadyConfident`] (no spend). If the
/// budget runs out — or no tier reaches the target — it's
/// [`CascadeOutcome::Exhausted`] carrying the best tier reachable within budget.
///
/// Pure and deterministic: a given `(current_confidence, policy)` always yields
/// the same outcome.
pub fn decide_cascade(current_confidence: f64, policy: &CascadePolicy) -> CascadeOutcome {
    let target = policy.confidence_target.clamp(0.0, 1.0);
    let start = current_confidence.clamp(0.0, 1.0);

    if start >= target {
        return CascadeOutcome::AlreadyConfident { confidence: start };
    }

    let mut cumulative_cost = 0.0;
    // Best tier reachable within budget so far (highest expected confidence).
    let mut best_tier: Option<CascadeTier> = None;
    let mut best_confidence = start;
    let mut best_cost = 0.0;

    for spec in &policy.tiers {
        let next_cost = cumulative_cost + spec.cost;
        if next_cost > policy.budget {
            // Can't afford this tier (or anything costlier after it) — stop.
            break;
        }
        cumulative_cost = next_cost;
        let conf = spec.expected_confidence.clamp(0.0, 1.0);

        if conf >= target {
            return CascadeOutcome::Accept {
                tier: spec.tier,
                confidence: conf,
                cost_spent: cumulative_cost,
            };
        }

        // Track the most confident affordable tier as the fallback.
        if conf > best_confidence {
            best_confidence = conf;
            best_tier = Some(spec.tier);
            best_cost = cumulative_cost;
        }
    }

    CascadeOutcome::Exhausted {
        best_tier,
        confidence: best_confidence,
        cost_spent: best_cost,
    }
}

/// What running a tier produced: the knowledge it acquired and the confidence it
/// *actually* achieved. The observed confidence is the load-bearing difference
/// from [`decide_cascade`], which only knows each tier's *predicted*
/// `expected_confidence` — the live evolve loop escalates on what a tier really
/// delivered, not on what it was expected to.
#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
pub struct TierResult {
    /// The knowledge the tier acquired/validated (e.g. a reflection, a
    /// tool-verified fact, an expert's answer).
    pub knowledge: String,
    /// The confidence in `[0,1]` actually achieved by running this tier.
    pub confidence: f64,
}

/// One tier that was actually run during [`run_cascade`], in order.
#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
pub struct CascadeStep {
    pub tier: CascadeTier,
    /// Observed confidence after running this tier.
    pub confidence: f64,
    /// Cumulative cost spent through this tier.
    pub cost: f64,
}

/// The result of actually running the cascade.
#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
pub struct CascadeRun {
    /// The tier whose result met the target, if any. `None` means the target was
    /// never reached (or the start was already confident — see `steps` empty).
    pub accepted_tier: Option<CascadeTier>,
    /// The best knowledge acquired (from the highest-confidence run so far), if
    /// any tier ran.
    pub knowledge: Option<String>,
    /// The final/best confidence achieved (falls back to the starting confidence
    /// when no tier ran).
    pub confidence: f64,
    /// Total cost spent across every tier run.
    pub cost_spent: f64,
    /// Each tier actually run, cheapest first.
    pub steps: Vec<CascadeStep>,
}

/// Run U-Mem's *Evolve* cascade for real, escalating on **observed** confidence.
///
/// Unlike [`decide_cascade`] (which picks a tier from *predicted* confidences
/// without running anything), this walks the tiers cheapest-first and actually
/// invokes `run(tier)` for each — stopping as soon as a tier's *observed*
/// confidence meets `policy.confidence_target`, or when the next tier would
/// exceed `policy.budget`. This is the genuine Retrieve-Infer-**Evolve** loop:
/// cheap signal first, escalate only on what was really delivered.
///
/// `run` is injected (kept out of this pure crate, like CWM's `EffectModel`
/// closures) so the orchestration is testable in isolation; the live engine
/// maps each [`CascadeTier`] onto `reflect()` (self), tool execution
/// (tool-verified), and the durable HITL `ApprovalLedger` (`car-policy`) for the
/// expert tier. A `run` that returns `Err` aborts the cascade and propagates the
/// error (the caller decides whether a tier failure is fatal).
///
/// If the starting confidence already meets the target, no tier runs and the
/// returned [`CascadeRun`] has empty `steps`.
///
/// See [`run_cascade_async`] for the async sibling (live tiers); the two share
/// identical escalation/budget logic and must be kept in lockstep.
pub fn run_cascade(
    current_confidence: f64,
    policy: &CascadePolicy,
    mut run: impl FnMut(CascadeTier) -> Result<TierResult, String>,
) -> Result<CascadeRun, String> {
    let target = policy.confidence_target.clamp(0.0, 1.0);
    let start = current_confidence.clamp(0.0, 1.0);

    let mut result = CascadeRun {
        accepted_tier: None,
        knowledge: None,
        confidence: start,
        cost_spent: 0.0,
        steps: Vec::new(),
    };

    if start >= target {
        return Ok(result);
    }

    let mut cumulative_cost = 0.0;
    let mut best_confidence = start;

    for spec in &policy.tiers {
        let next_cost = cumulative_cost + spec.cost;
        if next_cost > policy.budget {
            break; // can't afford this tier — stop escalating
        }
        cumulative_cost = next_cost;

        let outcome = run(spec.tier)?;
        let conf = outcome.confidence.clamp(0.0, 1.0);
        result.steps.push(CascadeStep {
            tier: spec.tier,
            confidence: conf,
            cost: cumulative_cost,
        });
        result.cost_spent = cumulative_cost;

        // Keep the best knowledge seen so far (highest observed confidence).
        if conf >= best_confidence || result.knowledge.is_none() {
            best_confidence = best_confidence.max(conf);
            result.knowledge = Some(outcome.knowledge);
        }
        result.confidence = best_confidence;

        if conf >= target {
            result.accepted_tier = Some(spec.tier);
            result.confidence = conf;
            return Ok(result);
        }
    }

    Ok(result)
}

/// Async sibling of [`run_cascade`] for live call-sites whose tier runners are
/// asynchronous — the real CAR tiers are: `SelfReflect` → `engine.reflect()`
/// (async), `ToolVerify` → tool execution (async), `HumanExpert` → an
/// [`car-policy`] `ApprovalLedger` lookup. Identical escalation/budget logic to
/// [`run_cascade`]; it just `.await`s each `run(tier)` before deciding whether
/// to escalate, so a tier's *observed* confidence drives the loop.
///
/// `run` is `FnMut(CascadeTier) -> Future`. Because the cascade awaits each
/// tier's future fully before invoking the next, the futures never overlap —
/// the daemon's runner clones the engine `Arc` and locks it inside each future
/// rather than holding a borrow across calls.
///
/// Keep the escalation/budget logic identical to the sync [`run_cascade`] — the
/// two are line-for-line equivalent bar the `.await`.
pub async fn run_cascade_async<F, Fut>(
    current_confidence: f64,
    policy: &CascadePolicy,
    mut run: F,
) -> Result<CascadeRun, String>
where
    F: FnMut(CascadeTier) -> Fut,
    Fut: std::future::Future<Output = Result<TierResult, String>>,
{
    let target = policy.confidence_target.clamp(0.0, 1.0);
    let start = current_confidence.clamp(0.0, 1.0);

    let mut result = CascadeRun {
        accepted_tier: None,
        knowledge: None,
        confidence: start,
        cost_spent: 0.0,
        steps: Vec::new(),
    };

    if start >= target {
        return Ok(result);
    }

    let mut cumulative_cost = 0.0;
    let mut best_confidence = start;

    for spec in &policy.tiers {
        let next_cost = cumulative_cost + spec.cost;
        if next_cost > policy.budget {
            break; // can't afford this tier — stop escalating
        }
        cumulative_cost = next_cost;

        let outcome = run(spec.tier).await?;
        let conf = outcome.confidence.clamp(0.0, 1.0);
        result.steps.push(CascadeStep {
            tier: spec.tier,
            confidence: conf,
            cost: cumulative_cost,
        });
        result.cost_spent = cumulative_cost;

        if conf >= best_confidence || result.knowledge.is_none() {
            best_confidence = best_confidence.max(conf);
            result.knowledge = Some(outcome.knowledge);
        }
        result.confidence = best_confidence;

        if conf >= target {
            result.accepted_tier = Some(spec.tier);
            result.confidence = conf;
            return Ok(result);
        }
    }

    Ok(result)
}

#[cfg(test)]
mod tests {
    use super::*;

    fn policy(target: f64, budget: f64) -> CascadePolicy {
        CascadePolicy {
            confidence_target: target,
            budget,
            tiers: vec![
                TierSpec {
                    tier: CascadeTier::SelfReflect,
                    cost: 1.0,
                    expected_confidence: 0.6,
                },
                TierSpec {
                    tier: CascadeTier::ToolVerify,
                    cost: 5.0,
                    expected_confidence: 0.85,
                },
                TierSpec {
                    tier: CascadeTier::HumanExpert,
                    cost: 50.0,
                    expected_confidence: 0.99,
                },
            ],
        }
    }

    #[test]
    fn already_confident_spends_nothing() {
        let out = decide_cascade(0.9, &policy(0.8, 100.0));
        assert_eq!(out, CascadeOutcome::AlreadyConfident { confidence: 0.9 });
    }

    #[test]
    fn picks_cheapest_tier_that_meets_target() {
        // Target 0.6 → the cheap self-reflect tier suffices.
        let out = decide_cascade(0.2, &policy(0.6, 100.0));
        assert_eq!(
            out,
            CascadeOutcome::Accept {
                tier: CascadeTier::SelfReflect,
                confidence: 0.6,
                cost_spent: 1.0,
            }
        );
    }

    #[test]
    fn escalates_when_cheap_tier_insufficient() {
        // Target 0.8 → self-reflect (0.6) is not enough, escalate to tool-verify
        // (0.85). cost_spent is cumulative: 1.0 + 5.0.
        let out = decide_cascade(0.2, &policy(0.8, 100.0));
        assert_eq!(
            out,
            CascadeOutcome::Accept {
                tier: CascadeTier::ToolVerify,
                confidence: 0.85,
                cost_spent: 6.0,
            }
        );
    }

    #[test]
    fn escalates_to_human_for_high_target() {
        let out = decide_cascade(0.1, &policy(0.95, 100.0));
        assert_eq!(
            out,
            CascadeOutcome::Accept {
                tier: CascadeTier::HumanExpert,
                confidence: 0.99,
                cost_spent: 56.0, // 1 + 5 + 50
            }
        );
    }

    #[test]
    fn budget_caps_escalation_returns_best_affordable() {
        // Target 0.95 needs the human tier, but budget only covers self+tool.
        let out = decide_cascade(0.1, &policy(0.95, 10.0));
        assert_eq!(
            out,
            CascadeOutcome::Exhausted {
                best_tier: Some(CascadeTier::ToolVerify),
                confidence: 0.85,
                cost_spent: 6.0,
            }
        );
    }

    #[test]
    fn budget_too_small_for_any_tier() {
        // Even the cheapest tier (cost 1.0) is unaffordable.
        let out = decide_cascade(0.1, &policy(0.6, 0.5));
        assert_eq!(
            out,
            CascadeOutcome::Exhausted {
                best_tier: None,
                confidence: 0.1,
                cost_spent: 0.0,
            }
        );
    }

    #[test]
    fn empty_tiers_is_exhausted() {
        let p = CascadePolicy {
            confidence_target: 0.8,
            budget: 100.0,
            tiers: vec![],
        };
        let out = decide_cascade(0.2, &p);
        assert_eq!(
            out,
            CascadeOutcome::Exhausted {
                best_tier: None,
                confidence: 0.2,
                cost_spent: 0.0,
            }
        );
    }

    // --- run_cascade (Slice 5: observed-confidence orchestration) ---

    /// A mock tier runner: returns the observed confidence the test prescribes
    /// per tier, with knowledge tagged by tier.
    fn runner(
        observed: std::collections::HashMap<CascadeTier, f64>,
    ) -> impl FnMut(CascadeTier) -> Result<TierResult, String> {
        move |tier| {
            let confidence = *observed.get(&tier).unwrap_or(&0.0);
            Ok(TierResult {
                knowledge: format!("{tier:?} knowledge"),
                confidence,
            })
        }
    }

    #[test]
    fn run_already_confident_runs_nothing() {
        let run = run_cascade(0.9, &policy(0.8, 100.0), runner(Default::default())).unwrap();
        assert!(run.steps.is_empty());
        assert_eq!(run.accepted_tier, None);
        assert_eq!(run.knowledge, None);
        assert_eq!(run.confidence, 0.9);
        assert_eq!(run.cost_spent, 0.0);
    }

    #[test]
    fn run_stops_at_cheapest_tier_that_observes_target() {
        // Self-reflect's *observed* confidence (0.9) clears target 0.8 even
        // though its *predicted* expected_confidence (0.6) would not — proving
        // the loop escalates on observation, not prediction.
        let observed = [(CascadeTier::SelfReflect, 0.9)].into_iter().collect();
        let run = run_cascade(0.2, &policy(0.8, 100.0), runner(observed)).unwrap();
        assert_eq!(run.accepted_tier, Some(CascadeTier::SelfReflect));
        assert_eq!(run.steps.len(), 1);
        assert_eq!(run.cost_spent, 1.0);
        assert_eq!(run.confidence, 0.9);
        assert_eq!(run.knowledge.as_deref(), Some("SelfReflect knowledge"));
    }

    #[test]
    fn run_escalates_on_low_observed_confidence() {
        // Self-reflect under-delivers (0.4 < 0.8), tool-verify clears it (0.85).
        let observed = [
            (CascadeTier::SelfReflect, 0.4),
            (CascadeTier::ToolVerify, 0.85),
        ]
        .into_iter()
        .collect();
        let run = run_cascade(0.2, &policy(0.8, 100.0), runner(observed)).unwrap();
        assert_eq!(run.accepted_tier, Some(CascadeTier::ToolVerify));
        assert_eq!(run.steps.len(), 2);
        assert_eq!(run.cost_spent, 6.0); // 1 + 5
        assert_eq!(run.knowledge.as_deref(), Some("ToolVerify knowledge"));
    }

    #[test]
    fn run_budget_caps_escalation_keeps_best_knowledge() {
        // Target 0.95, but budget covers only self+tool (cost 6, not 56).
        // Neither clears the target; the best knowledge (tool, 0.85) is kept.
        let observed = [
            (CascadeTier::SelfReflect, 0.5),
            (CascadeTier::ToolVerify, 0.85),
            (CascadeTier::HumanExpert, 0.99),
        ]
        .into_iter()
        .collect();
        let run = run_cascade(0.1, &policy(0.95, 10.0), runner(observed)).unwrap();
        assert_eq!(run.accepted_tier, None); // never reached target
        assert_eq!(run.steps.len(), 2); // human tier unaffordable
        assert_eq!(run.cost_spent, 6.0);
        assert_eq!(run.confidence, 0.85); // best observed
        assert_eq!(run.knowledge.as_deref(), Some("ToolVerify knowledge"));
    }

    #[test]
    fn run_propagates_runner_error() {
        let err = run_cascade(0.2, &policy(0.8, 100.0), |_tier| {
            Err("tool exploded".to_string())
        });
        assert_eq!(err, Err("tool exploded".to_string()));
    }

    // --- run_cascade_async: same logic, awaited tier runners ---

    /// An async mock runner: returns the prescribed observed confidence per
    /// tier, tagging knowledge by tier. Records which tiers actually ran so a
    /// test can assert lazy escalation (a later tier is never awaited once an
    /// earlier one clears the target).
    fn async_runner(
        observed: std::collections::HashMap<CascadeTier, f64>,
        ran: std::rc::Rc<std::cell::RefCell<Vec<CascadeTier>>>,
    ) -> impl FnMut(
        CascadeTier,
    ) -> std::pin::Pin<
        Box<dyn std::future::Future<Output = Result<TierResult, String>>>,
    > {
        move |tier| {
            let confidence = *observed.get(&tier).unwrap_or(&0.0);
            ran.borrow_mut().push(tier);
            Box::pin(async move {
                Ok(TierResult {
                    knowledge: format!("{tier:?} knowledge"),
                    confidence,
                })
            })
        }
    }

    #[tokio::test]
    async fn async_stops_at_cheapest_tier_that_observes_target() {
        let ran = std::rc::Rc::new(std::cell::RefCell::new(Vec::new()));
        let observed = [(CascadeTier::SelfReflect, 0.9)].into_iter().collect();
        let run = run_cascade_async(
            0.2,
            &policy(0.8, 100.0),
            async_runner(observed, ran.clone()),
        )
        .await
        .unwrap();
        assert_eq!(run.accepted_tier, Some(CascadeTier::SelfReflect));
        assert_eq!(run.cost_spent, 1.0);
        // Only the self-reflect tier was awaited — escalation is lazy.
        assert_eq!(*ran.borrow(), vec![CascadeTier::SelfReflect]);
    }

    #[tokio::test]
    async fn async_escalates_on_low_observed_confidence() {
        let ran = std::rc::Rc::new(std::cell::RefCell::new(Vec::new()));
        let observed = [
            (CascadeTier::SelfReflect, 0.4),
            (CascadeTier::ToolVerify, 0.85),
        ]
        .into_iter()
        .collect();
        let run = run_cascade_async(
            0.2,
            &policy(0.8, 100.0),
            async_runner(observed, ran.clone()),
        )
        .await
        .unwrap();
        assert_eq!(run.accepted_tier, Some(CascadeTier::ToolVerify));
        assert_eq!(run.cost_spent, 6.0);
        assert_eq!(
            *ran.borrow(),
            vec![CascadeTier::SelfReflect, CascadeTier::ToolVerify]
        );
    }

    #[tokio::test]
    async fn async_propagates_runner_error() {
        let err = run_cascade_async(0.2, &policy(0.8, 100.0), |_tier| async {
            Err::<TierResult, String>("tool exploded".to_string())
        })
        .await;
        assert_eq!(err, Err("tool exploded".to_string()));
    }
}