- 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.