acceptodds
Under review as a conference paper at ICLR 2027

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

Abstract

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.

Primary area:
learning theory
Keywords:
finite-state machines, streaming algorithms, communication complexity, branching programs, state representations, finite-memory control

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_SuQ9OpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
1
Soundness
3
Read review
Paper summary

The paper is clearly AI slop and impossible to read. I read the abstract and introduction and even the most basic things about the paper, like the motivation, problem setup, and warmup example (which is supposed to be easy to understand!), are so poorly explained that even an expert cannot understand what is going on.

Critical strengths

I am not writing a detailed review for this paper as it is obviously completely AI generated

Critical weaknesses

I am not writing a detailed review for this paper as it is obviously completely AI generated

Questions for authors

I am not writing a detailed review for this paper as it is obviously completely AI generated

1 comment

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.

Reviewer_bAyzOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

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.

Critical strengths
  • The paper's central result is not merely an upper or lower bound but a two-sided law: for every finite number of states, the worst-case execution error is pinned between constant multiples of the smaller of (horizon × tolerance) and one, with constants that do not depend on the state budget, horizon, or tolerance.

  • The paper sharply distinguishes two uses of the same memory: rereading a compressed history at each cut versus updating one persistent state.

Critical weaknesses
  • The general lower bound is proved only for tasks whose observation alphabet grows with the state budget, so the headline "for every finite K" law is weaker than it reads.

The uniform lower bound in Theorem 1 uses a witness whose block reads a q-valued vector as a single observation with K ≤ q < 2K, so the input alphabet scales with K; the authors themselves acknowledge this and supply a separate binary-observation construction (Proposition 11).

  • The conversion guarantee is a sum over cuts, so the horizon factor is baked into the upper bound rather than derived from the task; and the paper's own compiler analysis shows the conversion can be loose or statistically costly.

The upper bound comes from Proposition 4, where the error is at most twice the sum of per-cut errors, and converting that sum to a maximum introduces the factor N. This means the upper half of the law partly reflects the specific posterior-recompression compiler rather than an inherent limitation (a point the paper itself makes in Appendix D).

Questions for authors
  • The uniform lower bound uses a witness whose block reads a q-valued vector as one observation, with K≤q<2K,K \leq q < 2K, so the input alphabet grows with the state budget; Proposition 11's binary-input construction charges L=2⌈log2K⌉+2L = 2⌈log_2K⌉+ 2 bits per block and you note that the bounds "do not close the binary-input dependence on K" when KK varies with N.N. Concretely: for independent Bernoulli observations and KK allowed to grow with NN (say K=NαK = N^\alpha), what is the best currently provable two-sided bound on Γbin\Gamma^{bin}, and is there a concrete reason to believe the truth matches the growing-alphabet law or the weaker charged-block law?

  • The upper half of the law comes from Proposition 4's sum-over-cuts compiler, and Appendix D exhibits a task where cut-optimal supplied summaries compile to 2hr(1−r)2hr(1−r) against an optimum of hr.hr. Is the (N−1)(N−1) factor in the upper bound known or believed to be inherent to any compilation from cut summaries to a K-state machine, or is it an artifact of posterior recompression that a better conversion could remove?

  • Section 7 positions the result against recurrent RL and approximate information states. Is there an experiment (even a small one) comparing a per-cut retrained summary against a single recurrent/FSM controller at matched state budget on a task from the delayed-query family, to check that the predicted horizon-dependent gap appears in learned models and not just in the optimal-error calculation?

  • For the three-observation counterexample in Appendix D (excess risk 2hr(1−r) − hr), could you verify empirically that cut-optimal summaries compiled by posterior recompression actually exhibit that excess, and that a direct FSM optimization at the same state budget does not?

  • Could you report a direct empirical estimate of E_cut(K) and E_seq(K) on the Bernoulli example.

1 comment

Thank you for the questions about the bounds and for suggesting the matched-budget learning comparison. We strengthened the binary lower bound and added checks for the learning and compiler examples.

Growing state budgets on binary inputs. In response to your question, we strengthened the binary lower bound to match the upper bound in order, Θ(min{Nε,1}), for K=⌊N^α⌋ with fixed α>0 and sufficiently large N. For independent Bernoulli bits, possibly with different biases, a Boolean target, and optimal K-label error at most ε at every cut, let Γ be the worst optimal K-state online error. Set D=⌈log₂⌊K/2⌋⌉, m=⌊(N−2D−4)/2⌋ and r=min{⌊log₂K⌋,N−1}. For K≥2, N≥4D+10 and 0≤ε≤1/4,

