Decoding Fronts in Log-Time Memory

A log-time memory keeps a running summary of a stream. Recent moments are stored sharply, and older moments are blurred into progressively wider time bins. This kind of memory makes sequence models robust to changes in playback speed, but it cannot say how far back a specific past event can still be recovered. We propose to treat such a memory as a communication channel. The stream writes events into a bank of leaky integrators with logarithmically spaced decay rates. A reader then tries to decode which events happened and when. Density evolution is a technique from coding theory that predicts exactly where iterative decoders stop working. It tracks the probability distribution of the decoder's errors rather than individual messages. We will use it to predict the recall horizon: the lag beyond which a past event becomes undecodable, as a function of how busy the stream is and how many features the memory carries.

Our central conjecture comes from a structural coincidence. A log-time memory looks like a spatially coupled code. In such codes, neighboring blocks share information, and an easily decoded "seed" block lets decoding spread outward like a wave. In a log-time memory, neighboring time bins overlap, and the most recent bins are high-precision seeds. An iterative decoder can decode recent events first, subtract them from all the integrators, and thereby clean up older bins. This should push a decoding front backward into the past. The memory itself stays the same; only the reader changes. If the conjecture holds, this extends recall well beyond what a one-shot readout achieves, and the theory says by how much.

Core Claim

Write the memory as a bank of $N$ integrators. Each integrator $i$ holds a vector $F_i(t)=\sum_{t'\le t} e^{-s_i (t-t')}x(t') + \text{noise}$. Here $x(t')\in\mathbb{R}^d$ is the feature vector of the stream at time $t'$, typically a sparse sum of codewords from a dictionary of event types. The decay rates $s_i$ are log-spaced.

This is the recurrent form of the Laplace-transform memory used in DeepSITH and CogRNN. In those works, an approximate inverse transform turns the bank into "time cells" whose receptive fields widen in proportion to their peak lag. Those papers read the memory with a learned dense layer or convolution, which amounts to a one-shot readout.

Our decoder instead runs iterative interference cancellation over the time bins. In each round, every bin estimates its event using a sectioned denoiser of the kind used for superposition codes in Barbier & Krzakala. It then subtracts its estimated contribution from all integrators. In the many-feature limit ($d\to\infty$ with event load fixed), we conjecture that the effective noise $\sigma_j^2$ on bin $j$ evolves over decoding rounds $\ell$ by a vector recursion of the form

$$\sigma_j^{2,(\ell+1)} = \sigma_w^2 + \sum_k A_{jk}\,\mathrm{mmse}\big(\sigma_k^{2,(\ell)}\big).$$

In this recursion, $\sigma_w^2$ is the channel noise floor. $\mathrm{mmse}(\cdot)$ is the error of the per-bin denoiser at a given noise level. $A_{jk}$ measures how much bin $k$'s residual leaks into bin $j$, scaled by the number of events per bin relative to $d$.

Log spacing makes $A_{jk}$ depend only on $j-k$, so the system is shift-invariant along the log-time axis. This is the structure under which Montanari found that iterative decoding behaves like a traveling front with constant velocity. It is also the structure under which Andriyanova et al. and Häger et al. prove "threshold saturation": a simple iterative decoder reaching the performance limit of the best possible decoder.

Three falsifiable predictions follow. First, recall at lag $\tau$ should depend on stream density $\rho$ and lag mainly through the product $\rho\tau$. Recall curves should therefore collapse across playback speeds for the log memory, but not for a linear-time recurrent network. Second, a constant front velocity in log-time means the decoded horizon in real time should grow roughly geometrically with decoding rounds until it stalls. Third, the stall point should be predicted by the recursion's fixed point, and should move outward as the decay rates are reallocated. This last effect would parallel how irregular degree allocation raised the generalized product code threshold from $c^*\approx 11.34$ to $c^*\approx 13.42$ in Häger et al..

Relation to Prior Work

