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