University of Waterloo · Computational Learning Theory Research Seminar

CS 886: Learning Theory for Modern AI

Transformers and Large Language Models

Course Overview and Logistics

Learning Theory for Modern AI is a graduate research seminar on the theoretical foundations of transformers and large language models. We study what these models can represent and compute, what computational resources they require, when their training dynamics are stable, how they learn and generalize from finite data, and why they fail. The course begins with an instructor-led case study in exact algorithmic learning, certification, and hardness.

After the opening case study, Module I moves from expressivity and computational complexity to trainability and finite-sample learning of attention. Module II studies statistical targets, optimization, and generalization in in-context learning. Module III studies autoregressive chain-of-thought, curricula, and length generalization. Module IV is devoted to student project presentations.

Recommended preparation. Students should have mathematical maturity and working knowledge of probability, linear algebra, optimization, algorithms, asymptotic notation, and introductory machine learning. Familiarity with reading proofs is expected. Prior coursework in computational complexity, statistical learning theory, or transformers is helpful but not required.

Required materials. No textbook is required, and all assigned papers are linked from this website.

Note for non-theory students. The course is open to students without a theory background. You can still gain substantial insight into how transformers work and use the course project to scrutinize existing theoretical claims through empirical evidence.

Preparatory Background

Students who need a refresher should review the following concepts before the corresponding modules. Short course notes or references will be posted before they are needed.

Term
Fall 2026
Instructor
Kimon Fountoulakis, Associate Professor · kimon.fountoulakis@uwaterloo.ca
Office
DC 3611
Office hours
Email the instructor at kimon.fountoulakis@uwaterloo.ca.
Meeting time
Fridays, 1:30–4:20 p.m.
Delivery mode
In person
Scheduled seminar meetings
September 11–December 4, 2026
University class period
September 9–December 8, 2026
Reading Week
No class on October 16, 2026. University Reading Week runs October 10–18, 2026.
Last updated
September 13, 2026

Course Materials

Learning Outcomes

  1. Distinguish representation, computational-complexity, trainability, optimization, learnability, generalization, and certification claims for transformers and related neural models.
  2. State and interpret principal theorems with their assumptions, quantifiers, and dependence on sample size, dimension, sequence length, width, depth, precision, conditioning, and task complexity.
  3. Explain how differences in architecture, attention mechanism, precision, depth, recurrence, data-generating process, training rule, and evaluation criterion can produce apparently conflicting theoretical conclusions.
  4. Explain and compare principal techniques used in modern transformer theory, including circuit and communication reductions, statistical-query lower bounds, kernel and mean-field limits, stability, concentration, margin arguments, and minimax analysis.
  5. Assess how closely an idealized theoretical model corresponds to a modern transformer or large language model and identify which omitted features may materially affect the conclusion.
  6. Develop a theoretical extension or design a reproducible empirical investigation that tests, verifies, stress-tests, or challenges a formal theoretical prediction.
  7. Present technical research clearly in written and oral form and synthesize multiple papers into a coherent account of what is known, which assumptions matter, and which questions remain open.

Topics at a Glance

Tentative schedule: The current schedule is a work in progress. Topics, papers, and their order may change.

WeekDateTopicCentral question
Instructor-led opening case studyExact Algorithmic Learning, Certification, and HardnessA motivating case study contrasting exact learning of discrete algorithms with statistical-query and certification hardness.
1September 11, 2026Exact Algorithmic Learning, Certification, and HardnessWhen can neural models learn discrete algorithms exactly from small structured samples, and when are exact learning or behavioral certification provably hard?
Module ITransformer Capacity, Computation, and LearningFrom representational power and formal limitations to computational resources, trainability, and finite-sample learning of attention.
2September 18, 2026Computational Expressivity, Formal Languages, and Circuit ClassesHow can Turing completeness coexist with exact formal-language and circuit upper bounds, and which assumptions about depth, precision, masking, recurrence, and positional information explain the difference?
3September 25, 2026Parallel and Fine-Grained Complexity of TransformersHow do depth, parallel communication, entry magnitudes, and approximation error determine what transformers and self-attention can compute efficiently?
4October 2, 2026Transformer Trainability: Normalization, Depth, and Rank CollapseHow do layer normalization, residual structure, and depth determine whether transformer representations and gradients remain stable at initialization and during early training?
5October 9, 2026Sparse Structure and Token Selection in Self-AttentionWhy does self-attention favor sparse dependencies, and how does gradient descent select and learn task-relevant tokens?
Module IITheory of In-Context LearningStatistical targets and benchmarks, optimization and training dynamics, and finite-sample generalization with optimal rates.
6October 23, 2026Bayesian and Frequentist Foundations of In-Context PredictionWhen does next-token pretraining approximate Bayesian inference, how does its error scale with pretraining data and context length, and when is the resulting predictor statistically consistent from a frequentist viewpoint?
7October 30, 2026Optimization and Training Dynamics of In-Context LearningWhich in-context algorithms minimize the pretraining objective, and under what assumptions does gradient-based pretraining converge to one-step or multi-step learned optimization rules?
8November 6, 2026Finite-Sample Generalization and Minimax Optimality of In-Context LearningOnce pretraining has produced an in-context algorithm, how many tasks and prompt examples are needed for it to generalize and attain optimal statistical rates?
Module IIITheory of ReasoningLearning with autoregressive reasoning traces, followed by scratchpads, curricula, self-training, and length extrapolation.
9November 13, 2026Sample Complexity of Autoregressive Chain-of-ThoughtHow do observed or latent reasoning traces change the sample and computational complexity of learning, and when can they yield provable sample-efficiency gains?
10November 20, 2026Curricula, Scratchpads, and Length Generalization for ReasoningWhich forms of intermediate supervision, curriculum design, and self-training make compositional reasoning learnable and transferable to harder or longer instances?
Module IVProjects
11November 27, 2026Project Presentations I
12December 4, 2026Project Presentations II

Instructor-led opening case study

Exact Algorithmic Learning, Certification, and Hardness

