From Compact Summaries to Usable Memory: A Calibration Law for Finite-State Computation

When a policy reads its previous action, choosing an action also writes the code it will read next. With K freely writable, exactly echoed action codes and no other persistent state, this is a K-state memory register. We ask what accurate, separately optimized K-label history summaries guarantee about online computation with the same state budget. At each cut, a decoder evaluates the summary using the actual remaining observations, while the online machine processes observations sequentially. For streams of N independent finite observations and a binary terminal target, we establish a uniform calibration law. For every finite K≥2, allowing finite input alphabets to vary with K, the worst optimal online error among tasks whose maximum cut error is at most ε is Θ(minNε,1), with universal constants for N≥3 and 0≤ε≤1/4. Thus a class-wide final-error guarantee 0<δ≤1/4 requires cut error on the scale δ/N. A construction using the same K states and delayed-query tasks establish matching upper and lower bounds.