Paying for Doubt in Keystrokes: Latency-Aware Uncertainty for Autocomplete

Autocomplete is supposed to save typing, yet a wrong suggestion costs the user more than showing nothing: they stop, read, reject, and refocus. Deciding when to stay silent therefore depends on knowing when the model is likely wrong. The reliable ways to estimate that, such as repeated sampling or several randomized forward passes, multiply inference cost. In an interface that has to respond between two keystrokes, a suggestion that arrives late is useless. Uncertainty estimation and the human cost of bad suggestions are usually studied apart. Here they share one budget: the user's time.

This proposal measures both in that one currency. A single equation charges three things in milliseconds of user time: the user's reading cost for correct and incorrect suggestions, the keystrokes a suggestion saves, and the compute latency of estimating confidence, which counts against the chance that the suggestion arrives before the next keystroke. Against that cost, we build and test a cascade. A cheap learned confidence head runs on every keystroke. Extra multi-candidate uncertainty computation runs only when the cheap estimate sits close enough to the show-or-suppress boundary that more information could change the decision, and only within the expected pause before the user types again. The central empirical question is whether stochastic uncertainty is ever worth its latency in interactive typing, or whether a well-trained single-pass head captures all the available value. Either answer would be new, because no existing study prices uncertainty compute in user time.

Core Claim

The decision to show a suggestion is a value-of-information problem. Let $p$ be the estimated probability that the user accepts candidate $c$, $s$ the number of characters it would save, $t_k$ the user's time per typed character, and $r_+$ and $r_-$ the reading costs of a correct and an incorrect suggestion. Let $q(L)$ be the probability that a suggestion requiring compute latency $L$ arrives before the user's next keystroke. The expected net time saved by showing is

$$U = q(L)\,\big[\,p\,(t_k s - r_+) - (1-p)\,r_-\,\big],$$

and silence is worth zero. The suggestion should be shown when $p$ exceeds $p^* = r_- / (t_k s - r_+ + r_-)$. Extra uncertainty computation that raises latency from $L_0$ to $L_1$ is worth running only when the cheap estimate of $p$ is close enough to $p^*$ that a better estimate might flip the decision, and only when the expected gain from flipping it outweighs the loss from $q(L_1) < q(L_0)$.

Two claims follow. First, the right single-pass score is a learned estimate of acceptance probability that reads the model's hidden state, not raw token probability. The cutoff $p^*$ moves with suggestion length $s$, so any score that is a fixed monotone function of one probability gives the same decisions as a tuned threshold. Second, multi-candidate uncertainty should be spent selectively in a band around $p^*$, under a deadline set by keystroke timing. We predict that this selective spending beats both never estimating uncertainty and always estimating it. We commit to reporting the case where it does not.

Grounding in Prior Work

The human side of the cost comes from Sequential Decision-Making for Inline Text Autocomplete. That paper treats autocomplete as a sequence of decisions in which the system can show a suggestion or wait. Its user study found that reading cost barely depends on suggestion length, while correctness dominates: roughly 10 ms for a correct suggestion and 50 ms for an incorrect one. We reuse these numbers as $r_+$ and $r_-$.

The same paper also constrains the design. Its reinforcement-learning policies failed to beat a well-tuned confidence threshold under realistic parameters, and its PPO agent became over-aggressive. Our reading is that the policy was limited by its input signal, a raw deterministic token probability, rather than by the decision algorithm. We therefore keep the decision rule analytic, the cutoff $p^*$ above, and put the learning into the confidence estimate. The paper also ignores the compute cost of producing confidence, which is the gap our latency term $q(L)$ fills.

Two papers supply methods we reuse. Lightweight Word-Level Confidence Estimation for Neural Interactive Translation Prediction suppressed bad interactive-translation predictions with logistic regression over cheap features, scored against strict reference matches. It is the closest precedent for a cheap learned gate. We differ by training on hidden states, by targeting acceptance of the shown prefix rather than single-word correctness, and by charging compute latency. Calibrating Language Models with Adaptive Temperature Scaling trains a single Transformer-layer head on the final hidden state to predict a temperature for each token. It reduced calibration error by 10–50% on MMLU, TriviaQA and TruthfulQA at about 0.08 s (~7%) extra forward-pass cost. Our single-pass head borrows that architecture, but predicts acceptance of a multi-character suggestion directly instead of rescaling next-token probabilities.

The escalation step comes from Don't Throw Away Your Beams. That paper shows that for short outputs, random sampling keeps regenerating the same strings, a waste it calls the redundancy trap. It proposes weighting the top beam-search candidates by their sequence probability, and finds the resulting uncertainty estimate plateaus after only 3–5 beams. That makes it the natural expensive estimator for short completions. Its weighted beams also yield a ranked candidate list, which bears on the ranking gap identified by ChaI-TeA. ChaI-TeA found that models often place the right completion in their top 100 candidates but perplexity ranks it poorly. That paper evaluated only offline question answering, never prefix completion under a deadline.

Two papers argue against brute-force alternatives. AdaNSP used dropout variance across repeated forward passes to trigger extra computation per token in semantic parsing. It shows that uncertainty can usefully decide when to spend compute, but it ran the expensive estimator at every step, which is exactly what an interactive setting cannot afford. EAGLE speeds up generation 2.7–3.5x on LLaMA2-Chat 70B by drafting hidden-state features ahead of the main model, but it does nothing about wrong suggestions.

Research Program

The first component is an evaluation harness. It replays held-out conversations prefix by prefix, using either real keystroke timing or a typing-speed model whose parameters we vary. At each keystroke the system chooses among three actions: wait, show its top-1 candidate, or show a small list. It is charged according to the equation above, with the measured compute latency of each method on fixed hardware.

