Blog

A Model That Imitates Everything It Read

A language model trained only on next-token prediction learns to continue text the way text on the internet tends to continue. Ask it a question and it may answer, or it may produce three more questions, because a list of questions is a perfectly plausible continuation. It has no built-in idea that one continuation is helpful and another is not. It only knows which one is likely.

Supervised fine-tuning on written demonstrations helps, but it has a ceiling. Someone has to write every good answer by hand, and the model learns to copy the style of those answers rather than to understand what made them good. There is also a practical asymmetry: most people cannot write an excellent summary of a legal document on demand, but almost anyone can read two summaries and say which one is better. Reinforcement learning from human feedback (RLHF) is built on that asymmetry.

Comparisons Instead of Scores

The idea predates chatbots. In 2017, Paul Christiano, Jan Leike and colleagues at OpenAI and DeepMind published «Deep Reinforcement Learning from Human Preferences» at NeurIPS. Their agents played Atari games and controlled simulated robots, and instead of receiving a reward from the environment, they received human judgments about pairs of short video clips: which of these two looks more like what I want?

It needed very little human input. The paper reports that the method worked while humans gave feedback on less than 1% of the agent’s interactions with the environment, and that complex new behaviors could be trained with about an hour of human time. The best known example was a simulated robot learning to do a backflip, a behavior that is hard to write as a reward function but easy to recognize. According to OpenAI, it took around 900 bits of feedback from the evaluator.

Asking for comparisons rather than numeric scores is a deliberate choice. People are inconsistent when asked to rate something from 1 to 10, and two raters rarely share the same scale. They are much more consistent when asked to pick one of two.

The Reward Model

Comparisons cannot be optimized directly, so the first step is to turn them into a function. A reward model, usually a copy of the language model with its output layer replaced by a single number, is trained to give the preferred response a higher score than the rejected one.

The training objective comes from the Bradley-Terry model, proposed by Ralph Bradley and Milton Terry in 1952 for ranking items from paired comparisons. It says that the probability a person prefers response A over response B is the sigmoid of the difference between their scores. Training the reward model means maximizing the log-likelihood of the human choices under that assumption. Only the difference between two scores matters, so the absolute value of a reward means nothing on its own.

Once trained, the reward model can score any new response in milliseconds. That is the point: a human cannot sit in the loop for millions of training steps, but a model of the human can.

PPO and the KL Penalty

The second step treats the language model as a policy. A prompt is the state, the generated response is the action, and the reward model provides the score at the end. The usual algorithm is Proximal Policy Optimization (PPO), introduced by John Schulman and colleagues in 2017, which limits how far each update can move the policy.

Left alone, this optimization finds strange outputs. The reward model was trained on responses from the original model, and once the policy drifts into text that looks nothing like that distribution, the reward model’s scores stop meaning anything. To prevent this, the reward is reduced by a penalty proportional to the KL divergence between the current policy and the original supervised model. The model is pushed toward higher reward but kept close to the language it already knows how to produce. The strength of that penalty, usually called beta, is one of the most important settings in the whole pipeline.

In practice this means running four models at once: the policy being trained, the frozen reference model, the reward model, and a value network that PPO uses to estimate expected reward. That cost, and PPO’s sensitivity to hyperparameters, explains much of what came later.

Case: InstructGPT

Two papers made RLHF work on language. In 2020, Nisan Stiennon and colleagues applied it to summarizing Reddit posts. OpenAI reported that a 1.3 billion parameter model trained with human feedback outperformed a 12 billion parameter model trained only with supervised learning, and labelers preferred the feedback models’ summaries to the human-written ones in the dataset.

In 2022, Long Ouyang and colleagues published InstructGPT (NeurIPS 2022), the method behind the first version of ChatGPT. The pipeline had three stages: supervised fine-tuning of GPT-3 on demonstrations written by labelers, a reward model trained on rankings of model outputs, and PPO against that reward model. The headline result was that people preferred outputs from the 1.3 billion parameter InstructGPT model to those of the 175 billion parameter GPT-3, a model with roughly 100 times more parameters. The paper also reported better truthfulness and less toxic output, with small regressions on some public NLP benchmarks.

That comparison is the one people remember. A large part of what users experienced as quality was not coming from more parameters. It came from rankings that labelers wrote for roughly 33,000 prompts.

Reward Hacking

A reward model is an approximation of what people want, and optimizing hard against an approximation eventually exploits its errors. Leo Gao, John Schulman and Jacob Hilton measured this in «Scaling Laws for Reward Model Overoptimization» (ICML 2023). They used a large fixed reward model as a stand-in for humans, trained smaller proxy reward models on its labels, and optimized policies against the proxies. The proxy score kept rising, while the score from the «gold» model rose, peaked, and then fell. Larger reward models delayed the drop but did not remove it.

The errors that get exploited are often mundane. Stiennon’s team noticed that their labelers favored longer summaries, and the models converged to the longest length allowed. Prasann Singhal and colleagues later found that, in several standard setups, a reward based purely on response length reproduced most of the improvement RLHF gave over supervised fine-tuning. Mrinank Sharma and colleagues at Anthropic (ICLR 2024) found that both humans and preference models sometimes preferred convincingly written answers that agreed with the user over correct ones, which gives the training process a direct incentive toward sycophancy.

Direct Preference Optimization

In 2023, Rafael Rafailov, Archit Sharma, Eric Mitchell, Christopher Manning, Stefano Ermon and Chelsea Finn published «Direct Preference Optimization: Your Language Model is Secretly a Reward Model» at NeurIPS. Their observation was mathematical. The KL-constrained objective that RLHF optimizes has a known optimal solution: the best policy is the reference model’s distribution reweighted by the exponential of the reward divided by beta.

That relationship can be inverted. Any policy implies a reward, equal to beta times the log ratio between the policy’s probability of a response and the reference model’s probability, plus a term that depends only on the prompt. Substitute that implied reward into the Bradley-Terry loss and the prompt-only term cancels, because Bradley-Terry only looks at differences. What remains is a loss written entirely in terms of the policy and the reference model: increase the log-probability ratio of the preferred response relative to the rejected one, passed through a sigmoid.

DPO needs no separate reward model, no sampling during training, and no PPO. It looks like ordinary supervised training on pairs. Many open models adopted it quickly, and variants followed, including IPO (Azar and colleagues) and KTO (Ethayarajh and colleagues), which works from single responses labeled good or bad instead of pairs. DPO does not escape the underlying problem, though. It still learns from the same preference data, with the same biases toward length and agreement.

Rewards From Rules and From Other Models

Human comparisons are expensive, so later work replaced some of them. Anthropic’s Constitutional AI (Bai and colleagues, 2022) had a model critique and revise its own answers against a written list of principles, then used AI-generated preference labels for the reinforcement learning stage, an approach often called RLAIF.

For tasks with checkable answers, the reward model can be dropped entirely. DeepSeekMath (Shao and colleagues, 2024) introduced Group Relative Policy Optimization (GRPO), which removes PPO’s value network: it samples several answers to the same question and uses each answer’s reward relative to the group’s average as its advantage. DeepSeek-R1 (2025) combined GRPO with rule-based rewards, checking whether a math answer is correct or whether code passes tests, rather than relying on a learned reward model. A rule is harder to fool than a neural network, but only a narrow set of tasks have rules.

Closing Note

The name suggests that RLHF teaches a model human values. What it teaches is narrower: the model learns to produce the response that a particular group of raters, reading quickly, would pick from a pair. Most of the time that is close to the response a careful person would want. The cases where it is not (longer is not better, agreeing is not the same as being right) are where the method’s real assumptions show up. Every preference dataset carries a description of its raters, and the model trained on it inherits that description along with the good answers.

By: Max Johnson B.

Paying for Every Parameter

In a standard dense neural network, every parameter takes part in every prediction. If a language model has 70 billion weights, all 70 billion are multiplied against each token it reads, whether the token is a word in a legal contract, a line of Python or a comma. Capacity and cost are tied together: a model that knows more also costs more to run, in a nearly fixed proportion.

A mixture of experts (MoE) model breaks that link. Instead of one large feed-forward block, a layer holds many smaller blocks, the experts, plus a small network called a router that decides which of them should process the current input. Only the chosen experts run. The model can store a very large number of parameters while spending, per token, the compute of a much smaller one. Many of the largest open-weight language models released since 2024 are built this way, and the reasons it works (and the ways it misbehaves) say a lot about how these systems are trained.

Local Experts in 1991

The idea is older than deep learning. In 1991, Robert Jacobs, Michael Jordan, Steven Nowlan and Geoffrey Hinton published «Adaptive Mixtures of Local Experts» in Neural Computation. Their system trained several small networks together with a gating network that assigned each input to the expert most likely to handle it well. Because the experts competed for training cases, each one drifted toward a different region of the input space.

They tested it on vowel discrimination, and the paper reports that the procedure split the task into subtasks, each simple enough for a very small expert network to solve. A companion paper by Nowlan and Hinton found that the modular version generalized better than a single backpropagation network across many variations of the problem. The motivation then was specialization and cleaner learning, not saving compute. That second motivation took another 26 years to arrive.

Noisy Top-k Gating

In 2017, Noam Shazeer and colleagues at Google published «Outrageously Large Neural Networks: The Sparsely-Gated Mixture-of-Experts Layer» at ICLR. They placed a layer with up to thousands of feed-forward experts between stacked LSTM layers and let a trainable gate pick a sparse set of them for each example. The largest configuration had 137 billion parameters, an enormous number for 2017, and the authors reported more than a thousandfold increase in model capacity with only minor losses in computational efficiency on GPU clusters.

