BOCPD — Bayesian Online Change-Point Detection

What goes wrong with a naive approach

The resize coalescer has to decide, on every incoming resize event, whether the user is in a “steady” regime (one deliberate resize) or a “burst” regime (dragging a window edge, producing 30 resizes per second). The choice of coalescing delay — 16 ms vs. 40 ms — depends on the regime and gets the frame budget horribly wrong if you pick incorrectly.

The naive answer is a hard threshold: “if inter-arrival time is below 30 ms, we’re in burst mode”. In practice:

• Thresholds drift. A user on a 144 Hz display and a user on a 60 Hz SSH connection have different “burst” rates. One threshold cannot serve both.
• Binary switching flickers. A single fast event flips the mode, the next slow event flips it back. The coalescing delay oscillates, and so does the frame cadence.
• No uncertainty. The detector cannot say “I’m not sure yet” and behave conservatively; it has already committed.

BOCPD (Adams & MacKay, 2007) solves all three problems at once with a run-length posterior — a proper probability distribution over “how long ago did the regime last change?”

Mental model

Every resize arrives with an inter-arrival time $x_t$. Model $x_t$ as drawn from one of two exponentials:

• $x_t \sim \text{Exp}(\lambda_{\text{steady}})$ with $\lambda_{\text{steady}} = 1/200\,\text{ms}$.
• $x_t \sim \text{Exp}(\lambda_{\text{burst}})$ with $\lambda_{\text{burst}} = 1/20\,\text{ms}$.

The hidden state is the run length $r_t$: the number of consecutive observations since the last change-point. On each step the run length either grows (no change) or resets to 0 (change detected), governed by a hazard function $H(r)$.

Maintain a posterior $P(r_t = r \mid x_{1:t})$. The regime probability at time $t$ is:

Smooth the coalescing delay between 16 ms (steady) and 40 ms (burst) as a function of the burst probability — no binary flips.

The math

Hazard function (geometric prior on run length)

Run-length recursion (Adams & MacKay)

Grow:

Reset (change-point at $t$):

Normalise to obtain the posterior $P(r_t \mid x_{1:t})$.

Observation model — exponential

For a run of length $r$, the observation is exponential at the regime’s rate:

$K = 100$ truncation

Keeping every run length forever is O(t) in time and memory. Truncate at $K = 100$ by folding the tail into the $K$-th bucket. The truncation error is bounded by $P(r_t > K)$, which becomes negligible after a few dozen observations with a non-trivial hazard.

Regime probability and coalesce delay

Let $p_b = P(\text{burst} \mid x_{1:t})$. Coalescing delay:

The linear interpolation in the middle band is what removes the oscillation — the delay changes smoothly as evidence accumulates.

Worked example — a resize drag

x_t (ms): 180, 190, 210, 25, 22, 18, 22, 25, ..., 200, 210
          └── steady ──┘  └────── burst ──────┘  └─ steady ─┘

P(r_t = 0 | x_1:t) spikes twice:
  - at t=4  (when the first fast x arrives)
  - at t=N  (when the drag ends)

p_b trajectory:
   0.02 → 0.04 → 0.05 → 0.68 → 0.93 → 0.96 → 0.96 → ... → 0.20 → 0.05

delay_ms trajectory:
   16 → 16 → 16 → ~38 → 40 → 40 → ... → 16 → 16

Notice the delay does not snap from 16 to 40 when p_b crosses a magic number — it glides, following the posterior.

Rust interface

use ftui_runtime::bocpd::{Bocpd, BocpdConfig, Regime};
 
let mut bocpd = Bocpd::new(BocpdConfig {
    lambda_steady: 1.0 / 200.0,
    lambda_burst:  1.0 / 20.0,
    hazard:        1.0 / 50.0,
    max_run_length: 100,
});
 
// On each resize:
let dt_ms = now.duration_since(last).as_millis() as f64;
let regime = bocpd.observe(dt_ms);
 
let delay_ms = match regime {
    Regime::Steady(p_burst) if p_burst < 0.3 => 16,
    Regime::Burst(p_burst)  if p_burst > 0.7 => 40,
    Regime::Mixed(p_burst)                   => lerp(16, 40, (p_burst - 0.3) / 0.4),
    _ => 16,
};

The runtime holds the Bocpd instance inside the resize coalescer; see /runtime/overview for how the delay feeds the rest of the frame loop.

How to debug

Every resize decision emits a resize_decision line:

{"schema":"resize_decision","dt_ms":22,
 "p_burst":0.93,"log_bayes_factor":3.1,
 "regime":"burst","delay_ms":40,
 "run_length_mode":5,"max_run_length":100}

FTUI_EVIDENCE_SINK=/tmp/ftui.jsonl cargo run -p ftui-demo-showcase
 
# Trace p_burst over a drag:
jq -c 'select(.schema=="resize_decision") | [.dt_ms, .p_burst, .delay_ms]' \
  /tmp/ftui.jsonl

If p_burst never reaches 0.7 during a real drag, your $\lambda_{\text{burst}}$ is too aggressive for the input hardware — bump it toward 1/30 ms and recalibrate against your showcase trace.

Pitfalls

Cross-references

• /runtime/overview — where the resize coalescer and BOCPD live inside the frame loop.
• CUSUM — a cheaper change-point detector used for hover jitter.
• Alpha-investing — sequential FDR control that gates BOCPD’s alerts against a budget.

Where next