A motivating case study contrasting exact learning of discrete algorithms with statistical-query and certification hardness.

  1. Week 1September 11, 2026

    Exact Algorithmic Learning, Certification, and Hardness

    Central question: When can neural models learn discrete algorithms exactly from small structured samples, and when are exact learning or behavioral certification provably hard?

Module I

Transformer Capacity, Computation, and Learning

From representational power and formal limitations to computational resources, trainability, and finite-sample learning of attention.

  1. Week 2September 18, 2026

    Computational Expressivity, Formal Languages, and Circuit Classes

    Central question: How can Turing completeness coexist with exact formal-language and circuit upper bounds, and which assumptions about depth, precision, masking, recurrence, and positional information explain the difference?

  2. Week 3September 25, 2026

    Parallel and Fine-Grained Complexity of Transformers

    Central question: How do depth, parallel communication, entry magnitudes, and approximation error determine what transformers and self-attention can compute efficiently?

  3. Week 4October 2, 2026

    Transformer Trainability: Normalization, Depth, and Rank Collapse

    Central question: How do layer normalization, residual structure, and depth determine whether transformer representations and gradients remain stable at initialization and during early training?

  4. Week 5October 9, 2026

    Sparse Structure and Token Selection in Self-Attention

    Central question: Why does self-attention favor sparse dependencies, and how does gradient descent select and learn task-relevant tokens?

Module II

Theory of In-Context Learning

Statistical targets and benchmarks, optimization and training dynamics, and finite-sample generalization with optimal rates.

  1. Week 6October 23, 2026

    Bayesian and Frequentist Foundations of In-Context Prediction

    Central question: When does next-token pretraining approximate Bayesian inference, how does its error scale with pretraining data and context length, and when is the resulting predictor statistically consistent from a frequentist viewpoint?

  2. Week 7October 30, 2026

    Optimization and Training Dynamics of In-Context Learning

    Central question: Which in-context algorithms minimize the pretraining objective, and under what assumptions does gradient-based pretraining converge to one-step or multi-step learned optimization rules?

  3. Week 8November 6, 2026

    Finite-Sample Generalization and Minimax Optimality of In-Context Learning

    Central question: Once pretraining has produced an in-context algorithm, how many tasks and prompt examples are needed for it to generalize and attain optimal statistical rates?

Module III

Theory of Reasoning

Learning with autoregressive reasoning traces, followed by scratchpads, curricula, self-training, and length extrapolation.

  1. Week 9November 13, 2026

    Sample Complexity of Autoregressive Chain-of-Thought

    Central question: How do observed or latent reasoning traces change the sample and computational complexity of learning, and when can they yield provable sample-efficiency gains?

  2. Week 10November 20, 2026

    Curricula, Scratchpads, and Length Generalization for Reasoning

    Central question: Which forms of intermediate supervision, curriculum design, and self-training make compositional reasoning learnable and transferable to harder or longer instances?

Module IV

Projects

  1. Week 11November 27, 2026

    Project Presentations I

  2. Week 12December 4, 2026

    Project Presentations II

Reading Expectations

For every scheduled paper, all students should read at least the abstract, introduction, formal setup, main theorem or principal result, and discussion or limitations. Before class, students should be able to identify the paper's result type and its decisive assumption. The two assigned presenters are jointly responsible for the proof details and supplementary material needed to explain the result accurately. Both presenters must understand the complete paper; their division of speaking roles does not divide responsibility for the paper. Other students are not expected to read every technical detail in the appendix.

Detailed Paper Schedule

Instructor-led opening case study

Exact Algorithmic Learning, Certification, and Hardness

A motivating case study contrasting exact learning of discrete algorithms with statistical-query and certification hardness.

Week 01 · September 11, 2026Exact Algorithmic Learning, Certification, and Hardness

Central question. When can neural models learn discrete algorithms exactly from small structured samples, and when are exact learning or behavioral certification provably hard?

Lecture Materials
Part I: Exact execution learned from examples

How NTK-regime neural models can learn local update rules, arithmetic operations, and algorithmic instructions exactly from small structured training sets.

  1. Artur Back de Luca, George Giapitzakis, and Kimon Fountoulakis Learning to Add, Multiply, and Execute Algorithmic Instructions Exactly with Neural Networks. NeurIPS 2025.
    Theoretical focus: Proves that ensembles of infinite-width two-layer networks in the neural-tangent-kernel regime can exactly execute binary permutations, addition, multiplication, and a Turing-complete SBN instruction set with high probability from logarithmically many structured examples.

  2. Muhammad Fetrat Qharabagh, Artur Back de Luca, George Giapitzakis, and Kimon Fountoulakis Learning to Execute Graph Algorithms Exactly with Graph Neural Networks. ICML 2026 (Spotlight).
    Theoretical focus: Uses neural-tangent-kernel theory to learn local update instructions from a small training set and composes them in a graph neural network that exactly executes bounded-degree, finite-precision graph algorithms with high probability.

Part II: Hardness of exact learning and certification

Why exact transition behavior can be statistically hard to learn and why verifying exact behavior from examples can become exponentially hard after minimal overparameterization.

  1. George Giapitzakis, Kimon Fountoulakis, Eshaan Nichani, and Jason D. Lee On the Statistical Query Complexity of Learning Semiautomata: a Random Walk Approach. COLT 2026.
    Theoretical focus: Proves the first statistical-query hardness result for learning semiautomata under a uniform distribution over words and initial states, using random walks, Fourier analysis, representation theory, and spectral-gap bounds.

  2. Artur Back de Luca and Kimon Fountoulakis Certification from Examples is Hard for Circuits and Transformers under Minimal Overparametrization. Preprint 2026.
    Theoretical focus: Proves that one additional threshold gate can make behavioral certification from examples exponentially hard and gives an analogous lower bound for a specific log-precision transformer model under constant architectural overhead.

Back to schedule

Module I

Transformer Capacity, Computation, and Learning

From representational power and formal limitations to computational resources, trainability, and finite-sample learning of attention.

Week 02 · September 18, 2026Computational Expressivity, Formal Languages, and Circuit Classes

