Long Term Memory in AI — Vector Search and Databases (COS 597A, Fall 2023)

Class Description

Long Term Memory is a foundational capability in the modern AI Stack. At their core, these systems use vector search. Vector search is also a basic tool for systems that manipulate large collections of media like search engines, knowledge bases, content moderation tools, recommendation systems, etc.

As such, the discipline lies at the intersection of Artificial Intelligence and Database Management Systems. This course covers the theoretical foundations and practical implementation of vector search applications, algorithms, and systems — ranging from text and image embeddings to dimensionality reduction, locality-sensitive hashing, clustering, vector quantization, and graph-based approximate nearest neighbor indexes. The course is evaluated with a final project and in-class presentation.

Syllabus & Class Notes

• Class 1 (9/8) — Introduction to Vector Search (PDF) [Matthijs + Edo + Nataly]

  • Intro to the course: Topic, Schedule, Project, Grading, …
  • Embeddings as an information bottleneck: instead of learning end-to-end, use embeddings as an intermediate representation.
  • Advantages: scalability, instant updates, and explainability.
  • Typical volumes of data and scalability: embeddings are the only way to manage and access large databases.
  • The embedding contract: the embedding extractor and embedding indexer agree on the meaning of the distance. Separation of concerns.
  • The vector space model in information retrieval.
  • Vector embeddings in machine learning.
  • Definitions: vector, vector search, ranking, retrieval, recall.

• Class 2 (9/15) — Text Embeddings (PDF) [Matthijs]

  • 2-layer word embeddings: Word2vec and fastText, obtained via a factorization of a co-occurrence matrix. Embedding arithmetic: king + woman − man = queen (already based on similarity search).
  • Sentence embeddings: how to train, masked language models, properties of sentence embeddings.
  • Large Language Models: reasoning as an emerging property of an LM; what happens when the training set equals the whole web.

• Class 3 (9/22) — Image Embeddings (PDF) [Matthijs]

  • Pixel structures of images and early works on direct pixel indexing.
  • Traditional computer vision models: global descriptors (GIST), local descriptors (SIFT and friends), direct indexing of local descriptors for image matching, local descriptor pooling (Fisher, VLAD).
  • Convolutional Neural Networks: off-the-shelf models and models trained specifically via contrastive learning and self-supervised learning.
  • Modern computer vision models.

• Class 4 (9/29) — Low Dimensional Vector Search (PDF) [Edo]

  • Vector search problem definition.
  • k-d trees and space-partitioning data structures.
  • Worst-case proof for k-d trees.
  • Probabilistic inequalities: recap of Markov, Chernoff, and Hoeffding inequalities.
  • Concentration of measure phenomena and orthogonality of random vectors in high dimensions.
  • Curse of dimensionality and the failure of space partitioning.

• Class 5 (10/6) — Dimensionality Reduction (PDF) [Edo]

  • Singular Value Decomposition (SVD) and applications of the SVD.
  • Rank-k approximation in the spectral norm and Frobenius norm.
  • Linear regression in the least-squares loss.
  • Principal Component Analysis (PCA): optimal squared-loss dimension reduction and closest orthogonal matrix.
  • Computing the SVD: the power method.
  • Random projections: matrices with normally distributed independent entries and Fast Random Projections (FJLT).

• Class 6 (10/27) — Approximate Nearest Neighbor Search (PDF) [Edo]

  • Definition of Approximate Nearest Neighbor Search (ANNS).
  • Evaluation criteria: speed, accuracy, memory usage, updateability, and index construction time.
  • Definition of Locality Sensitive Hashing (LSH) and examples.
  • The LSH algorithm, analysis, proof of correctness, and asymptotics.

• Class 7 (11/3) — Clustering (PDF) [Edo]

  • k-means clustering: mean squared error criterion.
  • Lloyd’s algorithm.
  • k-means and PCA.
  • ε-net argument for fixed dimensions.
  • Sampling-based seeding for k-means and k-means++.
  • The Inverted File Model (IVF).

• Class 8 (11/10) — Quantization for Lossy Vector Compression (PDF) [Matthijs · Remote via Zoom]

  • Companion Python Notebook: Class_08_runbook_for_students.ipynb.
  • Vector quantization as a topline (directly optimizing the objective).
  • Binary quantization and Hamming distance comparison.
  • Product quantization (PQ), chunked vector quantization, and optimized product quantization (OPQ).
  • Additive quantization: extension of product quantization and difficulty in training approximations (Residual Quantization, CQ, TQ, LSQ, etc.).
  • Cost of coarse quantization vs. inverted list scanning.

• Class 9 (11/17) — Graph-Based Indexes (PDF) [Guest Lecturer: Harsha Vardhan Simhadri]

  • Early works: hierarchical k-means.
  • Neighborhood graphs: how to construct them and Nearest Neighbor Descent (NN-Descent).
  • Greedy search in neighborhood graphs: why local greedy routing is insufficient and the need for long-range jumps.
  • HNSW: a practical hierarchical graph-based index.
  • NSG and DiskANN: evolving a k-NN graph for fast, scalable search.

