Fixed-Window Models and the Hidden State They Cannot Represent

Predicting the next symbol of a sequence from the previous $k$ symbols is the entry point to sequence modelling. The construction is a sliding window: concatenate the embeddings of positions $t-k+1$ through $t$ into a single vector of length $k \cdot n$ for embedding width $n$, and pass it through a multilayer perceptron that emits a distribution over the next symbol. Nothing in that construction depends on $t$, so the same weights serve every position and every position of a corpus can be trained at once.

The design question is what to do with $k$. It is fixed before training, and the model contains no representation of anything outside the window. Two prefixes that agree on their last $k$ symbols produce identical inputs, and therefore bit-identical outputs. That property, rather than the choice of activation or the number of layers, is what defines the family.

A window is a Markov assumption of order k

Writing the model as $p(x_{t+1} \mid x_{t-k+1}, \dots, x_t)$ states the assumption directly: the future depends on the past only through the last $k$ symbols. Dependencies that outlive $k$ steps are not approximated, they are absent. The window has $|V|^k$ possible contents for a vocabulary $V$, so for an alphabet of two symbols and a window of 32 positions there are just over four billion distinct inputs, each of which receives one fixed output distribution. All histories that share a suffix of length 32 collapse to the same distribution.

The failure is countable rather than gradual. Take the task of emitting the running count of one symbol modulo three. The correct output at step $t$ is a function of the whole prefix, and no suffix of bounded length determines it. A wider window shifts the point of failure later without removing it, because two prefixes that differ only in their count of the tracked symbol beyond position $t-k$ remain indistinguishable to the model. The same argument covers matching brackets, the scope of a negation, whether a quoted string is still open, and any quantity that must be carried forward without bound.

What a learned state changes

A recurrence replaces the window with a vector of fixed width $d$:

$$h_t = \phi(W_{xh} x_t + W_{hh} h_{t-1} + b)$$

The input at step $t$ is the current symbol together with the previous state, and the output is the next state. The parameter count is $d(n+d)+d$, independent of sequence length, and the same weights are applied $T$ times. The step-by-step mechanics of that cell, including the shapes involved and the cost per step, are covered in what a recurrent cell computes.

The representational difference is not that one family is approximate and the other exact. Both are functions of bounded internal width. A window model of width $k$ and embedding size $n$ has $k \cdot n$ real values of input to work with, and its history equivalence classes are exactly the suffixes of length $k$, fixed in advance by the frame. A recurrent model of width $d$ in 32-bit floats has $32d$ bits of state, so $d = 256$ gives 8192 bits, and the map from prefix to state is chosen by training rather than imposed. The state is not a lossless record of the prefix; it is a statistic that has to be sufficient for the training objective, and whether training produces such a statistic is an empirical property of the objective and the optimization, not a guarantee of the architecture.

Where the state is spent

Because the state is trained, what it holds is whatever reduces the loss. In a language-model style objective the gradient rewards state that helps predict the next symbol, so the state tends to encode a compressed summary of the recent topic, syntactic category, and open constituents. A linear recurrence is a genuine accumulator: a state that adds a constant at each step and is never squashed can hold an unbounded count, and in the presence of a squashing nonlinearity the accumulation saturates. Long short-term memory was designed around exactly this observation, using an additive path controlled by gates so that information can be held without being overwritten every step; the gate mechanisms are described in gating in LSTM and GRU cells.

Two degenerate cases are worth naming because they appear with any fixed-width state. The first is saturation: once a state component sits in the flat region of $\tanh$, differences in the input produce differences below the resolution of the representation and the component stops carrying information. The second is overwriting: a cell that writes every step to the same subspace loses long-range content unless the write is conditional on the input, which is the role gates play.

Deciding which frame fits a task

A single test separates the two frames without any measurement. Take an input whose distance-$(k+1)$ history should change the answer, alter that out-of-window symbol, and check whether the model’s output can change at all: for a window model it cannot, because the input vector is unchanged. Applied to a task rather than a model, the test asks whether the label is a function of a bounded span. Tense agreement between an auxiliary and a following verb form, the segmentation of a word into morphemes, and transliteration are all decidable from a span of a few symbols, and a window with $k$ in the range of the longest such span is the right frame; the recurrence adds a serial chain of $T$ steps for reach that the task never uses. Contradiction detection between two clauses of a paragraph, matching delimiters, and coreference have no such bound, and any wide-window approximation is a truncation of the dependency rather than a model of it.

The two frames also differ in what inference costs as a stream lengthens. Evaluating a window model requires reading $k$ embeddings per position, so per-position cost and per-position memory are constant, and the model has no notion of how much text it has already seen. A recurrent model is initialized once and then applies a $O(d(n+d))$ update per position while retaining $d$ values, so its memory is constant in the stream length and its per-position cost does not grow. That constant-memory property is the reason recurrence remains the natural frame for unbounded streams even where a wider unsupervised context is available.

The cost of sequential dependence

For a window of width $k$, embedding width $n$, and hidden width $d$, a position costs on the order of $k \cdot n \cdot d$ multiply-accumulates, and positions are independent, so a batch of length $T$ is evaluated in parallel with depth independent of $T$. A recurrent cell costs on the order of $d(n + d)$ per step, which is cheaper once $k$ is comparable to $d$, but step $t$ cannot start before step $t-1$ has finished. Arithmetic per sequence is $O(T \cdot d^{2})$ and the critical path is $T$ sequential matrix-vector products. That is the axis: the window trades representational reach for parallelism along time, and the recurrence trades parallel depth for a state that survives any number of steps.

Memory follows the same split. Training a window model needs one input vector per position, $O(k \cdot n)$ values, while backpropagation through a recurrence retains per-step activations for all $T$ steps, $O(T \cdot d)$, so the activation footprint grows linearly in sequence length. Chunking the sequence into segments bounds the footprint and truncates the gradient path, which is the standard compromise discussed in backpropagation through time.

Locality without a learned state

The window construction survives in two forms. Stacked convolutions produce a receptive field that grows linearly with depth for a fixed kernel width, which restores parallel evaluation and a gradient path of constant depth across positions while keeping parameters shared. Attention over a restricted span does the same thing with input-dependent weights, so the set of positions that influence a given output is chosen per input rather than fixed by the architecture, a shift described in attention as alignment. Both retain a bounded receptive field per layer. Depth, not width, is what buys reach, and reach purchased that way costs compute that grows with the sequence.

What no fixed-width construction escapes is compression. Any function computed by a network with a finite state must assign the same output to two prefixes that map to the same state, and for arbitrary long sequences there is no finite state that separates all of them. The real question for a sequence model is which distinctions the objective needs, and whether the training signal is strong enough to force them into the state before the dependency decays.