acceptodds
Under review as a conference paper at ICLR 2027

Memory for Late Evidence: A Delay–Resolution Phase Law

Abstract

Sequential state estimators are designed to forget: once a compact state is sufficient for predicting the future, the observations that produced it can be discarded. Late evidence exposes a fundamental limitation of this principle. A state may be sufficient for forward prediction yet insufficient to revise the present when an observation about a discarded timestamp arrives later. We characterize the minimum persistent memory required to support such revisions under arbitrary legal arrival orders. For a class of positive, invertible -state models with bounded, locally rich on-time evidence and retrodictively observable late evidence, the optimal deterministic code satisfies Thus, correction-state memory is delay-limited only up to the point at which the required resolution dominates: beyond this horizon, memory becomes resolution-limited and no longer grows with physical delay. The upper bound stores a quantized cut belief together with the resolvable suffix, while a matching response-packing converse shows that every retained direction is necessary, ruling out an explanation based solely on truncating a mixing filter. Without bounded evidence, even delay one can preclude any finite uniformly accurate code. These results identify statistical resolution, rather than physical delay, as the relevant capacity variable for correctable state beyond the mixing horizon. A packed cut–suffix construction realizes the predicted memory and replay-work saturation, while a controlled recurrent bottleneck diagnostic reveals the forward–revision tension on prediction-equivalent histories. Overall, the theory provides a concrete criterion for sequential representations under late evidence: preserve the responses required for future corrections, not merely the information needed for prediction from the current state.

Primary area:
probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)
Keywords:
Bayesian filtering, out-of-sequence measurements, sequential state estimation, memory complexity, minimax lower bounds

Reviews

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

The paper studies the minimum memory required by a sequential estimator when observations about past states may arrive late. For the class of finite-state HMMs considered, the results establish matching upper and lower bounds on the persistent memory needed for any prescribed estimation accuracy.

Critical strengths

This paper raises an interesting distinction between prediction and revision by studying information unnecessary for a predictive task but not for later corrections. The matching upper and lower bounds derived substantiates the technical contributions.

Critical weaknesses
  1. I think the writing is ok but could be better. There are multiple disclaimer statements such as "proof establishes the existence of constant; it does not provide numerical threshold" that can be collectively put in a single section in the appendix as opposed to scattered in the main text. On the other hand, the paper could be improved by stating the exact set of assumptions for each statement, as well as elaborating on proof intuitions.

  2. The scope is relatively narrow. Main results apply to a restrictive observation and dynamics class assuming known, positive, invertible finite-state transitions and locally rich on-time likelihood fields

Questions for authors

How representative are the histories and late observations driving the lower bound under the model’s observed distribution? Since the packing construction uses a neighborhood that shrinks with horizon, does comparable memory requirements persist when allowing a small probability of estimation failure?

1 comment

Response to Reviewer BiQJ

Thank you for the positive assessment and for the question about failure probability, which our appendix addresses directly. All results cited below are already in the paper; we ran no new experiments for this reply.

Q. Do comparable memory requirements persist when a small probability of failure is allowed, and how representative are the packing histories? Yes. The lower bound does not rely on a shrinking neighborhood of rare histories.

  • Failure on a fraction of histories (Theorem typical, appendix). Suppose a deterministic BB-bit state is ϵ\epsilon-accurate for every legal continuation on a set of histories of probability at least 1−δ1-\delta, with any 0≤δ<10\le\delta<1. Then for each 1≤n≤D+11\le n\le D+1, B≥nlog⁡2(1/ϵ)−O(nlog⁡(1/η))+⋯+log⁡2(1−δ)B\ge n\log_2(1/\epsilon)-O(n\log(1/\eta))+\dots+\log_2(1-\delta). The failure allowance enters only through the additive log⁡2(1−δ)\log_2(1-\delta).
  • General finite-alphabet case (Theorem 9, generalhistory). The same holds with a bound of the form B≥qnlog⁡2(1/ϵ)−⋯+log⁡2(1−δ)B\ge qn\log_2(1/\epsilon)-\dots+\log_2(1-\delta). For a fixed model, KK and δ<1\delta<1, this gives Θ(qmin⁡{D+1,x}x)\Theta(q\min\{D+1,x\}x) as x=log⁡2(1/ϵ)→∞x=\log_2(1/\epsilon)\to\infty, together with the uniform upper bound.
  • Failure on observed queries (Theorems randomquery and 10, generalquery). If the baseline and post-query TV errors exceed ϵ\epsilon with probabilities at most δ0,δ1\delta_0,\delta_1, the bound has the same form, with a term log⁡2s\log_2 s where s=1−δ0−δ1/(pβ)>0s=1-\delta_0-\delta_1/(p_\beta)>0. These bounds need explicit outcome/query conditions to be positive.
  • Conditions we do not hide. These extensions need positive invertible PP, bounded-density on-time fields before late arrivals, and response rank (Table 2). Observed risk also needs outcome/query and recent-coverage conditions, and Corollary 5 adds exogenous masks.

