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. Quantization
  9. Inference-Time Algorithms
  10. Expressivity: Transformers as a Computational Model
  11. Learning at Inference Time: ICL and Test-Time Compute
  12. Privacy and Provenance
  13. Alignment
Assignments will include a semester-long final project (including proposal, presentation/poster, final write-up) that could be theoretical or empirical.

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.