Sutskever Ties AI Generalization to Data Compression Limits
Simons Institute for the Theory of Computing
Unsupervised pre-training succeeds because next-step prediction forces neural networks to execute bounded program searches that extract shared algorithmic structure from data.
AI-assisted summary of An Observation on Generalization — original source. Check the original for full context.
Source published:
Key ideas
- Supervised learning provides ironclad generalization guarantees via simple three-line union bounds, while unsupervised learning theoretically remains mysterious due to the persistent mismatch between surrogate pre-training objectives and downstream evaluation tasks. (2:01)
- Unsupervised pre-training can be rigorously understood through joint data compression: optimizing models on concatenated datasets uncovers algorithmic mutual information, formally explaining how pre-training on general data directly boosts downstream supervised transfer. (14:48)
- Stochastic gradient descent operates as a practical, continuous micro-program search over neural circuits, approximating theoretical non-computable Kolmogorov complexity under fixed parameter and execution budgets. (20:40)
- OpenAI's 2020 Image GPT experiment proved that autoregressive next-step prediction alone extracts high-level semantic representations without specialized inductive biases, achieving 99% accuracy on CIFAR-10 via linear probing. (31:51)
Detailed notes
## Background Published on YouTube by the Simons Institute for the Theory of Computing on August 14, 2023, this lecture features Ilya Sutskever of OpenAI speaking on fundamental perspectives regarding generalization. According to the page description and talk details, the session covers large language models and transformers within the context of theoretical computer science.
## TL;DR Ilya Sutskever contrasts the mathematically sound guarantees of supervised learning with the persistent theoretical mystery behind why unsupervised learning succeeds. He proposes viewing unsupervised pre-training through algorithmic information theory and joint data compression, where predictive modeling acts as a compressor and success is framed through regret minimization against optimal shared-structure extraction. Sutskever characterizes neural network training with stochastic gradient descent as a continuous, bounded approximation of Kolmogorov program search, citing OpenAI's Image GPT results as empirical proof that next-step likelihood maximization inherently produces rich semantic representations. In an extended Q&A, he explores why autoregressive prediction yields superior linear representations over masked models, acknowledges how pure compression theory ignores real-world compute costs, and explains why smooth optimization landscapes diminish the need for curriculum learning.
## Atmosphere & style The presentation carries an intimate, cerebral, and refreshingly candid atmosphere, marked by Sutskever’s low-key delivery and self-deprecating humor regarding OpenAI's corporate secrecy. Rather than presenting a slick corporate keynote, he treats the audience of theoreticians to an exploratory, whiteboard-style reflection on first principles, playfully welcoming audience callouts when a typo is spotted on his slide. The subsequent discussion feels like a spirited seminar among intellectual peers, with audience members cordially defending classical learning theory while Sutskever offers grounded, pragmatic insights into modern deep learning.
## Bulletin - [02:01](https://www.youtube.com/watch?v=AKMuA_TVz3A&t=121s) Supervised learning provides ironclad generalization guarantees via simple three-line union bounds, while unsupervised learning theoretically remains mysterious due to the persistent mismatch between surrogate pre-training objectives and downstream evaluation tasks. - [14:48](https://www.youtube.com/watch?v=AKMuA_TVz3A&t=888s) Unsupervised pre-training can be rigorously understood through joint data compression: optimizing models on concatenated datasets uncovers algorithmic mutual information, formally explaining how pre-training on general data directly boosts downstream supervised transfer. - [20:40](https://www.youtube.com/watch?v=AKMuA_TVz3A&t=1240s) Stochastic gradient descent operates as a practical, continuous micro-program search over neural circuits, approximating theoretical non-computable Kolmogorov complexity under fixed parameter and execution budgets. - [31:51](https://www.youtube.com/watch?v=AKMuA_TVz3A&t=1911s) OpenAI's 2020 Image GPT experiment proved that autoregressive next-step prediction alone extracts high-level semantic representations without specialized inductive biases, achieving 99% accuracy on CIFAR-10 via linear probing.
## Key takeaways - [02:01](https://www.youtube.com/watch?v=AKMuA_TVz3A&t=121s) Supervised learning rests on a complete theoretical foundation where bounded degrees of freedom and identical train/test distributions mathematically guarantee generalization. - [05:51](https://www.youtube.com/watch?v=AKMuA_TVz3A&t=351s) Vapnik–Chervonenkis (VC) dimension is largely an artifact of assuming infinite precision parameters; finite-precision digital computation allows generalization bounds to reduce directly to counting arguments and concentration bounds. - [07:16](https://www.youtube.com/watch?v=AKMuA_TVz3A&t=436s) The core mystery of unsupervised learning is the objective gap: optimizing an arbitrary proxy loss like next-token prediction should not mathematically guarantee performance on distinct downstream capabilities. - [12:14](https://www.youtube.com/watch?v=AKMuA_TVz3A&t=734s) High-dimensional distribution matching offers theoretical guarantees for unsupervised alignment without paired data, but remains too artificial to explain modern representation learning. - [14:48](https://www.youtube.com/watch?v=AKMuA_TVz3A&t=888s) Compression and prediction are mathematically equivalent, and joint compression of concatenated datasets exposes shared structure through algorithmic mutual information. - [18:27](https://www.youtube.com/watch?v=AKMuA_TVz3A&t=1107s) A low-regret unsupervised algorithm guarantees extracting all possible utility from an auxiliary dataset, ensuring optimal performance whether the data is highly structured or pure noise. - [20:40](https://www.youtube.com/watch?v=AKMuA_TVz3A&t=1240s) Kolmogorov complexity serves as the ultimate idealized low-regret compressor, and training neural networks with SGD acts as an empirical micro-Kolmogorov bounded program search. - [24:59](https://www.youtube.com/watch?v=AKMuA_TVz3A&t=1499s) Architectural modifications often yield marginal benefits because baseline networks easily simulate them, whereas breakthroughs occur when intrinsic bottlenecks are broken, such as transitioning from RNNs to Transformers. - [29:26](https://www.youtube.com/watch?v=AKMuA_TVz3A&t=1766s) Evaluating accumulated negative log probabilities across independent training samples directly measures the dataset's total compression size in bits. - [31:51](https://www.youtube.com/watch?v=AKMuA_TVz3A&t=1911s) Image GPT (iGPT) validated the compression theory across modalities by demonstrating that next-pixel prediction on flattened images naturally yields linearly separable semantic features. - [36:20](https://www.youtube.com/watch?v=AKMuA_TVz3A&t=2180s) Autoregressive next-step prediction forces models to resolve hard, long-range dependencies, producing superior linear representations compared to masked models like BERT that rely on local interpolation. - [38:27](https://www.youtube.com/watch?v=AKMuA_TVz3A&t=2307s) The analogy between neural network training and Kolmogorov complexity breaks down primarily at the search procedure, as SGD is a path-dependent, local heuristic rather than an exhaustive search. - [45:03](https://www.youtube.com/watch?v=AKMuA_TVz3A&t=2703s) Compression theory predicts the emergence of strong fine-tuning capability rather than strictly requiring linear representation manifolds. - [48:01](https://www.youtube.com/watch?v=AKMuA_TVz3A&t=2881s) Pure compression theory ignores computational costs, treating autoregressive models, diffusion models, and Universal Transformers as interchangeable despite massive differences in practical engineering efficiency. - [49:46](https://www.youtube.com/watch?v=AKMuA_TVz3A&t=2986s) In the regime of an infinite or arbitrarily large test distribution, the byte size of the compressor's parameters becomes negligible relative to the total evaluated data volume. - [52:52](https://www.youtube.com/watch?v=AKMuA_TVz3A&t=3172s) Curriculum learning matters significantly for fragile, heterogeneous architectures like Neural Turing Machines, but becomes largely unnecessary when the loss landscape and optimizer are well-behaved.
## Detailed walkthrough ### [00:00](https://www.youtube.com/watch?v=AKMuA_TVz3A&t=0s) Introduction and Revisiting Old Insights from OpenAI
Yejin Choi introduces Ilya Sutskever, highlighting his massive academic impact with a citation count spanning six digits—surpassing 139,000 citations—and expresses excitement to hear his perspective on large language models and the future. Stepping up to the podium amid applause, Sutskever begins with an candid, humorous admission about the constraints around his talk. When Umesh Vazirani invited him to speak at the Simons Institute, Sutskever looked at the impressive speaker lineup and eagerly planned to present recent developments. However, he quickly encountered a familiar dilemma: “And then I ran into a problem, which is that a lot of the technical work that we're doing at OpenAI, I actually can't talk about.”
He explains that his entire research focus had recently shifted to AI alignment. Although that work is yielding very compelling results, the findings are not quite ready for public disclosure and will have to wait for a future talk. Searching for a suitable topic, Sutskever decided to turn back the clock to fundamental foundational concepts: “I'll tell you about some very old results that we had at OpenAI many years ago, back in 2016 even, which really affected the way I think about unsupervised learning.” Acknowledging that the audience of theoreticians and researchers might find some points obvious today, he sets expectations modestly, hoping to share an intuitive yet rigorous framework for how a mathematical theory of unsupervised learning can actually exist.
[02:01](https://www.youtube.com/watch?v=AKMuA_TVz3A&t=121s) The Mathematical Elegance of Supervised Learning
Before dissecting unsupervised learning, Sutskever steps back to an even more fundamental inquiry: what is learning itself, and why should computers be able to do it at all? Practitioners have grown so accustomed to the empirical success of deep learning that they simply take for granted that neural networks learn, yet there is no a priori reason why natural data must exhibit regularities that algorithms can capture. The conceptual foundation that demystified this question decades ago was the formalization of supervised learning through PAC (Probably Approximately Correct) learning and statistical learning theory.
```mermaid flowchart TD accTitle: Supervised Learning Generalization Guarantee accDescr: Diagram showing how training data matching test distribution under bounded function capacity guarantees generalization.
subgraph Assumptions["Core Conditions"] D["Train Distribution == Test Distribution"] C["Degrees of Freedom < Training Set Size"] end
subgraph Optimization["Empirical Risk Minimization"] L["Find Function with Low Training Error"] end
subgraph Guarantee["Mathematical Guarantee"] G["Low Test Error Guaranteed"] end
Assumptions --> Optimization Optimization --> Guarantee ```
The beauty of supervised learning lies in providing an exact mathematical condition guaranteeing success. If a learning algorithm draws training samples from a distribution, identifies a function in its hypothesis class that achieves low empirical training error, and the model's degrees of freedom remain smaller than the dataset size, low generalization error on the test distribution is mathematically assured. Sutskever highlights how this entire foundation can be proved in roughly three lines of union-bound mathematics: “So three lines of math can prove all of supervised learning.” With identical training and testing distributions, supervised learning transforms seemingly complex real-world tasks—such as speech recognition or image categorization—into conceptually solved, mathematically sound problems where simply scaling up datasets guarantees improved performance.
[05:51](https://www.youtube.com/watch?v=AKMuA_TVz3A&t=351s) A Note on VC Dimension vs. Finite Precision
Sutskever digresses briefly with an aside directed at audience members who care about statistical learning theory mechanics, offering that anyone uninterested could safely zone out for thirty seconds. He observes that textbooks and research papers routinely place immense emphasis on Vapnik–Chervonenkis (VC) dimension as the central pillar of generalization theory. However, Sutskever argues that VC dimension is largely a mathematical workaround for idealized real numbers: “The VC dimension was invented to handle precision parameters with infinite precision.”
In theoretical models like infinite-precision linear classifiers, parameters can hold arbitrary real values, necessitating combinatorial measures like shattering coefficients. In physical computation, however, every parameter is represented as a finite-precision floating-point number, and modern machine learning tends toward ever-shrinking bit precisions. Because digital computers can only express a finite set of discrete functions, generalization bounds reduce straightforwardly to discrete counting arguments and simple concentration bounds. Sutskever finds this finite perspective far cleaner and more appealing because it bypasses technical measure-theoretic machinery and establishes tight bounds in just a few lines of proof.
[07:16](https://www.youtube.com/watch?v=AKMuA_TVz3A&t=436s) The Paradox and Mystery of Unsupervised Learning
Shifting to unsupervised learning, Sutskever underscores a glaring theoretical void: unlike supervised learning, there is no widely accepted mathematical condition that explains why unsupervised learning works. Historically, unsupervised learning carried an ambitious dream—dating back to Boltzmann machines in the 1980s, denoising autoencoders, and early language models—that exposing a network to raw images or unannotated text would force it to uncover the latent physical and semantic structures of reality. While contemporary large language models and diffusion models have fulfilled this ambition empirically, Sutskever maintains that our mathematical understanding remains deeply unsatisfying.
The core conceptual paradox stems from a profound objective mismatch: - **Optimization Target:** You optimize a proxy objective on unlabeled data, such as reconstruction loss, denoising error, or self-supervised next-token prediction. - **Evaluation Target:** You evaluate the model on an entirely different downstream downstream capability, such as classification, reasoning, or representation quality. - **The Mystery:** Why should minimizing one arbitrary surrogate loss guarantee success on an entirely different task?
As Sutskever puts it: “You optimize one objective, but you care about another objective. And yet it helps. How can that be? Magic.” Furthermore, unsupervised learning offers zero benefit if the input data is drawn from a featureless uniform distribution. Because real data must possess specific non-trivial structure for unsupervised learning to aid downstream tasks, any coherent theory cannot rely solely on empirical optimism; it must establish what assumptions are necessary to guarantee that unsupervised representations transfer.
[11:24](https://www.youtube.com/watch?v=AKMuA_TVz3A&t=684s) Distribution Matching: An Unsupervised Method Guaranteed to Work
To cut through this mystery, Sutskever introduces an alternative formulation of unsupervised learning that, while never becoming the dominant practical approach, possesses the rare property of being provably guaranteed to work: distribution matching.
Instead of relying on heuristic surrogate losses and hoping for downstream transfer, distribution matching operates across two distinct, unaligned data domains, $X$ and $Y$. Crucially, there are no paired examples, correspondence maps, or supervised labels bridging them—only independent samples drawn from their respective distributions. Sutskever poses distribution matching as a rigorous unsupervised learning paradigm that mirrors the mathematical guarantees of supervised learning, setting the stage to explore how mapping one distribution onto another can unlock provable unsupervised alignment.
[12:14](https://www.youtube.com/watch?v=AKMuA_TVz3A&t=734s) Distribution Matching and Its Limitations
Ilya Sutskever examines the problem of unsupervised alignment where there is no explicit pairing between two domains—such as language one and language two, or text and speech. The learning criterion is to find a function $f$ such that the transformed distribution of inputs, $f(X)$, matches the target distribution $Y$. When the inputs and outputs live in a sufficiently high-dimensional space, matching these distributions imposes a massive system of constraints on $f$. In settings like machine translation, speech recognition, or simple substitution ciphers, this condition can be restrictive enough that matching the marginal distribution of translated English sentences to French sentences allows one to almost completely recover the underlying mapping function $f$.
```mermaid flowchart LR accTitle: Distribution Matching Framework accDescr: Unpaired distribution X is transformed via function f to match distribution Y under high-dimensional constraints. subgraph InputSpace ["Source Domain"] X["Unpaired Data X<br/>(e.g., English text)"] end subgraph Mapping ["Transformation"] F["Function f"] end subgraph TargetSpace ["Target Domain"] Y["Target Data Y<br/>(e.g., French text)"] Match{"Distribution Matching<br/>dist(f(X)) ≈ dist(Y)"} end X --> F F --> Match Y --> Match ```
Reflecting on his own intellectual journey, Sutskever shares that he independently arrived at this distribution-matching formulation in 2015 and was initially enthralled by it, believing it might provide a rigorous mathematical foundation for unsupervised learning with theoretical guarantees analogous to supervised learning. However, he came to realize that the setup remains somewhat artificial and does not reflect how machine learning actually operates in practice, nor how researchers intuitively conceptualize unsupervised representation learning.
> “If the dimensionality of X and the dimensionality of Y is high enough, that's going to give you a lot of constraints.” — Ilya Sutskever
- Distribution matching establishes guarantees by requiring that applying $f$ across an entire high-dimensional dataset yields an output distribution indistinguishable from the target domain. - While mathematically solvable for settings like substitution ciphers and machine translation, the framing fails to capture the true versatility and mechanics of modern unsupervised deep learning.
---
[14:48](https://www.youtube.com/watch?v=AKMuA_TVz3A&t=888s) Compression Is Prediction: The Joint Compression Thought Experiment
To place unsupervised learning on an equal footing with supervised learning, Sutskever pivots to the principle that compression and prediction are fundamentally identical. While it is well-established that every predictor corresponds to a compressor and vice versa, Sutskever argues that framing the problem through the lens of data compression provides far sharper intuition. He introduces what he calls the central thought experiment of his talk: imagine having two separate files on a giant hard drive, a dataset $X$ and a dataset $Y$, and running a high-grade compression algorithm $C$ on their concatenation.
```mermaid flowchart TD accTitle: Joint Compression and Mutual Information accDescr: Concatenating dataset X and dataset Y through compressor C exposes shared algorithmic structure. subgraph Data ["Data Inputs"] X["Unsupervised Data (X)"] Y["Supervised Data (Y)"] end subgraph JointCompression ["Concatenation & Compression"] Concat["Concatenation (X + Y)"] Comp["Compressor C"] end subgraph Output ["Information Metrics"] Size["Compressed Size C(XY)"] Bound["C(XY) ≤ C(X) + C(Y)"] Gap["Shared Structure / Algorithmic Mutual Information"] end X --> Concat Y --> Concat Concat --> Comp Comp --> Size Size --> Bound Bound --> Gap ```
A sufficiently powerful compressor operating on the concatenated string $XY$ will instinctively leverage regularities, patterns, and structure discovered in $X$ to reduce the file size of $Y$, and vice versa. For any competent compressor, compressing the concatenated files jointly will yield a representation that is no worse than the sum of compressing each file independently ($C(XY) \le C(X) + C(Y)$). The compression gap between separate and joint compression represents the shared structure discovered across both domains—the algorithmic mutual information. When $Y$ represents a supervised downstream task and $X$ represents an unlabeled unsupervised corpus, joint compression provides a concrete mathematical justification for why unlabeled patterns directly aid downstream supervised performance, naturally subsuming distribution matching when an invertible mapping $f$ exists.
> “So any additional compression that was gained by concatenation is some kind of shared structure that your compressor noticed.” — Ilya Sutskever
- There is a strict one-to-one correspondence between predictive statistical models and lossless data compressors. - Jointly compressing concatenated files uncovers algorithmic mutual information, formally explaining how pre-training on general data ($X$) accelerates or enhances learning on a target task ($Y$).
---
[18:27](https://www.youtube.com/watch?v=AKMuA_TVz3A&t=1107s) Formalizing Unsupervised Learning via Regret
Building on the joint compression paradigm, Sutskever addresses how to formalize the evaluation of an unsupervised machine learning algorithm. Suppose an algorithm $A$ is tasked with compressing a target file $Y$ while being granted arbitrary read access to an unlabeled reference file $X$. The benchmark of success is framed as minimizing regret: evaluating how much predictive or compressive performance algorithm $A$ left on the table compared to the best possible compressor that could have processed that same unlabeled dataset.
Sutskever emphasizes the practical comfort of a low-regret algorithm: in real-world scenarios, a practitioner cannot know in advance whether an unlabeled dataset $X$ contains rich, task-relevant representations or consists entirely of uninformative noise, such as samples from a uniform distribution. A low-regret unsupervised learning algorithm guarantees that regardless of data quality, it extracts the maximum possible utility. If the data contains crucial insights for task $Y$, the algorithm exploits them fully; if the data is useless, it suffers no competitive disadvantage compared to any alternative method.
> “Being low regret means that I've gotten all the help that I can possibly get from this unlabeled data.” — Ilya Sutskever
- Regret measures the performance gap between a given learning algorithm and the theoretical optimum achievable when leveraging auxiliary unlabeled data $X$ to predict $Y$. - A zero-regret or low-regret unsupervised algorithm guarantees optimal sample efficiency from unlabeled corpora, granting practitioners confidence that no better extractor could extract more value from the available data.
---
[20:40](https://www.youtube.com/watch?v=AKMuA_TVz3A&t=1240s) Kolmogorov Complexity and SGD as Program Search
Sutskever shifts into theoretical territory, identifying Kolmogorov complexity as the ultimate, idealized low-regret compressor. By definition, the Kolmogorov complexity of a string is the length of the shortest computer program that outputs that string. When an audience member spots an error on the slide—pointing out that the definition displays $Y$ where it should say $X$—Sutskever playfully acknowledges the catch: “Yes, that is correct. You got me.” He outlines the simulation argument proving why Kolmogorov complexity acts as an upper bound on compression efficiency: if an engineer presents any compression algorithm $C$, that compressor can simply be encoded as an executable program and fed into the universal Turing machine, costing only the original compressed data length plus a constant overhead representing the code length of $C$.
Because the Kolmogorov compressor effectively evaluates all possible computer programs, it is fundamentally undecidable and non-computable. However, Sutskever draws an explicit connection between this theoretical ideal and modern deep learning. When stochastic gradient descent (SGD) optimizes the parameters of a 100-layer neural network, it is effectively executing a continuous, bounded program search over a physical computing circuit possessing a fixed memory footprint and execution budget. Sutskever describes training deep neural networks as a form of “micro-Kolmogorov” program search, marveling that the empirical success of deep learning rests upon the remarkable fact that gradient descent can reliably navigate this computational search space.
> “And all of deep learning hinges on top of the SGD miracle that we can actually train these computers with SGD.” — Ilya Sutskever
- Kolmogorov complexity represents the theoretical limit of compression, satisfying $K(X) \le C(X) + O(1)$ for any computable compressor $C$ via the simulation argument. - Although non-computable in the Turing sense, deep neural networks act as circuits (programs), and optimizing them with SGD represents an empirical approximation of bounded program search.
[24:59](https://www.youtube.com/watch?v=AKMuA_TVz3A&t=1499s) From Formal Kolmogorov Complexity to Neural Networks
Moving from theoretical foundations to empirical deep learning, the circuits that approximate theoretical programs are found directly from data via optimization. Sutskever notes that this perspective explains why designing fundamentally superior neural network architectures is notoriously difficult: an architectural variation such as adding a specialized connection or modifying layers usually provides minimal benefit because the existing architecture can easily simulate the new one.
The notable exception occurs when an old architecture faces an intrinsic bottleneck that prevents straightforward simulation. A canonical example is transitioning from recurrent neural networks (RNNs) to Transformers: the RNN relies on a fixed-size hidden state that bottlenecks its capacity, rendering it incapable of efficiently simulating a Transformer's global attention mechanism. Sutskever muses that if engineers had discovered a technique to scale an RNN's hidden state to massive dimensions, it might have remained competitive with Transformers. Through this lens, empirical deep learning maps directly onto algorithmic information theory, moving from abstract proofs into actionable engineering.
```mermaid flowchart TD accTitle: Architectural Simulation and Kolmogorov Approximation accDescr: Diagram illustrating how neural network search mirrors Kolmogorov complexity and why architecture modifications often fail due to simulation arguments.
subgraph Theory["Algorithmic Information Theory"] KP["Shortest Program Search<br/>(Kolmogorov Compressor)"] NoRegret["Theoretical Ideal:<br/>Zero Regret Predictor"] end
subgraph DeepLearning["Empirical Deep Learning"] SGD["Stochastic Gradient Descent (SGD)"] NN["Large Neural Networks"] Bottleneck{"Architectural<br/>Bottleneck?"} SimOld["Easily simulated by baseline<br/>(Marginal improvement)"] Breakthrough["Fundamental breakthrough<br/>(e.g., RNN → Transformer)"] end
Theory -.->|"Squinting / Analogous mapping"| DeepLearning SGD --> NN NN --> Bottleneck Bottleneck -- "No" --> SimOld Bottleneck -- "Yes" --> Breakthrough NN -.->|"Approximates closer as scale grows"| KP Breakthrough -.-> NoRegret ```
[26:12](https://www.youtube.com/watch?v=AKMuA_TVz3A&t=1572s) Conditional Complexity and the Joint Compression Shortcut
Sutskever extends the theoretical framing to conditional Kolmogorov complexity, denoted as $K(Y \mid X)$, which formalizes the length of the shortest computer program that outputs a target distribution or dataset $Y$ given the ability to probe an input dataset $X$. In this formulation, $X$ and $Y$ represent entire datasets rather than isolated individual examples. This construction mathematically extracts every drop of predictive utility from $X$ for predicting $Y$.
> “If you use that, you can sleep very, very safely at night—soundly at night, knowing that no one does unsupervised learning better than you.”
However, conditioning on massive training sets remains practically unwieldy in standard machine learning pipelines: models can easily fit huge collections of data, but dynamically conditioning on them remains largely unfeasible. Sutskever resolves this with a theoretical shortcut: rather than executing explicit conditional compression, an engineer can simply concatenate all data files into a single master sequence and apply a standard, unconditional Kolmogorov compressor to the combined input. Compressing the joint concatenation $X$ and $Y$ achieves the exact same predictive performance on downstream supervised targets.
- Conditional Kolmogorov complexity $K(Y \mid X)$ defines the algorithmic minimum code length to produce dataset $Y$ with access to dataset $X$. - Conditioning across massive corpora remains an open operational hurdle in machine learning workflows. - Unconditional compression on concatenated datasets mathematically matches conditional compression for downstream tasks. - Maximizing the joint data likelihood under parameter constraints aligns with standard machine learning training without overfitting.
[29:26](https://www.youtube.com/watch?v=AKMuA_TVz3A&t=1766s) SGD as Kolmogorov Program Search and the Limits of Text GPTs
Joint data compression translates directly into maximum likelihood estimation under the condition that a model avoids overfitting. The sum of the data negative log-likelihoods evaluated under the model parameters constitutes the compression cost of the dataset, balanced against the bit cost of storing the parameters themselves. Scaling up training simply requires appending more data points to the loss sum, making concatenation the most natural operation in deep learning.
Viewing gradient optimization through this prism suggests that running stochastic gradient descent (SGD) over giant neural networks functions as an empirical program search algorithm. Larger models approximate the theoretical Kolmogorov compressor more accurately, providing a crisp foundational justification for why scaling model parameters consistently improves generalization.
Sutskever points out an epistemological limitation when applying this hypothesis exclusively to Large Language Models (LLMs). The few-shot learning phenomena observed in autoregressive language models can be explained away without appealing to deep compression theories: - Natural text on the internet already consists of repeated patterns and prompts. - Autoregressive modeling naturally continues repeated sequences by conditioning on local context. - Because language behavior can be dismissed as surface-level text statistics, direct empirical validation required exploring an entirely different data modality.
[31:51](https://www.youtube.com/watch?v=AKMuA_TVz3A&t=1911s) Validating Compression on Pixels: The Image GPT (iGPT) Experiment
To rigorously validate whether next-step prediction inherently extracts semantic representations via compression, Sutskever highlights OpenAI's 2020 experiment, Image GPT (iGPT). Rather than treating vision with specialized convolutional architectures, iGPT flattened raw images into simple sequences of discrete pixel intensities and trained a standard autoregressive Transformer strictly on next-pixel prediction.
```mermaid flowchart LR accTitle: Image GPT (iGPT) Pipeline accDescr: Block diagram showing the process of turning raw images into pixels, autoregressive next-pixel prediction, and linear probing.
subgraph DataPrep["Data Preprocessing"] Img["Raw Image<br/>(64x64 resolution)"] --> Pixels["1D Sequence of<br/>Discrete Pixels"] end
subgraph Pretraining["Unsupervised Pretraining"] Pixels --> GPT["Autoregressive Transformer<br/>(Next-Pixel Prediction)"] GPT --> Comp["Maximizes Likelihood<br/>(Joint Compression)"] end
subgraph Evaluation["Linear Probe"] Comp --> Feat["Extract Hidden Features<br/>(Best Intermediate Layer)"] Feat --> Probe["Linear Classifier<br/>(ImageNet / CIFAR-10)"] end ```
Despite lacking inductive visual biases and using low-resolution $64 \times 64$ images, the model achieved remarkable representation learning. When fitting a basic linear probe atop frozen intermediate layers, classification accuracy scaled monotonically with next-pixel prediction accuracy. The model reached 99% accuracy on CIFAR-10 and nearly closed the performance gap with the top unsupervised vision techniques of 2020 on ImageNet using a 6-billion-parameter network. The result validated that generic next-step likelihood maximization inherently extracts high-level semantics from raw sensory input.
- **Data Representation:** Images serialized as discrete intensity pixel tokens fed sequentially into a standard Transformer architecture. - **Model Scale:** Up to 6 billion parameters, which Sutskever characterizes as "giant for the day" though "tiny by today's standards." - **CIFAR-10 Performance:** Linear probing on learned representations reached approximately 99% accuracy. - **ImageNet Linear Probing:** Competitive with contemporary state-of-the-art self-supervised vision methods despite the compute handicap of training on $64 \times 64$ inputs.
[34:50](https://www.youtube.com/watch?v=AKMuA_TVz3A&t=2090s) The Mystery of Linearly Separable Representations and Autoregression vs. BERT
Sutskever concludes his presentation by reflecting on the persistent puzzle of linear representations. While compression theory explains why optimization extracts predictive information, it fails to explain why that information should emerge in the form of linearly separable manifolds within neural activations.
> “The thing—I like the compression theory, because I feel like it just bothered me for a long time that you couldn't think rigorously about unsupervised learning. I claim now you can, at least to some partial degree.”
Empirical evaluations show that causal autoregressive architectures—like next-pixel or next-word prediction—consistently produce superior linear representations compared to masked bidirectional models like BERT. After wrapping up his prepared slides to applause, an audience member immediately asks him to share his speculation on why autoregressive next-step models yield such robust linear feature spaces. Sutskever begins addressing the question by focusing on the unique mechanistic pressures imposed by causal next-step prediction.
[36:20](https://www.youtube.com/watch?v=AKMuA_TVz3A&t=2180s) Next-Pixel Prediction vs. BERT and Diffusion Models
Ilya Sutskever contrasts autoregressive next-pixel prediction with bidirectional masked prediction methods like BERT. When predicting the next pixel sequentially from all preceding pixels, the network is forced to uncover and model long-range structure across the entire visual field. In a masked framework such as BERT, if roughly 25% of the tokens or pixels are omitted, a network can fill in most blanks simply by interpolating between nearby context—looking just slightly into the past and slightly into the future. By doing so, “you remove all the hard prediction tasks, or you make them much easier.” Consequently, the most challenging prediction tasks in next-pixel prediction are fundamentally far more demanding than the hardest tasks posed by masked prediction.
```mermaid flowchart TD accTitle: Autoregressive vs Masked Image Prediction accDescr: Comparison of next-pixel autoregression requiring global structure versus local interpolation in masked token modeling.
subgraph AR["Next-Pixel Prediction (Autoregressive)"] A1["Prior Context"] -->|"Requires global structure"| A2["Next Pixel"] end
subgraph Masked["BERT / Masked Autoencoding"] B1["Past Context"] --> B2["Masked Target (25%)"] B3["Future Context"] --> B2 B2 ---|"Local interpolation suffices"| B4["Easier Prediction Task"] end ```
When an audience member asks if a more robust two-dimensional formulation exists for next-pixel prediction, Sutskever clarifies that broadly speaking, any architecture that turns a neural network into a probabilistic model assigning normalized probabilities to inputs accomplishes this. He brings up diffusion models as the other prominent formulation for generative modeling. While high-performance image generators in practice optimize objectives other than pure data likelihood, the foundational formulation of diffusion is maximum likelihood. Sutskever points out that diffusion models serve as an intriguing counterargument or parallel: he claims diffusion models should form worse linear representations than autoregressive next-token models for the very same reason BERT does, which “further, in my mind, increases the mystery of what caused leads to linear representations to form.”
[38:27](https://www.youtube.com/watch?v=AKMuA_TVz3A&t=2307s) The Limits of the Kolmogorov Complexity Analogy
An audience member raises an objection regarding the analogy between neural network training and Kolmogorov complexity. In classic algorithmic information theory, compressing via Kolmogorov complexity searches over computer programs where the ordering of the data does not matter. Neural networks, by contrast, possess non-trivial training dynamics: simple heuristics and features are learned early on and persist, making training sensitive to data ordering and trajectory.
Sutskever fully acknowledges that the analogy breaks down precisely around the optimization and search mechanisms. A theoretical Kolmogorov compressor utilizes an infinitely expensive search procedure that enumerates and tests all possible programs from scratch each time, whereas practical deep learning relies on gradient descent. As Sutskever explains: “The place where that analogy breaks down the most is in the search procedure.” Because stochastic gradient descent (SGD) is a comparatively weak, path-dependent search heuristic, “caution should be used with this particular analogy.” Nevertheless, he maintains that the conceptual frame of compression provides indispensable intuition for understanding why unsupervised pre-training yields powerful representations.
- Kolmogorov complexity relies on an exhaustive brute-force search over all Turing machines from scratch. - Neural networks rely on stochastic gradient descent (SGD), a local and comparatively weak search procedure where data ordering and training dynamics matter. - Despite this optimization gap, viewing pre-training through the lens of compression explains the empirical transfer from unsupervised learning to downstream tasks.
[40:17](https://www.youtube.com/watch?v=AKMuA_TVz3A&t=2417s) Cryptographic Distinguishability and Energy-Based Models
Another participant draws a connection to 1980s cryptography and computational complexity theory, where next-bit predictability, compression, and polynomial-time distribution indistinguishability are proven to be equivalent. In cryptographic settings, the premise is that pseudorandom outputs cannot be compressed because no efficient distinguisher can tell them apart from uniform noise; the audience member asks how this equivalence might map back to learning representations in natural data.
Sutskever notes that while he is not an expert on that specific cryptographic literature, a related concept in machine learning is energy-based models (EBMs). EBMs provide an alternative mechanism for turning unnormalized neural network outputs into valid probability distributions: the network assigns a scalar "energy" score to an arbitrary configuration of vectors reflecting how typical or plausible it is, followed by normalizing across the entire space. In this regime, the ratio of two probabilities translates directly to the difference between their respective energy states, creating a structural link to distinguishing between data distributions.
[42:50](https://www.youtube.com/watch?v=AKMuA_TVz3A&t=2570s) A Defense of VC Dimension and Empirical Compression Bounds
An audience member interjects with a lighthearted defense of classical statistical learning theory: “Ilya, maybe I'll just put in a tiny word to defend the honor of VC dimension.” The speaker recounts a 2007 result regarding PAC learning of quantum states, pointing out that even when discretizing the state space without assuming infinite precision, the Vapnik–Chervonenkis (VC) dimension or fat-shattering dimension can be exponentially smaller than the logarithm of the hypothesis class size. Sutskever smiles and concedes, “That is a cool example.”
```mermaid flowchart LR accTitle: Dataset Compression via Summed Log Probabilities accDescr: Pipeline showing individual log probabilities summed across training samples to yield the total dataset compression cost in bits.
subgraph LossEval["Log Loss Evaluation"] D["Dataset X = {x_1,..., x_N}"] --> NN["Neural Net Probability Model"] NN --> LP["Individual Log Probabilities: log P(x_i)"] end
subgraph TotalBits["Negative Log Likelihood"] LP --> Sum["Sum across all cases"] Sum --> Bits["Negative Log Probability = Total Bits"] end ```
The discussion turns back to Sutskever's formal notation, where $X$ denotes a sampled dataset and the model assigns probabilities to each example. A questioner asks whether treating SGD-trained Transformers as compressors is compromised because the model processes samples sequentially rather than taking in the whole dataset at once. Sutskever clarifies that evaluating the total training loss across all independent samples corresponds directly to computing the aggregate log probability assigned to the full dataset: “And that gives you your negative log probability, literally the number of bits you need to compress this data set using this neural network as a compressor.” Even though per-sample processing prevents the network from learning patterns across the temporal order of the samples, the summed negative log-likelihood remains an exact measure of dataset compression length.
[45:03](https://www.youtube.com/watch?v=AKMuA_TVz3A&t=2703s) Linear Representations, Fine-Tuning, and Function Classes
A participant asks whether compression can serve as an objective justification for unsupervised learning in domains where linear representations do not spontaneously appear. In language, unsupervised learning can look superficially like supervised prediction because any NLP task can be cast as next-word prediction. In vision tasks like Image GPT, next-pixel prediction does not mirror typical tasks, yet linear probe performance on intermediate features demonstrated unsupervised transfer. If certain effective compressors fail to generate linearly separable representations, what justifies compression as the foundational objective?
Sutskever responds that the emergence of linearly accessible representations is simply an added bonus rather than a requirement of the theoretical framework. The underlying theory instead predicts that good fine-tuning capability will emerge: “At no point does this argument say, and therefore linear representation should emerge. However, I would argue that the theory does say that good fine-tuning should emerge, because joint compression is kind of like hacky approximate fine-tuning using the bad search algorithm, which is SGD.” He notes that just as BERT underperforms next-pixel prediction on linear visual feature probes, diffusion models likely exhibit similar trade-offs, raising the question of how fine-tuned diffusion models would compare empirically.
When asked what lessons from unsupervised compression can be transferred back to supervised learning, Sutskever points to architectural guidance on hypothesis classes: - Depth is essential because stacking many layers gives the neural network the computational steps required to do more expressive processing. - Width allows models to capture larger parameter spaces and complex interactions, matching the empirical shift toward scaled-up models. - The compression perspective provides theoretical grounding for why massively overparameterized networks generalize well on supervised tasks without requiring sample sizes proportional to parameter counts.
[48:01](https://www.youtube.com/watch?v=AKMuA_TVz3A&t=2881s) Theoretical Blind Spots: Compute Costs and Architecture Agnosticism
Responding to an audience question about parameter counts, Ilya Sutskever points out an inherent limitation in viewing deep learning strictly through the lens of information-theoretic compression: it completely disregards computational efficiency. “So the weakness of this theory—by the way, this theory has a huge practical weakness, which is it ignores compute cost,” Sutskever explains. “It only focuses on information.” To illustrate the issue, he points to the Universal Transformer, an architecture where the same network weights are reused across every successive layer. On paper, it is an elegant, parameter-efficient design, but if one wants to scale up parameter capacity or effective depth, it comes at an immense compute penalty that practitioners simply refuse to pay in practice.
```mermaid flowchart TD accTitle: Information Theory vs Practical Deep Learning accDescr: Diagram contrasting pure information-theoretic compression with real-world compute-constrained models. subgraph InfoTheory["Pure Information / Compression Theory"] A["Focuses purely on bits & data"] B["Ignores computational budget"] C["Architectures look equivalent"] end subgraph Practical["Practical Engineering Reality"] D["Autoregressive Transformers: simple & compute-efficient"] E["Diffusion / EBMs: require 10x-15x more compute"] F["Universal Transformers: tied weights penalize compute"] end InfoTheory -.->|"Omits constant factors"| Practical ```
An audience member asks about the specific importance of autoregressive modeling over probability distributions, pointing out that masked models like BERT can also be viewed as doing maximum likelihood training, and one can devise ways to sample from BERT as well. Sutskever broadens the scope to include diffusion models, noting that certain diffusion formulations can likewise be framed as maximum likelihood estimators. Because pure compression theory is indifferent to compute budgets, it treats these model families as fundamentally interchangeable:
> “So it's going to say, OK, maybe you need like a factor of 10 or 15 compute, and then things will be the same between the autoregressive and diffusion model.”
From this high-level theoretical perspective, whether one selects an autoregressive model, a diffusion model, or an energy-based model matters very little. Autoregressive transformers dominate today primarily because they are simple, direct, and computationally convenient, even if other formulations might theoretically achieve identical results at higher computational overhead.
---
[49:46](https://www.youtube.com/watch?v=AKMuA_TVz3A&t=2986s) Compressor Size vs. Data Size in the Infinite Test Set Regime
An audience member raises a paradox regarding model scale: GPT-4 appears to be the most capable compressor currently in existence, yet it is also the largest model deployed, meaning the size of the compressor itself has ballooned. In classical Kolmogorov complexity, a large decompression program penalizes the overall code length unless the data being compressed is exponentially larger.
Sutskever acknowledges that this represents another point where the clean theoretical model diverges from the reality of large language model pre-training. Classical Minimum Description Length (MDL) and Kolmogorov complexity assume a fixed, bounded dataset that must be compressed into a self-contained program and bitstream. In real-world machine learning, however, models are trained on massive training sets with the explicit objective of generalizing to an evaluation stream:
> “If the test set is infinite and you care about compressing the test set, then you don't care about the size of your compressor, so long as this test set size is much larger.”
Because the downstream distribution can be considered arbitrarily large or infinite, the fixed byte size of the network weights becomes asymptotically negligible relative to the total sequence volume evaluated.
When another audience member asks whether evaluating on an independent validation set resolves this discrepancy, Sutskever agrees that keeping an independent holdout set is good practice. He adds that in the single-epoch pre-training regime—where a model never sees the same training token twice—the distinction largely collapses: - In a single epoch, computing accumulated log probabilities during training already serves as an online measure of the model’s data compression. - Online single-epoch training loss provides an exceptionally close estimate of generalization performance on an unseen validation distribution.
---
[51:51](https://www.youtube.com/watch?v=AKMuA_TVz3A&t=3111s) Gzip + k-NN Text Classification and the Value of Squeezing Bits
An attendee raises a recent paper (presented at ACL) that demonstrated text classification without parameter training by combining `gzip` compression with a simple $k$-nearest neighbors ($k$-NN) classifier. In that method, pairs of text strings are compressed both individually and concatenated together to compute a normalized compression distance metric.
Sutskever is skeptical about drawing sweeping conclusions from such lightweight compressors:
> “My only comment on that is that gzip is not a very strong compressor of text. So I think it does show that things are possible to some degree, but all the really meaty stuff happens when you squeeze the last bits, if you see what I mean.”
While the audience member suggests it serves as a working toy proof-of-concept, another audience member interjects that early benchmark claims for that paper were distorted by implementation bugs. Sutskever smiles and agrees with the critique: “It doesn't work.” True semantic generalization, he maintains, only emerges when a model reaches the extreme compression ratios where every subtle statistical dependency in human text is discovered and modeled.
---
[52:52](https://www.youtube.com/watch?v=AKMuA_TVz3A&t=3172s) Curriculum Learning and Optimization Landscape
The final discussion centers on curriculum learning, which had been raised earlier in relation to how humans learn sequentially compared to how Kolmogorov complexity ignores order. An audience member notes that while curriculum effects are frequently discussed for neural networks, there was no consensus among colleagues over lunch regarding how much curriculum learning actually matters empirically in modern practice.
Sutskever offers a distinct perspective, arguing that the importance of a curriculum is inversely proportional to how easy the model architecture and optimizer are to train:
> “The easier is—the more easy the training optimization problem is, the less susceptible you are to curriculum effects.”
He recounts that the deep learning community has spent years heavily engineering the standard transformer setup—discovering robust weight initializations, tuning learning rate schedules and hyperparameters, and refining residual and normalization placements specifically so gradient descent navigates the loss surface smoothly. When an optimization landscape is well-behaved, a model can absorb arbitrary, unstructured data mixtures right from step zero without getting trapped in bad local minima.
By contrast, Sutskever points to fragile, highly heterogeneous architectures from earlier research: - Neural Turing Machines (NTMs) and memory-augmented networks featured complex routing, read/write heads, and distinct non-uniform components. - For those architectures, training was notoriously finicky: presenting the full, uncurated task suite upfront caused optimization to fail completely, making an incremental, step-by-step curriculum strictly mandatory.
---
[54:21](https://www.youtube.com/watch?v=AKMuA_TVz3A&t=3261s) Concluding Applause
Session chair Yejin Choi takes the microphone to bring the session to a close. “All right, let's thank Ilya again,” she announces to the room, prompting a round of applause from the audience before the attendees transition into informal side conversations.
## Notable quotes > [20:40](https://www.youtube.com/watch?v=AKMuA_TVz3A&t=1240s) And all of deep learning hinges on top of the SGD miracle that we can actually train these computers with SGD. — Ilya Sutskever
> [05:51](https://www.youtube.com/watch?v=AKMuA_TVz3A&t=351s) The VC dimension was invented to handle precision parameters with infinite precision. — Ilya Sutskever
> [02:01](https://www.youtube.com/watch?v=AKMuA_TVz3A&t=121s) So three lines of math can prove all of supervised learning. — Ilya Sutskever
> [49:46](https://www.youtube.com/watch?v=AKMuA_TVz3A&t=2986s) If the test set is infinite and you care about compressing the test set, then you don't care about the size of your compressor, so long as this test set size is much larger. — Ilya Sutskever
## Mentioned Ilya Sutskever, OpenAI, Yejin Choi, Umesh Vazirani, Simons Institute for the Theory of Computing, Transformer, Recurrent Neural Networks, Image GPT, BERT, CIFAR-10, ImageNet, Universal Transformer, GPT-4, Neural Turing Machines, gzip
## Video description Ilya Sutskever (OpenAI) https://simons.berkeley.edu/talks/ilya-sutskever-openai-2023-08-14 Large Language Models and Transformers
[Source](https://www.youtube.com/watch?v=AKMuA_TVz3A)