So the packing is carried by a set of histories of probability at least 1−δ1-\delta, not by a vanishing-probability neighborhood. What is lost is the explicit constant. The log⁡2(1−δ)\log_2(1-\delta) and log⁡2s\log_2 s terms cost only lower-order bits.

Weakness 1: scattered disclaimers, and stating assumptions and intuition. We agree and have made three changes in the revised first ten pages.

  • Assumptions per result. Table 2 now lists, for each result, its additional assumptions and conclusion, with colour banding to make rows easy to scan.
  • Proof intuition. The Introduction now has a paragraph "How the proof tells the story": the construction stores a quantized cut belief plus the still-resolvable suffix, and the converse packs histories that a common future insertion still distinguishes. The "Proof idea" paragraph in Section 5 explains the block-triangular response map.
  • Disclaimers. We shortened the closing scope paragraph and moved the long list of caveats into one place. In the camera-ready version we will collect the remaining scattered statements (such as that constants exist but are not numerical thresholds) into a single appendix section, as you suggest.

Weakness 2: narrow scope. We agree the main theorem is for a known, positive, invertible finite-state model, and Table 2 states this. Scope has been widened in two ways within that setting: finite on-time alphabets with informative late fields (Theorem 8, D≥1D\ge1), and a growing-KK reset family with explicit contraction ≤4/9\le 4/9. Extending beyond these classes, including unknown models and general growing-KK families, is not claimed and is listed as a limitation.

Thank you again for the constructive review.

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

The paper studies the minimum persistent memory required for Bayesian filtering with arbitrarily ordered late observations.

Critical strengths
  • Theoretical novelty: Matching minimax memory bounds, beyond established fixed-lag filtering and contraction-based truncation.

  • Mathematical rigor: Doob contraction, block-triangular response Jacobian, volume-packing converse; explicit binary/three-state constructions and unbounded-evidence impossibility result.

Critical weaknesses
  • Restricted applicability: Known finite-state model, positive invertible transitions, bounded evidence, and locally rich observations. Constants and practical saturation thresholds unspecified; growing-(K) result restricted to a reset family.

  • Incomplete practical validation: 343 vs. 9,680 bytes (28.2× reduction), but only against a particular full-window implementation; scheduler metadata excluded. Neural results limited to synthetic binary HMMs and one-unit GRUs.

Questions for authors

Q1. Can (L_\epsilon), (\epsilon_0), and hidden constants be quantified for representative models?

Q2. Does the matching lower bound survive finite-alphabet on-time evidence without open field support?

Q3. How quickly do the bounds deteriorate as (P) approaches singularity or mixing becomes slow?

Q4. Does (\Theta(D)) pending-mask storage undermine the claimed saturation at the system level?

Q5. Why no comparison with optimized OOSM or fixed-lag algorithms under matched TV accuracy?

1 comment

Response to Reviewer 5QpV

Thank you for the careful and accurate summary, and for the five specific questions. Every figure below comes from results already in the paper and appendices; we ran no new experiments for this reply.