Connection to the previous week. Week 1 showed that exact algorithmic behavior can be learned in carefully structured regimes. Week 2 steps back to ask what transformer architectures can compute at all, and why different assumptions yield Turing completeness or severe formal limitations.

Central question. How can Turing completeness coexist with exact formal-language and circuit upper bounds, and which assumptions about depth, precision, masking, recurrence, and positional information explain the difference?

Part I: Computational universality and exact language characterization

How hard-attention transformers can simulate general computation under one set of assumptions, while strictly masked hard attention without positional embeddings recognizes exactly the star-free languages under another.

  1. Jorge Perez, Pablo Barcelo, and Javier Marinkovic Attention Is Turing Complete. JMLR 2021.
    Theoretical focus: Proves that hard-attention transformers are Turing complete through their ability to compute and access dense internal representations, under explicit architectural and precision assumptions.

  2. Andy Yang, David Chiang, and Dana Angluin Masked Hard-Attention Transformers Recognize Exactly the Star-Free Languages. NeurIPS 2024.
    Theoretical focus: Proves that strictly masked hard-attention transformers without positional embeddings are equivalent to linear temporal logic and therefore recognize exactly the star-free languages, while analyzing how masking, position embeddings, and depth change expressivity.

Part II: Finite-precision circuit upper bounds

How saturated floating-point attention expands expressivity beyond unique hard attention while remaining simulable by constant-depth threshold circuits.

  1. William Merrill, Ashish Sabharwal, and Noah A. Smith Saturated Transformers Are Constant-Depth Threshold Circuits. TACL 2022.
    Theoretical focus: Shows that saturated attention is more expressive than hard attention while proving that floating-point saturated transformers can be simulated by constant-depth threshold circuits, yielding TC0 as an upper bound.

Back to schedule

Week 03 · September 25, 2026Parallel and Fine-Grained Complexity of Transformers

Connection to the previous week. Week 2 characterized transformer computational expressivity under different architectural and numerical assumptions. Week 3 asks what depth, parallel communication, and running time are required to realize those computations.

Central question. How do depth, parallel communication, entry magnitudes, and approximation error determine what transformers and self-attention can compute efficiently?

Part I: Parallel depth and communication

How transformer layers correspond to Massively Parallel Computation rounds and what logarithmic depth adds beyond constant-depth parallelism.

  1. Clayton Sanford, Daniel Hsu, and Matus Telgarsky Transformers, Parallel Computation, and Logarithmic Depth. ICML 2024.
    Theoretical focus: Proves a two-way simulation between a constant number of self-attention layers and a constant number of Massively Parallel Computation rounds, and shows that logarithmic depth suffices for tasks beyond several sequence models and subquadratic transformer approximations.

Part II: Fine-grained complexity of attention

Why exact or approximate attention can require quadratic time and how bounded entries produce a sharp transition to almost-linear approximation.

  1. Feyza Duman Keles, Pruthuvi Mahesakya Wijewardena, and Chinmay Hegde On the Computational Complexity of Self-Attention. ALT 2023.
    Theoretical focus: Establishes SETH-based quadratic lower bounds for exact and approximate attention across several mechanisms and gives a finite-Taylor-series linear-time approximation with exponential dependence on the polynomial order.

  2. Josh Alman and Zhao Song Fast Attention Requires Bounded Entries. NeurIPS 2023.
    Theoretical focus: Proves a sharp transition for low-dimensional approximate softmax attention: sufficiently bounded entries permit almost-linear time, while larger entries yield a conditional truly-subquadratic lower bound under SETH.

Back to schedule

Week 04 · October 2, 2026Transformer Trainability: Normalization, Depth, and Rank Collapse

Connection to the previous week. Efficiently representable transformer computations are useful only if training remains stable. Week 4 studies how normalization, residual structure, and depth govern representations and gradients.

Central question. How do layer normalization, residual structure, and depth determine whether transformer representations and gradients remain stable at initialization and during early training?

Part I: Normalization and depth-induced rank collapse

How normalization placement changes initial gradients and why repeated pure self-attention drives token representations toward rank one.

  1. Ruibin Xiong, Yunchang Yang, Di He, Kai Zheng, Shuxin Zheng, Chen Xing, Huishuai Zhang, Yanyan Lan, Liwei Wang, and Tie-Yan Liu On Layer Normalization in the Transformer Architecture. ICML 2020.
    Theoretical focus: Uses mean-field analysis at initialization to show that Post-LN produces large expected gradients near the output while Pre-LN yields better-behaved initial gradients, providing a theoretical explanation for warmup sensitivity under the paper's model.

  2. Yihe Dong, Jean-Baptiste Cordonnier, and Andreas Loukas Attention Is Not All You Need: Pure Attention Loses Rank Doubly Exponentially with Depth. ICML 2021.
    Theoretical focus: Uses a path decomposition to prove that pure self-attention without residual connections or multilayer perceptrons converges doubly exponentially toward rank-one token representations and explains how those architectural components prevent degeneration.

Part II: Gradient consequences and residual scaling

How token-rank collapse causes query and key gradients to vanish and how depth-dependent residual scaling preserves signal propagation.

  1. Lorenzo Noci, Sotiris Anagnostidis, Luca Biggio, Antonio Orvieto, Sidak Pal Singh, and Aurelien Lucchi Signal Propagation in Transformers: Theoretical Perspectives and the Role of Rank Collapse. NeurIPS 2022.
    Theoretical focus: Proves that token-rank collapse causes query and key gradients to vanish at initialization, analyzes gradient imbalances across query, key, and value parameters, and derives depth-dependent residual scaling that preserves signal propagation.

Back to schedule

Week 05 · October 9, 2026Sparse Structure and Token Selection in Self-Attention

Connection to the previous week. Stable signals and gradients do not guarantee that training discovers task-relevant structure. Week 5 studies the statistical and optimization biases that drive attention toward sparse, informative tokens.

Central question. Why does self-attention favor sparse dependencies, and how does gradient descent select and learn task-relevant tokens?

Part I: Statistical learnability and implicit bias

