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 3 (9/16/2026) Data corpus: exact and near-duplicate detection.

  • Data pipelines, an overview: Penedo et al.: The FineWeb datasets: decanting the web for the finest text data at scale (NeurIPS 2024); Soldaini et al.: Dolma: an open corpus of three trillion tokens (ACL 2024);
  • Exact deduplication (suffix arrays): Manber, Myers: Suffix arrays: a new method for on-line string searches (SIAM J. Comput. 1993); Bloom: Space/time trade-offs in hash coding with allowable errors (CACM 1970) (the streaming alternative; used in Dolma's bff); Lee et al.: Deduplicating training data makes language models better (ACL 2022).
  • Near-duplicates (Jaccard, MinHash): Broder: On the resemblance and containment of documents (1997); Broder, Charikar, Frieze, Mitzenmacher: Min-wise independent permutations (STOC 1998, JCSS 2000); Li, König: b-bit minwise hashing (WWW 2010); Li, Owen, Zhang: One permutation hashing (NeurIPS 2012).
  • Not covered in class (for reading) — data selection by importance resampling: Xie, Santurkar, Ma, Liang: Data selection for language models via importance resampling (NeurIPS 2023) (DSIR);

• Lecture 4 (9/21/2026) — Sketching and nearest neighbor search in high dimensions.

  • Sketching similarity (MinHash): Cohen: Min-hash sketches (Encyclopedia of Algorithms, 2016) (k-mins, bottom-k and k-partition estimators with their variances); Nelson: Sketching Algorithms for Big Data, Lecture 2 — distinct elements (Harvard/MIT 2017) (the Chebyshev + median-trick analysis of a min-hash estimator).
  • Nearest neighbor search, the curse of dimensionality, LSH: Indyk, Motwani: Approximate nearest neighbors: towards removing the curse of dimensionality (STOC 1998); Har-Peled, Indyk, Motwani: Approximate nearest neighbor: towards removing the curse of dimensionality (Theory of Computing 2012) (journal version; reduction from approximate NNS to the near-neighbor problem). Andoni, Indyk, Razenshteyn: Approximate nearest neighbor search in high dimensions (ICM 2018) (survey).

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

• Lectures 8 & 9 (10/5/2026 & 10/7/2026) — Randomized Linear Algebra in Large Language Models.

  • Class Notes: Randomized Linear Algebra in Large Language Models — Johnson-Lindenstrauss Random Projections, Singular Value Decomposition & Randomized Power Methods.
  • Random Projections & Johnson-Lindenstrauss: Dasgupta, Gupta: An elementary proof of a theorem of Johnson and Lindenstrauss (Random Structures & Algorithms 2003); Park et al.: TRAK: Attributing model behavior at scale (ICML 2023).
  • Randomized SVD & Simultaneous Iteration: Rokhlin, Szlam, Tygert: A randomized algorithm for principal component analysis (SIMAX 2009); Halko, Martinsson, Tropp: Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions (SIAM Review 2011); Musco, Musco: Randomized block Krylov methods for stronger and faster approximate singular value decomposition (NeurIPS 2015); Zhao et al.: GaLore: Memory-efficient LLM training by gradient low-rank projection (ICML 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)