Bayesian Height Prediction

What goes wrong with a naive approach

A virtualized list needs the total height of rows it has not rendered yet. The usual answers are all bad:

• Assume fixed row height. Breaks the moment rows contain wrapping text, emoji, images, or collapsible content. Users scroll past the “end” and then back up when the real height materialises; the scrollbar jumps.
• Measure every row up front. Defeats virtualisation — you paid the rendering cost you were trying to avoid.
• Use the running mean. Better, but gives no uncertainty. On a short warm-up the running mean is dominated by the first few rows; scroll far and the estimate is wrong in both directions with no indication.

The list widget needs a distribution over row height, not a point estimate, and it needs finite-sample guarantees — conformal bounds, not asymptotic ones — because users scroll with 10 samples not 10,000.

Mental model

Group rows into categories with similar layout (e.g., “single-line code block”, “multi-line markdown”, “expanded JSON”). Maintain per category:

• Normal-Normal conjugate posterior over the mean height.
• Welford running variance for the residual scale.
• Conformal quantile over recent residuals for a distribution-free upper bound.

The predictor returns a triple (mean, lower, upper). The list reserves space for the upper bound so it never has to reflow when the real row turns out to be taller than expected — no scroll jumps.

The math

Normal-Normal conjugate update

Prior $\mu \sim \mathcal{N}(\mu_0, \sigma_0^2 / \kappa_0)$ with precision strength $\kappa_0$. After $n$ observations with sample mean $\bar{x}$:

Posterior variance of the mean:

Defaults: $\mu_0 = 1.0$, $\kappa_0 = 2.0$, $\sigma_0^2 = 4.0$.

Welford running variance

Online one-pass for residual variance (numerically stable, no catastrophic cancellation):

$\hat{\sigma}^2 = M_{2,n} / (n-1)$ gives the per-observation variance — not the posterior’s variance of the mean.

Conformal upper bound

For coverage $1 - \alpha$ (default $\alpha = 0.10$), collect residuals $R_i = x_i - \mu_n$ from a rolling calibration window and take:

The prediction interval is:

with finite-sample guarantee $P(R_{n+1} \le q) \ge 1 - \alpha$. The list preallocates $\mu_n + q$ cells per row — a tail row cannot exceed the bound with probability greater than $\alpha$.

Why this beats fixed-row-height

assumed = 1 row
real    = 2 rows (markdown paragraph)
→ scrollbar ends halfway through content, user scrolls "past"
  the end, list re-lays-out, scrollbar snaps back. Flicker.

μ_n = 1.3, Var = 0.1  →  reserve 1.3 rows
real  = 4 rows (fenced code block, rare)
→ still jumps. Posterior mean is right on average, but a
  heavy tail blows past the credible interval.

μ_n = 1.3, q = 3.0    →  reserve μ + q = 4.3 rows
real  = 4 rows        → fits the preallocation. No jump.
average case          → 1.3 rows used; UI still feels dense.

Rust interface

use ftui_widgets::height_predictor::{HeightPredictor, HeightPrediction};
 
let mut hp = HeightPredictor::new()
    .with_prior(1.0, 2.0, 4.0) // mu_0, kappa_0, sigma2_0
    .with_coverage(0.90);      // conformal 1 - alpha
 
// When a row actually renders, feed back the observed height:
hp.observe("markdown", 2.0);
 
// When laying out future rows, ask for the prediction:
let HeightPrediction { predicted, lower, upper, observations }
    = hp.predict("markdown");

Categories (&str keys) let you keep separate posteriors for row types that live in the same list without cross-contamination.

How to debug

The predictor is consumed by the virtualized list; its decisions show up indirectly through diff_decision, conformal_alert, and the list widget’s own tracing. To inspect the posterior state directly:

tracing::debug!(
    target = "ftui_widgets::height_predictor",
    ?hp.state(),
    "height posterior"
);

Watch for two smells in the evidence stream:

• Upper bound stuck at conservative default. The calibration window is too small; the predictor is falling back to the prior variance. Scroll around more to populate the residual buffer.
• Upper bound collapses to $\mu$. Residuals are all zero because rows are identical. Harmless but wasteful — you can disable the conformal layer for that category.

Pitfalls

Cross-references

• /widgets/virtualized-list — the consumer that turns (predicted, lower, upper) into row offsets.
• Vanilla conformal — the theory behind the $q$ bound used here.
• Fenwick tree — the O(log n) prefix sum that uses the reserved heights.

Where next