The gate works like this. It computes a score for every expert, keeps the top k scores, sets the rest to minus infinity and applies a softmax, so only k experts receive nonzero weight. The layer’s output is the weighted sum of those k experts’ outputs. Shazeer’s team added tunable Gaussian noise to the scores before taking the top k. The noise gives experts that are slightly behind a chance to be selected and receive gradient, which matters because an expert that is never chosen never learns.

The Load Balancing Problem

That last point is the central difficulty of the whole approach. Routing is learned, and learning is greedy. Early in training, a few experts happen to perform slightly better, so the router sends them more tokens, so they improve faster, so the router sends them even more. Left alone, the router collapses onto a handful of experts and the rest of the parameters sit idle. The model then has the memory cost of a huge network and the quality of a small one.

The usual fix is an auxiliary loss added to the training objective that penalizes uneven routing. Shazeer’s 2017 paper used a term based on how much total gate weight each expert received across a batch. Later work simplified it to a product of two quantities per expert: the fraction of tokens actually sent to it and the average probability the router assigned to it. The loss is smallest when both are uniform. The coefficient has to be small (values around 0.01 are common), because a strong balancing term forces the router to spread tokens evenly even when an uneven split would produce better predictions.

Switch Transformer and One Expert per Token

Google’s next step, the Switch Transformer by William Fedus, Barret Zoph and Noam Shazeer (2021, later in JMLR), took sparsity further. Earlier designs such as GShard routed each token to two experts. Switch sent each token to exactly one, reasoning that this cuts both computation and the communication between devices. The authors reported large gains in pre-training speed over dense T5 models at the same compute, including about a fourfold speedup over a tuned T5-XXL, and trained models up to roughly 1.6 trillion parameters.

Two practical details from that paper show up in almost every MoE system since. The first is the capacity factor. Hardware wants fixed tensor shapes, so each expert gets a buffer sized to the average number of tokens it would receive under perfect balance, multiplied by a factor such as 1.25. Tokens that arrive after an expert’s buffer is full are dropped: they skip the expert and pass through the layer’s residual connection unchanged. The second is selective precision. Most of the model trained in bfloat16, but the router ran in float32, because the exponentials in its softmax were a frequent source of training instability. A follow-up, ST-MoE (Zoph and colleagues, 2022), added a «router z-loss» that keeps the router’s raw scores small for the same reason.

Case: Mixtral 8x7B

The model that made MoE familiar outside large labs was Mixtral 8x7B, released by Mistral AI in December 2023 under the Apache 2.0 license. Each of its 32 layers has eight feed-forward experts, and the router sends each token to two of them. According to Mistral, the model has 46.7 billion parameters in total but uses 12.9 billion per token. The name can mislead: it is not eight 7B models glued together, since the attention layers and embeddings are shared and only the feed-forward blocks are duplicated.

Mistral reported that Mixtral matched or outperformed Llama 2 70B and GPT-3.5 on most of the benchmarks they tested, with roughly a fifth of Llama 2 70B’s active parameters. The paper’s routing analysis is the more interesting part. The authors checked whether experts specialized by subject, using text from sources like arXiv papers, biology abstracts and philosophy, and found no clear pattern by topic. What they did find was that routing followed structure: consecutive tokens often went to the same expert, and some tokens in code (such as indentation) were assigned consistently. The experts divided the work along lines that made sense to the optimizer, not to a librarian.

Finer Experts and a Bias Instead of a Loss

DeepSeek’s line of models changed the recipe in two ways. The DeepSeekMoE paper (Dai and colleagues, ACL 2024) argued that eight or sixteen large experts are too coarse, because each one ends up covering a mix of unrelated knowledge. Its answer was fine-grained segmentation: split each expert into several smaller ones and activate more of them, so the compute per token stays the same while the number of possible combinations grows. It also isolated a few shared experts that every token passes through, so common knowledge does not have to be copied into every routed expert.

DeepSeek-V3, described in a technical report released in December 2024, has 671 billion parameters with 37 billion active per token, trained on 14.8 trillion tokens using 2.788 million H800 GPU hours. Its most cited routing change is what the authors call auxiliary-loss-free load balancing. Each expert gets a bias term that is added to its score only when deciding which experts to select; the weights used to combine the outputs still come from the original scores. After each step, the bias of an overloaded expert is lowered and the bias of an underused one is raised, by a fixed small amount. Balance is enforced by a dial outside the gradient, so the language modeling loss is not pulled in two directions. A tiny sequence-level balance loss is kept only as a safety net against extreme cases.

Memory and Communication

Sparse computation does not mean sparse memory. All 46.7 billion of Mixtral’s parameters must be loaded to serve it, because any token might need any expert. On a single machine, an MoE model needs the memory of its total size and gives the speed of its active size. That trade is favorable for providers serving many users at once and less favorable for someone running a model on one consumer GPU.

At larger scale, the experts live on different accelerators, an arrangement called expert parallelism. Every MoE layer then requires two all-to-all exchanges: tokens are sent to whichever devices hold their chosen experts and the results are sent back. GShard (Lepikhin and colleagues, ICLR 2021) was largely a paper about making this practical, and it trained a 600-billion-parameter multilingual translation model, covering 100 languages into English, on 2,048 TPU v3 cores in four days. Much of the engineering in recent MoE reports is about hiding this communication behind computation, because on real clusters the network, not the arithmetic, is often the bottleneck.

A Final Observation

The word «expert» invites a picture of a panel of specialists: one for medicine, one for law, one for code. The evidence points elsewhere. The 1991 vowel experiments, Mixtral’s routing analysis and DeepSeek’s push for finer granularity all show experts organizing around whatever division of labor lowers the loss and keeps the load even, which is often syntactic, positional or simply hard to name. A mixture of experts is better understood as a way of renting capacity: the model keeps a very large set of parameters and pays for a small slice of them at a time. The specialists are a metaphor that the training process never agreed to.

By: Max Johnson B.

Learning to Undo Damage

Ruining an image is easy. Add a little Gaussian noise to every pixel, then a little more, and after enough rounds the picture of a cat is indistinguishable from television static. Nobody needs a neural network for that part. The interesting question is whether a network can learn to run the process backwards, one small step at a time, until static turns into a cat that never existed.

That is the whole idea behind diffusion models. It was first written down by Jascha Sohl-Dickstein and colleagues at ICML 2015, in a paper that borrowed its framing from nonequilibrium thermodynamics. The results were modest and the paper stayed fairly quiet for five years. Then in 2020 Jonathan Ho, Ajay Jain and Pieter Abbeel published «Denoising Diffusion Probabilistic Models» (DDPM) at NeurIPS, reported a state-of-the-art FID of 3.17 on unconditional CIFAR-10, and the field changed direction. Within two years the systems people used to turn text into pictures were almost all diffusion models.

The Forward Process

A diffusion model has two halves, and only one of them is learned. The forward process is fixed. Starting from a real image, it adds Gaussian noise over T steps according to a schedule. In the DDPM paper T was 1,000 and the amount of noise added per step grew linearly from 0.0001 to 0.02. By the last step almost nothing of the original image survives, and the result is very close to pure Gaussian noise.

One property makes training cheap. Because each step adds Gaussian noise, the noisy image at any step t can be written directly in terms of the clean image: a scaled copy of the original plus a scaled sample of noise. You never have to simulate the 999 intermediate steps. To make a training example you pick a random t, draw one noise sample, and mix.

Predicting the Noise

The reverse process is where the network lives. In principle it should model the distribution of a slightly cleaner image given a noisier one. Ho and his coauthors showed that, after working through the variational bound, this reduces to something almost embarrassingly simple: show the network a noisy image and the step number t, and ask it to predict the exact noise that was added. The loss is the mean squared error between the predicted noise and the real one.

They also found that dropping the weighting terms from the full bound gave better-looking samples, even though it gave up some likelihood. The network itself was a U-Net, the encoder and decoder architecture with skip connections that had become standard for segmentation, with the step number fed in as an embedding.

Generation then means starting from pure noise and applying the network 1,000 times. At each step it estimates the noise, removes a portion of it, and adds back a smaller amount of fresh randomness. The output of one step is the input of the next.

Score Matching

A separate line of research reached the same place from another direction. The score of a probability distribution is the gradient of its log density with respect to the data. It is a vector field that points, from any location, toward regions where data is more likely. If you know the score everywhere, you can sample by following it with a bit of added noise, a procedure called Langevin dynamics.

Aapo Hyvärinen introduced score matching in 2005 as a way to estimate this gradient without knowing the normalizing constant of the density. Pascal Vincent showed in 2011 that a denoising autoencoder trained on noisy data implicitly learns the score. Yang Song and Stefano Ermon built a generative model on this at NeurIPS 2019. Their key observation was that scores are badly estimated in empty regions far from the data, so they trained one network on many noise levels at once and sampled by annealing from large noise to small.

Predicting the added noise and estimating the score turn out to be the same quantity up to a scaling factor. Song, Sohl-Dickstein, Kingma, Kumar, Ermon and Poole made this explicit at ICLR 2021 by describing both methods as discretizations of a stochastic differential equation that slowly turns data into noise. Reversing that equation requires only the score. The same framework gave a deterministic version, an ordinary differential equation with the same marginal distributions, which allowed exact likelihood computation. The paper reported an FID of 2.20 on CIFAR-10 and the first 1024 by 1024 samples from a score-based model.