• Class 10 (12/1) — Student Project and Paper Presentations [Edo + Nataly]

  • In-class final project presentations and discussions (5 minutes per student).

Class Calendar

Below is the schedule of lectures, notes, and project milestones for Fall 2023.

Project & Grading

Class work centers on a final project graded on two equal components:

• Project Submission (50%): Written report and/or code artifact depending on the chosen project flavor.

• In-Class Presentation (50%): 5 minutes per student presented during Class 10 (10 minutes for teams of two; 15 minutes for teams of three).

Project Flavors

• Theory / Research: Propose a new algorithm for a problem explored in class (or modify an existing one), explain what it achieves, and provide experimental evidence or a proof for its behavior. Expected submission: a formal write-up.

• Data Science / AI: Create an interesting use case for vector search using Pinecone, explain what data you used, what value your application brings, and what insights you gained. Expected submission: code (e.g., Jupyter Notebooks) and a write-up of your results and insights.

• Engineering / HPC: Adapt or add to FAISS, explain your improvements, and show experimental results. Expected submission: a branch of FAISS for review along with a short write-up of your suggested improvement and experiments.

Logistics & Timeline

• Project Instructor: Nataly Brukhim (nbrukhim@princeton.edu).

• Team Size: Projects can be worked on individually, in teams of two, or at most three students.

• Expected Effort: Expect to spend a few hours over the semester on the one-page project proposal (aim to get it approved well ahead of the 11/24 deadline) and 3–5 full days on the project itself (on par with preparing for a final exam) ahead of the 12/1 submission and presentation.

Selected Literature

Foundational and contemporary papers in dimensionality reduction, sketching, clustering, quantization, and approximate nearest neighbor search:

• A Comprehensive Survey and Experimental Comparison of Graph-Based Approximate Nearest Neighbor Search — Mengzhao Wang, Xiaoliang Xu, Qiang Yue, and Yuxiang Wang (2021)

• A Fast Random Sampling Algorithm for Sparsifying Matrices — Sanjeev Arora, Elad Hazan, and Satyen Kale (2006)

• A Randomized Algorithm for Principal Component Analysis — Vladimir Rokhlin, Arthur Szlam, and Mark Tygert (2009)

• A Search Structure Based on k-d Trees for Efficient Ray Tracing — K. R. Subramanian and D. S. Fussell (1990)

• A Short Proof for Gap Independence of Simultaneous Iteration — Edo Liberty (2016)

• Accelerating Large-Scale Inference with Anisotropic Vector Quantization — Ruiqi Guo, Philip Sun, Erik Lindgren, Quan Geng, David Simcha, Felix Chern, and Sanjiv Kumar (2020)

• Advances in Neural Information Processing Systems 28 (NeurIPS 2015) — C. Cortes, N. D. Lawrence, D. D. Lee, M. Sugiyama, and R. Garnett, Eds. (2015)

• An Algorithm for Online K-Means Clustering — Edo Liberty, Ram Sriharsha, and Maxim Sviridenko (2016)

• An Almost Optimal Unrestricted Fast Johnson-Lindenstrauss Transform — Nir Ailon and Edo Liberty (2011)

• An Elementary Proof of the Johnson-Lindenstrauss Lemma — Sanjoy Dasgupta and Anupam Gupta (1999)

• Approximate Nearest Neighbors and the Fast Johnson-Lindenstrauss Transform — Nir Ailon and Bernard Chazelle (2006)

• Approximate Nearest Neighbor Search on High Dimensional Data — Experiments, Analyses, and Improvement — Wen Li, Ying Zhang, Yifang Sun, Wei Wang, Mingjie Li, Wenjie Zhang, and Xuemin Lin (2020)

• Billion-Scale Similarity Search with GPUs — Jeff Johnson, Matthijs Douze, and Hervé Jégou (2017)

• Clustering Data Streams: Theory and Practice — Sudipto Guha, Adam Meyerson, Nina Mishra, Rajeev Motwani, and Liadan O’Callaghan (2003)

• DiskANN: Fast Accurate Billion-Point Nearest Neighbor Search on a Single Node — Suhas Jayaram Subramanya, Fnu Devvrit, Harsha Vardhan Simhadri, Ravishankar Krishnaswamy, and Rohan Kadekodi (2019)

• Efficient and Robust Approximate Nearest Neighbor Search Using Hierarchical Navigable Small World Graphs — Yu. A. Malkov and D. A. Yashunin (2018)

• Efficient K-Nearest Neighbor Graph Construction for Generic Similarity Measures — Wei Dong, Moses Charikar, and Kai Li (2011)

• Even Simpler Deterministic Matrix Sketching — Edo Liberty (2022)

• Extensions of Lipschitz Mappings into a Hilbert Space — William B. Johnson and Joram Lindenstrauss (1984)

