Induction Heads Interpolate N-Grams

Induction heads are attention circuits believed to underlie in-context learning in transformers, yet a precise characterization of the estimators they implement remains elusive. We study transformers trained on order-$k$ Markov chains and identify two complementary smoothing mechanisms. First, at finite attention-weight scale, the circuit implements a soft context-matching estimator: it aggregates contributions from exact and partial context matches, weighted exponentially by their overlap, and induces a data-dependent interpolation across context orders analogous to Jelinek--Mercer smoothing. Second, a beginning-of-sequence (BOS) token induces additive pseudo-counts, recovering Dirichlet-style smoothing. We construct a disentangled transformer implementing both mechanisms and show that trained transformers recover the predicted attention patterns. Across settings where pseudo-count smoothing is optimal or lower-order contexts provide structured evidence, trained transformers match or outperform classical count-based baselines. Our results bridge mechanistic interpretability of induction heads with classical statistical smoothing, revealing that transformers learn to regularize in-context estimation rather than simply count.

One of the most striking abilities of large language models is in-context learning: the ability to adapt to a new task from examples given in the prompt, without changing the model’s parameters. One proposed explanation is that these models contain small internal circuits, or recurring patterns of computation, that carry out useful prediction strategies. A well-known example is the induction head, which looks back through the prompt, finds earlier patterns that resemble the current one, and copies the token that followed those patterns. This paper studies what induction heads are actually doing in a controlled sequence-prediction setting. Previous work often described them as simply counting exact repeated patterns. We show that they can do something richer: they also use partial matches, giving more weight to past contexts that are more similar to the current one. This helps the model make better predictions when exact repeats are rare. We also show that a special beginning-of-sequence token can help the model avoid overconfident predictions when there is little evidence, acting like a built-in smoothing mechanism. Overall, our results connect transformer circuits and induction heads with classical methods for improving sequence prediction, showing that transformers do more than memorize and count: they learn to combine evidence from context in a statistically useful way.