We report two metrics. The first is net user time saved per 100 characters. The second is ChaI-TeA's saved@k, which credits saved characters while charging for choosing among $k$ candidates; we include it so results stay comparable with that benchmark. Acceptance is defined as the user's actual continuation beginning with the suggested string. A secondary analysis relaxes this to accepting meaning-preserving variants, addressing the reference-match weakness noted for word-level confidence work.

The second component is the single-pass acceptance head. It is a one-layer Transformer on the language model's final hidden states plus the candidate's length. It is trained with cross-entropy on acceptance labels mined from the true continuations, so it costs one small extra layer per keystroke.

The third component is the deadline-bounded escalation. When the head's estimate falls within a band of $p^*$, the system runs batched beam search with 3–5 beams. It combines the beams' probability-weighted agreement with the head's score through a small learned combiner, and re-ranks the candidates. The run is cancelled if a keystroke arrives first. The band width and beam count are tuned on validation data to maximize net time saved.

The fourth component is an analysis that splits errors into in-domain and out-of-domain cases. The claimed advantage of multi-candidate uncertainty is catching confidently wrong suggestions on unfamiliar text, the distinction Directly Optimizing Calibrated Test-Time Uncertainty formalizes as generalization noise. If that advantage exists, it should be largest under domain shift.

Baselines

The naive reference points are never suggesting, which saves zero time by definition, and always showing the top-1 candidate ranked by perplexity, as in ChaI-TeA. On OASST, ChaI-TeA reports keystroke-savings potential "between 35% and 45%" for Phi-3 3.8B and Mistral-7B, and 167 ms p90 latency for SmolLM-1.7B. These figures are an upper bound on savings that ignores reading cost. We expect always-show to fall well below them once wrong suggestions are charged.

The strongest existing competitor is a tuned threshold on raw candidate probability, because it is the baseline that defeated reinforcement learning in Sequential Decision-Making for Inline Text Autocomplete. That paper reports no scalar savings number we can quote. No reported result was found on Lacuna for a threshold baseline on OASST or ShareGPT, so we will establish the number ourselves under identical conditions. The threshold gets the same validation set and tuning budget as our methods, a grid over thresholds per length bucket. Giving it a per-length threshold prevents it from losing simply because $p^*$ depends on $s$.

Next to it we run the lightweight logistic-regression gate of Lightweight Word-Level Confidence Estimation, which reports F1-BAD of 69.6 (en-de) and 73.0 (en-cs) with single-feature thresholding. We also run global temperature scaling followed by a threshold, and an Adaptive Temperature Scaling head followed by a threshold.

The expensive end is represented by three methods run on every keystroke: dropout across 5–10 forward passes, consistency across 10 random samples, and probability-weighted beam uncertainty from Don't Throw Away Your Beams. For the beam method the file quotes no single scalar result. All of these are charged their real measured latency. We also include an offline policy trained with implicit Q-learning on our head's features, to test again whether learned sequential policies help once the confidence signal is better.

Beating the threshold means a statistically significant gain in net time saved, with a bootstrap over conversations, across the plausible ranges of $t_k$ and $r_-$. Two ablations isolate the key ingredients. The first removes the deadline, letting escalation run regardless of keystroke timing. The second separates the uses of the beams: once for gating only, once for re-ranking only.

Why not just…?

Why not just tune a confidence threshold? This is the baseline to beat, and it may win in domain. Our argument is narrow: the cutoff $p^*$ depends on suggestion length, and raw probabilities from aligned models are miscalibrated in ways that vary across contexts, as Calibrating Language Models with Adaptive Temperature Scaling documents. We will measure the head's advantage separately in domain and out of domain. If the advantage vanishes in both, the conclusion is that the threshold suffices, and we will report it.

Why not just train a cheap classifier, as in interactive translation? This is the most serious threat, and our single-pass head is essentially a stronger version of that idea. The real question is therefore whether escalation adds anything beyond a well-trained cheap gate. The decisive comparison is the full cascade against the head alone at equal tuning budget. If the cascade gains nothing, the paper's finding becomes that stochastic uncertainty is not worth its latency in typing.

Why not just run beam or sampling uncertainty on every keystroke? Even 3–5 batched beams add latency on a model whose single pass already takes 167 ms at p90 (ChaI-TeA), and random sampling additionally wastes draws on duplicates (Don't Throw Away Your Beams). The always-on variants charged with real latency show directly how much $q(L)$ erodes their better estimates.

Why not just make generation faster with speculative decoding? Speed raises $q(L)$ but leaves the $(1-p)\,r_-$ term untouched; Foster et al. found that interactive prediction slowed professional translators by up to 17%. Faster decoding also widens the window available for escalation, so we treat it as complementary and test the cascade with and without an EAGLE-style drafter.

Proposed Experiments

The main experiment trains on OASST and tests on held-out OASST and ShareGPT through the ChaI-TeA protocol, using SmolLM-1.7B and Mistral-7B. The shift experiment applies the same OASST-trained heads, without retraining, to SMS ham messages and Webis-TLDR-17, the datasets used by Sequential Decision-Making for Inline Text Autocomplete.

There are three decisive checks. The first is whether the acceptance head beats the per-length-tuned threshold on net time saved. The second is whether deadline-bounded escalation beats the head alone, with its gain concentrated near $p^*$ and under domain shift as the value-of-information argument predicts. The third is whether beam re-ranking raises the rate at which the shown top-1 candidate is accepted, which would narrow ChaI-TeA's ranking gap.

A sensitivity sweep over $t_k$, $r_-/r_+$ and hardware latency maps the regimes in which uncertainty compute pays for itself. A small confirmation study with real typists, measuring completion time with suggestions on versus off, will check that the simulated cost model ranks the methods in the same order as human timing does.