The log-compression line supplies the memory and motivates the question. SITHCon showed zero-shot invariance to rescaling from 0.1x to 10x on Audio MNIST and Morse code by convolving over log-time. DeepSITH separated when (the fixed Laplace bank) from what (learned weights). Gradual Forgetting used a stateless bank of 53 filters as a front-end that compresses 8,192 tokens into roughly 300 attention slots. All of these concede that the distant past is lossy, and none characterizes how lossy as a function of stream statistics. We keep their memory unchanged and replace the one-shot reader with a decoder whose limits can be computed.

The density evolution line supplies the method. Montanari's front-propagation picture and the spatial-coupling results motivate the decoder design. Barbier & Krzakala's analysis of approximate message passing (AMP) on sectioned sparse signals supplies the per-bin denoiser and the error-tracking recursion. That paper also supplies a warning that constrains the design: their analysis shows iterative decoders getting trapped in metastable states when the error landscape has two competing optima. The concentration results for deterministic product codes in Häger et al. are our reason to expect a deterministic, non-random structure like a Laplace bank to follow an ensemble-style recursion at all.

The recurrent video line supplies the application regime. ALVC and VideoStreaming propagate learned states at a fixed frame rate with no theory of when they forget. EgoSchema shows the cost: models score 20–32% against 76.2% for humans, and adding more frames can hurt.

A reviewer will rightly object that density evolution has never been shown to apply to nonlinear neural hidden states. We avoid that gap by design. The memory is linear and analytically fixed, and all learning sits in the codebook encoder upstream and the denoiser. The theory therefore concerns a linear channel plus a structured decoder, which is the setting where density evolution has a track record.

There is a serious technical risk. The Laplace kernels are smooth and heavily overlapping, so the measurement operator is far from the independent random matrices assumed by standard AMP theory. Plain AMP may diverge. We will use damped and bin-wise variants, and we treat agreement between the recursion and simulation as an empirical result to be established, not assumed.

Research Program

The first stage is purely analytic and synthetic. We will derive the coupling matrix $A$ for the Post-inversion and Padé versions of the bank, and compute fixed points of the recursion over a grid of event load, noise level and number of filters $N$. We will then compare predicted per-lag recall against simulation on synthetic codeword streams with $d$ from 64 to 4096. The aim is to see whether agreement sharpens as $d$ grows, as concentration arguments suggest.

The second stage uses the recursion as a design tool. We will optimize the allocation of decay rates and the per-bin load to push the stall point outward at a fixed state size. We will then confirm in simulation that the optimized bank beats uniform log spacing.

The third stage embeds the memory as the persistent state of a streaming model. The memory replaces the stateless front-end of Gradual Forgetting and the propagated memory tokens of a VideoStreaming-style pipeline. We add a small exact cache that stores only the events the recursion predicts the log memory will lose. In this way, density evolution decides when verbatim storage is needed, which addresses the tension between fading resolution and the long-certificate questions in EgoSchema.

Baselines

The naive reference point is an exact sliding window holding the same number of floating-point values as the log memory ($N\cdot d$), read by the same denoiser. This shows what log compression buys over simple truncation at equal memory size.

The key ablation is the same log memory read in one shot, with no iterative cancellation. It is run with the same denoiser, codebook and training budget. Any gain in recall horizon over this ablation is attributable to the decoding front, and that gain is the central result. Beating it means a statistically clear outward shift of the lag at which recall drops below 50%, at matched compute per step, with the shift matching the recursion's prediction within the predicted stall bin.

The strongest learned competitor on the synthetic and timing tasks is DeepSITH's learned dense readout of the same bank. It reports 97.36% on permuted sequential MNIST, against 97.15% for the Legendre Memory Unit and 90.2% for an LSTM (DeepSITH). We will retrain it with the same parameter count and hyperparameter search budget as our decoder. We must at least match 97.36% on that benchmark so that the iterative reader costs nothing on standard tasks. We must also exceed it on delayed-recall streams at high event density.

