Large language models (LLMs) are, on an abstract level, autoregressive generators: given a prompt (input string), they assign a next-token distribution depending on the context, sample a token from this distribution, append it to the context, and repeat with the expanded context. Thus, even when the task is not inherently iterative, the output is produced by an iterated next-token process. A recent line of theoretical work abstracts this process through autoregressive chain-of-thought learning, where a next-token function is iterated for T steps before producing the final output bit we aim to learn.
In this talk, I will present recent progress on this topic. In particular, I will present new results on PAC learning in this model without observing the intermediate chain of thought, as well as results for other variants of the model, demonstrating that observing the chain of thought can be crucial for learning.
Registration link