• Fast Approximate Nearest Neighbor Search with the Navigating Spreading-out Graph — Cong Fu, Chao Xiang, Changxu Wang, and Deng Cai (2018)

• Finding Structure with Randomness: Probabilistic Algorithms for Constructing Approximate Matrix Decompositions — N. Halko, P. G. Martinsson, and J. A. Tropp (2011)

• Invertibility of Random Matrices: Norm of the Inverse — Mark Rudelson (2008)

• K-Means Clustering via Principal Component Analysis — Chris H. Q. Ding and Xiaofeng He (2004)

• k-means++: The Advantages of Careful Seeding — David Arthur and Sergei Vassilvitskii (2007)

• Least Squares Quantization in PCM — Stuart P. Lloyd (1982)

• LSQ++: Lower Running Time and Higher Recall in Multi-Codebook Quantization — Julieta Martinez, Shobhit Zakhmi, Holger H. Hoos, and James J. Little (2018)

• Multidimensional Binary Search Trees Used for Associative Searching — Jon Louis Bentley (1975)

• Near-Optimal Entrywise Sampling for Data Matrices — Dimitris Achlioptas, Zohar S. Karnin, and Edo Liberty (2013)

• Pass Efficient Algorithms for Approximating Large Matrices — Petros Drineas and Ravi Kannan (2003)

• Product Quantization for Nearest Neighbor Search — Hervé Jégou, Matthijs Douze, and Cordelia Schmid (2011)

• QuickCSG: Arbitrary and Faster Boolean Combinations of n Solids — Matthijs Douze, Jean-Sébastien Franco, and Bruno Raffin (2015)

• Quicker ADC: Unlocking the Hidden Potential of Product Quantization with SIMD — Fabien André, Anne-Marie Kermarrec, and Nicolas Le Scouarnec (2021)

• Random Projection Trees and Low Dimensional Manifolds — Sanjoy Dasgupta and Yoav Freund (2008)

• Randomized Algorithms for Low-Rank Matrix Factorizations: Sharp Performance Bounds — Rafi Witten and Emmanuel Candès (2015)

• Randomized Block Krylov Methods for Stronger and Faster Approximate Singular Value Decomposition — Cameron Musco and Christopher Musco (2015)

• Revisiting Additive Quantization — Julieta Martinez, Joris Clement, Holger H. Hoos, and James J. Little (2016)

• Sampling from Large Matrices: An Approach Through Geometric Functional Analysis — Mark Rudelson and Roman Vershynin (2007)

• Similarity Estimation Techniques from Rounding Algorithms — Moses Charikar (2002)

• Similarity Search in High Dimensions via Hashing — Aristides Gionis, Piotr Indyk, and Rajeev Motwani (1999)

• Simple and Deterministic Matrix Sketching — Edo Liberty (2012)

• Smaller Coresets for k-Median and k-Means Clustering — Sariel Har-Peled and Akash Kushal (2005)

• Sparser Johnson-Lindenstrauss Transforms — Daniel M. Kane and Jelani Nelson (2012)

• Sparsity Lower Bounds for Dimensionality Reducing Maps — Jelani Nelson and Huy L. Nguyen (2012)

• Spectral Relaxation for K-Means Clustering — Hongyuan Zha, Xiaofeng He, Chris H. Q. Ding, Ming Gu, and Horst D. Simon (2001)

• Streaming k-Means Approximation — Nir Ailon, Ragesh Jaiswal, and Claire Monteleoni (2009)

• Strong Converse for Identification via Quantum Channels — Rudolf Ahlswede and Andreas Winter (2002)

• Survey of Vector Database Management Systems — James Jie Pan, Jianguo Wang, and Guoliang Li (2024)

• Transformer Memory as a Differentiable Search Index — Yi Tay, Vinh Q. Tran, Mostafa Dehghani, Jianmo Ni, Dara Bahri, Harsh Mehta, Zhen Qin, Kai Hui, Zhe Zhao, Jai Gupta, Tal Schuster, William W. Cohen, and Donald Metzler (2022)

• Unsupervised Neural Quantization for Compressed-Domain Similarity Search — S. Morozov and A. Babenko (2019)

• Worst-Case Analysis for Region and Partial Region Searches in Multidimensional Binary Search Trees and Balanced Quad Trees — D. T. Lee and C. K. Wong (1977)

Contribute & Open Course Materials

All class materials are intended to be used freely by academics anywhere, students and professors alike. Please contribute in the form of pull requests or by opening issues on GitHub.

On Unix-like systems (e.g., macOS or Linux) with bibtex and pdflatex available, you can build the LaTeX lecture notes directly from source:

git clone https://github.com/edoliberty/long-term-memory-in-ai.git
cd long-term-memory-in-ai
./build.sh

Related Classes

• COMS E6998: Algorithms in Large Language Models, Fall '26 (Columbia; A. Andoni, E. Liberty)

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