Skip to Content
IntelligenceBayesian inferenceDiff strategy

Bayesian Diff Strategy Selection

What goes wrong with a naive approach

The render loop has three diff strategies with different cost curves:

  • Full — scan every cell, emit only the ones that changed. Cheap when change rate is small; O(N) scan dominates.
  • DirtyRow — skip clean rows entirely via the dirty bitmap; emit per-row runs. Cheap when changes cluster in few rows.
  • FullRedraw — skip the scan; emit every cell unconditionally. Cheap only when almost everything changed.

A hand-tuned “if change_pct > 0.4 use FullRedraw else DirtyRow” works until the workload drifts. When a dashboard settles into a steady state the threshold is wrong in one direction; during a scroll burst it is wrong in the other. The p99 frame time breathes with the workload and no amount of knob-twiddling stabilizes it.

The diff engine needs (a) an estimator of the current change rate, (b) an explicit cost model, and (c) a conservative mode that degrades gracefully when uncertainty is high.

Mental model

Every frame produces one Bernoulli observation per cell (changed or not). Over a rolling window the rate pp is well approximated by a Beta posterior — conjugate to Bernoulli, closed form, finite-sample sensible.

Because workloads drift, use exponential decay on the posterior counts: recent frames matter more than the entire history.

For each strategy compute expected cost as a linear function of p⋅Ncellsp \cdot N_{\text{cells}}. Pick arg⁡min⁡\arg\min. When the posterior variance is high (cold start, regime change) pick the strategy that minimizes the 95th-percentile cost instead of the mean — the conservative mode.

The diff engine is a Bayesian cost-minimiser. The posterior over change rate is the state; the three cost curves are the decision rule; exponential decay lets the estimator follow the workload.

The math

Posterior over change rate

p∼Beta(α,β)p \sim \text{Beta}(\alpha, \beta)

Updates under exponential decay with factor γ∈(0,1)\gamma \in (0,1):

α←γα+k,β←γβ+(n−k)\alpha \leftarrow \gamma \alpha + k, \qquad \beta \leftarrow \gamma \beta + (n - k)

where nn is the cell count and kk the observed change count for the current frame. Default γ=0.95\gamma = 0.95 (half-life ≈ 14 frames).

Posterior mean and variance:

E[p]=αα+β,Var⁡(p)=αβ(α+β)2(α+β+1)E[p] = \frac{\alpha}{\alpha + \beta}, \qquad \operatorname{Var}(p) = \frac{\alpha \beta}{(\alpha + \beta)^2 (\alpha + \beta + 1)}

Cost model

Let NN = total cells, RR = row count, pp = posterior mean.

Cfull=cscan⋅N+cemit⋅(pN)Cdirty=cscan⋅N+crow⋅(pR)Credraw=cemit⋅N\begin{aligned} C_{\text{full}} &= c_{\text{scan}} \cdot N + c_{\text{emit}} \cdot (p N) \\ C_{\text{dirty}} &= c_{\text{scan}} \cdot N + c_{\text{row}} \cdot (p R) \\ C_{\text{redraw}} &= c_{\text{emit}} \cdot N \end{aligned}

Default coefficients: cscan=1.0c_{\text{scan}} = 1.0, cemit=6.0c_{\text{emit}} = 6.0, crow=0.1c_{\text{row}} = 0.1. These are measured once on the presenter/bench harness and held constant — they describe the terminal, not the workload.

Decision rule

strategy⋆=arg⁡min⁡s∈{full, dirty, redraw}Cs(p)\text{strategy}^\star = \arg\min_{s \in \{\text{full, dirty, redraw}\}} C_s(p)

Conservative (95th-percentile) mode

When Var⁡(p)>θvar\operatorname{Var}(p) > \theta_{\text{var}} (default 0.02):

p95=BetaQuantile(α,β,0.95),strategy⋆=arg⁡min⁡sCs(p95)p_{95} = \text{BetaQuantile}(\alpha, \beta, 0.95), \qquad \text{strategy}^\star = \arg\min_s C_s(p_{95})

The 95th-percentile call picks the strategy with the cheapest worst-plausible cost rather than the cheapest expected cost.

Worked example — the three regimes

p ≈ 0.002, Var(p) small  →   C_full  =  N + 6·0.002N = 1.012N
                              C_dirty =  N + 0.1·0.002R ≈ 1.0N
                              C_redraw = 6N
                              pick: DirtyRow

Rust interface

crates/ftui-render/src/diff_strategy.rs
use ftui_render::diff_strategy::{DiffStrategyPicker, DiffStrategyConfig, Strategy};
 
let mut picker = DiffStrategyPicker::new(DiffStrategyConfig {
    c_scan: 1.0, c_emit: 6.0, c_row: 0.1,
    decay: 0.95,
    conservative_var_threshold: 0.02,
    conservative_quantile: 0.95,
});
 
// Each frame: observe, then pick.
picker.observe(changes, total_cells);
let Strategy { kind, expected_cost, posterior_mean, posterior_var }
    = picker.pick(rows, total_cells);

The picker returns both the chosen strategy and the posterior summary so the renderer can log it without recomputing. Link out to /render/diff for how Strategy feeds into the actual diff pass.

How to debug

Every decision emits a diff_decision line:

{"schema":"diff_decision","strategy":"DirtyRow",
 "posterior_mean":0.047,"posterior_var":0.0014,
 "expected_cost":1024.5,"conservative":false,
 "alpha":3.1,"beta":62.0}
FTUI_EVIDENCE_SINK=/tmp/ftui.jsonl cargo run -p ftui-demo-showcase
 
# Watch how often each strategy wins:
jq -c 'select(.schema=="diff_decision") | .strategy' /tmp/ftui.jsonl \
  | sort | uniq -c

If FullRedraw never wins on scroll-heavy workloads, the cemitc_{\text{emit}} coefficient is probably too large for your terminal — re-run presenter/bench and update the config.

Pitfalls

Decay too slow, strategy lags. With γ=0.99\gamma = 0.99 the posterior half-life is ~70 frames, so a regime change takes a full second of 30 fps to propagate. Keep γ≤0.95\gamma \le 0.95 unless you’re consciously suppressing noise at the cost of reactivity.

Coefficients are terminal-specific. cemitc_{\text{emit}} is much higher on a ssh-tunnelled terminal than a local iTerm2. Run the calibration on representative hardware; a laptop-tuned constant will pick DirtyRow on machines where FullRedraw is actually cheaper.

Cross-references

Hint rankingCapability detection