7 papers
Recursive Language Models Generalize Out of Domain
Chenxiao Yang, Zhiyuan Li, David McAllester +1
We study when limiting what a language model can see improves learning. We compare standard CoT, the more general learner that reads the full trace, with recursive language models,…
Tight Sample Complexity of Transformers
Chenxiao Yang, Nathan Srebro, Zhiyuan Li
We tightly characterize the VC dimension of depth- Transformers with a total of parameters, mapping an input sequence of length to a single output, establishing an upper…
Hierarchical Domain Generalization
Chenxiao Yang, Zhiyuan Li, Shai Ben-David +1
We study hierarchical domain generalization as a problem of extrapolation from finite observed regions to an entire instance space, replacing i.i.d. sampling with arbitrary domain…
The Optimal Sample Complexity of Learning Autoregressive Chain-of-Thought
Zhiyuan Li
We prove that, in the realizable PAC setting, the sample complexity of exact-trace learning for full autoregressive Chain-of-Thought traces is upper bounded by the standard multicl…
INFUSER: Influence-Guided Self-Evolution Improves Reasoning
Siyu Chen, Miao Lu, Beining Wu +7
Self-evolution offers a scalable path to stronger reasoning: a pretrained language model improves itself with only minimal external supervision. Yet existing methods either depend…
Recursive Models for Long-Horizon Reasoning
Chenxiao Yang, Nathan Srebro, Zhiyuan Li
Modern language models reason within bounded context, an inherent constraint that poses a fundamental barrier to long-horizon reasoning. We identify recursion as a core principle f…