Algorithms in Large Language Models (COMS E6998, Fall'26)

Class Description

This class covers algorithmic aspects of various parts of modern-day LLMs, with a focus on theoretically grounded ideas. The class will primarily cover the theoretical/formal computational frameworks within which one can reason about best algorithms for specific problems. Most of the class will be devoted to mathematical analysis of algorithms.

What the class is not about: while we will try to cover most stages of the LLM pipeline, the main focus is on stages where algorithms have theoretical underpinnings. There will be little emphasis on implementation/code (though it can appear in final projects). There is less emphasis on a pure Machine Learning perspective (e.g., generalization).

Tentative topics (subject to change), with about one topic per week:

  1. Data, Tokenization
  2. Attention Mechanism
  3. Mixture of Experts
  4. Optimization
  5. Distributed Training
  6. Scaling Laws
  7. Retrieval: RAG and Nearest Neighbor Search
  8. Inference-Time Algorithms
  9. Expressivity: Transformers as a Computational Model
  10. Learning at Inference Time: ICL and Test-Time Compute
  11. Privacy and Provenance
  12. Alignment

Prerequisites

Mathematical maturity is a must: the class is based on theoretical ideas and is proof-heavy. You are expected to be able to read and write formal mathematical proofs. Some familiarity with algorithms and randomness will be assumed as well. COMS 4231 (Analysis of Algorithms) or equivalent is useful, but not required if you have a solid math background.

Undergraduate students and students from other departments are welcome.