Algorithms in Large Language Models (COMS E6998, Fall 2026)

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.

Large Language Models (LLMs) are built from a pipeline of stages: data collection and filtering, tokenization, retrieval, the transformer architecture itself (attention in particular), training via stochastic optimization, compression (quantization, sparsity), and inference under a memory/latency budget. Each stage hides one or more algorithmic problems. The focus of the class is on why, not what: not a catalog of the techniques currently used, but the fundamental reasons the good techniques look the way they do.

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).

Lectures & Class Materials

Handouts: Course information • Self-evaluation test (solutions) • Scribes: LaTeX template (contains instructions for the lecture notes and additional chapter).

• Lecture 1 (9/9/2026) — Introduction: Language modeling; the transformer.

  • Language models and the loss: Jurafsky–Martin, Speech and Language Processing, ch. 3 (n-gram language models); Gneiting, Raftery: Strictly proper scoring rules, prediction, and estimation (JASA 2007).
  • Language models are compressors: MacKay, Information Theory, Inference, and Learning Algorithms, ch. 4–6; Shannon: Prediction and entropy of printed English (1951); Delétang et al.: Language modeling is compression (ICLR 2024); Huang et al.: Compression represents intelligence linearly (COLM 2024).
  • Transformers: Vaswani et al.: Attention is all you need (NeurIPS 2017); Phuong, Hutter: Formal algorithms for transformers (2022); The Llama 3 herd of models (2024) and DeepSeek-V3 technical report (2024), as examples of full modern pipelines.

• Lecture 2 (9/14/2026) — Tokenization as an optimization problem.

  • BPE and Unigram: Sennrich, Haddow, Birch: Neural machine translation of rare words with subword units (ACL 2016); Radford et al.: Language models are unsupervised multitask learners (2019), Sec. 2.2 (byte-level BPE); Kudo: Subword regularization (ACL 2018); Kudo, Richardson: SentencePiece (EMNLP 2018); Larsson, Moffat: Off-line dictionary-based compression (Proc. IEEE 2000) (Re-Pair: BPE in linear time).
  • Hardness: Whittington, Bachmann, Pimentel: Tokenisation is NP-complete (ACL 2025).
  • Approximation: Kozma, Voderholzer: Theoretical analysis of byte-pair encoding (2024); Zouhar et al.: A formal perspective on byte-pair encoding (Findings of ACL 2023); Lim, Tan, Choo, Lauw: A partition cover approach to tokenization (NeurIPS 2025) (GreedTok).
  • Is compression the right objective? Schmidt et al.: Tokenization is more than compression (EMNLP 2024); Gallé: Investigating the effectiveness of BPE: the power of shorter sequences (EMNLP 2019); Liu et al.: SuperBPE: Space travel for language models (COLM 2025); Limisiewicz et al.: Compute optimal tokenization (2026).

• Lecture 5 (9/23/2026) — Nearest Neighbor Search: Algorithms in Retrieval-Augmented Generation (RAG).

  • Class Notes: Algorithms in Retrieval-Augmented Generation (RAG) — Submodular Information Maximization & Feedback Arc Set in Tournaments.
  • Reranking & Aggregating Inconsistent Preferences: Ailon, Charikar, Newman: Aggregating inconsistent information: Ranking and clustering (STOC 2005 / JACM 2008).

• Lectures 6 & 7 (9/28/2026 & 9/30/2026) — Algorithmic Concepts in Attention Mechanisms.

  • Class Notes: Algorithmic Concepts in Attention Mechanisms — Kernel Linearization, Random Fourier Features, Coresets & Discrepancy.
  • Kernel Linearization & Random Fourier Features: Rahimi, Recht: Random features for large-scale kernel machines (NeurIPS 2007); Choromanski et al.: Rethinking attention with Performers (ICLR 2021); Dao et al.: FlashAttention: Fast and memory-efficient exact attention with IO-awareness (NeurIPS 2022).
  • Coresets, Discrepancy & KV-Cache Compression: Karnin, Liberty: Discrepancy, coresets, and sketches in machine learning (FOCS 2019); Zhang et al.: H2O: Heavy-Hitter Oracle for efficient generative inference of large language models (NeurIPS 2023); Xiao et al.: Efficient streaming language models with attention sinks (ICLR 2024).

Class Calendar

Below is the schedule of lectures and assignments. Details on readings and lecture notes are updated periodically.

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.

To check whether you have the necessary background, see the self-evaluation test (solutions): you are expected to be able to solve all of its problems.

Undergraduate students and students from other departments are welcome.

Evaluation & Grading

Course grades are based on three components (see course information for full policies):

• Final Project (50%): Research/exploratory (theory) or implementation/empirical project in teams of 1–3 students comparing theoretical guarantees with practical heuristics.

• Homework (30%): One problem set testing the formal frameworks from class, followed by a 10–15 minute individual meeting with a TA to walk through and explain your solutions.

• Scribing (20%): A complete, self-contained LaTeX write-up of one lecture plus a 2–3 page extra chapter on a related result, lower bound, or practical connection using the scribe template.

Related Classes

A sample of related courses (primarily biased towards the theoretical side):

• COMS 6998: Theoretical Foundations of Large Language Models, Spring '25 (Columbia; D. Hsu)

• COS 597R: Deep Dive into Large Language Models, Fall '24 (Princeton; D. Chen, S. Arora)

• COS 597A: Long Term Memory in AI — Vector Search and Databases, Fall '23 (Princeton; E. Liberty, M. Douze)

• STATS 700: LLMs and Transformers, Fall '24 (U. Michigan; A. Tewari)

• CS336: Language Modeling from Scratch (Stanford; P. Liang, T. Hashimoto)