acceptodds
Under review as a conference paper at ICLR 2027

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

Abstract

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.

Primary area:
learning theory
Keywords:
autoregressive online learning, Littlestone dimension, endpoint-only feedback, trajectory feedback, alphabet size, mistake bounds, PAC learning

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_PAhmOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies how the token alphabet size introduces a learning penalty in autoregressive models when a learner observes only the final output token vs. than the entire chain-of-thought trajectory. The authors construct a two-step shared-address family to illustrate that hiding intermediate routing decisions creates a log complexity gap in alphabet size between e2e and cot. Matching their result with a general upper bound, the paper establishes tight separations for both deterministic online mistake bounds and PAC sample complexity.

Critical strengths

The authors raised a well-defined question and provided a sharp theoretical answer. Furthermore, the paper provides exact deterministic mistake bounds and matching PAC rates.

Critical weaknesses

The scope of theoretical contribution seem limited, and the experiments are only verification of the theory (as opposed to providing new evidence on the practical relevance). See questions.

Questions for authors

What is the precise novelty relative to existing results? I feel like the message could be improved by highlighting exactly what is new separating the new alphabet lower bound, removal of the binary upper bound’s extra log d, and learning consequences already implied by existing trajectory bounds.

Reviewer_8SaDOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

This paper considers the problem of online learning, and introduces two different hypothesis classes, derived from two mappings (one called end-to-end, which only outputs the final prediction, and one called CoT, which outputs the entire history). The main results are a characterization of the Litttlestone dimensions of these two hypothesis classes.

Critical strengths

The distinction between the two hypothesis classes introduced in the paper is potentially interesting. Unfortunately, I'm unable to discern the essence of the problem formulation and to appreciate the main results.

Critical weaknesses

This paper is hard for me to follow, to the extent that I am unable to read all sections carefully. I'm listing a few questions in the "Questions for Authors" section below, where * denotes the major concerns.

Questions for authors
    • I’m puzzled by the actual problem formulation. I understand the statement in (1) and the definition of f^{2e2, M} and f^{CoT, M}, the authors then use f^{2e2, M} and f^{CoT, M} to define two hypothesis classes F^{2e2} and F^{CoT} (however, I would move the definition of these from the Appendix to the main text, as they are central to the results). My understanding is that the authors would like to characterize the learnability of these two different hypothesis classes, where the goal is just to predict the final token y_M. What is unclear to me is how the two hypothesis classes are different, if the goal is only to predict the final y_M. More precisely, it is not clear to me for the hypothesis class F^{CoT}, what difference the history (y_1,…. y_{M-1}) makes in terms of defining the prediction capability of y_M.
    • my understanding is that the Littlestone dimension is a relevant quantity for online learnability (in both realizable and unrealizable cases) if we care about predicting the entire sequence. However it seems that the current paper only cares about predicting the final y_M. So it is not entirely clear to me, from the paper, why the Littlestone dimension is an important quantity for this setup.
  • Section 3.1 “Throughout, online complexity means the optimal deterministic realizable mistake bound.” - not clear what this means. And there is no reference to the term “online complexity” after section 3.1

  • the paper uses the terms “token”, “prompt”, “chain of thought” etc. as they appear in papers on the topic of language models. However, I don’t see any actual connection to a problem formulation in the language model (which is linked to my comment 1, as the problem formulation is not clear to me). As such, I don’t see the need of using these terminology, which to me, makes the paper more confusing than needed.

  • The paper is very hard to read. For example in section 4.1, the first sentence introduces a few terms: what does “prompt” mean here? What are “block-coordinate pair” or “block address”? These terms are introduced without any proper definition. Although some of these are explained later in the text, the overall structure of the writing makes the paper difficult to follow.

Reviewer_Wm7YOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper theoretically proves that when an autoregressive model produces intermediate reasoning tokens, learning from only its final answer can be substantially harder than learning from its complete reasoning trajectory. It goes on to say that this difficulty grows with the number of possible tokens i.e. length of rollout.

Critical strengths
  1. The paper provides a theoretical upper bound on the learning complexity of autoregressive models as a function of vocabulary size and generation length.
  2. The paper constructs a matching lower bound, showing that the logarithmic vocabulary-size dependence is unavoidable in the worst case, even with just two generation steps.
  3. The paper derives exact online mistake bounds and PAC sample-complexity rates for its construction, supported by numerical verification.
Critical weaknesses
  1. Unclear implications. The paper shows that intermediate tokens can carry additional information useful for learning the final prediction. However, it is unclear what actionable insight follows from this result beyond the fact that observing more informative intermediate tokens can improve learning.
  2. Limited applicability. The theoretical separation relies on a specifically constructed hidden-address mechanism and unrestricted next-token function classes. It is unclear whether the result extends to realistic autoregressive models or reasoning tasks.
  3. Limited empirical evaluation. All evaluations use the proposed synthetic construction and primarily verify the theoretical predictions. There is no evaluation showing whether the predicted separation appears in practical learning settings.
Questions for authors

See weaknesses please.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.