metrale_bench/benchmarks/kat_equality/
compare.rs

1// SPDX-License-Identifier: MIT OR Apache-2.0
2
3//! 2026-09-26: Given what each order produced, decide whether every reply is a
4//! function of its own request. The driver does the requests; this module does
5//! no I/O, so the tests construct each failure without a server.
6//!
7//! Owner: bench, kat_equality.
8//! Invariants:
9//! - `verdict` passes only with at least two orders, at least one sample, not
10//!   every reference reply empty, and every sample `Equal`.
11
12use crate::benchmarks::transcript::RequestOutcome;
13
14/// 2026-09-26: The order a sample set is issued in, as indices into it.
15///
16/// Deterministic and RNG-free, so a failing run can be re-run to reproduce it.
17/// Order 0 is the order `dataset::load_shard` returns, which is also the
18/// order the BFCL benchmark issues its draw in.
19/// Order 1 is the reverse, which changes what preceded every sample. Further
20/// orders are rotations; for `len >= 2` none of them is order 0.
21pub fn permutation(index: usize, len: usize) -> Vec<usize> {
22    match index {
23        0 => (0..len).collect(),
24        1 => (0..len).rev().collect(),
25        k if len == 0 => {
26            let _ = k;
27            Vec::new()
28        }
29        k => {
30            // 2026-09-26: The shift is forced into 1..len, so for len >= 2 no
31            // rotation is order 0.
32            let shift = (k * len / (k + 1)).max(1) % len.max(1);
33            let shift = if shift == 0 { 1 } else { shift };
34            (0..len).map(|i| (i + shift) % len).collect()
35        }
36    }
37}
38
39/// 2026-09-26: What one sample produced under one order.
40#[derive(Debug, Clone)]
41pub struct Observation {
42    pub sample_id: String,
43    pub outcome: RequestOutcome,
44}
45
46/// 2026-09-26: One full pass over the sample set, in one order.
47#[derive(Debug, Clone)]
48pub struct OrderRun {
49    /// 2026-09-26: The order's name (`canonical`, `reversed`, `rotation-<k>`),
50    /// for the failure message.
51    pub label: String,
52    /// 2026-09-26: In issue order. Lookups go through `sample_id`, so the
53    /// storage order is not an index.
54    pub observations: Vec<Observation>,
55}
56
57impl OrderRun {
58    fn find(&self, sample_id: &str) -> Option<&Observation> {
59        self.observations.iter().find(|o| o.sample_id == sample_id)
60    }
61}
62
63/// 2026-09-26: What happened to one `sample_id` across every order.
64#[derive(Debug, Clone, PartialEq, Eq)]
65pub enum SampleVerdict {
66    /// 2026-09-26: Byte-identical everywhere, with equal completion-token
67    /// counts. The only passing outcome.
68    Equal,
69    /// 2026-09-26: Differs from the reference order in `other_order`, the
70    /// first order that differs.
71    Diverged {
72        other_order: String,
73        /// 2026-09-26: Bytes of `canonical()` that matched before the first
74        /// difference.
75        common_prefix: usize,
76    },
77    /// 2026-09-26: A request failed, or the sample is missing from an order. A
78    /// failure is evidence of neither equality nor inequality, so it is never
79    /// counted as agreement.
80    Unmeasured(String),
81}
82
83/// 2026-09-26: The reduction the verdict and the report both read.
84#[derive(Debug, Clone, Default)]
85pub struct Score {
86    pub orders: usize,
87    pub samples: usize,
88    pub equal: usize,
89    pub diverged: usize,
90    pub unmeasured: usize,
91    /// 2026-09-26: At most `NAMED_DIVERGENCES` ids, for the verdict string.
92    pub diverged_ids: Vec<String>,
93    /// 2026-09-26: Reference-order replies whose `canonical()` has no
94    /// character at or above U+0020: nothing was said. A server that answers
95    /// every request with nothing is equal across orders, so `verdict` fails a
96    /// run where every reply is empty.
97    pub empty_replies: usize,
98}
99
100/// 2026-09-26: How many diverged ids a verdict names before it stops.
101const NAMED_DIVERGENCES: usize = 8;
102
103/// 2026-09-26: Compare every sample of order 0 against every other order.
104/// Order 0 is the reference.
105pub fn score(runs: &[OrderRun]) -> Score {
106    let mut s = Score {
107        orders: runs.len(),
108        ..Default::default()
109    };
110    let Some(reference) = runs.first() else {
111        return s;
112    };
113    s.samples = reference.observations.len();
114    for obs in &reference.observations {
115        match verdict_for(&obs.sample_id, reference, &runs[1..]) {
116            SampleVerdict::Equal => s.equal += 1,
117            SampleVerdict::Diverged { .. } => {
118                s.diverged += 1;
119                if s.diverged_ids.len() < NAMED_DIVERGENCES {
120                    s.diverged_ids.push(obs.sample_id.clone());
121                }
122            }
123            SampleVerdict::Unmeasured(_) => s.unmeasured += 1,
124        }
125        if let RequestOutcome::Ok(t) = &obs.outcome
126            && t.canonical().chars().all(|c| (c as u32) < 0x20)
127        {
128            // 2026-09-26: Only separators and other control characters.
129            s.empty_replies += 1;
130        }
131    }
132    s
133}
134
135/// 2026-09-26: One sample's verdict across the non-reference orders.
136pub fn verdict_for(sample_id: &str, reference: &OrderRun, others: &[OrderRun]) -> SampleVerdict {
137    let Some(base) = reference.find(sample_id) else {
138        return SampleVerdict::Unmeasured(format!("{sample_id} missing from the reference order"));
139    };
140    let RequestOutcome::Ok(base_t) = &base.outcome else {
141        let RequestOutcome::Error(e) = &base.outcome else {
142            unreachable!("RequestOutcome has two variants")
143        };
144        return SampleVerdict::Unmeasured(format!("reference order: {e}"));
145    };
146    let base_c = base_t.canonical();
147    for other in others {
148        let Some(obs) = other.find(sample_id) else {
149            return SampleVerdict::Unmeasured(format!("{sample_id} missing from {}", other.label));
150        };
151        let RequestOutcome::Ok(t) = &obs.outcome else {
152            let RequestOutcome::Error(e) = &obs.outcome else {
153                unreachable!("RequestOutcome has two variants")
154            };
155            return SampleVerdict::Unmeasured(format!("{}: {e}", other.label));
156        };
157        let c = t.canonical();
158        // 2026-09-26: `completion_tokens` is compared too: a reply can be
159        // byte-identical as text while the server disagrees about how many
160        // tokens it emitted, and that is a real difference in what ran.
161        if c != base_c || t.completion_tokens != base_t.completion_tokens {
162            return SampleVerdict::Diverged {
163                other_order: other.label.clone(),
164                common_prefix: common_prefix_len(&base_c, &c),
165            };
166        }
167    }
168    SampleVerdict::Equal
169}
170
171fn common_prefix_len(a: &str, b: &str) -> usize {
172    a.bytes().zip(b.bytes()).take_while(|(x, y)| x == y).count()
173}
174
175/// 2026-09-26: The gate's rule, in order. Anything not proven equal fails.
176pub fn verdict(s: &Score) -> crate::result::Verdict {
177    use crate::result::Verdict;
178    if s.orders < 2 {
179        return Verdict::fail(format!(
180            "EQUALITY UNPROVEN: {} order(s) ran. Equality is a claim about TWO orders; \
181             one order compares with nothing.",
182            s.orders
183        ));
184    }
185    if s.samples == 0 {
186        return Verdict::fail(
187            "EQUALITY UNPROVEN: the reference order issued no samples, so nothing was compared."
188                .to_string(),
189        );
190    }
191    // 2026-09-26: Before believing any equality result, refuse a run that could
192    // not have seen a difference: a server answering every request with
193    // nothing is byte-identical across every order.
194    if s.empty_replies == s.samples {
195        return Verdict::fail(format!(
196            "EQUALITY VACUOUS: all {} replies were empty, so every order agrees trivially. \
197             This proves the harness ran, not that the server is order-independent.",
198            s.samples
199        ));
200    }
201    if s.unmeasured > 0 {
202        return Verdict::fail(format!(
203            "EQUALITY UNPROVEN: {} of {} samples were unmeasured (a failed request is not \
204             evidence of agreement).",
205            s.unmeasured, s.samples
206        ));
207    }
208    if s.diverged > 0 {
209        let named = s.diverged_ids.join(", ");
210        let more = s.diverged.saturating_sub(s.diverged_ids.len());
211        let tail = if more > 0 {
212            format!(" (+{more} more)")
213        } else {
214            String::new()
215        };
216        return Verdict::fail(format!(
217            "ORDER-DEPENDENT: {} of {} samples changed when the request ORDER changed — \
218             {named}{tail}. At temperature 0 a sample's reply must be a function of that \
219             sample. A benchmark built on this cannot be sharded, and a score taken under \
220             one order does not describe another.",
221            s.diverged, s.samples
222        ));
223    }
224    crate::result::Verdict::pass(format!(
225        "{} samples byte-identical across {} request orders",
226        s.samples, s.orders
227    ))
228}
metrale_bench/benchmarks/kat_equality/compare.rs

metrale_bench/benchmarks/kat_equality/
compare.rs