A Thousand Steps Is Too Many

The obvious weakness was speed. A GAN produces an image in one forward pass. A DDPM needed a thousand. Much of the work since 2020 has gone into cutting that number without retraining from scratch.

DDIM (Jiaming Song, Chenlin Meng and Stefano Ermon, ICLR 2021) kept the DDPM training objective but defined a non-Markovian reverse process that can skip steps. The authors reported samples of similar quality 10 to 50 times faster in wall-clock time. Viewing sampling as solving an ODE also opened the door to better numerical solvers, and dedicated samplers now get usable images in a few dozen steps or fewer. Distillation goes further: a student network is trained to match two or more steps of a teacher in one. Consistency models (Yang Song, Prafulla Dhariwal, Mark Chen and Ilya Sutskever, ICML 2023) train a network to map any point on a sampling trajectory directly to its endpoint, which makes single-step generation possible.

Guidance

An unconditional model produces random samples from whatever it was trained on. To ask for a specific class or a text prompt, the model needs conditioning, and conditioning alone tends to give images that only loosely follow the request.

Prafulla Dhariwal and Alex Nichol introduced classifier guidance in «Diffusion Models Beat GANs on Image Synthesis» (NeurIPS 2021). A separate classifier, trained on noisy images, supplies a gradient that pushes each denoising step toward the desired class. With it they reached an FID of 2.97 on ImageNet at 128 by 128 and matched BigGAN-deep with as few as 25 forward passes per sample.

Training a classifier on noisy images is awkward, though. Jonathan Ho and Tim Salimans proposed classifier-free guidance at a NeurIPS 2021 workshop. One network is trained with the condition dropped a small fraction of the time, so it learns both conditional and unconditional predictions. At sampling time the two predictions are combined, and the difference between them is amplified by a guidance weight. Raising the weight makes images follow the prompt more closely at the cost of diversity. Most text-to-image systems use this trick, and the guidance scale is one of the few knobs ordinary users touch.

Diffusion in a Latent Space

Running a U-Net a few dozen times over a full-resolution image is expensive, and most of that computation goes into pixel detail the eye barely notices. Robin Rombach, Andreas Blattmann, Dominik Lorenz, Patrick Esser and Björn Ommer addressed this in «High-Resolution Image Synthesis with Latent Diffusion Models» (CVPR 2022). They first train an autoencoder that compresses images into a smaller latent grid while keeping perceptual quality, then run the diffusion process in that latent space. A decoder turns the final latent back into pixels.

The paper also added cross-attention layers to the U-Net, so conditioning inputs such as text embeddings or bounding boxes can steer the denoiser at every resolution. This design became Stable Diffusion. Its first versions diffused in a 64 by 64 latent to produce 512 by 512 images and used a frozen CLIP text encoder for the prompt. Because it was released with open weights and ran on consumer graphics cards, it was the version of diffusion most researchers and hobbyists first worked with. Later systems replaced the U-Net with Transformers operating on latent patches, following the Diffusion Transformer of William Peebles and Saining Xie (ICCV 2023), but the latent space idea stayed.

Case: Training Images That Come Back

A model that learns the score of its training distribution should, in theory, be able to reproduce training images. Nicholas Carlini and eight coauthors tested this at USENIX Security 2023 in «Extracting Training Data from Diffusion Models.» They generated large numbers of images from Stable Diffusion and Google’s Imagen using captions from the training data and searched for outputs that were near copies of training images. They extracted over a thousand training examples across the models they studied, including photographs of identifiable people and trademarked logos.

The memorized images were mostly ones that appeared many times in the training set. Deduplicating data reduces the problem but does not remove it. The authors also reported that the diffusion models they tested leaked more training data than the GANs they compared against. For a technique so often described as generating something new, that is an uncomfortable result.

Closing Thought

The most unusual thing about diffusion models is how the learned part and the procedure are separated. The network is only ever trained to do one modest thing: look at a noisy input and estimate the noise. Everything else, the number of steps, the solver, the guidance weight, the choice between a random or a deterministic path, is decided after training. DDIM, better ODE solvers and classifier-free guidance all improved results by changing how a network is used rather than what it learned. Most of deep learning puts its effort into the training objective. With diffusion, a large share of the progress came from the sampler instead.

By: Max Johnson B.

A Thousand Labels Is a Small Vocabulary

For most of the history of computer vision, a classifier knew exactly the categories it was trained on and nothing else. A model trained on ImageNet’s 1,000 classes could tell a Siberian husky from an Alaskan malamute, but if you asked it to find «a dog wearing a raincoat» it had no way to even represent the request. Adding a new category meant collecting new labeled images and retraining.

The internet, meanwhile, is full of images that already come with text: captions, alt attributes, titles, surrounding paragraphs. That text is noisy and inconsistent, but it describes far more than 1,000 concepts. Contrastive multimodal models are built on a simple bet: if a network learns which caption goes with which image across hundreds of millions of examples, it will learn a visual vocabulary as wide as the language people use to describe pictures.

Two Encoders and a Matching Game

CLIP (Contrastive Language-Image Pre-training) was published by Alec Radford, Jong Wook Kim and colleagues at OpenAI in 2021 and presented at ICML that year. The architecture has two separate parts. An image encoder (a ResNet or a Vision Transformer) turns a picture into a vector. A text encoder (a Transformer) turns a caption into a vector of the same size. Both vectors are normalized, so comparing them is just a cosine similarity.

Training uses a batch of N image-caption pairs. The model computes the similarity between every image and every caption, which gives an N by N matrix. The N correct pairs sit on the diagonal; everything else is a mismatch. The loss is a cross-entropy in both directions: each image has to pick its own caption out of the N candidates, and each caption has to pick its own image. A learned temperature parameter scales the similarities before the softmax.

The batch is where the negatives come from, so batch size matters a lot. CLIP used batches of 32,768 pairs, which means every caption competes against more than 32,000 wrong images at each step. The training set, called WebImageText, held 400 million pairs collected from public sources on the internet.

Classification Written as a Sentence

The payoff is zero-shot classification. To classify an image into a set of categories CLIP has never been trained on as labels, you write each category as a sentence («a photo of a cat», «a photo of a truck»), encode all the sentences, and pick the one closest to the image embedding. The class list is just text, so you can change it at inference time.

The paper reported that its best model, a ViT-L/14 at 336 pixel resolution, reached about 76 percent top-1 accuracy on ImageNet this way, roughly the same as the original ResNet-50 trained on ImageNet’s 1.28 million labeled images. CLIP saw none of those labels. The wording of the prompt turned out to matter: «a photo of a {label}» worked better than the bare class name, and averaging over dozens of templates helped further. People started calling this prompt engineering for vision.

A second result got less attention at the time but may matter more. On variants of ImageNet with sketches, renditions and adversarially filtered photos, a standard ImageNet model loses much of its accuracy. Zero-shot CLIP lost far less. The authors argued that a supervised model learns shortcuts specific to one dataset, while a model trained on a broad distribution of web images and text has fewer of them to exploit.

Scale Over Cleanliness

Within weeks of CLIP, Google described ALIGN (Chao Jia and colleagues, also ICML 2021), which used the same dual-encoder idea with an EfficientNet image encoder and a BERT text encoder. Its dataset was 1.8 billion image and alt-text pairs with only minimal filtering. The message of ALIGN was that you can skip most of the expensive cleaning if you have enough data, because the contrastive objective averages out a lot of the noise.

Neither OpenAI’s nor Google’s dataset was released. The LAION project filled that gap with LAION-5B (Schuhmann et al., NeurIPS 2022 Datasets and Benchmarks track), 5.85 billion image-text pairs filtered by CLIP similarity itself. The OpenCLIP project trained open models on it, which made it possible to study scaling laws for CLIP-style training in public. Later work such as DataComp (Gadre et al., 2023) turned the question around: hold the model and training recipe fixed, and compete only on how you filter the data. Filtering choices alone moved results by large margins.

Replacing the Softmax With a Sigmoid

The softmax in CLIP’s loss has a practical cost. Every image’s probability depends on every caption in the batch, so devices have to share all embeddings to compute it, and the memory grows with the square of the batch. In 2023 Xiaohua Zhai, Basil Mustafa, Alexander Kolesnikov and Lucas Beyer at Google proposed SigLIP, which treats every image-caption pair as an independent binary question: do these two belong together, yes or no? Each cell of the similarity matrix gets its own sigmoid loss.

That change removes the global normalization. SigLIP trained well with smaller batches than CLIP needed, and it scaled to larger ones too. In one setup that kept a pre-trained image encoder frozen and trained only the text side, the authors reached 84.5 percent zero-shot ImageNet accuracy using four TPUv4 chips for two days. SigLIP encoders have since become a common choice as the vision component of open multimodal language models.

An Embedding Space Other Systems Reuse

The shared embedding space ended up being more useful than zero-shot classification. Image search is the direct application: encode a text query, find the nearest image vectors, no tags required. Content moderation and dataset filtering use the same trick, and LAION itself was built by keeping only pairs whose CLIP similarity passed a threshold.

