Skip to main content

spider_optimize/
gate.rs

1//! Whether any candidate is worth applying.
2//!
3//! [`choose`] scores keep and every valid candidate, ranks the candidates by
4//! credits per successful result, and applies the best one only when it
5//! clears every threshold in [`Gate`]. Any doubt keeps the request as it is:
6//! no model, a NaN anywhere, too little evidence, too little gain, or a caller
7//! who fixed the mode, pool or country.
8//!
9//! That last guard matches the client's explorer. A caller who pinned any of
10//! the three has said how the request should be sent, and an edit to what is
11//! left would be attributed to settings the caller chose.
12
13use crate::candidates::{multiplier, Candidate, Context};
14use crate::edit::EditSet;
15use crate::features::{featurize_edit, Input};
16use crate::model::{Score, Scorer};
17use crate::schema::{Key, Schema};
18use crate::validate::validate;
19use spider_route::{featurize, RouteInput};
20use std::cmp::Ordering;
21
22/// The thresholds a candidate has to clear.
23#[derive(Debug, Clone, Copy, PartialEq)]
24pub struct Gate {
25    /// The lowest success chance a candidate may have.
26    pub min_p_success: f32,
27    /// How much lower, as a fraction of keep's, a candidate's credits per
28    /// success must be.
29    pub min_gain: f32,
30    /// The least evidence a candidate's estimate may rest on.
31    pub min_support: f32,
32    /// The dearest multiplier a candidate may have.
33    pub max_multiplier: f32,
34}
35
36impl Default for Gate {
37    fn default() -> Gate {
38        Gate {
39            min_p_success: 0.9,
40            min_gain: 0.05,
41            min_support: 1.0,
42            max_multiplier: 8.0,
43        }
44    }
45}
46
47/// Why the request was kept.
48#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
49pub enum Reason {
50    /// The scorer has no weights.
51    NoModel,
52    /// A score was NaN, or no candidate had enough support.
53    NoEvidence,
54    /// There was nothing but keep to choose from.
55    NoCandidates,
56    /// No candidate beat keep by enough.
57    NoGain,
58    /// No candidate cleared the success floor.
59    BelowFloor,
60    /// No candidate got through: each one failed validation, cost more than
61    /// the gate allows, sat under the success floor, or had too little
62    /// support, and none of the held back ones would have beaten keep.
63    Unsupported,
64    /// The caller fixed the mode, the pool or the country.
65    Pinned,
66}
67
68/// What to do with the request.
69#[derive(Debug, Clone, PartialEq)]
70pub enum Choice {
71    /// Send it as it is.
72    Keep(Reason),
73    /// Apply these edits.
74    Apply {
75        /// The edits.
76        edits: EditSet,
77        /// The candidate's score.
78        expected: Score,
79        /// Keep's score.
80        baseline: Score,
81    },
82}
83
84/// One scored candidate.
85#[derive(Clone, Copy)]
86struct Ranked<'c> {
87    candidate: &'c Candidate,
88    score: Score,
89    objective: f32,
90}
91
92/// Credits per successful result. Lower is better; no chance of success is
93/// infinitely expensive.
94fn objective(score: &Score) -> f32 {
95    if score.p_success > 0.0 {
96        score.credits / score.p_success
97    } else {
98        f32::INFINITY
99    }
100}
101
102/// Pick the edit to apply, or the reason to keep the request.
103///
104/// Deterministic, and allocates nothing unless it returns
105/// [`Choice::Apply`], which owns a copy of the chosen edits.
106pub fn choose(scorer: &dyn Scorer, ctx: &Context<'_>, cands: &[Candidate], gate: &Gate) -> Choice {
107    if ctx.caller.is_set(Key::Request)
108        || ctx.caller.is_set(Key::Proxy)
109        || ctx.caller.is_set(Key::CountryCode)
110    {
111        return Choice::Keep(Reason::Pinned);
112    }
113    if scorer.version().is_none() {
114        return Choice::Keep(Reason::NoModel);
115    }
116
117    let schema = Schema::v1();
118    let offered = cands.iter().filter(|c| !c.edits.is_keep());
119    if offered.clone().next().is_none() {
120        return Choice::Keep(Reason::NoCandidates);
121    }
122
123    // The router's features for the request as the router saw it. The caller
124    // pinned nothing, or this would have returned above.
125    let mut route = RouteInput::new(ctx.url, ctx.need);
126    if let Some(memory) = &ctx.observation.memory {
127        route = route.with_memory(memory);
128    }
129    let base = featurize(&route);
130
131    let keep = Candidate {
132        edits: EditSet::keep(),
133        multiplier: multiplier(ctx, &EditSet::keep()),
134    };
135    let baseline = scorer.score(&Input {
136        base,
137        edit: featurize_edit(ctx, &keep),
138    });
139    if baseline.has_nan() {
140        return Choice::Keep(Reason::NoEvidence);
141    }
142    let baseline_objective = objective(&baseline);
143
144    let mut best: Option<Ranked<'_>> = None;
145    // Set when a candidate that would have beaten keep was held back, so the
146    // reason names what stopped a gain rather than the gain that was left.
147    let mut below_floor = false;
148    let mut thin = false;
149
150    for candidate in offered {
151        if validate(&schema, ctx, candidate).is_err() {
152            continue;
153        }
154        if multiplier(ctx, &candidate.edits) > gate.max_multiplier {
155            continue;
156        }
157
158        let score = scorer.score(&Input {
159            base,
160            edit: featurize_edit(ctx, candidate),
161        });
162        if score.has_nan() {
163            return Choice::Keep(Reason::NoEvidence);
164        }
165        let ranked = Ranked {
166            candidate,
167            score,
168            objective: objective(&score),
169        };
170        if score.p_success < gate.min_p_success || score.p_success < baseline.p_success - 0.01 {
171            below_floor |= beats(&ranked, &baseline, baseline_objective, gate);
172            continue;
173        }
174        if score.support < gate.min_support {
175            thin |= beats(&ranked, &baseline, baseline_objective, gate);
176            continue;
177        }
178
179        // Strictly better only, so on a tie the earlier candidate stands.
180        let better = match &best {
181            None => true,
182            Some(seen) => match ranked.objective.partial_cmp(&seen.objective) {
183                Some(Ordering::Less) => true,
184                Some(Ordering::Equal) => ranked.score.latency_ms < seen.score.latency_ms,
185                _ => false,
186            },
187        };
188        if better {
189            best = Some(ranked);
190        }
191    }
192
193    match best {
194        Some(best) if beats(&best, &baseline, baseline_objective, gate) => Choice::Apply {
195            edits: best.candidate.edits.clone(),
196            expected: best.score,
197            baseline,
198        },
199        _ if below_floor => Choice::Keep(Reason::BelowFloor),
200        _ if thin => Choice::Keep(Reason::NoEvidence),
201        Some(_) => Choice::Keep(Reason::NoGain),
202        None => Choice::Keep(Reason::Unsupported),
203    }
204}
205
206/// Whether a candidate beats keep. Keep wins every tie: a candidate has to be
207/// cheaper per success by the gain, or exactly as cheap and faster when no
208/// gain is required.
209fn beats(ranked: &Ranked<'_>, baseline: &Score, baseline_objective: f32, gate: &Gate) -> bool {
210    match ranked.objective.partial_cmp(&baseline_objective) {
211        Some(Ordering::Less) => ranked.objective <= baseline_objective * (1.0 - gate.min_gain),
212        Some(Ordering::Equal) => {
213            gate.min_gain <= 0.0 && ranked.score.latency_ms < baseline.latency_ms
214        }
215        _ => false,
216    }
217}
218
219#[cfg(test)]
220mod tests {
221    #![allow(
222        clippy::unwrap_used,
223        clippy::expect_used,
224        clippy::panic,
225        clippy::unreachable,
226        clippy::indexing_slicing,
227        clippy::string_slice
228    )]
229    use super::*;
230    use crate::candidates::generate;
231    use crate::features::EDIT_KEY;
232    use crate::model::{ModelVersion, NoModel};
233    use crate::schema::learnable_slot;
234    use crate::testing::Fixture;
235    use spider_route::{Country, ProxyPool, RequestMode};
236
237    /// A scorer that answers by which learnable key the edit touches, read
238    /// back out of the features, with keep's score for keep.
239    struct ByKey {
240        keep: Score,
241        keyed: Vec<(Key, Score)>,
242    }
243
244    impl Scorer for ByKey {
245        fn score(&self, input: &Input) -> Score {
246            for (key, score) in &self.keyed {
247                let slot = EDIT_KEY + learnable_slot(*key).unwrap();
248                if input.edit.get(slot) == Some(1.0) {
249                    return *score;
250                }
251            }
252            self.keep
253        }
254
255        fn version(&self) -> Option<ModelVersion> {
256            Some(ModelVersion(1))
257        }
258    }
259
260    const fn score(p_success: f32, latency_ms: f32, credits: f32, support: f32) -> Score {
261        Score {
262            p_success,
263            latency_ms,
264            credits,
265            support,
266        }
267    }
268
269    /// Keep costs 4 credits at 0.95; blocking ads costs 2 at 0.96.
270    fn cheaper_block() -> ByKey {
271        ByKey {
272            keep: score(0.95, 900.0, 4.0, 50.0),
273            keyed: vec![(Key::BlockAds, score(0.96, 800.0, 2.0, 50.0))],
274        }
275    }
276
277    fn run(scorer: &dyn Scorer, fixture: &Fixture, gate: &Gate) -> Choice {
278        let ctx = fixture.ctx();
279        let cands = generate(&Schema::v1(), &ctx);
280        choose(scorer, &ctx, &cands, gate)
281    }
282
283    #[test]
284    fn a_confident_cheaper_candidate_is_applied() {
285        let choice = run(&cheaper_block(), &Fixture::observed(), &Gate::default());
286        let Choice::Apply {
287            edits,
288            expected,
289            baseline,
290        } = choice
291        else {
292            panic!("expected an edit, got {choice:?}");
293        };
294        assert_eq!(edits.edits().len(), 1);
295        assert_eq!(edits.edits()[0].key, Key::BlockAds);
296        assert_eq!(expected.credits, 2.0);
297        assert_eq!(baseline.credits, 4.0);
298    }
299
300    #[test]
301    fn no_model_always_keeps() {
302        for fixture in [Fixture::cold(), Fixture::observed()] {
303            assert_eq!(
304                run(&NoModel, &fixture, &Gate::default()),
305                Choice::Keep(Reason::NoModel)
306            );
307        }
308        let ctx = Fixture::cold();
309        let ctx = ctx.ctx();
310        assert_eq!(
311            choose(
312                &cheaper_block(),
313                &ctx,
314                &[Candidate::keep(&ctx)],
315                &Gate::default()
316            ),
317            Choice::Keep(Reason::NoCandidates)
318        );
319    }
320
321    #[test]
322    fn a_gate_never_applies_below_the_success_floor() {
323        let fixture = Fixture::observed();
324        let gate = Gate::default();
325
326        // Cheaper, well supported, and under the floor.
327        let under = ByKey {
328            keep: score(0.95, 900.0, 4.0, 50.0),
329            keyed: vec![(Key::BlockAds, score(0.89, 800.0, 1.0, 50.0))],
330        };
331        assert_eq!(
332            run(&under, &fixture, &gate),
333            Choice::Keep(Reason::BelowFloor)
334        );
335
336        // Over the floor, and more than a point worse than keep.
337        let worse = ByKey {
338            keep: score(0.99, 900.0, 4.0, 50.0),
339            keyed: vec![(Key::BlockAds, score(0.97, 800.0, 1.0, 50.0))],
340        };
341        assert_eq!(
342            run(&worse, &fixture, &gate),
343            Choice::Keep(Reason::BelowFloor)
344        );
345
346        // Enough of a gain but too little evidence.
347        let thin = ByKey {
348            keep: score(0.95, 900.0, 4.0, 50.0),
349            keyed: vec![(Key::BlockAds, score(0.96, 800.0, 1.0, 0.5))],
350        };
351        assert_eq!(
352            run(&thin, &fixture, &gate),
353            Choice::Keep(Reason::NoEvidence)
354        );
355
356        // Too little gain.
357        let marginal = ByKey {
358            keep: score(0.95, 900.0, 4.0, 50.0),
359            keyed: vec![(Key::BlockAds, score(0.95, 800.0, 3.9, 50.0))],
360        };
361        assert_eq!(
362            run(&marginal, &fixture, &gate),
363            Choice::Keep(Reason::NoGain)
364        );
365    }
366
367    #[test]
368    fn keep_wins_ties() {
369        let same = score(0.95, 900.0, 4.0, 50.0);
370        let tied = ByKey {
371            keep: same,
372            keyed: vec![(Key::BlockAds, same)],
373        };
374        let no_gain_needed = Gate {
375            min_gain: 0.0,
376            ..Gate::default()
377        };
378        assert_eq!(
379            run(&tied, &Fixture::observed(), &no_gain_needed),
380            Choice::Keep(Reason::NoGain)
381        );
382
383        // The same objective and faster does win when no gain is required,
384        // so the tie above is decided by keep and not by the objective alone.
385        let faster = ByKey {
386            keep: same,
387            keyed: vec![(Key::BlockAds, score(0.95, 100.0, 4.0, 50.0))],
388        };
389        assert!(matches!(
390            run(&faster, &Fixture::observed(), &no_gain_needed),
391            Choice::Apply { .. }
392        ));
393    }
394
395    #[test]
396    fn nan_scores_abstain() {
397        let fixture = Fixture::observed();
398        let gate = Gate::default();
399        let nan_keep = ByKey {
400            keep: score(f32::NAN, 900.0, 4.0, 50.0),
401            keyed: vec![(Key::BlockAds, score(0.99, 800.0, 1.0, 50.0))],
402        };
403        assert_eq!(
404            run(&nan_keep, &fixture, &gate),
405            Choice::Keep(Reason::NoEvidence)
406        );
407
408        let nan_candidate = ByKey {
409            keep: score(0.95, 900.0, 4.0, 50.0),
410            keyed: vec![
411                (Key::BlockAds, score(0.99, 800.0, 1.0, 50.0)),
412                (Key::FullResources, score(0.99, 800.0, f32::NAN, 50.0)),
413            ],
414        };
415        assert_eq!(
416            run(&nan_candidate, &fixture, &gate),
417            Choice::Keep(Reason::NoEvidence)
418        );
419    }
420
421    #[test]
422    fn a_pinned_request_is_never_edited() {
423        let gate = Gate::default();
424
425        let mut mode = Fixture::observed();
426        mode.caller.request = Some(RequestMode::Smart);
427        let mut pool = Fixture::observed();
428        pool.caller.proxy = Some(ProxyPool::Isp);
429        let mut country = Fixture::observed();
430        country.caller.country_code = Country::new("de");
431
432        for fixture in [mode, pool, country] {
433            assert_eq!(
434                run(&cheaper_block(), &fixture, &gate),
435                Choice::Keep(Reason::Pinned)
436            );
437        }
438        // The same scorer edits the unpinned request, so the guard is what
439        // kept these.
440        assert!(matches!(
441            run(&cheaper_block(), &Fixture::observed(), &gate),
442            Choice::Apply { .. }
443        ));
444    }
445
446    #[test]
447    fn a_candidate_dearer_than_the_gate_is_passed_over() {
448        let fixture = Fixture::observed();
449        let browser = ByKey {
450            keep: score(0.95, 900.0, 4.0, 50.0),
451            keyed: vec![(Key::Request, score(0.99, 800.0, 1.0, 50.0))],
452        };
453        let strict = Gate {
454            max_multiplier: 1.5,
455            ..Gate::default()
456        };
457        // Only http survives the gate's cap, and the scorer prices it the
458        // same as browser, so it is applied.
459        let Choice::Apply { edits, .. } = run(&browser, &fixture, &strict) else {
460            panic!("expected the plain fetch");
461        };
462        assert_eq!(
463            edits.edits()[0],
464            crate::edit::Edit::set(Key::Request, crate::edit::Value::Mode(RequestMode::Http))
465        );
466    }
467}