1−(1−4ε)m8≤Γ≤min⁡{1/2,2(N−1−r)ε}.\frac{1-(1-4\varepsilon)^m}{8}\le\Gamma\le\min\{1/2,2(N-1-r)\varepsilon\}.

The lower-bound task reuses one address across rare gates, so every cut needs to omit at most the current gate. Conditioning on a marked fair gate exposes the affine suffix responses of Brody et al. (2011) under the same original stream law. The upper bound stores the first r bits exactly (revised §3 and Appendix A.4).

The horizon factor. The horizon factor is unavoidable in the worst case for any compiler that outputs a K-state machine. The original lower bound constructs a task with optimal K-label error at most ε at every cut and forces every K-state machine to incur at least a constant times min{Nε,1}. For a supplied compiler, the certificate has an N/√M fixed-confidence penalty with M independent validation episodes. A fixed controller can be validated directly (§5 and Appendix C).

Learned models at the same state budget. In the added two-state learning comparison on Bernoulli(1/4) delayed queries, the mean online and worst-cut errors coincided at three observations. At twelve they were 20.691% vs 6.545%, even though all five online fits reached the exact optimum. Cut encoders can reread the prefix, their decoders see the suffix, and the cut suite used more total restarts. Appendix B.3 and q3_fresh/README.md give the fitting protocol, parity-favoring initialization and exact input-law scoring. q3_fresh/REPORT.md gives the result table.

Posterior compilation. For the original three-observation selector with h=r=1/4, the exact best-machine and posterior-compiler errors are 6.25% and 9.375%. We added a paired simulation and an exhaustive check of the optimum. The summaries forget B. The compiler resamples it when Y=1. Paired estimates over 500,000 episodes are 6.2496% and 9.3456%. Enumeration of 16,384 deterministic programs checks the optimum (Appendices B.3 and D).

Empirical errors in the 100-block task. For the original Bernoulli(0.1) example, E_cut(2)=1% (proved in the revision) and E_seq(2)≈43.369% (original Lemma 5). In the added 500,000-episode check, the worst-cut summary after A₁,B₁ errs on 0.9960%, and the optimal machine on 43.3362% (Appendix B.3).

Reviewer_9JcKOpenReview ↗
Rating
2
Confidence
2
Informativeness
1
Presentation
1
Soundness
3
Read review
Paper summary

Consider a sequence X1,…,XNX_1, \dots, X_N drawn from a joint product distribution and a target binary function ff. The authors consider the problem of representing f(X1:N)f(X_{1:N}) using some low memory encoding mechanism via two approaches. The first approach consists in using a summary of a prefix X<tX_{<t} using some encoder taking values in [K][K] at some cut t∈[N]t \in[N], then using a decoder that takes the encoded value together with Xt:NX_{t:N} to approximate f(X1:N)f(X_{1:N}). The second approach consists in using a finite state machine evolving as St∼Tt(⋅∣St−1,Xt)S_{t} \sim T_t(\cdot \vert S_{t-1}, X_t) in [K][K], then using a binary read-out bN(SN)b_N(S_N) to approximate f(X1:N)f(X_{1:N}). They measure the difference between the two approaches for NN-product source Boolean tasks via what they refer two as a calibration profile denoted ΓN,K(ε)\Gamma_{N, K}(\varepsilon). This measure correspond to the worst case approximation error across the various tasks using a finite state machine should the approximation error using the summary idea be at most ε\varepsilon. Their main result establishes that the calibration profile is of order NεN\varepsilon in the small ε\varepsilon regime (See Theorem 1).

Critical strengths
  1. This work provides an interesting mathematical result about the gap between the errors of two memory compression or representation mechanisms, one using a summarizing history idea and on reliant on a finite state machine. The authors establish that the two errors for these two memory representation approaches are within a factor of NN is the small approximation error regime. This is an elegant result.

  2. This work is quite technical but the authors do a good job at making sure their presentation is thorough. The proof is well structured and presented.

Critical weaknesses
  1. The abstract is quite technical, and not accessible at all to a non-expert. The authors should revisit their abstract.

  2. The motivation behind this work is unclear to me, especially the link to RL or why it is useful for RL. It is therefore hard to gauge the significance of the work and established results.

  3. The settings and established results are quite hard to follow at first. I would say mainly to a lack of concrete RL example demonstrating the utility. Therefore, the usefulness of the result is unclear. Clarifying the usefulness of the setting will benefit the exposition of this work greatly.

  4. There is only one main result and that is theorem 1. The rest of the paper is about providing the proof and technical ideas behind such result. In terms of contributions this is rather limited. Why is this result impactful?

Questions for authors

While this seem to be motivated by some RL applications, it is not quite clear to me how it is related. It would be useful to add further explanations. What is really the core issue that this work is trying to solve for or enable in it RL? Could the authors clarify further the link between (Rudinetal.,2022) and their results? How insightful this new results for RL?