For rescaling, the reference is SITHCon. It held 100% Morse decoding accuracy over an order of magnitude of speed change, while a temporal convolutional network fell to chance (SITHCon). Our system must preserve that invariance while adding recall depth.

We will also run a learned diagonal linear recurrence with trainable decay rates initialized log-spaced. This is the state-space model family a reviewer will name. We found no reported result on Lacuna for this family on these benchmarks, so we will train it ourselves under the same budget.

On language, the strongest reported comparison is WikiText-103 perplexity: 23.56 for the SITH-augmented GPT-2 Small, against 24.00 for Transformer-XL and 24.85 for Recurrent Memory Transformers (Gradual Forgetting). We will first reproduce 23.56, then swap in the recurrent memory with iterative decoding at equal attention slots. Beating it means lower perplexity than our own reproduction.

On EgoSchema, current models sit at 20–32% (EgoSchema). We found no reported result on Lacuna for VideoStreaming's EgoSchema accuracy, so we will rerun its memory-token pipeline with the same frozen encoder and language model.

Why not just…?

Why not just train a bigger learned readout and let it discover interference cancellation itself? This is the most serious threat. An attention layer over time cells with enough parameters could, in principle, learn to subtract recent events. We will test it directly with equal-parameter and double-parameter learned readouts trained on the same streams. If they match the iterative decoder's recall horizon, the decoder adds nothing practical. Two things would still remain in that case. The recursion would predict where any reader fails, and it would allow allocation of decay rates without grid search. We would then reframe the contribution around those two uses. We expect, but do not assume, that learned readouts trained at one load will fail to extrapolate to higher loads, whereas the recursion's fixed point transfers.

Why not just add more filters or a longer exact buffer? More memory always helps, but cost grows linearly with horizon for a buffer. EgoSchema also shows that feeding more raw frames can lower accuracy rather than raise it (EgoSchema). The equal-memory sliding-window baseline and a sweep over $N$ will show whether iterative decoding gives a better horizon per stored float than simply enlarging the bank.

Why not just learn the decay rates, as state-space models do? Learned rates can fit the training timescale but have no reason to stay log-spaced. Shift-invariance along log-time is what both the scale invariance and the front structure depend on. The learned-decay baseline evaluated under 0.25x–4x rescaling, and the recall-collapse test in $\rho\tau$, will show whether learning the rates breaks invariance. If learned rates stay invariant and recall as far, the fixed bank loses its justification, and we would report that.

Why not just augment training data across playback speeds? In the cited evidence, temporal convolutional networks failed outside their training scale (SITHCon), and recurrent agents failed at 2x and 4x where CogRNN succeeded (CogRNN). Our rescaling experiments include an augmented LSTM so this is checked again on recall tasks rather than classification.

Proposed Experiments

The decisive check is synthetic. We will generate codeword event streams at multiple densities, speeds and feature dimensions, and plot predicted against empirical per-lag recall for both one-shot and iterative readers. The theory survives if three things hold. The empirical stall lag must sit within one log-bin of the predicted fixed point for $d\ge 512$. The decoded horizon must grow over rounds as the front picture predicts. And curves at different speeds must collapse in $\rho\tau$ for the log memory but not for the LSTM or learned-decay baselines. It fails if the recursion's error grows rather than shrinks with $d$, which would mean the overlapping kernels break the independence the analysis needs.

Secondary checks test whether the iterative reader preserves known results while extending recall. We will run permuted sequential MNIST, the Adding problem up to $T=5000$, Morse and Audio MNIST with rescaling, plus a delayed-recall Morse variant in which the queried character lies far in the past. The interval-timing tasks of CogRNN test whether this holds under reinforcement learning.

The applied checks are WikiText-103 against the reproduced 23.56 perplexity, and EgoSchema with a frozen frame encoder. On EgoSchema, the recursion-gated exact cache must beat both the ungated log memory and the VideoStreaming-style rerun at equal token budget. The human score of about 67% at one frame per second (EgoSchema) indicates that coarse temporal structure carries most of the signal, which is the regime a log memory is built for.