detector.js

/* A faithful JavaScript port of flashback/bisect.py.
 *
 * Hugging Face hosts static Spaces free for everyone but charges for Gradio
 * ones, so the public demo runs the detector in the browser.  A port is only
 * worth anything if it agrees with the original, so every function below
 * mirrors a named Python function, and index.html checks the results against
 * the answers Python computed for the same data (shipped in data/*.json).
 *
 * Python's numeric conventions that matter here:
 *   - np.nanmedian ignores non-finite entries in a window
 *   - np.percentile uses linear interpolation
 *   - non-finite metric values mean "bad" and score +Infinity
 */

export const MAD_TO_SIGMA = 1.4826;
export const HARD_SIGNALS = new Set([
  "nonfinite_grad", "nonfinite_param", "group:all:nonfinite",
]);

function median(sorted) {
  const n = sorted.length;
  if (n === 0) return NaN;
  const m = n >> 1;
  return n % 2 ? sorted[m] : 0.5 * (sorted[m - 1] + sorted[m]);
}

function medianOf(values) {
  const f = [];
  for (const v of values) if (Number.isFinite(v)) f.push(v);
  f.sort((a, b) => a - b);
  return median(f);
}

/** numpy.percentile(a, q) with the default 'linear' method. */
function percentile(sortedAsc, q) {
  const n = sortedAsc.length;
  if (n === 0) return NaN;
  const pos = (q / 100) * (n - 1);
  const lo = Math.floor(pos), hi = Math.ceil(pos);
  if (lo === hi) return sortedAsc[lo];
  return sortedAsc[lo] + (sortedAsc[hi] - sortedAsc[lo]) * (pos - lo);
}

/** Port of flashback.bisect.prepare_series. */
export function prepareSeries(x, mode = "diff") {
  const n = x.length;
  if (mode === "level" || n < 3) return Float64Array.from(x);
  let work = Float64Array.from(x);
  let allPositive = true, any = false, mn = Infinity, mx = -Infinity;
  for (const v of x) {
    if (!Number.isFinite(v)) continue;
    any = true;
    if (v <= 0) allPositive = false;
    if (v < mn) mn = v;
    if (v > mx) mx = v;
  }
  if (any && allPositive) {
    const span = mx / Math.max(mn, 1e-300);
    if (span > 100) for (let i = 0; i < n; i++) work[i] = Math.log(Math.max(work[i], 1e-300));
  }
  const d = new Float64Array(n);
  for (let i = 1; i < n; i++) d[i] = work[i] - work[i - 1];
  // A step whose *original* value is non-finite stays non-finite, so the
  // hard-signal and nonfinite_is_bad paths still see it.
  for (let i = 0; i < n; i++) if (!Number.isFinite(x[i])) d[i] = Infinity;
  return d;
}

/** Port of flashback.bisect.rolling_z. Returns {z, ok}. */
export function rollingZ(series, win = 64, gap = 1,
                         relFloor = 1e-3, globalFloorFrac = 1e-2, absFloor = 1e-12) {
  const n = series.length;
  const z = new Float64Array(n);
  const ok = new Uint8Array(n);
  if (n < win + gap + 2) return { z, ok };

  let gmax = 0;
  for (const v of series) if (Number.isFinite(v)) gmax = Math.max(gmax, Math.abs(v));
  const floor = Math.max(gmax * globalFloorFrac, absFloor);

  for (let i = win + gap; i < n; i++) {
    const start = i - gap - win;
    const w = [];
    for (let j = start; j < start + win; j++) if (Number.isFinite(series[j])) w.push(series[j]);
    let center = 0, scale = 0;
    if (w.length) {
      w.sort((a, b) => a - b);
      center = median(w);
      const dev = w.map((v) => Math.abs(v - center)).sort((a, b) => a - b);
      scale = median(dev) * MAD_TO_SIGMA;
    }
    if (!Number.isFinite(center)) center = 0;
    if (!Number.isFinite(scale)) scale = 0;
    scale = Math.max(scale, Math.max(Math.abs(center) * relFloor, floor));
    const x = series[i];
    let zi = Number.isFinite(x) ? (x - center) / scale : Infinity;
    if (Number.isNaN(zi)) zi = 0;
    z[i] = zi;
    ok[i] = 1;
  }
  return { z, ok };
}

/** Port of flashback.bisect.calibrate (healthy_upto is unused by the demo). */
export function calibrate(z, ok, kCal = 12.0, kMin = 8.0) {
  const a = [];
  for (let i = 0; i < z.length; i++) {
    if (!ok[i]) continue;
    const v = Math.abs(z[i]);
    if (Number.isFinite(v)) a.push(v);
  }
  if (a.length < 8) return { threshold: Infinity, usable: false };
  a.sort((x, y) => x - y);
  const med = median(a);
  const dev = a.map((v) => Math.abs(v - med)).sort((x, y) => x - y);
  let sc = median(dev) * MAD_TO_SIGMA;
  if (!(sc > 0)) sc = (percentile(a, 90) - med) || 1.0;
  return { threshold: Math.max(kMin, med + kCal * sc), usable: true, median: med, scale: sc };
}