Generative models borrowed the text side. Stable Diffusion’s first versions conditioned image generation on the output of CLIP’s ViT-L/14 text encoder, and OpenAI’s DALL-E 2 generated images from CLIP image embeddings. Going the other way, LLaVA (Liu et al., 2023) connected a frozen CLIP image encoder to a language model through a small projection layer and trained the result to answer questions about images. Meta’s ImageBind (Girdhar et al., CVPR 2023) pushed the idea further, aligning audio, depth, thermal and motion data to the same space by pairing each one with images, so that modalities never seen together during training could still be compared.

Case: An Apple Labeled «iPod»

In March 2021, OpenAI researchers studying CLIP’s internal units found what they called multimodal neurons: single units that responded to a concept whether it appeared as a photo, a drawing or written text. One responded to spiders, to the word «spider» and to Spider-Man. The same property produced a strange weakness. When they stuck a handwritten paper note saying «iPod» on a Granny Smith apple, CLIP classified the photo as an iPod. They called these typographic attacks. Unlike most adversarial examples, they need no gradients and no computer, only a pen.

The failure follows from the training signal. Web captions often repeat the text that appears inside an image, so reading the text is a reliable shortcut for matching captions. CLIP learned to read because reading helped, and it has no separate notion of «the object» versus «words written near the object.»

What a Bag of Words Cannot Tell Apart

Other limits show up in careful benchmarks. Yuksekgonul and colleagues (ICLR 2023) tested whether vision-language models understand word order and relations, for example whether they can distinguish «the horse is eating the grass» from «the grass is eating the horse.» CLIP-style models often could not. Their explanation was that the contrastive task rarely requires order: in a batch of random web pairs, getting the nouns right is almost always enough to find the matching caption, so the model has little reason to learn more. CLIP also struggled with counting objects and, in the original paper, scored poorly on handwritten digits (MNIST) despite its broad training.

Bias came along with the web data. An audit by Agarwal and colleagues in 2021, using images from the FairFace dataset with extra labels added, found that photos of Black people were classified into non-human categories such as «gorilla» at a rate of about 14 percent, against under 8 percent for every other group. Changing the label set changed the outcome, which is the other side of zero-shot flexibility: whoever writes the class list also shapes the errors.

Closing Thought

CLIP’s objective never asks the model to understand an image. It asks only that the right caption score higher than the other captions in the batch. Everything the model learns, from recognizing dog breeds to reading text on an apple to ignoring word order, is whatever happened to be useful for winning that comparison against random internet captions. That makes the choice of negatives, and of data, the real specification of what these models know. A harder batch teaches a finer distinction; a lazier one lets the shortcut stand.

By: Max Johnson B.

Optimization With Only a Score

Some optimization problems give you almost nothing to work with. You can hand the problem a vector of numbers and get back a single score, and that is all. There is no gradient, no formula you can differentiate, sometimes not even a guarantee that the same input returns the same score twice. Tuning the gains of a controller in a physics simulator looks like this. So does fitting the parameters of a chemical model, or choosing the learning rate and dropout of a neural network.

The Covariance Matrix Adaptation Evolution Strategy, almost always shortened to CMA-ES, is one of the most respected tools for this kind of problem when the variables are continuous. Its standard form was published by Nikolaus Hansen and Andreas Ostermeier in 2001, in the journal Evolutionary Computation, under the title «Completely Derandomized Self-Adaptation in Evolution Strategies.» Twenty-five years later it is still a standard first choice, and a standard baseline, for hard black-box problems with a few dozen to a few hundred variables.

Sampling From a Gaussian

CMA-ES does not keep a population of individuals the way a genetic algorithm does. It keeps a probability distribution: a multivariate normal with a mean vector m, a global step size σ, and a covariance matrix C. Each generation it draws λ candidate solutions from that distribution, evaluates them, and sorts them from best to worst.

The new mean is a weighted average of the best μ candidates, usually the top half, with better ones receiving larger weights. So the center of the search moves toward the region where good solutions were just found. That part alone is a fairly ordinary evolution strategy. What makes CMA-ES different is what it does next with the covariance matrix and the step size.

The default population size is small. Hansen’s tutorial on the method recommends λ = 4 + ⌊3 ln n⌋, where n is the number of variables. For a 100-dimensional problem that gives 17 samples per generation. The suggested defaults for the other internal parameters are also derived from n, which is why practitioners rarely tune them.

Learning the Shape of the Search

Picture a long, narrow valley that runs diagonally across the search space. A plain random search with circular steps wastes most of its samples climbing the walls, because almost every direction points uphill except the one along the valley floor. To make progress it would need tiny steps, and tiny steps make the walk along the valley painfully slow.

The covariance matrix fixes this. After each generation, CMA-ES looks at the steps that led to the selected candidates and nudges C so that those directions become more likely in the future. Over many generations the sampling distribution stretches into an ellipsoid aligned with the valley. The algorithm has, in effect, learned which combinations of variables move together.

This is called the rank-μ update, because it uses information from all μ selected steps at once. On a convex quadratic function, the learned covariance tends toward a matrix proportional to the inverse of the Hessian. That is the same matrix a Newton or quasi-Newton method tries to approximate with derivatives. CMA-ES gets there using nothing but the ordering of sampled points.

Evolution Paths

The second idea in the 2001 paper is called cumulation. Instead of looking only at the current generation, CMA-ES keeps a running, exponentially fading sum of the recent movements of the mean. Hansen and Ostermeier call this the evolution path.

The path carries information a single generation cannot. If the mean keeps moving in roughly the same direction, the steps add up and the path grows long. If it zigzags back and forth, consecutive steps cancel and the path stays short. The rank-one update adds the outer product of this path to the covariance matrix, which strengthens directions of consistent progress.

The two updates complement each other. The rank-μ update is efficient with large populations, while the rank-one update with cumulation works well with the small default population. The modern algorithm uses both.

Step-Size Control

Shape is only half of the problem. The algorithm also has to decide how far to step overall, and a covariance matrix learned from past steps cannot answer that by itself, because it adapts too slowly.

CMA-ES handles this with a second evolution path, built in a coordinate system where the current covariance has been factored out. The rule then compares the length of this path with the length expected under pure random selection. If the path is longer than expected, successive steps are pointing the same way and the step size is too small, so σ grows. If it is shorter, steps are cancelling each other and σ shrinks. The paper calls this cumulative step-size adaptation.

The rule is short. It lets the algorithm take large steps far from the optimum and converge quickly once it gets close, without a manually designed schedule like the cooling schedule in simulated annealing.

Invariance

Hansen’s tutorial on the method names invariance as one of the governing principles of its design. CMA-ES only uses the ranking of candidates, never their raw scores, so its behavior does not change if the objective function is replaced by any strictly increasing transformation of itself. Squaring a positive objective or taking its logarithm makes no difference.

It is also invariant, given a matching starting point and covariance, to rotations, translations and general linear transformations of the search space. A badly scaled, rotated problem is, for CMA-ES, the same problem as a well-scaled one once the covariance has adapted. This is why the 2001 paper reported speed-ups of several orders of magnitude on badly scaled, non-separable functions, and a factor of three to ten on moderately mis-scaled ones.

There is a theoretical account of why this works. The Information-Geometric Optimization framework, published by Yann Ollivier and coauthors in the Journal of Machine Learning Research in 2017, shows that the rank-μ update of CMA-ES can be read as a natural gradient step on the parameters of the search distribution. The algorithm came first and the theory came later, which is a common order of events in this field.

Restarts and Larger Populations

With its default settings, CMA-ES behaves like a fast local search. On a function with many local optima it will often converge cleanly to the wrong one. The standard fix is to restart.

Anne Auger and Nikolaus Hansen proposed IPOP-CMA-ES at the 2005 IEEE Congress on Evolutionary Computation. Each time the run stalls, it restarts with the population size doubled. Larger populations smooth over small bumps in the landscape and make the search more global. On the 25 test functions of the CEC 2005 special session on real-parameter optimization, IPOP-CMA-ES ranked first overall. A later variant, BIPOP-CMA-ES, alternates between large and small populations, and the two were among the best performers in the Black-Box Optimization Benchmarking workshops of 2009 and 2010.

Case: An 867-Parameter Driver

One well-known use in machine learning is the 2018 World Models paper by David Ha and Jürgen Schmidhuber. They trained a variational autoencoder to compress game frames and a recurrent network to predict what comes next. The part that actually chose actions was a small linear controller with 867 parameters, and they did not train it with gradients. They evolved it with CMA-ES, using a population of 64, on the CarRacing task. The agent reached an average score of 906 ± 21, which the authors reported as the first result to solve that environment.

The choice made sense. A reinforcement learning reward is noisy and delayed, and 867 parameters is well within the range where CMA-ES is comfortable. Every candidate can also be evaluated on a separate CPU core, so the method parallelizes almost perfectly.

Hyperparameter tuning is another natural fit. In 2016 Ilya Loshchilov and Frank Hutter compared CMA-ES with Bayesian optimization methods for tuning a convolutional network on MNIST, running evaluations on 30 GPUs in parallel, and argued that CMA-ES is a competitive option when many evaluations can run at once. Today the method is easy to try: the pycma library is maintained by Hansen, and the Optuna framework includes a CMA-ES sampler.

The Quadratic Cost

The weakness is the covariance matrix itself. For n variables it has about n²/2 free entries, and the standard algorithm needs memory and time per sample that grow quadratically with n. It also needs on the order of n² evaluations to learn a full matrix. With a few hundred variables this is fine. With tens of thousands it becomes impractical, which is why nobody trains the weights of a large neural network with standard CMA-ES.

