Hidden Routing: A Tight Alphabet-Size Gap in Autoregressive Online Learning

An autoregressive model generates a sequence by applying the same next-token rule at every step, and intermediate steps can carry information that is absent from the final token. Endpoint-only feedback observes only that final token, while full-trajectory feedback observes every step, so the two protocols can differ in online complexity even under the same prediction target and loss. For binary alphabets, existing analyses show how this gap grows with the rollout length, but they do not determine whether alphabet size adds a separate cost. We prove that this alphabet-size cost is unavoidable in the worst case. For finite alphabets, a multiclass sequential-growth argument bounds final-token complexity linearly in the base-class Littlestone dimension and logarithmically in the product of alphabet size and rollout length. We match this alphabet dependence with a two-step, time-invariant shared-address family that preserves the base and trajectory dimensions. Its intermediate token identifies a block address, whereas its endpoint reveals one requested bit. The construction yields exact deterministic mistake bounds and realizable learning rates in the probably approximately correct (PAC) model under both feedback protocols. Computational checks reproduce the feedback gap and its alphabet-size staircase.