/** Port of flashback.bisect.detect_on_series (two_sided, min_run=1). */
export function detectOnSeries(raw, steps, spec, opts = {}) {
  const { win = 32, gap = 1, mode = "diff", kCal = 12.0, kMin = 8.0 } = opts;
  const n = raw.length;

  if (HARD_SIGNALS.has(spec)) {
    for (let i = 0; i < n; i++) {
      if ((Number.isFinite(raw[i]) && raw[i] > 0) || !Number.isFinite(raw[i])) {
        return { detected: true, index: i, step: steps[i], z: Infinity, threshold: 0, spec };
      }
    }
    return { detected: false, spec, threshold: 0 };
  }

  const w = Math.max(8, Math.min(win, Math.max(8, Math.floor(n / 4))));
  const { z, ok } = rollingZ(prepareSeries(raw, mode), w, gap);
  const prof = calibrate(z, ok, kCal, kMin);
  if (!prof.usable) return { detected: false, spec, threshold: prof.threshold };
  for (let i = 0; i < n; i++) {
    if (!ok[i]) continue;
    const zz = Math.abs(z[i]);
    if (zz > prof.threshold || !Number.isFinite(raw[i])) {
      return { detected: true, index: i, step: steps[i],
               z: Number.isFinite(raw[i]) ? zz : Infinity,
               threshold: prof.threshold, spec };
    }
  }
  return { detected: false, spec, threshold: prof.threshold };
}

/** |z| series for plotting, matching what detectOnSeries scores. */
export function zSeries(raw, spec, opts = {}) {
  const { win = 32, gap = 1, mode = "diff" } = opts;
  const n = raw.length;
  if (HARD_SIGNALS.has(spec)) {
    const z = new Float64Array(n), ok = new Uint8Array(n);
    for (let i = 0; i < n; i++) {
      ok[i] = 1;
      z[i] = ((Number.isFinite(raw[i]) && raw[i] > 0) || !Number.isFinite(raw[i])) ? Infinity : 0;
    }
    return { z, ok, threshold: 0 };
  }
  const w = Math.max(8, Math.min(win, Math.max(8, Math.floor(n / 4))));
  const { z, ok } = rollingZ(prepareSeries(raw, mode), w, gap);
  const az = new Float64Array(n);
  for (let i = 0; i < n; i++) az[i] = Number.isFinite(raw[i]) ? Math.abs(z[i]) : Infinity;
  const prof = calibrate(z, ok, opts.kCal ?? 12.0, opts.kMin ?? 8.0);
  return { z: az, ok, threshold: prof.threshold };
}

/**
 * Port of flashback.bisect.bisect_first_bad(metric="auto", strategy="scan").
 * Returns the earliest step at which `minVotes` metrics agree within
 * `voteWindow`, falling back to the earliest single detection unless
 * `requireConsensus`.
 */
export function bisectFirstBad(table, steps, specs, opts = {}) {
  const { minVotes = 3, voteWindow = 4, requireConsensus = false } = opts;
  const dets = [];
  for (const spec of specs) {
    const s = table[spec];
    if (!s) continue;
    const d = detectOnSeries(s, steps, spec, opts);
    if (d.detected) dets.push(d);
  }
  const indexReads = steps.length * specs.length;
  if (!dets.length) {
    return { step: null, votes: 0, metric: "auto", indexReads, stateProbes: 0,
             candidates: [], note: "no metric crossed threshold" };
  }
  dets.sort((a, b) => (a.index - b.index) || (b.z - a.z));
  const idxs = dets.map((d) => d.index);
  for (const d of dets) {
    const votes = idxs.filter((i) => i >= d.index && i <= d.index + voteWindow).length;
    if (votes >= minVotes) {
      return { step: d.step, index: d.index, metric: d.spec, z: d.z,
               threshold: d.threshold, votes, indexReads, stateProbes: 0,
               candidates: dets, note: "" };
    }
  }
  const note = `no ${minVotes}-metric consensus; reporting earliest single detection`;
  if (requireConsensus) {
    return { step: null, votes: 0, metric: "auto", indexReads, stateProbes: 0,
             candidates: dets, note: note + " (suppressed: require consensus)" };
  }
  const b = dets[0];
  return { step: b.step, index: b.index, metric: b.spec, z: b.z, threshold: b.threshold,
           votes: 1, indexReads, stateProbes: 0, candidates: dets, note };
}

/**
 * The `git bisect` predicate: has anything gone wrong at or *before* this step?
 * Only the cumulative form is monotone -- "is THIS step bad?" is false again
 * one step after a transient fault, and a binary search on it walks off the end
 * of the run.
 */
export function prefixBad(zs, i) {
  let worst = 0;
  for (let j = 0; j <= i && j < zs.z.length; j++) {
    if (!zs.ok[j]) continue;
    if (zs.z[j] > worst) worst = zs.z[j];
  }
  return { bad: worst > zs.threshold, z: worst };
}