The authors study how learnable autoregressive next-token generation is, framed as an online learning problem where you're trying to predict the final token after M steps of chain-of-thought. They compare two feedback regimes: end-to-end (you only see the final output) versus chain-of-thought (you see the entire intermediate trajectory). The key result is that seeing the intermediate reasoning tokens eliminates dependence on the generation horizon M, while end-to-end feedback can require logarithmic mistake growth.
Main takeaways:
- In the end-to-end setting (only final token visible), the number of mistakes needed to learn grows between constant and logarithmic in M (the number of autoregressive steps), and this logarithmic ceiling is unavoidable.
- In the chain-of-thought setting (full trajectory visible), the mistake bound becomes independent of M entirely — seeing intermediate tokens is a huge advantage.
- This echoes prior statistical learning results but at a different scale, showing the online theory has its own qualitative structure.
- For specific function classes like linear thresholds, they prove tight bounds on how many mistakes are needed.