Several variants trade expressiveness for scale. In 2008 Raymond Ros and Nikolaus Hansen proposed sep-CMA-ES, which restricts C to a diagonal matrix and brings the cost down to linear. It loses the ability to learn correlations between variables, but in their experiments it needed fewer evaluations than full CMA-ES on several problems above a hundred dimensions, including the non-separable Rosenbrock function. Limited-memory versions such as LM-CMA, inspired by L-BFGS, keep a few vectors instead of a full matrix.

Closing Thought

What I find most interesting about CMA-ES is how little it assumes. It never reads the value of the objective, only the order of the candidates. And yet, from that ordering alone, it reconstructs something close to the curvature of the problem, the same information a second-order method gets from derivatives. A lot of «nature-inspired» optimizers are described by their metaphor. CMA-ES is better described by what it estimates, and that is probably why it has outlasted so many of them.

By: Max Johnson B.

Searching for Programs Instead of Parameters

Most optimization algorithms search for numbers. A genetic algorithm evolves a string of bits or a vector of real values, and a neural network adjusts millions of weights inside an architecture someone else designed. In both cases the shape of the solution is fixed ahead of time. The algorithm only fills in the blanks.

Genetic programming asks for something more ambitious. The thing being evolved is a program: a formula, a decision procedure, a circuit, a set of instructions. The size and structure of the solution are not decided in advance. They emerge from the search.

The idea has an early version in Nichael Cramer’s 1985 paper at the first International Conference on Genetic Algorithms, which represented simple sequential programs in a form that could be mutated and recombined. The field took its name and its standard form from John Koza, whose 1992 book Genetic Programming: On the Programming of Computers by Means of Natural Selection (MIT Press) set out the tree-based approach that most people still mean when they say GP.

Programs as Trees

In Koza’s formulation, a program is a tree. Internal nodes are functions such as addition, multiplication, sine or an if-then-else. Leaves are terminals: input variables and constants. The expression (x + 3) * sin(y) becomes a tree with a multiplication at the root, an addition on one side and a sine on the other.

The designer chooses two sets before the run starts. The function set lists the operations the program may use, and the terminal set lists the inputs it may read. This choice matters a great deal. Give the search only arithmetic and it can never discover a periodic signal; give it fifty operators and the space becomes so large that progress slows to a crawl.

Every function must also accept any value another node might produce. Koza called this closure. Division is the usual example: a random tree will sooner or later divide by zero, so GP systems use a «protected» division that returns a fixed value in that case (Koza used 1) instead of crashing.

The first generation is random. A common recipe from Koza’s book is ramped half-and-half, which builds some trees to full depth and others with irregular shapes, across a range of depths, so the starting population contains small, large, bushy and thin programs.

Crossover and Mutation on Trees

Each program is run on a set of test cases and scored. Better programs are more likely to be selected as parents, usually through tournament selection, where a few individuals are drawn at random and the best of them wins.

Subtree crossover is the signature operator. Pick a random node in each parent, cut there, and swap the two branches. The children are valid programs by construction, because any subtree can replace any other once closure holds. Mutation does the same thing with a single parent, replacing a random branch with a freshly generated one.

Later research changed the representation without changing the principle. Cartesian GP, introduced by Julian Miller and Peter Thomson in 2000, encodes programs as graphs on a grid, which lets one node feed several others. Lee Spector’s PushGP uses a stack-based language where programs can manipulate their own code. Selection also got sharper: lexicase selection, studied by Thomas Helmuth, Lee Spector and James Matheson in a 2015 IEEE Transactions on Evolutionary Computation paper, picks parents by filtering on test cases one at a time in random order instead of averaging the errors, which keeps specialists alive that an averaged score would throw away.

Bloat

Run GP long enough and the programs grow. Trees get deeper and wider while fitness barely improves. This is called bloat, and it was noticed in the earliest runs.

Much of the extra material is code that does nothing, such as adding x and then subtracting it, or a branch that can never execute. Early explanations blamed these «introns,» arguing that they protect useful code from destructive crossover. Sean Luke later showed that the causation probably runs the other way: inactive code accumulates because trees grow, not the reverse. William Langdon and Riccardo Poli proposed an explanation that does not depend on introns at all. For any program, there are far more large programs with the same behavior than small ones, so a search that drifts among equally fit solutions will tend to drift toward larger ones.

Bloat is not a cosmetic problem. Large programs are slow to evaluate, hard to read, and more likely to overfit. Practitioners control it with depth limits, size penalties added to fitness, or multi-objective selection that treats size as a second objective. Luke and Liviu Panait compared several of these methods in a 2006 paper in Evolutionary Computation, and the simple depth limit Koza used in 1992 was competitive with the more elaborate alternatives.

Symbolic Regression

The most common use of GP today is symbolic regression: given data, find a formula that fits it. Unlike linear regression, the form of the formula is not given. Unlike a neural network, the answer is an equation a person can read.

The best-known demonstration is a 2009 Science paper by Michael Schmidt and Hod Lipson at Cornell, «Distilling Free-Form Natural Laws from Experimental Data.» They recorded the motion of physical systems, from simple harmonic oscillators to a chaotic double pendulum, and used symbolic regression to search for quantities that stayed constant over time. The system recovered Hamiltonians, Lagrangians and conservation laws without being told what physics to look for. The method became a commercial tool called Eureqa.

GP has also held up under systematic comparison. In 2021, William La Cava and colleagues published SRBench at NeurIPS, a benchmark of 14 symbolic regression methods on 252 datasets, including real-world regression tasks and physics equations with known answers. On the real-world data, Operon, a GP system that tunes constants with the Levenberg-Marquardt algorithm, produced the most accurate models, and four of the top five methods were GP-based. On the noiseless physics problems, AI Feynman, which is not a GP method, recovered the most exact equations, though its advantage shrank as noise was added. No single method won everywhere.

Case: Patents, Antennas and Lenses

Koza spent years trying to show that GP could produce results a human expert would respect. He set criteria for «human-competitive» results, one being that the result duplicates or improves on an invention that had been patented. A 2010 survey in Genetic Programming and Evolvable Machines counted at least 36 such results, including 15 that duplicated the function of a patented 20th-century invention, 6 that did the same for 21st-century patents, and 2 that were patentable new inventions. His group rediscovered six patented optical lens systems (GECCO 2005), and a patent for improved general-purpose controllers, filed with GP-generated designs, was issued in 2005 as U.S. Patent 6,847,851.

A different group built a result that flew. For NASA’s Space Technology 5 mission, Jason Lohn, Gregory Hornby and Derek Linden evolved X-band antennas under tight requirements on beam width and bandwidth. They ran two algorithms, one of which used a GP-style tree representation that allowed the antenna’s arms to branch. The evolved designs outperformed the one produced by the mission’s antenna contractor, and an evolved antenna went to space on the ST5 spacecraft in 2006. It looks like a bent paperclip, and it is not a shape anyone would have sketched by hand.

Case: Repairing Bugs With GenProg

In 2012, Claire Le Goues, Michael Dewey-Vogt, Stephanie Forrest and Westley Weimer presented a study at ICSE with a memorable title: «A Systematic Study of Automated Program Repair: Fixing 55 out of 105 Bugs for $8 Each.» Their system, GenProg, takes a buggy C program and a test suite with at least one failing test. It evolves patches by copying, deleting and moving statements that already exist elsewhere in the program, and keeps a patch if all the tests pass.

The paper helped start the field of automated program repair. It also led to one of the most useful critiques in the GP literature. In 2015, Zichao Qi, Fan Long, Sara Achour and Martin Rinard reanalyzed the patches at ISSTA. Because of errors in the test scripts, most reported patches did not pass the full test suite. Only 18 were plausible, and only 2 were correct. Many of the rest simply deleted the functionality that was failing. The authors built a system called Kali that only deletes code, and it found plausible patches for 27 defects, more than GenProg.

Language Models as Mutation Operators

Random subtree swaps are a crude way to edit code. A recent line of work replaces them with a large language model. In FunSearch, published in Nature in 2023 by Bernardino Romera-Paredes and colleagues at Google DeepMind, a population of Python programs is kept and scored by an automatic evaluator, and a pretrained language model writes new candidates by modifying the best ones.

The structure is recognizably evolutionary: a population, variation, selection, an islands model to keep diversity. Applied to the cap set problem in combinatorics, FunSearch found a cap set of size 512 in eight dimensions, where the largest known had been 496, and it improved the asymptotic lower bound. It also found heuristics for online bin packing that beat the standard first-fit and best-fit rules. As in classic GP, the output is a program, short enough for a mathematician to read and analyze.

Closing Thought

Every genetic programming system depends on a fitness function, and in GP the fitness function is the specification. The search has no idea what the programmer wanted. It only knows which tests passed. GenProg’s deleted features, the bloated trees full of dead code, and the protected division that quietly returns 1 are all the same lesson: evolution finds whatever satisfies the test, including answers nobody intended. That is why FunSearch paired its language model with a strict evaluator, and why the hardest part of using GP is still writing a test that says exactly what you mean.

By: Max Johnson B.

Stuck at the Bottom of the Nearest Valley

The simplest way to optimize something is to start with a solution, look at small changes to it, and keep any change that makes things better. This is local search, or hill climbing if you are maximizing. For a traveling salesman tour, a small change might be reversing a segment of the route. You repeat until no small change helps.

