The paper tries to solve: if every cut (prefix) of a data stream admits a very accurate K-value summary of the past, what does that guarantee about the best executable K-state machine that must update one persistent state over time? These are two different uses of the same memory: a cut encoder can reread the full history at each cut, while a finite-state machine (FSM) must carry information forward via recursive updates S_t = u_t(S_{t−1}, X_t).
A stream consists of a fixed number of observations that are statistically independent of one another, and the thing to be predicted is a yes/no answer determined by the whole stream. Two kinds of memory-limited predictors are compared. The first is a "cut" predictor: at each point in the stream it may look back over the entire history so far, compress that history into one of a fixed number of labels, and pair that label with the future to make its guess. Each cut is optimized separately, and the cut error is the worst such error over all cut points. The second is a genuine finite-state machine: it holds one of the same fixed number of states, updates that state as each new observation arrives, and gives a single yes/no answer at the end; its error is the execution error. The calibration profile is then defined as follows: consider all tasks on which the best possible cut predictor can achieve an error no larger than some tolerance, and ask how badly the best possible finite-state machine can do on those tasks the worst such execution error is the profile's value.
For any finite number of states (at least two), any sufficiently long stream, and any tolerance up to one quarter, the worst-case execution error is bounded above and below by constant multiples of the smaller of two quantities: the product of the stream length and the tolerance, or one. The constants do not depend on the number of states, the stream length, or the tolerance. The practical upshot is that a per-cut error which shrinks toward zero does not by itself prevent the executing machine's error from remaining large as the stream gets longer. What actually governs the guarantee is the product of the stream length and the per-cut tolerance, not the tolerance on its own.
Thank you for commenting on the presentation. We revised the abstract, introduction, and Figure 1 caption to explain why rereading the past differs from updating one state and how a previous action can carry that state. Figure 2 now puts both errors on the same delivery task side by side.
One-bit delivery example. In the original task, all 300 signals are independent Bernoulli(0.1) bits in 100 rounds. One switches the destination, while the third confirms the second's switch request. Exact online prediction needs four states to distinguish the destination and the pending request. A cut encoder can reread the past, and its decoder sees the suffix. One-bit cut summaries err on at most 1% at each cut, while the best one-bit online controller errs about 43.4% (original Lemma 5 and revised Figure 2).
Author contributions. The authors led problem formulation and evidence collection. The paper discloses the AI assistance used.