Why bounded-norm attention favors sparse dependencies and how gradient descent selects locally optimal tokens through a max-margin bias.

  1. Benjamin L. Edelman, Surbhi Goel, Sham Kakade, and Cyril Zhang Inductive Biases and Variable Creation in Self-Attention Mechanisms. ICML 2022.
    Theoretical focus: Proves norm-based sample-complexity guarantees showing that bounded-norm self-attention can learn sparse dependencies with only logarithmic dependence on context length.

  2. Davoud Ataee Tarzanagh, Yingcong Li, Xuechen Zhang, and Samet Oymak Max-Margin Token Selection in Attention Mechanism. NeurIPS 2023.
    Theoretical focus: Proves that gradient descent on the attention parameter converges in direction to a max-margin solution separating locally optimal tokens from non-optimal tokens, and gives conditions for corresponding margin behavior under joint optimization with the prediction head.

Part II: Provable token-selection learning and length generalization

When gradient descent trains a one-layer transformer to learn a sparse selector, separate from fully connected networks, and extrapolate to longer contexts.

  1. Zixuan Wang, Stanley Wei, Daniel Hsu, and Jason D. Lee Transformers Provably Learn Sparse Token Selection While Fully-Connected Nets Cannot. ICML 2024.
    Theoretical focus: Proves that gradient descent trains a one-layer transformer to solve sparse token selection, establishes an average-case separation from fully connected networks, and obtains out-of-distribution length generalization.

Back to schedule

Module II

Theory of In-Context Learning

Statistical targets and benchmarks, optimization and training dynamics, and finite-sample generalization with optimal rates.

Week 06 · October 23, 2026Bayesian and Frequentist Foundations of In-Context Prediction

Connection to the previous week. Week 5 studied how training organizes attention around informative tokens. Week 6 asks what statistical inference procedure emerges when those learned attention mechanisms operate over an entire prompt.

Central question. When does next-token pretraining approximate Bayesian inference, how does its error scale with pretraining data and context length, and when is the resulting predictor statistically consistent from a frequentist viewpoint?

Part I: Bayesian interpretation and information-theoretic rates

When next-token prediction approximates latent-task Bayesian inference and how meta-learning and within-task prediction errors decay with the number and length of training sequences.

  1. Sang Michael Xie, Aditi Raghunathan, Percy Liang, and Tengyu Ma An Explanation of In-Context Learning as Implicit Bayesian Inference. ICLR 2022.
    Theoretical focus: Under a latent-concept mixture model, proves conditions under which next-token pretraining yields approximate Bayesian inference over concepts at test time despite a mismatch between pretraining sequences and in-context prompts.

  2. Hong Jun Jeon, Jason D. Lee, Qi Lei, and Benjamin Van Roy An Information-Theoretic Analysis of In-Context Learning. ICML 2024.
    Theoretical focus: Decomposes Bayes prediction error into meta-learning and within-task terms and derives how the error decreases with both the number of training sequences and their lengths without the mixing-time assumptions used by earlier analyses.

Part II: Frequentist consistency

How prior-data fitted predictors can be interpreted without assuming a Bayesian data-generating prior, and which variance and localization conditions are needed for consistency.

  1. Thomas Nagler Statistical Foundations of Prior-Data Fitted Networks. ICML 2023.
    Theoretical focus: Develops a frequentist theory of prior-data fitted networks, separating variance reduction from localization bias and identifying conditions under which the pretrained predictor is statistically consistent.

Back to schedule

Week 07 · October 30, 2026Optimization and Training Dynamics of In-Context Learning

Connection to the previous week. Week 6 identified Bayesian and frequentist target descriptions for prompt-conditioned prediction. Week 7 asks whether transformer pretraining reaches such predictors and which optimization dynamics produce them.

Central question. Which in-context algorithms minimize the pretraining objective, and under what assumptions does gradient-based pretraining converge to one-step or multi-step learned optimization rules?

Part I: One-step population optima and training

Which one-step gradient-like predictor minimizes the population objective and when gradient flow trains linear self-attention to implement a useful in-context predictor.

  1. Arvind V. Mahankali, Tatsunori Hashimoto, and Tengyu Ma One Step of Gradient Descent Is Provably the Optimal In-Context Learner with One Layer of Linear Self-Attention. ICLR 2024.
    Theoretical focus: Characterizes global population-risk minimizers of one-layer linear self-attention, showing that isotropic linear tasks yield one gradient step and non-isotropic tasks yield an appropriately preconditioned step.

  2. Ruiqi Zhang, Spencer Frei, and Peter L. Bartlett Trained Transformers Learn Linear Models In-Context. JMLR 2024.
    Theoretical focus: Proves gradient-flow convergence for a one-layer linear transformer, derives controlled in-context prediction risk, and analyzes how the learned predictor behaves under distribution shift.

Part II: Multi-step learned optimization

How a looped transformer can learn a multi-step preconditioned gradient-descent procedure rather than merely represent one.

  1. Khashayar Gatmiry, Nikunj Saunshi, Sashank J. Reddi, Stefanie Jegelka, and Sanjiv Kumar Can Looped Transformers Learn to Implement Multi-step Gradient Descent for In-context Learning?. ICML 2024.
    Theoretical focus: Shows that the population optimum of a linear looped transformer implements multi-step preconditioned gradient descent and proves fast gradient-flow convergence through a gradient-dominance argument despite nonconvexity.

Back to schedule

Week 08 · November 6, 2026Finite-Sample Generalization and Minimax Optimality of In-Context Learning

Connection to the previous week. Week 7 analyzed how training reaches in-context algorithms. Week 8 turns from optimization to finite-sample learnability, task transfer, stability, and minimax rates.

Central question. Once pretraining has produced an in-context algorithm, how many tasks and prompt examples are needed for it to generalize and attain optimal statistical rates?

Part I: Finite-sample learnability and stability

