Computational Thinking on Learning Models
summary
Argues that autoregressive chain-of-thought is the right computational model because a simple next-token function H iterated T times decouples runtime from representation size, and exposing intermediate steps makes learning computationally feasible; proves end-to-end learning becomes intractable even for learnable base classes (iterated linear thresholds can simulate constant-depth circuits); proposes a Turing-iterative model implemented by attention (hard lookup → soft attention makes it differentiable) so transformers can efficiently learn short programs with long runtimes; shows a recursive attention/erase workspace cuts context and compute but not in-distribution sample complexity, yet improves out-of-distribution generalization, leaving open how to learn robust reasoning.
AI-written summary · about
chapters (6)
- 0:00Introduction
- 3:38Chain of thought in transformers
- 10:19Computational complexity of learning
- 23:18Transformers for learning
- 31:04Recursive chain of thought challenges
- 36:43Future directions in learning models
related talks
12mTheoretical understanding of learning through the computational lens
01h 30mToward Understanding In-context Learning
40mHuman Learning
46mLearning Theory of Transformers: Generalization and Optimization of In-Context Learning
02mInterview
17mCode World Model: Building World Models for Computation
42mReasonable AI
01h 01mUnderstanding Transformers through the Lens of Logic and Automata