betaFeedback

WorksMathematics

Recursive memory for prediction and generation

Abstract

Recurrent and state-space language models compress the past into a state of fixed size. The state must answer questions about the future now, and it must remain useful as new tokens arrive, including tokens the model samples itself. We show that the second requirement can cost far more memory than the first. For a known hidden Markov source with positive transition probabilities, a state of O(log⁡(1/ε))O(\log(1/\varepsilon)) bits answers every question about the future to accuracy ε\varepsilon, however far ahead it looks, because the Bayesian filter forgets its rounding errors. Generating the future is different. When a model feeds each sampled token back into its state, the small errors in its next-token distributions add up, and TT tokens can require a state of order log⁡(T/ε)\log(T/\varepsilon) bits. The lower bound comes from the KL chain rule: at every step, a model with KK states pays for approximating the true next-token distribution by one of only KK distributions. The argument applies to any source, including a language model continuing a prompt, and a small-ball estimate makes it tight for two-state sources. The extra log⁡T\log T disappears if the model keeps private randomness, or if error is budgeted per token, as in perplexity. Statistics of the recent past show the same gap between describing and maintaining. The number of ones among the last nn bits takes log⁡n\log n bits to write down. But if each bit is a noisy copy of the one nn steps earlier, tracking that count to a mean-square error E2E^2 well below its variance costs order n/(1+E2)+log⁡nn/(1+E^2)+\log n bits. Information about each bit must be kept until the bit leaves the window, and a queue holding the counts of recent blocks keeps just enough of it.

Paper details

vlnc:W_pcg3aera
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
Usage

views · 5

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…