The problem is where this process stops. It stops at a local optimum, a solution that is better than all of its neighbors but possibly much worse than the best solution overall. On a smooth bowl-shaped landscape that is fine. On the rugged landscapes of real combinatorial problems, with millions of small valleys, a greedy search falls into the first one it finds and never leaves.

Simulated annealing and tabu search both start from this same local search loop. They differ in how they allow it to escape. Annealing escapes by accepting bad moves at random, with a probability that shrinks over time. Tabu search escapes by remembering where it has been and refusing to go back.

Annealing in Metals and in Code

Annealing is an old metallurgical process. A metal is heated and then cooled slowly, which gives its atoms time to settle into an ordered, low-energy crystal structure. Cool it too fast and the atoms freeze in a disordered state full of defects.

In 1953, Nicholas Metropolis and colleagues published a Monte Carlo method for simulating a physical system at a fixed temperature. A random change to the system is proposed. If it lowers the energy, it is accepted. If it raises the energy by some amount Δ, it is accepted with probability exp(−Δ/T), where T is the temperature. At high temperature almost everything is accepted; at low temperature, uphill moves become rare.

Scott Kirkpatrick, C. Daniel Gelatt and Mario Vecchi, working at IBM, turned this into an optimization method in a 1983 paper in Science titled «Optimization by Simulated Annealing.» Their idea was to treat the cost of a solution as energy and to lower T gradually during the search. Early on, the algorithm wanders across the landscape almost freely. Later, it behaves more and more like plain hill climbing. Vladimír Černý reached the same idea independently and published it in 1985 in the Journal of Optimization Theory and Applications, applied to the traveling salesman problem.

The appeal is that the algorithm needs only a cost function and a way to generate neighbors. The same twenty lines of code work on permutations, graphs and bit strings.

The Cooling Schedule

Most of the practical difficulty of simulated annealing is one choice: how fast to lower the temperature. The common answer is geometric cooling, where T is multiplied by a constant such as 0.95 after a fixed number of moves. You also need a starting temperature high enough that most uphill moves are accepted at first, and a rule for when to stop.

There is a theory behind this, and it is unusually clean. Stuart and Donald Geman showed in 1984 that if the temperature falls no faster than a constant divided by the logarithm of the iteration count, the search converges to a global optimum. Bruce Hajek sharpened this in 1988 with a necessary and sufficient condition: the constant must be at least the depth of the deepest local minimum that is not global, meaning the largest uphill climb needed to escape a trap.

The catch is that logarithmic cooling is extremely slow. To halve the temperature you must square the number of iterations. For a realistic problem, the guaranteed schedule takes longer than exhaustive search would. So practitioners use fast schedules that carry no guarantee, and they tune them by experiment. The convergence theorem tells you the method is not arbitrary, but it does not tell you how to run it.

Case: Placing Circuits on a Chip

The first serious application was chip design. Placing thousands of circuit components on a chip so that the wires between them are short is a huge combinatorial problem. Their Science paper reported results on partitioning, placement and wiring of electronic systems, along with traveling salesman instances of several thousand cities.

Carl Sechen and Alberto Sangiovanni-Vincentelli followed with TimberWolf, published in the IEEE Journal of Solid-State Circuits in 1985. It used annealing for standard cell, macro cell and gate array placement, plus global routing. On industrial circuits, they reported area savings of 15 to 62 percent over the layout programs in use at the time.

Not every evaluation was so favorable. David Johnson, Cecilia Aragon, Lyle McGeoch and Catherine Schevon ran a long experimental study published in Operations Research in 1989. On graph partitioning, annealing beat the classic Kernighan-Lin heuristic on large sparse random graphs, but on graphs with geometric structure Kernighan-Lin won by a substantial margin. The authors described annealing’s success as mixed. That conclusion has held up: annealing is a dependable general method, and a good problem-specific heuristic often beats it.

Tabu Search and Short-Term Memory

Fred Glover introduced the term tabu search in a 1986 paper in Computers and Operations Research, «Future Paths for Integer Programming and Links to Artificial Intelligence,» and laid out its principles in a two-part article in the ORSA Journal on Computing starting in 1989. He described it as a metaheuristic superimposed on another heuristic, one that gets past local optimality by forbidding certain moves.

The mechanism works like this. At each step, tabu search examines the neighborhood and moves to the best neighbor that is not forbidden, even if that neighbor is worse than the current solution. This alone would make the search cycle forever, stepping out of a valley and straight back in. To prevent that, it keeps a tabu list of recent moves, or attributes of recent moves, and forbids reversing them for a certain number of iterations, called the tabu tenure.

If the search just swapped jobs A and B, swapping them back is tabu for, say, the next ten iterations. The search is forced to keep moving away from the local optimum it just left. What gets stored is usually an attribute, not a full solution, because attributes are cheap to compare.

This basic version needs no randomness. It always takes the best allowed move, while annealing samples one random neighbor at a time.

Aspiration, Intensification and Diversification

Forbidding moves by attribute has a side effect. Sometimes a tabu move would lead to a solution better than anything found so far, and the tabu list blocks it only because of a coincidence of attributes. Aspiration criteria fix this. The most common one says a tabu move is allowed if it produces a new best solution.

Glover also described longer-term memory. Intensification strategies return to regions where good solutions were found and search them more carefully, for example by fixing features that appear in most of the elite solutions. Diversification strategies push the search toward regions it has rarely visited, often by penalizing moves that have been used frequently. A frequency count per attribute is enough for both.

So tabu search is closer to a framework than a single algorithm. A competitive implementation usually combines tabu lists, aspiration, frequency memory and restarts from elite solutions, tuned to the problem.

Case: Job Shops and Quadratic Assignment

Two results show how much a well-designed tabu search can do. Éric Taillard published Robust Tabu Search for the quadratic assignment problem in Parallel Computing in 1991. Instead of a fixed tabu tenure, it draws the tenure at random from a range, which removes the need to tune one exact value and makes cycling less likely. Robust Tabu Search became a standard reference method for the quadratic assignment problem, and later algorithms often use it as their local improvement step.

Eugeniusz Nowicki and Czesław Smutnicki published «A Fast Taboo Search Algorithm for the Job Shop Problem» in Management Science in 1996. Their key contribution was a small, carefully chosen neighborhood: only swaps of adjacent operations on the critical path of the schedule, which are the only swaps that can shorten the total completion time. With a tiny neighborhood, each step is fast, and tabu memory keeps the search from circling. Their algorithm and its successor, i-TSAB, were for a long time the state of the art for minimizing makespan on standard job shop benchmarks.

In both cases, most of the strength came from the problem structure. The tabu mechanism let the search exploit it without getting stuck.

Randomness Versus Memory

The two methods make an opposite bet. Simulated annealing assumes that random uphill moves, accepted less and less often, will shake the search loose from traps. Tabu search assumes that remembering recent history is enough to avoid revisiting the same traps, and it uses that memory to drive the search deliberately.

In practice, annealing is easier to implement and needs only a cooling schedule. It also works well when neighborhoods are huge and only a random sample of moves can be evaluated. Tabu search evaluates the whole neighborhood, or a large part of it, at every step, so it fits problems where neighborhoods are small or can be scored incrementally.

The two are often combined. Annealing can use a short tabu list to avoid immediate reversals, and tabu search can add random tenure or restarts. Both also serve as the local improvement step inside genetic algorithms, where the population explores broadly and the single-solution method refines the best individuals.

A Final Observation

The convergence theorem for simulated annealing is one of the cleanest results in the field, and almost nobody runs the algorithm the way the theorem requires. The useful version is the one that throws away its own guarantee. Tabu search never had a guarantee, and it became one of the strongest tools for scheduling anyway. For hard combinatorial problems, the better question to ask about a method is not whether it will find the optimum but how it decides to accept a worse solution. A search that never takes a bad step stops in the first valley. Which bad steps it takes, and why, decides most of what it can find.

By: Max Johnson B.

Models Larger Than Their Task Requires

The most accurate neural networks are usually the largest ones, and large models are expensive to run. They need memory that a phone or a microcontroller does not have, they answer slowly, and at the scale of millions of requests per day, every extra millisecond and watt adds to the bill.

Researchers noticed early that trained networks are heavily redundant. Much of what makes a network large is needed to train it well, not to represent what it learned. That observation led to a family of techniques, grouped under the name model compression, that start from a large trained model and produce a smaller one with nearly the same accuracy. The three main ones are knowledge distillation, pruning and quantization. This post focuses on the first two.

Teachers and Students

The core idea of distillation appeared in 2006, when Cristian Bucilă, Rich Caruana and Alexandru Niculescu-Mizil published a paper called «Model Compression.» They had large ensembles of models that were accurate but slow, and they showed that a single small neural network could be trained to imitate the ensemble’s predictions and keep most of its accuracy.

Geoffrey Hinton, Oriol Vinyals and Jeff Dean gave the method its current form and name in «Distilling the Knowledge in a Neural Network» (2015). A large, already trained model is the teacher, and a smaller model is the student. The student is trained to reproduce the teacher’s outputs, not only the correct labels from the dataset.

Soft Targets and Temperature

Imitating a teacher works better than learning from labels alone because the teacher’s output contains more information than the label does. A label says an image is a dog and nothing else. A trained classifier’s output might say 90% dog, 9% wolf, 0.9% cat, and almost zero for truck. Those small probabilities encode which classes look alike, something the label alone never tells the student. Hinton called this «dark knowledge.»