How finite pretraining-task counts, prompt examples, and algorithmic stability control generalization and transfer for frozen-weight in-context learners.

  1. Noam Wies, Yoav Levine, and Amnon Shashua The Learnability of In-Context Learning. NeurIPS 2023.
    Theoretical focus: Introduces a PAC-style framework for pretraining followed by frozen-weight in-context adaptation and proves finite sample-complexity guarantees for latent-task mixtures.

  2. Yingcong Li, M. Emrullah Ildiz, Dimitris Papailiopoulos, and Samet Oymak Transformers as Algorithms: Generalization and Stability in In-Context Learning. ICML 2023.
    Theoretical focus: Treats the transformer as an algorithm operating on a prompt and derives excess-risk and task-transfer guarantees through algorithmic stability for independent examples and dynamical trajectories.

Part II: Minimax nonparametric rates

Whether transformer-based in-context learners can attain statistically optimal rates over rich nonparametric function classes.

  1. Juno Kim, Tai Nakamaki, and Taiji Suzuki Transformers Are Minimax Optimal Nonparametric In-Context Learners. NeurIPS 2024.
    Theoretical focus: Derives approximation and generalization bounds for nonparametric in-context regression, separates pretraining and within-context generalization gaps, and establishes minimax-optimal rates over rich function classes.

Back to schedule

Module III

Theory of Reasoning

Learning with autoregressive reasoning traces, followed by scratchpads, curricula, self-training, and length extrapolation.

Week 09 · November 13, 2026Sample Complexity of Autoregressive Chain-of-Thought

Connection to the previous week. Week 8 studied direct prompt-to-prediction generalization. Week 9 asks how the sample and computational complexity of learning change when the model generates intermediate reasoning traces autoregressively.

Central question. How do observed or latent reasoning traces change the sample and computational complexity of learning, and when can they yield provable sample-efficiency gains?

Part I: General framework and tight capacity bounds

A general learning model for observed and latent reasoning traces, followed by nearly matching transformer capacity and teacher-forced sample-complexity bounds.

  1. Nirmit Joshi, Gal Vardi, Adam Block, Surbhi Goel, Zhiyuan Li, Theodor Misiakiewicz, and Nathan Srebro A Theory of Learning with Autoregressive Chain of Thought. COLT 2025.
    Theoretical focus: Formalizes learning with observed and latent chains of thought, derives sample and computational complexity from properties such as VC dimension, and shows how time invariance can remove dependence on chain length from sample complexity.

  2. Chenxiao Yang, Nathan Srebro, and Zhiyuan Li Tight Sample Complexity of Transformers. COLT 2026.
    Theoretical focus: Tightly characterizes the VC dimension and sample complexity of depth-L transformers, including teacher-forced chain-of-thought learning, with nearly matching upper and lower bounds.

Part II: Sample-efficiency gains from sparse reasoning traces

Revisiting Week 5's sparse-dependence theme, this paper shows in a concrete learning model how intermediate traces can convert an exponential sample requirement into a polynomial one.

  1. Kaiyue Wen, Huaqing Zhang, Hongzhou Lin, and Jingzhao Zhang From Sparse Dependence to Sparse Attention: Unveiling How Chain-of-Thought Enhances Transformer Sample Efficiency. ICLR 2025.
    Theoretical focus: In a parity-learning model under the paper's training setup, proves that chain-of-thought enables polynomial-sample learning where direct prediction requires exponentially many samples and explains the gain through sparse sequential dependence and sparse attention.

Back to schedule

Week 10 · November 20, 2026Curricula, Scratchpads, and Length Generalization for Reasoning

Connection to the previous week. Week 9 established how reasoning traces change sample complexity. Week 10 asks which scratchpads, curricula, and self-training procedures overcome barriers on harder or longer problems, returning to Week 1's contrast between structured positive results and learning hardness.

Central question. Which forms of intermediate supervision, curriculum design, and self-training make compositional reasoning learnable and transferable to harder or longer instances?

Part I: Learning barriers and easy-to-hard curriculum

Why direct or hard-only training can fail and how structured scratchpads or easy-to-hard examples overcome formal learning barriers.

  1. Emmanuel Abbe, Samy Bengio, Aryo Lotfi, Colin Sandon, and Omid Saremi How Far Can Transformers Reason? The Globality Barrier and Inductive Scratchpad. NeurIPS 2024.
    Theoretical focus: Formalizes a globality measure for reasoning tasks, develops learning barriers under the paper's stated assumptions, and analyzes how increasingly structured scratchpads can change the learnability of global functions.

  2. Zixuan Wang, Eshaan Nichani, Alberto Bietti, Alex Damian, Daniel Hsu, Jason D. Lee, and Denny Wu Learning Compositional Functions with Transformers from Easy-to-Hard Data. COLT 2025.
    Theoretical focus: Proves an exponential statistical-query lower bound for hard-only data and polynomial sample and runtime guarantees for gradient descent on an O(log k)-depth transformer under suitable easy-to-hard or mixed curricula.

Part II: Self-training and length generalization

How structured chain-of-thought training and recursive self-training support extrapolation beyond the original training lengths.

  1. Yu Huang, Zixin Wen, Aarti Singh, Yuejie Chi, and Yuxin Chen Transformers Provably Learn Chain-of-Thought Reasoning with Length Generalization. NeurIPS 2025.
    Theoretical focus: Proves optimization and length-generalization guarantees for transformers trained on structured state-tracking tasks and analyzes attention concentration and recursive self-training beyond the original training lengths.

Back to schedule

Paper Presentations

Week 1 is instructor-led: the instructor will present all four papers. Student paper presentations run from Week 2 through Week 10, with 3 papers each week. Every paper is presented jointly by 2 students. The meeting format below applies to the student-led meetings in Weeks 2–10.

Each of the 27 students will give 2 paired paper presentations on two different papers. Each student will normally work with a different partner for the two presentations. The two paper presentations are worth 20% each, for 40% of the final grade in total. The required project presentation is separate and does not count toward these paper presentations.

Paired Presentation Expectations

Student-Presentation Meeting Format

