Class Materials — Algorithms in Large Language Models (COMS E6998)

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.

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

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

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

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)