In a well-trained network, though, the wrong-class probabilities are often so tiny that they barely affect the loss. The fix is a temperature parameter T in the softmax. Dividing the logits by a temperature above 1 flattens the distribution, so the small probabilities become large enough to matter. The student is trained with the same temperature to match these softened outputs, usually alongside the ordinary loss on the true labels, with a weight balancing the two. At inference the temperature goes back to 1.

Distilling Internal Representations

Matching only the final outputs gives the student a limited signal. FitNets, from Adriana Romero and colleagues (ICLR 2015), added «hints»: the student is also trained to reproduce the teacher’s activations at an intermediate layer, through a small adapter that accounts for the difference in size. This made it possible to train students that were thinner and deeper than the teacher.

Later methods transfer other internal quantities, such as attention maps or the relationships between examples in a batch. In Transformers, it is common to match hidden states and attention matrices layer by layer, as TinyBERT (Jiao and colleagues, 2020) does.

DistilBERT

The best-known example in language processing is DistilBERT, published in 2019 by Victor Sanh, Lysandre Debut, Julien Chaumond and Thomas Wolf at Hugging Face. The student has the same architecture as BERT-base with half the layers, 6 in place of 12, and was initialized by taking one layer out of every two from the teacher. It was trained with a combination of three losses: the usual masked language modeling loss, a distillation loss on the teacher’s softened output distribution, and a cosine loss that aligns the direction of the student’s hidden states with the teacher’s.

The paper reports a model 40% smaller and 60% faster than BERT that retains 97% of its language understanding performance as measured on the GLUE benchmark. DistilBERT became one of the most downloaded models on the Hugging Face Hub, largely because it could run on CPUs at reasonable speed.

Pruning

Pruning removes parts of a trained network. The idea dates back to 1989, when Yann LeCun, John Denker and Sara Solla published «Optimal Brain Damage,» which used second-derivative information to estimate which weights could be deleted with the least effect on the error.

The modern version is simpler. In 2015, Song Han and colleagues showed that removing the weights with the smallest absolute values, then retraining the remaining ones to recover accuracy, and repeating the cycle, could remove most of the connections in networks like AlexNet and VGG-16 without loss of accuracy. Their follow-up, «Deep Compression,» which won a best paper award at ICLR 2016, chained pruning with weight quantization and Huffman coding. It reduced the storage of AlexNet by 35 times, from 240 MB to 6.9 MB, and of VGG-16 by 49 times, from 552 MB to 11.3 MB, with no loss of accuracy.

Unstructured and Structured Pruning

There is an important practical distinction. Unstructured pruning deletes individual weights anywhere in the network. It reaches very high sparsity, but the result is a matrix of the same shape with many zeros in it, and ordinary hardware does not run a sparse matrix any faster unless the software and chips are built for it. The file gets smaller, and the speed often does not change.

Structured pruning removes whole units: neurons, convolutional filters, attention heads or entire layers. The resulting network is smaller in the ordinary sense and runs faster on any hardware. The cost is that accuracy drops sooner, because removing a whole filter is a much coarser operation than removing scattered weights. Paul Michel and colleagues showed in 2019 that many attention heads in Transformers can be removed at test time with little effect, which made head pruning a common technique for language models.

The Lottery Ticket Hypothesis

If a pruned network works well, a natural question is whether the small network could have been trained directly from the start. For a long time the answer seemed to be no: sparse networks trained from scratch did worse than pruned ones.

Jonathan Frankle and Michael Carbin proposed an explanation in «The Lottery Ticket Hypothesis,» which received a best paper award at ICLR 2019. They trained a network, pruned the smallest weights, and then reset the surviving weights to the exact values they had at initialization. Trained again from there, these sparse subnetworks, often 10 to 20% of the original size on MNIST and CIFAR-10, matched the accuracy of the full network. With a fresh random initialization, the same sparse structure did not.

Their hypothesis is that a large random network contains small subnetworks whose initial weights happen to be well suited for training, the winning tickets, and that part of the benefit of a large network is that it holds many such candidates. On larger networks, later work found that the weights need to be rewound to a point early in training instead of to the very beginning. Finding the tickets still requires training the big network first, so the result is more important for understanding why over-parameterized networks train well than as a practical shortcut.

Combining the Techniques

Distillation, pruning and quantization act on different things, so they are usually combined. Distillation produces a smaller architecture. Pruning removes what is left of the redundancy. Quantization then stores each remaining weight with fewer bits, for example 8-bit integers in place of 32-bit floating-point numbers. A typical pipeline for deployment on a device applies all three, checking accuracy after each step.

Distillation has also taken on a second role with large language models. A large model can generate answers, explanations or labels for a big set of inputs, and a much smaller model is then trained on that synthetic data. The student never sees the teacher’s internal probabilities, only its text, but the principle is the one from 2006: use an expensive model to teach a cheap one.

Limits

Compression always costs some accuracy. Average accuracy on a benchmark can stay almost unchanged while performance on rare cases gets worse. Sara Hooker and colleagues showed in 2019 that pruning affects a small subset of examples disproportionately, often atypical or underrepresented ones, even when the top-line accuracy barely moves. A student can also inherit its teacher’s errors and biases, since it is trained to copy them. And when the student is far smaller than the teacher, the gap can be too wide to bridge in one step, which is why some methods distill through an intermediate-size model first.

Reflection

Compression works because training a model and running it need different things. Training benefits from a large network, which has many possible paths to a good solution. Once the solution is found, most of that capacity is no longer needed. This is why the common practice is to train a large model first and then shrink it, and not to design a small model and train it directly. The lottery ticket experiments are the clearest evidence for this: the small network that works was inside the large one from the start, but it could only be identified after training the large one.

By: Max Johnson B.

What a Language Model Does Not Know

A large language model stores what it knows in its weights, and those weights stop changing when training ends. That has three consequences. The model knows nothing about events after its training cutoff. It knows nothing about private information, such as a company’s internal manuals or a hospital’s protocols. And when asked about something it has little information on, it often produces a fluent, confident and wrong answer, the behavior usually called hallucination.

Retraining a model every time a document changes is too expensive to be practical. Retrieval-augmented generation (RAG) takes a different route. When a question arrives, the system searches a collection of documents for relevant passages, places them in the prompt together with the question, and asks the model to answer using that material. The knowledge sits in a database that can be updated at any time, and the model’s job shifts from recalling facts to reading and summarizing them.

The 2020 Paper

The name comes from «Retrieval-Augmented Generation for Knowledge-Intensive NLP Tasks,» by Patrick Lewis and colleagues at Facebook AI Research, University College London and New York University, presented at NeurIPS 2020. Their system combined two trained components: a retriever based on Dense Passage Retrieval (DPR), which searched an index of about 21 million Wikipedia passages, and BART, a sequence-to-sequence model that generated the answer conditioned on the retrieved passages. The two were fine-tuned together.

The paper described the combination as parametric memory (the weights of the generator) plus non-parametric memory (the document index). It set state-of-the-art results on several open-domain question answering benchmarks and generated text that was more specific and factual than BART alone. It also pointed out a property that later became the main selling point: the index can be swapped to update what the system knows without retraining anything.

Modern RAG systems rarely train the retriever and generator jointly. They connect an off-the-shelf embedding model, a vector database and a general-purpose language model. The principle is the same.

Turning Documents Into a Searchable Index

Before any question can be answered, the documents have to be prepared. They are first split into chunks, pieces of a few hundred words each. Chunking matters more than it seems. Chunks that are too large dilute the relevant sentence among unrelated text. Chunks that are too small lose the context needed to understand them (a paragraph that says «this method» without saying which one).

Each chunk is then passed through an embedding model, which turns it into a vector of a few hundred to a few thousand numbers. The model is trained so that texts with similar meaning get nearby vectors. The vectors are stored in a vector database along with the original text. This step is done once, and repeated only for documents that change.

Sparse and Dense Retrieval

There are two families of search methods. Sparse retrieval matches words. Its standard algorithm is BM25, developed by Stephen Robertson and colleagues in the 1990s, which scores a document by how often the query’s terms appear in it, weighted by how rare each term is across the collection. It is fast, needs no training, and is very good with exact terms like product codes, names and error messages.

Dense retrieval compares embeddings. Karpukhin and colleagues introduced DPR in 2020, training two BERT encoders, one for questions and one for passages, so that a question and the passage that answers it end up close together. On open-domain question answering datasets, DPR beat a strong BM25 system by 9 to 19 percentage points in top-20 retrieval accuracy. Dense retrieval can match a question to a passage that shares no words with it, which sparse methods cannot do.

Each approach fails where the other works, so production systems often run both and merge the results, a setup called hybrid search. Searching millions of vectors exactly would be slow, so vector databases use approximate nearest neighbor indexes such as HNSW (Malkov and Yashunin), which trade a small loss in accuracy for a large gain in speed.

Reranking and Building the Prompt

The first retrieval step is tuned for speed and returns maybe 50 to 100 candidates. A second model, a reranker, then scores each candidate against the question more carefully. Rerankers are usually cross-encoders: they read the question and the passage together, which is more accurate than comparing two separately computed vectors but too slow to run on the whole collection.

The top few passages are inserted into the prompt with an instruction along the lines of «answer using only the following sources and cite them.» The order matters. In «Lost in the Middle» (2023), Nelson Liu and colleagues showed that language models use information at the beginning and end of a long context much better than information in the middle, with accuracy dropping noticeably when the relevant passage was placed in the center.

Ways RAG Fails