Presentation

  1. State the formal problem, including the data-generating process, architecture or hypothesis class, loss, training rule, and evaluation criterion.
  2. Classify the result as representation, computational complexity, trainability, optimization, learnability, generalization, or certification.
  3. State the main theorem with its assumptions, quantifiers, and important dependence on sample size, dimension, sequence length, width, depth, precision, conditioning, or task complexity.
  4. Explain the principal proof mechanism rather than only restating the theorem.
  5. Identify the assumption that carries the result and explain how closely the formal model corresponds to a modern transformer or large language model.
  6. Distinguish theorem-level conclusions from experimental evidence, conjectures, and informal interpretations.
  7. Explain how the paper advances, limits, contrasts with, or changes the assumptions of the adjacent papers.
  8. End with one precise limitation and one concrete theorem, counterexample, or experiment that would materially strengthen or challenge the result.

Required Course Project

The project accounts for 40% of the course grade. The topic must be discussed with and approved by the instructor.

Acceptable Project Forms

  1. New theoretical contribution. Examples include a new theorem, proof, lower or upper bound, sharper rate, weaker assumption, impossibility result, counterexample, or extension of an existing result to a more realistic transformer or language-model setting.
  2. Empirical validation or scrutiny of theory. The project may stress-test or challenge an existing theoretical claim.
    • Measuring whether the predicted dependence on sample size, sequence length, depth, width, number of heads, task diversity, or conditioning appears in finite models.
    • Checking how a theorem behaves when idealized assumptions such as linear attention, Gaussian data, population loss, infinite width, or realizability are relaxed.
    • Reproducing a paper's core theoretical experiment and identifying robustness or failure regimes.
    • Comparing a formal bound with observed behavior and explaining the gap.
    • Searching systematically for counterexamples to a conjectured extension or informal interpretation of a theorem.

A generic model comparison, benchmark leaderboard, prompt-engineering exercise, or systems implementation is not sufficient by itself.

Project Deliverables

Project Evaluation

Projects will be evaluated according to:

A complete publishable theorem is not required. Careful negative results, counterexamples, unsuccessful proof attempts that isolate a genuine obstruction, and rigorous empirical audits can all constitute strong projects when the analysis is technically substantive and clearly documented.

Although publication is not required, the instructor is happy to help develop strong projects toward publication. A project from a previous offering of CS 886 was subsequently developed into a NeurIPS 2024 publication.

Project Milestones and Deadlines

DeliverableDeadlineDetails
Project topic approvalOctober 23, 2026Submit an ungraded three-to-five-sentence description of the proposed contribution and, for empirical work, the principal experiment. This is an approval checkpoint rather than a separately graded proposal.
Final project report and reproducibility materialsNovember 26, 2026The final report and any required code, configurations, data instructions, or other reproducibility materials are due before project presentations begin. This component is worth 30% of the final grade.
Final project presentationNovember 27 or December 4, 2026Each student gives an individual presentation during the assigned project-presentation meeting. The assigned date will be announced after project topics are confirmed. This component is worth 10% of the final grade.

Project Presentation Requirements

Weeks 11–12 are reserved for 27 individual project presentations. Week 11 will have 14 presentations, and Week 12 will have 13. Presentations will be approximately 12–13 minutes, including questions. The project presentation is separate from the two required paired paper presentations.

Every presentation should include:

  1. The precise research question and its connection to the course.
  2. The existing theoretical result, conjecture, or limitation being extended or examined.
  3. The student's original contribution.
  4. The methods, assumptions, and experimental or proof setup.
  5. The main theorem, counterexample, quantitative finding, or negative result.
  6. The strongest limitation and the most important next step.

For empirical projects, plots and tables should be chosen to test the stated theoretical prediction rather than merely summarize benchmark performance. For theoretical projects, the talk should state the result with its quantifiers and parameter dependence, and should explain the main proof idea or obstruction.

Assessment

The final grade consists of two paired paper presentations (20% each; 40% in total), the required course project (40%), and class participation (20%).

Use of Generative AI

Generative-AI tools may be used for coursework in this class.

Students remain fully responsible for the accuracy, originality, and integrity of all submitted work and must be able to explain every mathematical statement, proof step, citation, experimental result, and piece of code. Factual, mathematical, citation, experimental, or coding errors will be graded as errors regardless of whether AI was used.

Suggested Additional Readings and Project Starting Points

These readings include foundational representational, mechanistic, and adjacent theory papers that support the seminar's learning-theory core, as well as possible project starting points. They are not scheduled paper presentations.

Transformer Architecture, Expressivity, and Computation

Foundational or complementary papers on universal approximation, initialization, infinite-width limits, signal propagation, formal-language limitations, circuit and parallel complexity, automata shortcuts, and explicitly programmed transformer computation.

  1. Xiao Shi Huang, Felipe Perez, Jimmy Ba, and Maksims Volkovs Improving Transformer Optimization Through Better Initialization. ICML 2020.
    Theoretical focus: Proposes T-Fixup using a simplified analysis of depth-dependent update scaling and validates that the initialization can train very deep encoder-decoder transformers without warmup or layer normalization. It is useful practical background for Week 4 but is not one of the core signal-propagation theorem papers.

  2. Akhil Kedia, Mohd Abbas Zaidi, Sushil Khyalia, Jungho Jung, Harshith Goka, and Haejun Lee Transformers Get Stable: An End-to-End Signal Propagation Theory for Language Models. ICML 2024.
    Theoretical focus: Combines end-to-end forward and backward signal-moment calculations with the DeepScaleLM scaling prescription and extensive empirical validation for very deep language-model transformers. It complements Week 4's theorem-centered core with a broader theory-and-method treatment of stable scaling.

  3. Jiri Hron, Yasaman Bahri, Jascha Sohl-Dickstein, and Roman Novak Infinite Attention: NNGP and NTK for Deep Attention Networks. ICML 2020.
    Theoretical focus: Establishes rigorous neural-network Gaussian-process and neural-tangent-kernel limits for deep attention networks, shows that standard single-head attention need not become Gaussian at infinite width while multi-head attention converges to a Gaussian process as the number of heads grows, and analyzes positional encodings and layer normalization.

  4. Chulhee Yun, Srinadh Bhojanapalli, Ankit Singh Rawat, Sashank J. Reddi, and Sanjiv Kumar Are Transformers Universal Approximators of Sequence-to-Sequence Functions?. ICLR 2020.
    Theoretical focus: Proves universal approximation of continuous permutation-equivariant sequence-to-sequence maps on compact domains without positional encodings and of arbitrary continuous sequence maps on compact domains with positional encodings.

  5. Michael Hahn Theoretical Limitations of Self-Attention in Neural Sequence Models. TACL 2020.
    Theoretical focus: A foundational formal-language lower-bound paper showing limitations of fixed-depth self-attention for periodic and hierarchical languages under its model assumptions. It supports Week 2, while the required schedule uses newer exact characterizations and circuit-class results.

  6. William Merrill and Ashish Sabharwal The Parallelism Tradeoff: Limitations of Log-Precision Transformers. TACL 2023.
    Theoretical focus: Proves that log-precision transformers with suitably space-bounded feed-forward blocks can be simulated by constant-depth logspace-uniform threshold circuits and derives conditional computational limitations from standard complexity assumptions.

  7. Bingbin Liu, Jordan T. Ash, Surbhi Goel, Akshay Krishnamurthy, and Cyril Zhang Transformers Learn Shortcuts to Automata. ICLR 2023 oral.
    Theoretical focus: Proves that transformers can exactly simulate any finite-state automaton using O(log T) depth and that broad algebraic classes admit constant-depth shortcut constructions; the claim that gradient-based training discovers these shortcuts is supported empirically rather than by a general optimization theorem.

  8. Angeliki Giannou, Shashank Rajput, Jy-Yong Sohn, Kangwook Lee, Jason D. Lee, and Dimitris Papailiopoulos Looped Transformers as Programmable Computers. ICML 2023.
    Theoretical focus: Constructs explicit weights for a looped transformer that implements an explicit instruction-set architecture, memory access, branching, nonlinear operations, linear algebra, and backpropagation. It is a strong programmable-computation result but not a theorem that the program or weights are learned from data.