Q1. Can LϵL_\epsilon, ϵ0\epsilon_0 and the hidden constants be quantified for representative models?

  • LϵL_\epsilon is explicit. Theorem 2 gives Lϵ=⌈log⁡(2/ϵ)/(−log⁡κ)⌉L_\epsilon=\lceil \log(2/\epsilon)/(-\log\kappa)\rceil with κ=1−m/M\kappa=1-m/M, where m≤P(x,x′)≤Mm\le P(x,x')\le M. The upper-bound constant depends on m,M,H,Am,M,H,A and the initial-logit bound, but not on DD.
  • ϵ0\epsilon_0 and the lower-bound constants c,Cc,C are model-dependent. We do not claim explicit values for general models, and we say so in the scope paragraph.
  • One family has quantified constants. For the growing-state reset family, the prediction–update contraction is at most 4/94/9 for every KK, and σmin⁡(AK)≥(200K)−1\sigma_{\min}(A_K)\ge(200K)^{-1}. The bounds hold uniformly in K,DK,D when log⁡(1/ϵ)≥C0log⁡K\log(1/\epsilon)\ge C_0\log K (Corollary 3).
  • Measured thresholds. At K=2K=2, D=256D=256, ϵ=2−8\epsilon=2^{-8} (the generative comparison in Appendix, appendix_new_experiments), the adaptive cut code uses 4 / 15 / 155 bytes for reset families .125 / .6 / .94. For comparison, the full-grid code uses 290 / 322 / 418 bytes. The saturation point therefore moves strongly with mixing speed.

Q2. Does the matching lower bound survive finite-alphabet on-time evidence without open field support?

  • Mixed case. Theorem 8 (thm:generalmixed) extends the matching law to finite on-time alphabets with informative late fields. It needs positive invertible PP, a positive finite on-time channel, bounded late fields with a zero neighborhood, and D≥1D\ge1.
  • Both channels finite and positive. Then a fixed-prior symbol code applies (Proposition finitealphabet), so the field-rich converse does not carry over.
  • Delayed channel. A finite delayed alphabet suffices when one positive outcome satisfies condition (OC) (Proposition 2).

Q3. How quickly do the bounds deteriorate as PP approaches singularity or mixing becomes slow?

  • Singularity. Proposition 3 gives a quantitative fixed-KK margin: the measure of {∣RK∣≤γ}\{|\mathcal R_K|\le\gamma\} is at most min⁡{1,ACγ1/dK}\min\{1,A_{\mathcal C}\gamma^{1/d_K}\}, and the matching-law constants are uniform on {∣RK∣≥γ}\{|\mathcal R_K|\ge\gamma\}. We do not claim uniformity near the singular set, as stated in the limitations.
  • Slow mixing. κ→1\kappa\to1 makes LϵL_\epsilon grow, which delays saturation. The reset .94 row above (155 bytes versus 4 at reset .125) shows this empirically. The "Weak blocks" family (525 bytes) is a case where the cut code gives no savings over the full grid (514 bytes).

Q4. Does Θ(D)\Theta(D) pending-mask storage undermine saturation at the system level? Yes, in the worst case, and the paper states this. Exact pending-mask recovery adds Θ(D)\Theta(D) bits (Theorem 4), so total-system memory need not saturate (see the scope paragraph). Our law concerns correction state only. In the experiments, every reported byte count includes a mask allowance (e.g. a 32-byte mask in the joint run), and shared model bytes are listed separately.

Q5. Why no comparison with optimized OOSM or fixed-lag algorithms under matched TV accuracy? We do compare, within the limits of what we implemented.

  • Baselines. Cached full replay, validation-tuned quantized lag (a fixed-lag approximation), a full grid, and a dynamic product tree. All share the same posterior target, and every arrival prefix is checked.
  • Matched accuracy. In the joint run (K=8K=8, ρ=.6\rho=.6, D=256D=256, ϵ=1/256\epsilon=1/256), adaptive packing uses 392 bytes, uniform packing 455, cached lag 4,144, and a non-padded cut tree 20,504, each plus a 32-byte mask.
  • Honest outcome. The tree is faster (median .00262 s versus .14106 s per trace), and quantized lag is already close in memory. We therefore present the result as a characterization and storage–work tradeoff, not an algorithmic advantage.
  • Tuned lag has no certificate. 43 of 324 validation-tuned method/target cells violate the target on at least one test case, while no certified method exceeds its certificate.
  • Limitation. We did not benchmark the published storage-efficient or selective OOSM particle filters, and we agree this is a gap.

On the 343 vs 9,680 byte example. We agree with your caveat. It is retained only as one full-grid comparison, and the main text says it is not a general algorithmic advantage. On the neural results: they are mechanism tests and not neural superiority claims. We have added a scorecard to Section 6 listing what is and is not supported.

Thank you again.

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

This paper studies memory requirements for state estimation with delayed evidence. It presents theoretical results and toy numerical experiments. The impact of this paper's research topic in the current machine learning community seems not significant.

Critical strengths
  • The paper presents extensive theoretical analysis.

  • The paper provides numerical checks of the proposed construction and a controlled GRU experiment.

Critical weaknesses
  • The writing lacks clarity. For example, the "What this paper establishes" box uses DD whose formal definition is not given before, and "persistent deterministic bits" without sufficient explanation. The formulation is difficult to follow without a background section.

  • The practical applications and settings for learning tasks of this work are unclear to me.

  • The experiments focus on synthetic models and a small GRU study. They provide limited evidence of how the proposed result would help a practical learning task, considering the advancements of the modern deep learning approaches.

Questions for authors
  • Can the authors add a background section explaining state estimation, delayed observations, and the problem formulation?

  • Can the authors give a concrete application and explain how the result could inform the design of learning methods, and in which sense this formulation remains valuable in the current deep learning regime?

1 comment

Response to Reviewer pHta

Thank you for the careful review and for flagging the clarity problems. We have revised the first ten pages in response, and we answer each point below.

  1. Clarity: undefined notation and "persistent deterministic bits". We agree that the "What this paper establishes" box was hard to read without context. In the revision, every symbol in the box is defined before the box appears.
  • The Introduction now has a paragraph titled "One running example", placed before the box. It explains what an HMM and its filtering belief are, with the example of walking, sitting or standing. It also explains what a late packet is, using the trace a2,a3,a4,g2a_2,a_3,a_4,g_2, where a gyroscope packet about time 2 arrives after an accelerometer has reached time 4.
  • The same paragraph defines DD (maximum timestamp lag) and ϵ\epsilon (total-variation error, half the sum of absolute probability differences).
  • It also defines "persistent deterministic bits": a BB-bit state takes at most 2B2^B values between events, and model parameters and temporary workspace are counted separately.
  • Inside the box, q=K−1q=K-1 and x=log⁡(1/ϵ)x=\log(1/\epsilon) are now stated, and the two regimes of min⁡{D+1,x}\min\{D+1,x\} are colour-coded as delay-limited and resolution-limited.
  • A four-step strip at the top of the Introduction (forget, late packet, phase law, evidence) gives the storyline before any formalism.
  1. Background section. Rather than adding a separate section under the page limit, we moved the background into the Introduction, as described above, and kept the formal problem statement in Section 3. If the reviewer still finds this insufficient, we will expand it in the camera-ready version.

  2. Concrete application and learning relevance. The main text uses UCI HAPT with real accelerometer and gyroscope data and injected communication delays. Section 6 is now organised around three explicit questions.

  • Q2 (real sensor fusion): At delay 4, fusion raises F1 from .47035 to .54141. A certified code keeps this F1 using 38 bytes of state, context and mask, versus 973 for cached replay.
  • Q3 (learned predictor): In a supervised task with actual labels, a 64-bit explicit-cut decoder improves F1 from .56526 to .58725 when the late query is provided, with a paired 95% subject-bootstrap interval of [.01023, .04598].
  • Design criterion: The practical message is to preserve responses to future corrections, not only predictive information. This gives a concrete budget for how many bits a late-evidence-aware state needs.
  1. Limited evidence against modern deep learning. We agree this is a limitation and have made it more visible. A scorecard at the end of Section 6 separates what is supported from what is not.
  • Supported: certified codes never exceed their certificate, fusion is useful, compact storage preserves the fusion gain, and learned predictors use late evidence.
  • Not claimed: robust F1 dominance over strong replay baselines, and neural superiority. In our experiments, stronger replay controls match or beat the cut code at several budgets.

The contribution is a known-model information-theoretic characterization of correction memory. The experiments are mechanism checks, and we do not claim they establish an advantage for modern deep learning pipelines.

We thank the reviewer again and note that your confidence is low, so we have tried to make the main text self-contained for readers outside this subfield.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.