# Prediction with a Short Memory

arXiv: https://arxiv.org/abs/1612.02526 · HTML: https://mlsanity.com/paper/1612.02526/

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Dec 2016.

## Built on by (most cited first, 13 of 13)

- [Make Your LLM Fully Utilize the Context](https://mlsanity.com/paper/2404.16811/) (2024)
- [Do Long-Range Language Models Actually Use Long-Range Context?](https://mlsanity.com/paper/2109.09115/) (2021)
- [RankGen: Improving Text Generation with Large Ranking Models](https://mlsanity.com/paper/2205.09726/) (2022)
- [Planning in Observable POMDPs in Quasipolynomial Time](https://mlsanity.com/paper/2201.04735/) (2022)
- [BatchPrompt: Accomplish more with less](https://mlsanity.com/paper/2309.00384/) (2023)
- [Model Stealing for Any Low-Rank Language Model](https://mlsanity.com/paper/2411.07536/) (2024)
- [Masks Can Be Distracting: On Context Comprehension in Diffusion Language Models](https://mlsanity.com/paper/2511.21338/) (2025)
- [Morphosyntactic probing of multilingual BERT models](https://mlsanity.com/paper/2306.06205/) (2023)
- [On the Privacy Risks of Deploying Recurrent Neural Networks in Machine Learning Models](https://mlsanity.com/paper/2110.03054/) (2021)
- [Learning what to remember](https://mlsanity.com/paper/2201.03806/) (2022)
- [Provable Long-Range Benefits of Next-Token Prediction](https://mlsanity.com/paper/2512.07818/) (2025)
- [A Hierarchical Language Model with Predictable Scaling Laws and Provable Benefits of Reasoning](https://mlsanity.com/paper/2605.13687/) (2026)
- [How Wrong Can a Good Predictor Be? Diverging Updates with Vanishing Predictive KL](https://mlsanity.com/paper/2609.11132/) (2026)

## Abstract (arXiv)

We consider the problem of predicting the next observation given a sequence of past observations, and consider the extent to which accurate prediction requires complex algorithms that explicitly leverage long-range dependencies. Perhaps surprisingly, our positive results show that for a broad class of sequences, there is an algorithm that predicts well on average, and bases its predictions only on the most recent few observation together with a set of simple summary statistics of the past observations. Specifically, we show that for any distribution over observations, if the mutual information between past observations and future observations is upper bounded by I, then a simple Markov model over the most recent I/ε observations obtains expected KL error ε---and hence ℓ1 error √ε---with respect to the optimal predictor that has access to the entire past and knows the data generating distribution. For a Hidden Markov Model with n hidden states, I is bounded by log n, a quantity that does not depend on the mixing time, and we show that the trivial prediction algorithm based on the empirical frequencies of length O(log n/ε) windows of observations achieves this error, provided the length of the sequence is dOmega(log n/ε), where d is the size of the observation alphabet. We also establish that this result cannot be improved upon, even for the class of HMMs, in the following two senses: First, for HMMs with n hidden states, a window length of log n/ε is information-theoretically necessary to achieve expected ℓ1 error √ε. Second, the dTheta(log n/ε) samples required to estimate the Markov model for an observation alphabet of size d is necessary for any computationally tractable learning algorithm, assuming the hardness of strongly refuting a certain class of CSPs.