Attention, Memory, and In-Context-Learning Mechanisms

Complementary work on token-composition dynamics, generative self-attention, associative memory, induction mechanisms, Bayesian adaptation, optimization dynamics, algorithm selection, and reusable representations.

  1. Yuandong Tian, Yiping Wang, Beidi Chen, and Simon S. Du Scan and Snap: Understanding Training Dynamics and Token Composition in 1-layer Transformer. NeurIPS 2023.
    Theoretical focus: Under no-positional-encoding, long-sequence, and decoder-timescale assumptions, rigorously analyzes SGD for one-layer next-token prediction and shows a scan-and-snap dynamic in which attention increasingly favors distinct, high-co-occurrence tokens while downweighting common or lower-co-occurrence tokens, then decelerates after a learning-rate-controlled phase transition, leaving an almost fixed rather than one-hot token mixture.

  2. Muhammed Emrullah Ildiz, Yixiao Huang, Yingcong Li, Ankit Singh Rawat, and Samet Oymak From Self-Attention to Markov Models: Unveiling the Dynamics of Generative Transformers. ICML 2024.
    Theoretical focus: Maps one-layer generative self-attention to a context-conditioned Markov chain, gives coverage conditions for consistent latent-model estimation and finite-sample guarantees under IID prompt-output data, and separately analyzes a single autoregressive trajectory, characterizing a winner-token distribution-collapse phenomenon. It is strong complementary theory, but its generative model-identification story is separate from Week 5's focused narrative on sparse token selection.

  3. Hubert Ramsauer et al. Hopfield Networks Is All You Need. ICLR 2021.
    Theoretical focus: Foundational associative-memory theory: proves modern Hopfield retrieval and storage results and identifies the transformer attention update with a Hopfield retrieval step. It is useful background for Week 6 but is not a core statistical-learning paper about pretraining or generalization.

  4. Alberto Bietti, Vivien Cabannes, Diane Bouchacourt, Herve Jegou, and Leon Bottou Birth of a Transformer: A Memory Viewpoint. NeurIPS 2023.
    Theoretical focus: A mechanistic theory and empirical study of how a simplified transformer develops global bigram memories and an induction-head mechanism. Its supplement contains an idealized population-gradient result, but it does not establish general finite-sample or end-to-end training guarantees.

  5. Ekin Akyurek, Dale Schuurmans, Jacob Andreas, Tengyu Ma, and Denny Zhou What Learning Algorithm Is In-Context Learning? Investigations with Linear Models. ICLR 2023.
    Theoretical focus: A foundational construction and empirical algorithm-identification paper: proves that transformers can represent several linear-learning procedures and shows that trained models resemble them, without proving that pretraining converges to those constructions.

  6. Johannes Von Oswald, Eyvind Niklasson, Ettore Randazzo, Joao Sacramento, Alexander Mordvintsev, Andrey Zhmoginov, and Max Vladymyrov Transformers Learn In-Context by Gradient Descent. ICML 2023.
    Theoretical focus: A foundational representational and mechanistic precursor: constructs linear self-attention weights that implement a gradient update and empirically compares trained transformers with that construction, but does not prove convergence of ordinary pretraining to it.

  7. Yu Huang, Yuan Cheng, and Yingbin Liang In-Context Convergence of Transformers. ICML 2024.
    Theoretical focus: Proves finite-time convergence of gradient descent for a one-layer softmax-attention model on structured in-context regression and characterizes stagewise learning when features occur at imbalanced frequencies.

  8. Yu Bai, Fan Chen, Huan Wang, Caiming Xiong, and Song Mei Transformers as Statisticians: Provable In-Context Learning with In-Context Algorithm Selection. NeurIPS 2023.
    Theoretical focus: Constructs transformers that implement regression and classification procedures, select among algorithms through in-context validation, and achieve formal statistical guarantees with polynomial pretraining requirements.

  9. Nick Cannella, Anzo Teh, Yanjun Han, and Yury Polyanskiy Universal Priors: Solving Empirical Bayes via Bayesian Inference and Pretraining. COLT 2026.
    Theoretical focus: For Poisson empirical Bayes, proves that universal pretraining priors achieve near-optimal regret uniformly over test distributions and explains length generalization through fractional-posterior inference.

  10. Tianyu Guo et al. How Do Transformers Learn In-Context Beyond Simple Functions? A Case Study on Learning with Representations. ICLR 2024.
    Theoretical focus: Analyzes in-context learning when tasks share a latent representation and explains how pretraining learns a reusable feature space.

  11. Yuchen Li, Yuanzhi Li, and Andrej Risteski How Do Transformers Learn Topic Structure: Towards a Mechanistic Understanding. ICML 2023.
    Theoretical focus: Analyzes how embeddings and attention learn co-occurrence and latent topic structure under a tractable generative model.