The result of Theorem 1 seem to be independent of KK. The statement only requires K≥2K\ge 2. Can you explain why this is the case? doesn't this mean that whether we choose K=2K=2 or any other value is irrelevant? so what is the point of KK in the problem? What happens if the finite state machine approach and history summary idea use different values of KK? does the result still hold?

1 comment

Thank you for asking how the theorem relates to control and why K matters. We clarified the offline-to-online guarantee and added two control comparisons.

The controller’s memory budget. In the original 300-observation task, one-bit cut summaries have at most 1% error at every cut, but the best one-bit online controller errs on about 43.4%. Two bits are exact. The signals are independent Bernoulli(0.1) bits. In each of 100 rounds, A switches a destination and C confirms B's switch request. Each cut encoder rereads the prefix and its decoder sees the actual suffix (original Lemma 5 and revised Figure 2).

The role of K. The class-wide rate is uniform in K, while exact error on a fixed task can depend sharply on K. For N independent finite-valued observations and a Boolean target, the worst error across tasks of the best K-state online machine is Θ(min{Nε,1}) when optimal K-label cut errors are at most ε. This holds for K≥2, N≥3 and 0≤ε≤1/4. The alphabet and worst task may change with K. For a class-wide final-error target δ∈(0,1/4], the largest admissible cut tolerance is of order δ/N (§3). For 300 observations, 0.008% per-cut error suffices for 5% final error at the same K (revised Introduction).

Unequal memory budgets. A post-review derivation gives the same order for K_exec≥K_cut≥2 under the same assumptions. The K_cut-state upper construction fits K_exec states, and the lower-bound task needs only two cut labels. Its alphabet may grow with K_exec (revised Appendix A). Conversely, the delivery task has zero cut error with four labels, while its best two-state machine errs about 43.37%.

The previous-action interface. We clarified the interface already discussed in original §6. Rudin et al.'s robot policy receives its previous command. In an exogenous task with terminal reward one iff correct, K freely writable, exactly echoed action codes carry the state if intermediate writes affect neither observations nor rewards and no other policy state persists. Optimal return equals one minus optimal online error. Under these conditions, the calibration law tells how accurate the offline summaries must be to guarantee that some controller with this action-code budget can reach a given return (§6).

Control comparisons. To test the role of feedback in control, we added two velocity-masked simulations. PPO with the previous action outperformed equal-width zero and random feedback in both tasks. In CartPole, mean survival was 112 steps versus 43–49 for the controls. The two-frame policy saw more observation history and scored highest in both tasks. Each condition used 12 training seeds and 524,288 interactions per model (revised §6.1 and Appendix E).

Comments on the paper

1 comment

We thank the reviewers for asking what the offline test guarantees as a sequence grows and how the result relates to control. We revised the abstract, introduction, and Figure 2 caption to distinguish two uses of the same memory budget. An offline encoder can reread the prefix at each cut and send one of K labels to a decoder that sees the suffix. An online predictor must update a single K-state memory throughout. This focus led us to change the title from From Compact Summaries to Usable Memory: A Calibration Law for Finite-State Computation to From Offline Summaries to Online Memory: A Calibration Law for Finite-State Prediction.

Our original Theorem 1 calibrates the two errors. For N independent finite-valued observations and a Boolean final target, suppose optimal K-label summaries have average error at most ε at every cut. Among those tasks, the worst error of the best online predictor for each task is Θ(min{Nε,1}), uniformly for K≥2, N≥3 and 0≤ε≤1/4. The observation alphabet may grow with K. The largest cut tolerance that guarantees final error at most δ across the class is of order δ/N for 0<δ≤1/4. On the original 300-observation task, the best online one-bit predictor errs on about 43.4% (original Lemma 5). Appendix B.3 now proves that 1% is the best one-bit error at the hardest cut. Revised Figure 2 puts both errors side by side and shows that two bits solve the same task exactly.

To answer whether the horizon penalty persists with binary observations as the memory budget grows, we strengthened the lower bound and obtain the same order when independent bits have possibly different biases and N≥4⌈log₂⌊K/2⌋⌉+10 (§3 and Appendix A.4). The proof reuses one address across rare gates and conditions on a marked fair gate under the original input law. We compared learned cut summaries and online predictors with the same state budget on shorter sequences from that task family. The gap between online and worst-cut error widened with horizon (§3 and Appendix B.3). We clarified the idealized previous-action interface in §6. In two added velocity-masked simulations, actual previous-action feedback improved performance over equal-width zero and random feedback (§6.1 and Appendix E).

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.