RAG reduces hallucinations, but it does not eliminate them. Failures happen at each stage. The retriever can miss the relevant passage, and then the model answers from memory or invents something. The retriever can return a passage that looks related but is about something else, and the model follows it. The correct passage can be retrieved and then misread or ignored. And some questions need information scattered across many documents («what are the main themes in these 500 reports?»), which retrieving five chunks will not answer.

A study from Stanford’s RegLab, by Varun Magesh and colleagues, tested commercial legal research tools built on RAG, whose vendors had advertised them as avoiding hallucinations. On about 200 legal queries scored by hand, the tools still gave incorrect or misgrounded answers a large share of the time: about 17% for Lexis+ AI and about 33% for Westlaw AI-Assisted Research. Those numbers were better than GPT-4 without retrieval, at 43%, but far from zero. In many cases the tools cited real documents that did not support the claim attributed to them.

Refinements

Much recent work targets those failure points. Query rewriting has a language model reformulate the user’s question, or break it into sub-questions, before searching. Self-RAG, from Akari Asai and colleagues (ICLR 2024), trains the model to decide when retrieval is needed and to critique whether the retrieved passages are relevant and whether its own answer is supported by them. GraphRAG, from Microsoft Research in 2024, uses a language model to extract entities and relationships from the documents into a knowledge graph and writes summaries of clusters in that graph, which helps with questions about the collection as a whole.

Agentic approaches let the model run several searches in sequence, read the results, and decide what to look for next, closer to how a person researches a topic.

RAG, Fine-Tuning and Long Context

RAG is not the only way to adapt a model to new knowledge. Fine-tuning changes the weights, which works well for teaching a style, a format or a skill, but poorly for facts that change often, and it gives no source to cite. Context windows have grown to hundreds of thousands of tokens, so small collections can be placed directly in the prompt, at a higher cost per query and with the middle-of-context problem described above. For large or frequently updated collections, and wherever answers need to point to their sources, retrieval is still the practical option. Many systems combine the three.

Evaluation

A RAG system has to be evaluated in two parts. Retrieval is measured with metrics like recall at k: of the questions in a test set, how often is the passage with the answer among the top k results. Generation is measured on faithfulness (is every claim in the answer supported by the retrieved passages) and on whether the answer addresses the question. Looking only at the final answer hides which part is failing, and a wrong answer caused by bad retrieval needs a different fix than one caused by the model misreading a good passage.

A Final Observation

RAG changes where the difficulty of the problem is. The language model no longer has to know the answer, but the system has to find the right paragraph among millions, and most of the errors come from that search step. Search has been studied for decades in information retrieval, long before language models existed. A team building a RAG system will usually get more out of improving chunking, indexing and ranking than out of switching to a larger model.

By: Max Johnson B.

An Architecture Borrowed From Language

For most of the 2010s, computer vision meant convolutional neural networks. Convolutions build in two assumptions about images: nearby pixels are related, and a pattern means the same thing wherever it appears. Those assumptions are correct often enough that CNNs learned well from modest amounts of data, and every major vision benchmark was led by one.

The Transformer came from machine translation and has neither assumption. It treats its input as a set of tokens and lets every token look at every other token through self-attention. In October 2020, a team at Google Research led by Alexey Dosovitskiy posted a paper titled «An Image is Worth 16×16 Words: Transformers for Image Recognition at Scale,» later published at ICLR 2021. It asked what would happen if a standard Transformer were applied to images with as few changes as possible. The model was called the Vision Transformer, or ViT.

From Pixels to Tokens

A Transformer needs a sequence, and an image is a grid. Treating every pixel as a token is not practical, because self-attention compares every token with every other one, so its cost grows with the square of the sequence length. A 224 by 224 image has more than 50,000 pixels.

ViT cuts the image into square patches instead, typically 16 by 16 pixels. A 224 by 224 image gives 196 patches. Each patch is flattened into a vector and passed through one linear layer to produce a patch embedding. These 196 vectors are the «words» of the title.

Two more pieces are added. A sequence of patches has no inherent order, so a learned position embedding is added to each patch to tell the model where it came from. And an extra learnable token, the class token, is placed at the start of the sequence. After the Transformer layers, the output at that position is used as the representation of the whole image and fed to a classifier.

Everything after that is a standard Transformer encoder: alternating layers of multi-head self-attention and small feed-forward networks, with residual connections and layer normalization. Nothing in it is specific to images.

What Attention Sees in an Image

In a CNN, a neuron in an early layer sees only a small neighborhood, and the network needs many layers before information from opposite corners of the image can meet. In a ViT, every patch can attend to every other patch in the very first layer.

The original paper measured how far attention reaches in each layer. Some attention heads in the earliest layers already covered most of the image, while others stayed local, behaving a lot like convolutions. Deeper layers attended globally. Raghu and colleagues compared the internal representations of ViTs and ResNets in 2021 and found that ViTs have more uniform representations across layers and carry spatial information further into the network.

The Need for Data

The most important result in the ViT paper was about data. Trained on ImageNet alone, with about 1.3 million images, ViT was worse than a comparable ResNet. Without the built-in assumptions of convolution, the model had to learn from scratch that nearby patches are related, and 1.3 million images were not enough for that.

With more data, the result reversed. Pre-trained on ImageNet-21k (14 million images), ViT matched the best CNNs. Pre-trained on JFT-300M, Google’s internal dataset of 300 million images, the largest model (ViT-H/14) reached 88.55% top-1 accuracy on ImageNet after fine-tuning, ahead of the best convolutional models of the time. The authors summarized it by saying that large-scale training trumps inductive bias.

That left a practical problem, since almost nobody outside Google had 300 million labeled images.

DeiT and Training on ImageNet Alone

A few months later, Hugo Touvron and colleagues at Facebook AI showed that the data requirement was partly a matter of training recipe. Their Data-efficient image Transformers (DeiT), published at ICML 2021, trained a ViT on ImageNet only and reached 81.8% top-1 accuracy (83.1% at a higher input resolution), competitive with CNNs of similar size. The changes were heavy data augmentation, strong regularization and a longer, carefully tuned schedule.

DeiT also introduced a distillation token. Alongside the class token, a second special token is trained to reproduce the prediction of a teacher network, and the best teachers turned out to be CNNs. The student Transformer picks up some of the convolutional network’s inductive bias through the teacher’s outputs.

Swin and Hierarchical Designs

Plain ViT has two limits for tasks beyond classification. It produces features at a single, coarse resolution, while object detection and segmentation need features at several scales. And the quadratic cost of global attention becomes too high for large images.

Swin Transformer, from Ze Liu and colleagues at Microsoft Research Asia, addressed both. It computes self-attention only inside small local windows, so cost grows linearly with image size. Between consecutive layers, the windows are shifted so that information can flow across window borders. Patches are merged as the network gets deeper, which produces a pyramid of feature maps at decreasing resolution, like a CNN. Swin set records in object detection on COCO and semantic segmentation on ADE20K and received the Marr Prize for best paper at ICCV 2021.

Self-Supervised Pre-Training: MAE and DINO

The other way around the labeled data problem is to not use labels. Masked Autoencoders (MAE), from Kaiming He and colleagues at CVPR 2022, hide 75% of the patches of an image and train a ViT to reconstruct the missing pixels from the remaining quarter. The encoder only processes the visible patches, so pre-training is fast, and a ViT-H trained this way on ImageNet-1k alone reached 87.8% accuracy after fine-tuning.

DINO, from Mathilde Caron and colleagues in 2021, trains a student network to match the output of a slowly updated teacher on different crops of the same image. A side effect got a lot of attention: the attention maps of the class token outlined objects in the image, although the model had never seen a segmentation label. DINOv2, released by Meta in 2023, scaled the approach to a curated set of 142 million images and produced features that work for classification, segmentation and depth estimation with no fine-tuning.

The CNN Response

ViT’s success raised the question of whether attention was the reason, or whether the improvements came from everything around it: bigger models, better augmentation, new training schedules. In «A ConvNet for the 2020s» (CVPR 2022), Zhuang Liu and colleagues took a standard ResNet and modernized it step by step, borrowing design choices from Swin such as larger kernels, fewer activation functions and layer normalization. The resulting ConvNeXt matched or beat Swin at similar size on ImageNet, detection and segmentation, using only convolutions.

The conclusion most researchers took from this is that the two families are closer than the early results suggested. Convolutions remain efficient on small data and limited hardware. Transformers scale better with data and combine naturally with text and other modalities, since everything becomes tokens.

ViT as a Backbone

That last property explains where ViTs ended up. CLIP, from OpenAI in 2021, trains an image encoder (in its best versions a ViT) together with a text encoder so that matching images and captions get similar embeddings. Vision-language models that answer questions about pictures typically feed ViT patch embeddings into a language model. The Segment Anything Model (Kirillov and colleagues, 2023) uses a ViT pre-trained with MAE as its image encoder and was trained on 11 million images with over a billion masks. Diffusion models for image generation have also moved from convolutional U-Nets to Transformer backbones operating on patches.

Closing Observation

ViT is a useful case for a general question in machine learning: how much knowledge should the designer build into a model, and how much should be left for the data to teach it. Convolutions build in knowledge about images, and that helps when data is scarce. ViT removes most of it, does worse with little data, and does better once there is enough. Neither choice is right in general. The better one depends on how much data and compute are available, and for image models that amount grew very quickly in the years after 2020.

By: Max Johnson B.