Reasoning and Autoregressive Limitations

Complementary theory on chain-of-thought expressivity, nonlinear transformer training for reasoning, adaptive curricula, and statistical-computational barriers in autoregressive learning.

  1. Zhiyuan Li, Hong Liu, Denny Zhou, and Tengyu Ma Chain of Thought Empowers Transformers to Solve Inherently Serial Problems. ICLR 2024.
    Theoretical focus: Computational-expressivity theory showing how autoregressive reasoning tokens allow bounded-depth transformers to serialize circuit computation. It is valuable background for Weeks 9–10 but does not prove that gradient-based training learns the construction.

  2. Hongkang Li, Songtao Lu, Pin-Yu Chen, Xiaodong Cui, and Meng Wang Training Nonlinear Transformers for Chain-of-Thought Inference: A Theoretical Generalization Analysis. ICLR 2025.
    Theoretical focus: Quantifies the samples and iterations needed to train nonlinear attention for chain-of-thought inference and proves generalization to unseen tasks under data shift and imperfect or noisy reasoning demonstrations.

  3. Nived Rajaraman, Audrey Huang, Miro Dudik, Rob Schapire, Dylan Foster, and Akshay Krishnamurthy Learning to Reason with Curriculum I: Provable Benefits of Autocurriculum. COLT 2026.
    Theoretical focus: Proves that adaptive problem selection can require exponentially fewer supervised reasoning demonstrations than non-adaptive fine-tuning and can decouple reinforcement-learning compute from reference-model quality after a burn-in phase.

  4. Dhruv Rohatgi, Adam Block, Audrey Huang, Akshay Krishnamurthy, and Dylan J. Foster Computational-Statistical Tradeoffs at the Next-Token Prediction Barrier: Autoregressive and Imitation Learning under Misspecification. COLT 2025.
    Theoretical focus: Studies error amplification and computational-statistical tradeoffs for autoregressive and imitation learning under model misspecification. It is strong adjacent learning theory, but it is separate from the curriculum, scratchpad, and length-generalization narrative of Week 10.

Fine-Tuning, Preference Learning, and Exploration

Theory of parameter-efficient adaptation, preference optimization, online data, coverage, and exploration with language-model policies.

  1. Sadhika Malladi et al. A Kernel-Based View of Language Model Fine-Tuning. ICML 2023.
    Theoretical focus: Develops a kernel approximation for language-model fine-tuning and uses it to predict data and hyperparameter effects.

  2. Yihan Wang, Jatin Chauhan, Wei Wang, and Cho-Jui Hsieh Universality and Limitations of Prompt Tuning. NeurIPS 2023.
    Theoretical focus: Proves universal approximation results for prompt tuning while deriving prompt-length and computational limitations.

  3. Wei Xiong, Hanze Dong, Chenlu Ye, Ziqi Wang, Han Zhong, Heng Ji, Nan Jiang, and Tong Zhang Iterative Preference Learning from Human Feedback: Bridging Theory and Practice for RLHF under KL-Constraint. ICML 2024.
    Theoretical focus: Analyzes reverse-KL-regularized contextual-bandit formulations of offline, online, and hybrid RLHF and gives efficient iterative algorithms with finite-sample guarantees.

  4. Tengyang Xie, Dylan J. Foster, Akshay Krishnamurthy, Corby Rosset, Ahmed H. Awadallah, and Alexander Rakhlin Exploratory Preference Optimization: Harnessing Implicit Q*-Approximation for Sample-Efficient RLHF. ICLR 2025.
    Theoretical focus: Gives a theoretically grounded exploration algorithm for online RLHF under general function approximation and proves sample-efficiency guarantees.

  5. Dylan J. Foster, Zakaria Mhammedi, and Dhruv Rohatgi Is a Good Foundation Necessary for Efficient Reinforcement Learning? The Computational Role of the Base Model in Exploration. COLT 2025.
    Theoretical focus: Introduces a sampling-oracle framework for reinforcement learning with language models, proves that base-model coverage lower-bounds runtime, and gives an efficient inference-time exploration algorithm when sufficient coverage is present.

  6. Yuda Song, Gokul Swamy, Aarti Singh, J. Andrew Bagnell, and Wen Sun The Importance of Online Data: Understanding Preference Fine-Tuning via Coverage. NeurIPS 2024.
    Theoretical focus: Derives coverage conditions separating online and offline preference optimization and explains when offline data is fundamentally insufficient.

Reliability, Hallucination, and Provenance

Formal limitations on factual prediction and cryptographic methods for identifying generated text.

  1. Adam Tauman Kalai and Santosh S. Vempala Calibrated Language Models Must Hallucinate. STOC 2024.
    Theoretical focus: Relates unavoidable hallucination on arbitrary rare facts to calibration and the Good-Turing missing mass.

  2. Miranda Christ, Sam Gunn, and Or Zamir Undetectable Watermarks for Language Models. COLT 2024.
    Theoretical focus: Constructs secret-key watermarks whose presence is efficiently detectable with the key but computationally indistinguishable from the original language-model distribution without it, even under adaptive prompting.

University Policies and Supports

This website is a companion to the official University of Waterloo course outline. The official outline is the authoritative source for assessment, deadlines, accommodations, academic integrity, and institutional policies. The links below provide direct access to the principal University resources.

This website provides the detailed reading schedule, seminar format, and project guidance. The official University of Waterloo course outline is the authoritative source for assessment, deadlines, accommodations, academic integrity, and institutional policies.

Official course outline: The official course-outline link will be added before the first meeting.

Waterloo provides additional information about course outlines and institutional requirements.