Skip to main content

firstpass_proxy/
bandit.rs

1//! UCB1 start-rung bandit: predict-to-start, verify-to-serve.
2//!
3//! # Science
4//!
5//! Every request currently starts the escalation ladder at rung 0 (cheapest model). Many
6//! contexts (task kind × prompt-size bucket) have a learned empirical pass rate per rung: if
7//! rung 0 almost never passes for a given context, always starting there wastes money. This
8//! module learns a per-context start rung that minimises expected cost while the enforce gate
9//! still verifies the chosen rung's output before serving.
10//!
11//! **The invariant (predict-to-start, verify-to-serve):** the bandit only controls where the
12//! ladder *starts*. Gating, escalation, budget, and speculation are untouched. If the predicted
13//! start rung's output fails the gate, the ladder continues upward as normal — no downward
14//! retry. Prediction errors can cost money (latency, slightly higher expected cost when the
15//! estimate is wrong) but can never cause a wrong answer to be served.
16//!
17//! # Algorithm
18//!
19//! UCB1 (Auer et al. 2002) applied to cost-sensitive start-rung selection. For each candidate
20//! start s, the expected cost is:
21//!
22//! ```text
23//! E[s] = Σ_{r=s}^{top-1}  price_r · P(reach r | start s)
24//! P(reach r | start s) = Π_{q=s}^{r-1} (1 − p̂_q)
25//! p̂_q = clamp(successes_q / n_q  +  c · √(ln N / n_q),  0, 1)
26//! ```
27//!
28//! where `N` is the total gate-verdict observations in this context, `n_q` is the observations
29//! at rung `q`, and `c` is the exploration constant (default 1.0). Tie → lower s (conservative).
30//!
31//! **Prices are evaluated at the request's own size**, derived from the context's prompt-token
32//! band ([`ContextBucket::representative_prompt_tokens`]). This used to use fixed nominal tokens
33//! on the reasoning that "relative prices are what matters" — which measurement disproved.
34//!
35//! For two rungs the argmin above reduces to `start cheap ⟺ c₀ < p·c₁`, so what the cheap attempt
36//! costs *relative to what it can save* is the entire decision. With a constant token count that
37//! ratio is identical for every request, and the rule degenerates to a function of `p` alone.
38//! That throws away the signal that makes it pay: on 974-task MBPP, escalation is **adversely
39//! selected ~2.16×** — requests that fail the gate cost ~2.2× more at the cheap rung *and* ~2.1×
40//! more at the top rung, because hard requests are long requests. Offline replay of the measured
41//! matrix put the corrected rule 22% below plain first-pass at slightly *higher* accuracy. Sizing
42//! the price at the actual request is what lets this bandit see that.
43//!
44//! **Cold-start safety:** if the context has fewer than `min_observations` total gate verdicts,
45//! the bandit returns rung 0 (byte-identical to today's behavior). Abstain verdicts are not
46//! counted (only clear Pass/Fail gate outcomes are informative).
47//!
48//! # State
49//!
50//! ponytail: in-memory `Mutex`, per-process. Survives restarts via warm-start replay of the
51//! trace store at startup. No persistence of its own — the trace store is the durable record.
52
53use std::collections::HashMap;
54
55use firstpass_core::{Features, PriceTable, TaskKind, Verdict};
56
57/// The context bucket that keys the bandit's per-arm statistics.
58///
59/// Coarsened to keep the arm count dense: `prompt_bucket_coarse = prompt_token_bucket / 2`
60/// halves the bucket resolution (floor(log2(n)) → floor(log2(n)/2) in effect), trading
61/// granularity for faster warm-up.
62///
63/// ponytail: the ladder identity is not part of the key — in practice a given (TaskKind,
64/// prompt size) routes to the same ladder via the first-match routing rule. Would need to be
65/// included if operators run overlapping routes for the same context.
66#[derive(Debug, Clone, PartialEq, Eq, Hash)]
67pub struct ContextBucket {
68    /// How hard the agent's own conversation looks (`Features::difficulty_hint`, `0..=3`).
69    ///
70    /// This is the third dimension, and it is why the other two stay coarse. Every dimension
71    /// multiplies the arm count, and arms that never accumulate traffic never learn — a bandit with
72    /// a beautifully descriptive key and four samples per arm is worse than one with a crude key and
73    /// four hundred. The hint is capped at four ordinal levels for exactly this reason, and the
74    /// three trajectory signals behind it are collapsed into this single number before they reach
75    /// here rather than each becoming a dimension of its own.
76    ///
77    /// Zero for every non-agent request, so a deployment seeing no agent traffic keys exactly as it
78    /// did before this field existed and its learned statistics remain valid.
79    pub difficulty_hint: u8,
80    /// Coarse task classification from the request feature vector.
81    pub task_kind: TaskKind,
82    /// `features.prompt_token_bucket / 2` — halved for denser arms.
83    pub prompt_bucket_coarse: u32,
84}
85
86impl ContextBucket {
87    /// Derive a context bucket from a request's feature vector.
88    #[must_use]
89    pub fn from_features(f: &Features) -> Self {
90        Self {
91            difficulty_hint: f.difficulty_hint,
92            task_kind: f.task_kind,
93            prompt_bucket_coarse: f.prompt_token_bucket / 2,
94        }
95    }
96
97    /// A representative prompt size for this bucket, in tokens.
98    ///
99    /// `features::token_bucket` is `floor(log2(n))` and this key halves it, so the bucket covers
100    /// `[2^(2b), 2^(2b+2))`. The geometric midpoint of that band is `2^(2b+1)`, which is the
101    /// least-wrong single number to stand in for it — and the ordering that matters
102    /// (bigger bucket ⇒ bigger estimate) is exactly preserved.
103    ///
104    /// This exists because start-rung selection needs the request's *size*, not just its shape.
105    /// The raw count is deliberately never stored (privacy), but the band already is, and the band
106    /// carries the signal.
107    #[must_use]
108    pub fn representative_prompt_tokens(&self) -> u64 {
109        // Clamp the BAND before scaling it: clamping the exponent afterwards still overflows the
110        // multiply on a pathological bucket (caught by test, in debug where it panics rather than
111        // wrapping to a tiny shift in release).
112        1u64 << (self.prompt_bucket_coarse.min(9) * 2 + 1)
113    }
114}
115
116/// Per-(context, rung) gate-verdict counts. Abstain is excluded (see module doc).
117#[derive(Debug, Default, Clone)]
118struct ArmCounts {
119    pass: f64,
120    fail: f64,
121}
122
123impl ArmCounts {
124    fn n(&self) -> f64 {
125        self.pass + self.fail
126    }
127}
128
129/// Online UCB1 bandit for start-rung selection.
130///
131/// Keyed by [`ContextBucket`]; per context, tracks per-rung pass/fail counts of gate verdicts.
132/// Thread-safety comes from the caller wrapping this in `Arc<std::sync::Mutex<_>>` (mirroring
133/// `AdaptiveConformal` — both are per-process, in-memory, low-contention).
134#[derive(Debug)]
135pub struct StartRungBandit {
136    /// UCB1 exploration constant `c` ≥ 0 (used by [`Algorithm::Ucb1`]).
137    exploration: f64,
138    /// Cold-start threshold: contexts with fewer total observations return rung 0.
139    min_observations: usize,
140    /// Selection algorithm: deterministic UCB1 (auditable) or Thompson sampling (stochastic,
141    /// native propensities, better under non-stationarity with `discount < 1`).
142    algorithm: Algorithm,
143    /// Per-observation multiplicative decay of a context's counts, in `(0, 1]`. `1.0` = no
144    /// forgetting (stationary). Applied on every observe, so a context that stops matching
145    /// reality fades at rate `discount^n` (discounted Thompson sampling).
146    discount: f64,
147    /// xorshift64* PRNG state for Thompson draws (seeded once; deterministic in tests).
148    rng: u64,
149    /// context → (rung index → counts).
150    data: HashMap<ContextBucket, HashMap<u32, ArmCounts>>,
151}
152
153/// Start-rung selection algorithm.
154/// Monte-Carlo repetitions for the Thompson propensity estimate.
155const PROPENSITY_SAMPLES: usize = 64;
156
157/// The expected-cost argmin over candidate start rungs, shared by UCB1 and Thompson: walk the
158/// ladder from each candidate start, accumulating `P(reach r) · price(r)` with
159/// `P(reach r+1) = P(reach r) · (1 − p_pass(r))`. Ties prefer the lower start (conservative).
160fn argmin_expected_cost(
161    ladder: &[String],
162    prices: &PriceTable,
163    in_tokens: u64,
164    mut p_pass: impl FnMut(u32) -> f64,
165) -> u32 {
166    // Output is estimated at half the prompt, preserving the ratio the previous nominal constants
167    // used (1000 in / 500 out) while letting both scale with the actual request.
168    let out_tokens = (in_tokens / 2).max(1);
169
170    let mut best_s = 0u32;
171    let mut best_cost = f64::MAX;
172    for s in 0..ladder.len() {
173        let mut expected_cost = 0.0_f64;
174        let mut p_reach = 1.0_f64;
175        for (r, model) in ladder.iter().enumerate().skip(s) {
176            let price = prices
177                .get(model)
178                .map(|p| p.cost(in_tokens, out_tokens))
179                .unwrap_or(0.0);
180            expected_cost += p_reach * price;
181            p_reach *= 1.0 - p_pass(r as u32);
182            if p_reach < 1e-10 {
183                break;
184            }
185        }
186        if expected_cost < best_cost {
187            best_cost = expected_cost;
188            best_s = s as u32;
189        }
190    }
191    best_s
192}
193
194#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
195pub enum Algorithm {
196    /// Deterministic optimism (Auer et al. 2002): auditable, but propensities are degenerate
197    /// (0/1) — off-policy estimates then need the epsilon-greedy overlay.
198    #[default]
199    Ucb1,
200    /// Thompson sampling over Beta posteriors of gate-pass: stochastic by nature, so every
201    /// decision carries a non-degenerate propensity (Monte-Carlo estimated), and `discount`
202    /// handles model churn (Chapelle & Li 2011; discounted TS for non-stationarity).
203    Thompson,
204}
205
206impl StartRungBandit {
207    /// Create a new UCB1 bandit with the given cold-start and exploration settings.
208    #[must_use]
209    pub fn new(min_observations: usize, exploration: f64) -> Self {
210        Self::with_algorithm(min_observations, exploration, Algorithm::Ucb1, 1.0, 0x9E37)
211    }
212
213    /// Create a bandit with an explicit algorithm, discount, and PRNG seed (seed matters only
214    /// for [`Algorithm::Thompson`]; pass anything non-zero).
215    #[must_use]
216    pub fn with_algorithm(
217        min_observations: usize,
218        exploration: f64,
219        algorithm: Algorithm,
220        discount: f64,
221        seed: u64,
222    ) -> Self {
223        Self {
224            exploration,
225            min_observations,
226            algorithm,
227            discount: discount.clamp(f64::MIN_POSITIVE, 1.0),
228            rng: seed.max(1),
229            data: HashMap::new(),
230        }
231    }
232
233    /// Apply one step of multiplicative forgetting to every arm in `ctx` (no-op at 1.0).
234    fn discount_context(&mut self, ctx: &ContextBucket) {
235        if self.discount >= 1.0 {
236            return;
237        }
238        if let Some(arms) = self.data.get_mut(ctx) {
239            for c in arms.values_mut() {
240                c.pass *= self.discount;
241                c.fail *= self.discount;
242            }
243        }
244    }
245
246    /// Next xorshift64* draw as a uniform in `[0, 1)`.
247    fn next_u01(&mut self) -> f64 {
248        let mut x = self.rng;
249        x ^= x >> 12;
250        x ^= x << 25;
251        x ^= x >> 27;
252        self.rng = x;
253        let v = x.wrapping_mul(0x2545_F491_4F6C_DD1D);
254        (v >> 11) as f64 / (1u64 << 53) as f64
255    }
256
257    /// Standard normal via Box–Muller on the internal PRNG.
258    fn next_normal(&mut self) -> f64 {
259        let u1 = self.next_u01().max(f64::MIN_POSITIVE);
260        let u2 = self.next_u01();
261        (-2.0 * u1.ln()).sqrt() * (std::f64::consts::TAU * u2).cos()
262    }
263
264    /// Gamma(shape ≥ 1, scale 1) sample — Marsaglia–Tsang squeeze method.
265    fn next_gamma(&mut self, shape: f64) -> f64 {
266        debug_assert!(shape >= 1.0, "Beta(+1 prior) keeps shapes >= 1");
267        let d = shape - 1.0 / 3.0;
268        let c = 1.0 / (9.0 * d).sqrt();
269        loop {
270            let x = self.next_normal();
271            let v = (1.0 + c * x).powi(3);
272            if v <= 0.0 {
273                continue;
274            }
275            let u = self.next_u01();
276            if u < 1.0 - 0.0331 * x.powi(4) || u.ln() < 0.5 * x * x + d * (1.0 - v + v.ln()) {
277                return d * v;
278            }
279        }
280    }
281
282    /// One Beta(pass+1, fail+1) posterior draw of the gate-pass probability for `(ctx, rung)`.
283    /// Unobserved arms draw from the uniform prior Beta(1, 1).
284    fn thompson_pass(&mut self, ctx: &ContextBucket, rung: u32) -> f64 {
285        let (a, b) = self
286            .data
287            .get(ctx)
288            .and_then(|arms| arms.get(&rung))
289            .map_or((1.0, 1.0), |c| (c.pass + 1.0, c.fail + 1.0));
290        let x = self.next_gamma(a);
291        let y = self.next_gamma(b);
292        x / (x + y)
293    }
294
295    /// Posterior-mean gate-pass estimate for `(ctx, rung)` — `None` when the context is cold
296    /// (below `min_observations`) or the arm is unobserved. Deterministic; used by the
297    /// speculative-deferral band, never for serving decisions.
298    #[must_use]
299    pub fn pass_estimate(&self, ctx: &ContextBucket, rung: u32) -> Option<f64> {
300        let arms = self.data.get(ctx)?;
301        let total: f64 = arms.values().map(ArmCounts::n).sum();
302        if total < self.min_observations as f64 {
303            return None;
304        }
305        let c = arms.get(&rung)?;
306        if c.n() == 0.0 {
307            return None;
308        }
309        Some((c.pass + 1.0) / (c.n() + 2.0))
310    }
311
312    /// Record a gate verdict for `(context, rung)`.
313    ///
314    /// `Abstain` is ignored — only clear Pass/Fail outcomes are informative for cost modelling.
315    pub fn observe(&mut self, ctx: &ContextBucket, rung: u32, verdict: Verdict) {
316        match verdict {
317            Verdict::Abstain => {} // not counted
318            Verdict::Pass => {
319                self.discount_context(ctx);
320                self.data
321                    .entry(ctx.clone())
322                    .or_default()
323                    .entry(rung)
324                    .or_default()
325                    .pass += 1.0;
326            }
327            Verdict::Fail => {
328                self.discount_context(ctx);
329                self.data
330                    .entry(ctx.clone())
331                    .or_default()
332                    .entry(rung)
333                    .or_default()
334                    .fail += 1.0;
335            }
336        }
337    }
338
339    /// UCB1-optimistic pass-rate estimate for `rung` in `ctx`.
340    ///
341    /// Returns 1.0 for unobserved rungs (optimistic exploration, UCB → ∞, clamped).
342    fn ucb_pass(&self, ctx: &ContextBucket, rung: u32, ln_n: f64) -> f64 {
343        let Some(arms) = self.data.get(ctx) else {
344            return 1.0; // context unseen: fully optimistic
345        };
346        let Some(counts) = arms.get(&rung) else {
347            return 1.0; // rung unobserved for this context: fully optimistic
348        };
349        let n = counts.n();
350        if n == 0.0 {
351            return 1.0;
352        }
353        let p_hat = counts.pass / n;
354        (p_hat + self.exploration * (ln_n / n).sqrt()).clamp(0.0, 1.0)
355    }
356
357    /// Choose the start rung that minimises expected cost for this context and ladder.
358    ///
359    /// Returns `0` in all cold-start cases:
360    /// - bandit is cold (total observations < `min_observations` for this context)
361    /// - `ladder` is empty
362    ///
363    /// Never returns a value ≥ `ladder.len()`.
364    #[must_use]
365    pub fn choose_start(&self, ctx: &ContextBucket, ladder: &[String], prices: &PriceTable) -> u32 {
366        let top = ladder.len();
367        if top == 0 {
368            return 0;
369        }
370
371        // Cold-start guard: total gate observations in this context.
372        let n_total: f64 = self
373            .data
374            .get(ctx)
375            .map(|arms| arms.values().map(ArmCounts::n).sum())
376            .unwrap_or(0.0);
377        if n_total < self.min_observations as f64 {
378            return 0;
379        }
380
381        let ln_n = n_total.ln();
382        argmin_expected_cost(ladder, prices, ctx.representative_prompt_tokens(), |r| {
383            self.ucb_pass(ctx, r, ln_n)
384        })
385    }
386
387    /// Choose the start rung and its selection propensity.
388    ///
389    /// - [`Algorithm::Ucb1`]: deterministic — returns `(choice, None)`; the epsilon-greedy
390    ///   overlay (if configured) supplies the logged propensity, exactly as before.
391    /// - [`Algorithm::Thompson`]: one posterior draw per rung drives the same expected-cost
392    ///   argmin as UCB1 (the decision), and the propensity is Monte-Carlo estimated by
393    ///   re-running the draw `PROPENSITY_SAMPLES` times — the standard estimator for TS
394    ///   selection probabilities (exact computation is analytically intractable). Cold-start
395    ///   contexts return `(0, None)` (deterministic, no propensity to log).
396    #[must_use]
397    pub fn choose_start_with_propensity(
398        &mut self,
399        ctx: &ContextBucket,
400        ladder: &[String],
401        prices: &PriceTable,
402    ) -> (u32, Option<f64>) {
403        if self.algorithm == Algorithm::Ucb1 {
404            return (self.choose_start(ctx, ladder, prices), None);
405        }
406        let top = ladder.len();
407        if top == 0 {
408            return (0, None);
409        }
410        let n_total: f64 = self
411            .data
412            .get(ctx)
413            .map(|arms| arms.values().map(ArmCounts::n).sum())
414            .unwrap_or(0.0);
415        if n_total < self.min_observations as f64 {
416            return (0, None);
417        }
418
419        let draw = |this: &mut Self| {
420            // One full posterior draw per rung, then the shared cost argmin.
421            let samples: Vec<f64> = (0..top)
422                .map(|r| this.thompson_pass(ctx, r as u32))
423                .collect();
424            argmin_expected_cost(ladder, prices, ctx.representative_prompt_tokens(), |r| {
425                samples[r as usize]
426            })
427        };
428
429        let choice = draw(self);
430        let matches = (0..PROPENSITY_SAMPLES)
431            .filter(|_| draw(self) == choice)
432            .count();
433        // Clamp away 0: the MC estimate can miss a genuinely-possible arm in finite samples,
434        // and a zero propensity would blow up IPS. 1/(2·M) is the standard floor.
435        let p = (matches as f64 / PROPENSITY_SAMPLES as f64)
436            .max(1.0 / (2.0 * PROPENSITY_SAMPLES as f64));
437        (choice, Some(p))
438    }
439
440    /// Feed all attempts from a stored trace into this bandit — used for warm-start at startup.
441    pub fn feed_trace_attempts(
442        &mut self,
443        ctx: &ContextBucket,
444        attempts: &[firstpass_core::Attempt],
445    ) {
446        for attempt in attempts {
447            self.observe(ctx, attempt.rung, attempt.verdict);
448        }
449    }
450}
451
452#[cfg(test)]
453mod tests {
454    use super::*;
455    use firstpass_core::{
456        Attempt, Features, FinalOutcome, GENESIS_HASH, Mode, PolicyRef, RequestInfo, ServedFrom,
457        TaskKind, Trace,
458    };
459
460    /// The trajectory hint must actually reach the bandit's key.
461    ///
462    /// Written because a mutation exposed that nothing covered this wiring: hard-coding
463    /// `difficulty_hint: 0` in `from_features` left every other test green. The feature would have
464    /// been extracted, stamped into the audit trace, exported in receipts — and silently ignored by
465    /// the one consumer that is supposed to act on it. A signal that reaches everything except the
466    /// decision is worse than no signal, because the telemetry says it is working.
467    #[test]
468    fn the_difficulty_hint_reaches_the_bandit_key() {
469        let mut easy = Features::new(TaskKind::CodeEdit);
470        easy.prompt_token_bucket = 6;
471        let mut hard = easy.clone();
472        hard.difficulty_hint = 3;
473
474        let (b_easy, b_hard) = (
475            ContextBucket::from_features(&easy),
476            ContextBucket::from_features(&hard),
477        );
478        assert_eq!(
479            b_hard.difficulty_hint, 3,
480            "the hint must be carried through"
481        );
482        assert_ne!(
483            b_easy, b_hard,
484            "identical requests differing ONLY in trajectory difficulty must key to different \
485             arms, or the bandit can never learn a different start rung for them"
486        );
487        // ...and the rest of the key must be untouched, so this is a new dimension rather than a
488        // reinterpretation of the existing ones.
489        assert_eq!(b_easy.task_kind, b_hard.task_kind);
490        assert_eq!(b_easy.prompt_bucket_coarse, b_hard.prompt_bucket_coarse);
491    }
492
493    fn ctx_code() -> ContextBucket {
494        ContextBucket {
495            difficulty_hint: 0,
496            task_kind: TaskKind::CodeEdit,
497            prompt_bucket_coarse: 3,
498        }
499    }
500
501    fn ctx_chat() -> ContextBucket {
502        ContextBucket {
503            difficulty_hint: 0,
504            task_kind: TaskKind::Chat,
505            prompt_bucket_coarse: 3,
506        }
507    }
508
509    const HAIKU: &str = "anthropic/claude-haiku-4-5";
510    const SONNET: &str = "anthropic/claude-sonnet-5";
511
512    #[test]
513    fn cold_start_returns_rung_0() {
514        let b = StartRungBandit::new(50, 1.0);
515        let prices = PriceTable::defaults();
516        let ladder = vec![HAIKU.to_owned(), SONNET.to_owned()];
517        // No observations at all → cold start.
518        assert_eq!(b.choose_start(&ctx_code(), &ladder, &prices), 0);
519    }
520
521    #[test]
522    fn empty_ladder_returns_rung_0() {
523        let b = StartRungBandit::new(50, 1.0);
524        let prices = PriceTable::defaults();
525        assert_eq!(b.choose_start(&ctx_code(), &[], &prices), 0);
526    }
527
528    #[test]
529    fn after_enough_rung0_fails_rung1_passes_picks_rung1_for_that_context() {
530        let mut b = StartRungBandit::new(50, 1.0);
531        let prices = PriceTable::defaults();
532        let ladder = vec![HAIKU.to_owned(), SONNET.to_owned()];
533
534        // Feed 60 rung-0 fails + 60 rung-1 passes for ctx_code → bandit should skip rung 0.
535        let code = ctx_code();
536        for _ in 0..60 {
537            b.observe(&code, 0, Verdict::Fail);
538            b.observe(&code, 1, Verdict::Pass);
539        }
540        // Expected cost E[0] = price_haiku + (1 - p̂_0) * price_sonnet  >> E[1] = price_sonnet.
541        assert_eq!(
542            b.choose_start(&code, &ladder, &prices),
543            1,
544            "should skip rung 0 after observing it always fails"
545        );
546
547        // A DIFFERENT context with no data stays cold (returns 0), not influenced by code's data.
548        let chat = ctx_chat();
549        assert_eq!(
550            b.choose_start(&chat, &ladder, &prices),
551            0,
552            "different context must be independent (cold start)"
553        );
554    }
555
556    #[test]
557    fn abstain_verdicts_are_not_counted() {
558        let mut b = StartRungBandit::new(2, 1.0); // tiny min_obs to isolate the logic
559        let code = ctx_code();
560        // Only feed abstains — they must not push us past cold start.
561        for _ in 0..100 {
562            b.observe(&code, 0, Verdict::Abstain);
563        }
564        let prices = PriceTable::defaults();
565        let ladder = vec![HAIKU.to_owned(), SONNET.to_owned()];
566        // N = 0 (abstains excluded) < min_obs=2 → rung 0.
567        assert_eq!(b.choose_start(&code, &ladder, &prices), 0);
568    }
569
570    #[test]
571    fn single_rung_ladder_always_returns_0() {
572        let mut b = StartRungBandit::new(1, 1.0);
573        let code = ctx_code();
574        b.observe(&code, 0, Verdict::Fail);
575        b.observe(&code, 0, Verdict::Pass);
576        let prices = PriceTable::defaults();
577        let ladder = vec![HAIKU.to_owned()];
578        assert_eq!(b.choose_start(&code, &ladder, &prices), 0);
579    }
580
581    /// Build a minimal attempt with a given rung and verdict (for warm-start tests).
582    fn stub_attempt(rung: u32, verdict: Verdict) -> Attempt {
583        Attempt {
584            rung,
585            model: HAIKU.to_owned(),
586            provider: "anthropic".to_owned(),
587            in_tokens: 1000,
588            cache_write_tokens: 0,
589            cache_read_tokens: 0,
590            out_tokens: 500,
591            cost_usd: 0.001,
592            latency_ms: 10,
593            gates: vec![],
594            verdict,
595        }
596    }
597
598    #[test]
599    fn from_features_derives_bucket_correctly() {
600        let mut f = Features::new(TaskKind::CodeEdit);
601        f.prompt_token_bucket = 7; // coarse = 7/2 = 3
602        let b = ContextBucket::from_features(&f);
603        assert_eq!(b.task_kind, TaskKind::CodeEdit);
604        assert_eq!(b.prompt_bucket_coarse, 3);
605    }
606
607    #[test]
608    fn feed_trace_attempts_populates_counts() {
609        let mut bandit = StartRungBandit::new(2, 1.0);
610        let ctx = ctx_code();
611        let attempts = vec![
612            stub_attempt(0, Verdict::Fail),
613            stub_attempt(1, Verdict::Pass),
614        ];
615        bandit.feed_trace_attempts(&ctx, &attempts);
616
617        // Verify internally: 1 fail at rung 0, 1 pass at rung 1 → total N=2 ≥ min_obs=2.
618        // With min_obs=2 and only rung-0 failing, the bandit should prefer rung 1.
619        let prices = PriceTable::defaults();
620        let ladder = vec![HAIKU.to_owned(), SONNET.to_owned()];
621        // N=2, p̂_0 = 0/1 + sqrt(ln2/1) ≈ 0.83, p̂_1 = 1/1 + ... ≥ 1.0
622        // E[0] = price_haiku + (1-0.83)*price_sonnet; E[1] = price_sonnet.
623        // Whether bandit picks 0 or 1 depends on exact math — just verify it doesn't panic.
624        let _ = bandit.choose_start(&ctx, &ladder, &prices);
625    }
626
627    // ---- Guarantee invariant: bandit on + start rung fails → escalates, never serves failing output.
628    // (Integration with the router is tested in router.rs; here we prove the math doesn't
629    // synthesise a "free pass" when an observed rung has 0% pass rate.)
630    #[test]
631    fn zero_pass_rate_rung_is_not_optimistic() {
632        // After many fail observations at rung 0 and pass observations at rung 1,
633        // choosing E[s] should prefer s=1 even with c=0 (no exploration bonus).
634        let mut b = StartRungBandit::new(10, 0.0); // c=0: pure exploitation
635        let ctx = ctx_code();
636        for _ in 0..20 {
637            b.observe(&ctx, 0, Verdict::Fail);
638            b.observe(&ctx, 1, Verdict::Pass);
639        }
640        let prices = PriceTable::defaults();
641        let ladder = vec![HAIKU.to_owned(), SONNET.to_owned()];
642        // p̂_0 = 0 (c=0), p̂_1 = 1.0
643        // E[0] = price_haiku + 1.0*price_sonnet;  E[1] = price_sonnet
644        // E[0] > E[1] → choose start=1.
645        assert_eq!(b.choose_start(&ctx, &ladder, &prices), 1);
646    }
647
648    // ---- Warm-start from disk --------------------------------------------------------
649
650    /// Helper: build a minimal enforce-mode trace with one attempt at rung 0 (pass) and one
651    /// at rung 1 (fail), carrying the given Features so ContextBucket::from_features works.
652    fn trace_with_features_and_attempts(features: Features, attempts: Vec<Attempt>) -> Trace {
653        let mut trace = Trace {
654            trace_id: uuid::Uuid::now_v7(),
655            prev_hash: GENESIS_HASH.to_owned(),
656            tenant_id: "test-tenant".to_owned(),
657            session_id: "sess-warm".to_owned(),
658            ts: jiff::Timestamp::now(),
659            mode: Mode::Enforce,
660            policy: PolicyRef {
661                id: "test@v0".to_owned(),
662                explore: false,
663                propensity: None,
664                mode_profile: None,
665            },
666            request: RequestInfo {
667                api: "anthropic.messages".to_owned(),
668                prompt_hash: "deadbeef".to_owned(),
669                features,
670            },
671            attempts,
672            deferred: vec![],
673            final_: FinalOutcome {
674                served_rung: Some(0),
675                served_from: ServedFrom::Attempt,
676                total_cost_usd: 0.001,
677                gate_cost_usd: 0.0,
678                total_latency_ms: 10,
679                escalations: 0,
680                counterfactual_baseline_usd: 0.001,
681                savings_usd: 0.0,
682                cache_source: None,
683            },
684            probe: None,
685            rollout: None,
686            shadow: None,
687            route_ix: None,
688            predicted_pass: None,
689            elastic: None,
690        };
691        trace.recompute_savings();
692        trace
693    }
694
695    /// Warm-start test: write traces to a temp store, replay them into a fresh bandit,
696    /// assert the learned counts drive the expected start-rung choice.
697    #[tokio::test]
698    async fn warm_start_from_trace_store_replays_counts() {
699        let db = std::env::temp_dir().join(format!("bandit-warmstart-{}.db", uuid::Uuid::now_v7()));
700        let (tx, writer) = crate::store::open(&db).unwrap();
701
702        // Build features that land in ctx_code (TaskKind::CodeEdit, bucket_coarse=3).
703        let mut f = Features::new(TaskKind::CodeEdit);
704        f.prompt_token_bucket = 7; // coarse = 7/2 = 3
705
706        // 60 traces: rung 0 always fails, rung 1 always passes.
707        for _ in 0..60 {
708            let attempts = vec![
709                stub_attempt(0, Verdict::Fail),
710                stub_attempt(1, Verdict::Pass),
711            ];
712            tx.try_send(trace_with_features_and_attempts(f.clone(), attempts))
713                .unwrap();
714        }
715        drop(tx);
716        writer.await.unwrap();
717
718        // Replay the stored traces into a fresh bandit (mirrors run.rs warm-start logic).
719        let mut bandit = StartRungBandit::new(50, 0.0); // c=0: pure exploitation
720        let stored = crate::store::load_all_traces(&db).unwrap();
721        assert_eq!(stored.len(), 60, "all traces must be stored");
722        for trace in &stored {
723            let ctx = ContextBucket::from_features(&trace.request.features);
724            bandit.feed_trace_attempts(&ctx, &trace.attempts);
725        }
726
727        // After warm-start: 60 rung-0 fails + 60 rung-1 passes → bandit prefers rung 1.
728        let prices = PriceTable::defaults();
729        let ladder = vec![HAIKU.to_owned(), SONNET.to_owned()];
730        let ctx = ContextBucket::from_features(&f);
731        assert_eq!(
732            bandit.choose_start(&ctx, &ladder, &prices),
733            1,
734            "warm-started bandit must prefer rung 1 after 60 fail/pass pairs"
735        );
736
737        // A context with different features sees no data — cold start, returns 0.
738        let mut f2 = Features::new(TaskKind::Chat);
739        f2.prompt_token_bucket = 7;
740        let ctx2 = ContextBucket::from_features(&f2);
741        assert_eq!(
742            bandit.choose_start(&ctx2, &ladder, &prices),
743            0,
744            "different context must be independent"
745        );
746
747        let _ = std::fs::remove_file(&db);
748    }
749
750    #[test]
751    fn beta_sampler_mean_matches_posterior_mean() {
752        let mut b = StartRungBandit::with_algorithm(0, 1.0, Algorithm::Thompson, 1.0, 0xDEADBEEF);
753        // Beta(8, 2): mean 0.8. 4000 draws give a tight empirical mean.
754        let ctx = ctx_code();
755        for _ in 0..7 {
756            b.observe(&ctx, 0, Verdict::Pass);
757        }
758        b.observe(&ctx, 0, Verdict::Fail);
759        // counts: pass 7, fail 1 → Beta(8, 2), mean 0.8.
760        let mean: f64 = (0..4000).map(|_| b.thompson_pass(&ctx, 0)).sum::<f64>() / 4000.0;
761        assert!(
762            (mean - 0.8).abs() < 0.03,
763            "Beta(8,2) sample mean should be ~0.8, got {mean}"
764        );
765        // Unobserved arm = Beta(1,1) uniform, mean 0.5.
766        let mean_u: f64 = (0..4000).map(|_| b.thompson_pass(&ctx, 5)).sum::<f64>() / 4000.0;
767        assert!(
768            (mean_u - 0.5).abs() < 0.03,
769            "uniform prior mean ~0.5, got {mean_u}"
770        );
771    }
772
773    #[test]
774    fn thompson_converges_to_skipping_a_hopeless_cheap_rung() {
775        let mut b = StartRungBandit::with_algorithm(10, 1.0, Algorithm::Thompson, 1.0, 42);
776        let ctx = ctx_code();
777        let ladder = vec![HAIKU.to_owned(), SONNET.to_owned()];
778        let prices = PriceTable::defaults();
779        // Rung 0 always fails, rung 1 always passes → starting at 1 is cheaper in expectation.
780        for _ in 0..80 {
781            b.observe(&ctx, 0, Verdict::Fail);
782            b.observe(&ctx, 1, Verdict::Pass);
783        }
784        let picks_rung1 = (0..100)
785            .filter(|_| b.choose_start_with_propensity(&ctx, &ladder, &prices).0 == 1)
786            .count();
787        assert!(
788            picks_rung1 >= 90,
789            "TS should overwhelmingly skip the hopeless cheap rung, picked rung 1 {picks_rung1}/100"
790        );
791    }
792
793    #[test]
794    fn discounting_adapts_after_a_distribution_flip() {
795        let ctx = ctx_code();
796        // History: rung 0 failed 200 times. Then the world flips: 40 recent passes.
797        let feed = |b: &mut StartRungBandit| {
798            for _ in 0..200 {
799                b.observe(&ctx, 0, Verdict::Fail);
800            }
801            for _ in 0..40 {
802                b.observe(&ctx, 0, Verdict::Pass);
803            }
804        };
805        let mut discounted = StartRungBandit::with_algorithm(10, 1.0, Algorithm::Thompson, 0.95, 7);
806        let mut undiscounted =
807            StartRungBandit::with_algorithm(10, 1.0, Algorithm::Thompson, 1.0, 7);
808        feed(&mut discounted);
809        feed(&mut undiscounted);
810        let p_disc = discounted.pass_estimate(&ctx, 0).unwrap();
811        let p_flat = undiscounted.pass_estimate(&ctx, 0).unwrap();
812        assert!(
813            p_disc > 0.7 && p_flat < 0.25,
814            "discounted tracks the flip (got {p_disc:.2}), undiscounted lags (got {p_flat:.2})"
815        );
816    }
817
818    #[test]
819    fn thompson_propensity_matches_empirical_selection_frequency() {
820        let mut b = StartRungBandit::with_algorithm(10, 1.0, Algorithm::Thompson, 1.0, 99);
821        let ctx = ctx_code();
822        let ladder = vec![HAIKU.to_owned(), SONNET.to_owned()];
823        let prices = PriceTable::defaults();
824        // Ambiguous data: rung 0 passes ~half the time → genuinely stochastic selection.
825        for _ in 0..20 {
826            b.observe(&ctx, 0, Verdict::Pass);
827            b.observe(&ctx, 0, Verdict::Fail);
828            b.observe(&ctx, 1, Verdict::Pass);
829        }
830        // Empirical frequency of each choice over many decisions vs the logged propensity.
831        let mut freq = std::collections::HashMap::new();
832        let mut props: Vec<(u32, f64)> = Vec::new();
833        for _ in 0..400 {
834            let (c, p) = b.choose_start_with_propensity(&ctx, &ladder, &prices);
835            *freq.entry(c).or_insert(0u32) += 1;
836            props.push((c, p.expect("thompson always logs a propensity")));
837        }
838        for (arm, count) in freq {
839            let empirical = f64::from(count) / 400.0;
840            let mean_logged: f64 = {
841                let logged: Vec<f64> = props
842                    .iter()
843                    .filter(|(c, _)| *c == arm)
844                    .map(|(_, p)| *p)
845                    .collect();
846                logged.iter().sum::<f64>() / logged.len() as f64
847            };
848            assert!(
849                (empirical - mean_logged).abs() < 0.15,
850                "arm {arm}: empirical {empirical:.2} vs logged propensity {mean_logged:.2}"
851            );
852        }
853    }
854
855    #[test]
856    fn pass_estimate_cold_and_warm() {
857        let mut b = StartRungBandit::with_algorithm(10, 1.0, Algorithm::Thompson, 1.0, 5);
858        let ctx = ctx_code();
859        assert!(
860            b.pass_estimate(&ctx, 0).is_none(),
861            "cold context: no estimate"
862        );
863        for _ in 0..12 {
864            b.observe(&ctx, 0, Verdict::Pass);
865        }
866        let p = b.pass_estimate(&ctx, 0).expect("warm");
867        assert!(p > 0.85, "12/12 passes: posterior mean high, got {p}");
868        assert!(
869            b.pass_estimate(&ctx, 3).is_none(),
870            "unobserved arm: no estimate"
871        );
872    }
873
874    /// The prompt-size band must invert to a monotonically increasing token estimate, since the
875    /// whole point is that a bigger request implies a costlier cheap attempt.
876    #[test]
877    fn representative_tokens_grow_with_the_prompt_band() {
878        let sizes: Vec<u64> = (0..5)
879            .map(|b| {
880                ContextBucket {
881                    difficulty_hint: 0,
882                    task_kind: TaskKind::CodeEdit,
883                    prompt_bucket_coarse: b,
884                }
885                .representative_prompt_tokens()
886            })
887            .collect();
888        assert!(
889            sizes.windows(2).all(|w| w[1] > w[0]),
890            "estimate must be strictly increasing in the band, got {sizes:?}"
891        );
892        // And bounded, so a pathological bucket cannot price a request absurdly.
893        let huge = ContextBucket {
894            difficulty_hint: 0,
895            task_kind: TaskKind::CodeEdit,
896            prompt_bucket_coarse: u32::MAX,
897        };
898        assert!(huge.representative_prompt_tokens() <= 1 << 20);
899    }
900
901    /// The behaviour the fixed nominal token count made impossible.
902    ///
903    /// Two contexts with **identical** gate statistics but different prompt sizes must be allowed
904    /// to reach different start rungs, because `start cheap ⟺ c₀ < p·c₁` scales both sides with
905    /// request size. Under the old constant-token pricing the ratio `c₀/c₁` was the same for every
906    /// request, so this decision could only ever depend on `p` — and the measured 2.16× adverse
907    /// selection was invisible to it.
908    ///
909    /// A cheap rung that is *not* meaningfully cheaper than the top rung should not be attempted
910    /// when its pass rate is poor; here the ladder is deliberately shallow so that the marginal
911    /// call is decided by price, which is exactly the regime this fix targets.
912    #[test]
913    fn start_rung_can_depend_on_request_size_not_just_pass_rate() {
914        let prices = PriceTable::defaults();
915        let ladder = vec![HAIKU.to_owned(), SONNET.to_owned()];
916
917        // Identical statistics, applied to a small and a large prompt band.
918        let mut small = StartRungBandit::new(4, 0.0);
919        let mut large = StartRungBandit::new(4, 0.0);
920        let c_small = ContextBucket {
921            difficulty_hint: 0,
922            task_kind: TaskKind::CodeEdit,
923            prompt_bucket_coarse: 1,
924        };
925        let c_large = ContextBucket {
926            difficulty_hint: 0,
927            task_kind: TaskKind::CodeEdit,
928            prompt_bucket_coarse: 8,
929        };
930        for _ in 0..10 {
931            small.observe(&c_small, 0, Verdict::Fail);
932            small.observe(&c_small, 1, Verdict::Pass);
933            large.observe(&c_large, 0, Verdict::Fail);
934            large.observe(&c_large, 1, Verdict::Pass);
935        }
936
937        // Both should skip the hopeless cheap rung; the point of the test is that the decision is
938        // now computed from a size-scaled price rather than a constant, so the two contexts price
939        // the same ladder differently.
940        assert_eq!(small.choose_start(&c_small, &ladder, &prices), 1);
941        assert_eq!(large.choose_start(&c_large, &ladder, &prices), 1);
942        assert!(
943            c_large.representative_prompt_tokens() > c_small.representative_prompt_tokens() * 8,
944            "the large context must price the same ladder materially higher"
945        );
946    }
947}