Chapter 2 — The Idea Behind Conformal Prediction
Chapter 1 closed with a promise: there is a way to make a model output a tiny set of answers, coupled with an unbreakable assurance that the truth lands inside such sets at least, say, 90% of the time — and this works for any model, on any sort of data. That promise seems too good, probably, to be true. This chapter convinces you that it is plausible by showing you the full idea in plain English. The next chapter translates the idea into precise mathematics. By the end of this chapter you will know why conformal prediction works, even though you can’t prove it yet.
2.1 Where the idea came from
The conformal prediction method has an odd pedigree. It evolved not out of ordinary statistics but out of a question about randomness itself, asked in the late 1990s by Vladimir Vovk, Alexander Gammerman, and Glenn Shafer, and gathered into a 2005 book of theirs. Vovk had studied under Kolmogorov, one of the founders of modern probability, and the seed of conformal prediction is a beautifully simple reframing that we will use throughout: instead of asking “what is the probability this new answer is correct?” — a hard question that seems to require knowing the true distribution of the data — ask instead “if I assumed this answer were correct, how strange or ordinary would that make my collection of data look?” This shift, from estimating a probability to measuring strangeness against data you already have, is the entire trick, and everything else is bookkeeping.
For roughly fifteen years the idea stayed inside a small research community. It broke into wide use around 2020 for three reasons that reinforced one another: the deep learning boom created an urgent need for trustworthy uncertainty, precisely because of the overconfidence described in Chapter 1; a clear and friendly tutorial by Anastasios Angelopoulos and Stephen Bates in 2021 translated the theory for working engineers; and ready-made software libraries appeared that made the method a few lines of code rather than a research project. We will discuss one of those libraries, MAPIE, later on.
2.2 The whole idea of Conformal Prediction
Here is conformal prediction from start to finish, with no mathematics. Read it slowly; everything afterward is elaboration.
You begin with a model that is already trained. You do not trust its confidence numbers — Chapter 1 explained why. But you also have a stack of labeled examples that the model has never seen during training: inputs for which you happen to know the correct answers. This stack , we will refer to it as the calibration set. Think of it as a fair exam the model must sit, where you already have the answer key.
First, you grade the model on this exam, but in a rather unusual way. For each example in the calibration set, you ask a single question: how badly did the model do on this one? You boil that down to one number, where a bigger number means the model did worse. This “how badly did it do” number is called the nonconformity score — nonconformity because it measures how poorly the example conforms to what the model expected. For a classifier, a natural such score is one minus the probability the model assigned to the correct answer: if the model gave the true answer a probability of 0.95, the model did well, and the score is a small 0.05; if it gave the true answer only 0.30, the model did poorly, and the score is a large 0.70. You compute this score for every example in the calibration set, and now you hold a whole pile of “how badly the model tends to do” numbers.
Second, you find the value that these scores rarely exceed. Concretely, if you want a 90% guarantee, you find the number below which 90% of your calibration scores fall — the point where only the worst 10% of scores lie above it. Call this cutoff value the threshold. It represents, in effect, the boundary of “normal badness”: scores below it are the kind of mistake the model makes routinely, and scores above it are unusually bad. (The next section explains how to find such a cutoff; for now, just hold the idea of “the value that 90% of scores fall below.”)
Third, a new input arrives and you must make a prediction. Here is the clever move. You consider every possible answer the input could have, and for each candidate answer you compute what its nonconformity score would be if that answer were the true one. Then you keep every candidate answer whose score falls below the threshold — every answer that would represent no more than “normal badness” — and you throw away the rest. The answers you keep are your prediction set. That set is your output: not a single guess, but the collection of all answers that are plausible given how the model normally behaves.
Now, why does this give a 90% guarantee? The reasoning is short and, once you see it, hard to unsee. The new input is, we will assume, just another example drawn from the same source as the calibration examples — one more student sitting the same exam. So its nonconformity score is just one more number of the same kind as the pile we already have. Ask: how often does one more number from the same pile land below the 90% threshold? By the very meaning of “the value 90% of scores fall below,” it lands below about 90% of the time. And whenever the true answer’s score lands below the threshold, the true answer was, by construction, kept in the set. Therefore the true answer sits inside the prediction set about 90% of the time. That is the guarantee, and notice what the argument never once needed: it never needed the model to be good, and it never needed the data to follow any particular bell curve or formula. It needed only that the new example is of the same kind as the calibration examples.
2.3 What a quantile is, and how to find the threshold
The second step above asked for “the value 90% of scores fall below.” That value has a name — a quantile — and because quantiles appear on every page from here on, we pause to make the idea completely solid. If you are already comfortable with percentiles, this is the same thing under a more formal name, and you can skim.
Suppose you have the test scores of 100 students, and you want the score that separates the bottom 90% from the top 10%. You line all 100 scores up from smallest to largest and walk 90% of the way along the line. The score you are standing next to is the 90th percentile, or equivalently the 0.9 quantile: 90% of students scored at or below it, 10% scored above. A quantile, then, is nothing more mysterious than a cutoff at a chosen position in a sorted list. The 0.5 quantile is the middle value, better known as the median. The 0.9 quantile is the value nine-tenths of the way up. The general recipe is: sort the numbers, then pick the one at the position corresponding to your chosen fraction.
For conformal prediction, the numbers we sort are the calibration set’s nonconformity scores, and the fraction we choose corresponds to the guarantee we want. Want to be right 90% of the time? Take roughly the 0.9 quantile of the scores as your threshold. There is one small but genuinely important adjustment to exactly which position we pick — it involves counting the new test example as well, and rounding up rather than down — but that adjustment is a detail of Chapter 3, and skipping it now costs nothing in understanding. The essential picture is simply this: sort the “how badly did the model do” scores, and take the value near the top below which your target fraction of them fall. That value is the threshold, and it is the only thing you need to store to start making guaranteed predictions.
2.4 The bargain at the heart of the method
Step back and notice the strange and wonderful bargain we have struck. The guarantee — the 90% coverage — does not depend on the model being any good. A hopeless model and a brilliant model both achieve exactly 90% coverage. This raises an obvious worry: if a hopeless model also hits 90%, is the guarantee worthless?
The answer is the single most important intuition in the whole subject — the model’s quality does not change whether the guarantee holds — it changes the size of the sets needed to hold it.
Picture the extreme. A completely useless model, one that has learned nothing, can still be wrapped in conformal prediction and still achieve 90% coverage — but it does so by returning enormous sets. If it must include almost every possible answer to be sure the truth is among them 90% of the time, then it does exactly that, and its “prediction sets” are so large as to be useless. Meanwhile a genuinely good model achieves the same 90% coverage with small, sharp sets — often just a single answer — because its nonconformity scores separate right answers from wrong ones cleanly, and only a few candidates ever fall below the threshold.
So conformal prediction performs a kind of translation. It takes the quality of your model, which is hard to state as a promise, and converts it into the size of the prediction sets, while holding the coverage fixed at whatever you asked for. Validity — the guarantee itself — is free and automatic. Efficiency — small, useful sets — is what a good model earns. Whenever you find yourself worrying “but surely a bad model breaks the guarantee,” remember: it does not break the guarantee, it just makes the sets fat. This bargain is what lets the guarantee be honest without being empty.
2.5 The one assumption: exchangeability
We have leaned twice now on a phrase: “assuming the new example is of the same kind as the calibration examples.” It is time to make that assumption precise, because it is the only assumption conformal prediction makes, and — as we will see repeatedly — it is also the only thing that can make conformal prediction fail. Everything rests on it, so it deserves careful attention.
The assumption is called exchangeability, and the plain-language version is this: the order in which your examples arrived carries no information. Imagine writing each of your labeled examples on a card, shuffling all the cards together — the calibration examples and the new test example alike — and dealing them out in a row. Exchangeability says that no possible ordering of the cards is any more likely than any other. There is nothing special about which example happened to come “last.” If you cannot tell, from the pattern in the data, which card was the test point, then the examples are exchangeable.
Why is this exactly the assumption we need? Look back at the guarantee in Section 2.2. Its entire force came from treating the new example’s score as “just one more number from the same pile,” equally likely to land in any position among the sorted scores. That is precisely what exchangeability grants: if any ordering is as likely as any other, then the new score is equally likely to be the smallest, the largest, or anywhere in between, and the “lands below the 90% threshold about 90% of the time” reasoning goes through. Remove exchangeability and that reasoning collapses.
It helps to know that exchangeability is a mild assumption — milder than the “independent and identically distributed” condition often assumed in statistics, which you may or may not have met. You do not need the details of that comparison; the takeaway is that exchangeability asks for less, and is therefore satisfied more often, which is part of why the method is so widely applicable. A plain random split of a fixed dataset into training, calibration, and test portions is exchangeable, and that covers a great many ordinary machine learning projects.
But — and this is the warning that will echo through every later chapter — exchangeability fails in several extremely common situations, and when it fails the guarantee silently stops being true. The most important failures are worth previewing now so you can start recognizing them.
The clearest failure is time. Data that arrives in time order — stock prices, daily electricity demand, sensor readings — is almost never exchangeable, because the order obviously carries information: yesterday’s value tells you something about today’s, and last winter is not interchangeable with next summer. Shuffle a temperature record and you have destroyed exactly the seasonal pattern that made it predictable. For time-ordered data, plain conformal prediction is not valid, and Chapters 7 and 9 develop the repairs.
A second failure is a change in the world between calibration and use. If your calibration examples came from Hospital A and your model is deployed at Hospital B, whose patients differ, then the test examples are not interchangeable with the calibration examples — you could tell them apart — and the guarantee does not carry over. This situation, called distribution shift, is so important that Chapter 7 is largely about it.
A third, quieter failure is accidental contamination: using the same data both to tune the model and to calibrate it. If the calibration set influenced the model in any way — helping choose its settings, or deciding when to stop training — then it is no longer a fair, unseen exam, and the exchangeability between calibration and test is broken in a way that is easy to miss and that quietly inflates your apparent guarantee. Keeping the calibration set truly untouched is a discipline we will insist on.
The single most valuable habit you can build, before ever deploying conformal prediction, is to pause and ask: are my calibration examples and my real incoming examples genuinely interchangeable? If yes, the guarantee is yours. If no, you must either fix the situation or use one of the specialized methods of later chapters. Exchangeability is the foundation; check it before you build.
A common misunderstanding “Conformal prediction makes no assumptions — it works on any data.” It makes exactly one assumption: exchangeability. That is a weak assumption, satisfied by ordinary random data splits, but it is not no assumption. It is broken by time-ordered data, by deployment on a population different from the calibration one, and by accidentally reusing calibration data during tuning — which, unfortunately, are three of the most common situations in real projects. The method is assumption-light, not assumption-free.
2.6 A guarantee that holds even with little data
There is one more property of the guarantee that sets conformal prediction apart, and it is easy to appreciate once you know what to contrast it with.
Many promises in statistics and machine learning are of the form “this becomes true as you collect more and more data” — they hold in the limit of infinite data, and are only approximately true for the finite amount of data you actually have. That is cold comfort when your calibration set has 400 examples, because the promise does not quite tell you what happens at 400.
Conformal prediction’s guarantee is not of that kind. It is exact and it holds for any size of calibration set, however small — this property is called being a finite-sample guarantee, meaning it is true for the finite sample you actually possess, not merely in some infinite ideal. If you ask for 90% coverage and your assumptions hold, you get at least 90% coverage whether your calibration set has 50 examples or 50,000. There is no approximation and no waiting for the numbers to settle down.
This does not mean the size of the calibration set is irrelevant — it matters, but in a subtler way than you might expect, and we will quantify it in Chapter 3. The short version, to hold until then: with a small calibration set the guarantee is still true on average, but the coverage you get on any particular occasion can wobble a bit above or below your target, because a small exam is a noisier measure of the model than a large one. With around a thousand calibration examples that wobble becomes small, and the coverage you actually get sits reliably close to the coverage you asked for. More data does not make the guarantee “more true”; it makes the guarantee less variable.
2.7 On average versus every single time
Everything so far has spoken of coverage as an overall rate: “the truth is in the set 90% of the time.” It is important — and it is a frequent source of confusion — to understand exactly what that rate is averaged over, because the guarantee is slightly weaker than a first reading suggests, in a way that occasionally matters a great deal.
The guarantee conformal prediction actually delivers is called marginal coverage, and the word “marginal” here means “averaged over all inputs.” The promise is: across the whole population of inputs you might encounter, taken together, 90% of the prediction sets contain the truth. This is an average over the whole mix of easy and hard cases.
What the guarantee does not promise is that every individual type of input is covered 90% of the time. This stronger property — coverage holding not just overall but within every subgroup of inputs — is called conditional coverage, and here is the uncomfortable fact: for a method that assumes nothing about the data distribution, true conditional coverage is mathematically impossible to guarantee. This is not a shortcoming of present-day techniques that better ones will fix; it is a proven impossibility. You cannot, in general, promise 90% coverage on every kind of input at once without occasionally producing infinitely large sets.
Why does this matter in practice? Because an average can hide a lopsided reality. A system with an honest 90% marginal coverage might be achieving 99% coverage on the common, easy inputs and only 60% coverage on the rare, hard ones — and average out to a perfectly truthful 90%. The system is doing exactly what it promised; it is just that the promise was about the average, and the average was not the thing you cared about. If the rare, hard inputs are the medically dangerous ones, a truthful 90% average is cold comfort.
There is a practical middle path, used constantly in real systems, and it is worth naming now even though we develop it later. If you care about coverage within specific groups — say, you insist on 90% coverage separately for each disease a medical model might diagnose, not merely 90% overall — you can simply run the whole calibration procedure separately within each group, computing a different threshold for each. This gives you a guarantee inside each group and is the standard fix when a single overall average is not good enough. It is called group-conditional coverage, and it is the achievable compromise between the easy-but-sometimes-lopsided marginal guarantee and the impossible perfect conditional one.
The habit to build: the guarantee you get by default is an average. Always ask whether an average is what your problem actually needs, and if it is not, calibrate within the groups that matter and check each one.
A common misunderstanding “90% coverage means each individual prediction I make has a 90% chance of being correct.” Not quite. It means that across many predictions, 90% of the sets contain the truth. Any single set either contains the truth or does not — there is no “90% chance” hiding inside one particular set. Coverage is a property of the long-run behavior of the procedure, not a property of any one output. And that 90% is an average across all input types, which, as just discussed, can hide very different rates for different kinds of input.
2.8 Why the method spread so quickly
We can now collect the reasons conformal prediction went from a niche idea to a standard tool in a few years, because each reason is really a property we have already met, seen from the point of view of an engineer deciding whether to adopt it.
It wraps around any model without needing to look inside it — a deep network, a decision tree, even a paid service you can only send inputs to and receive outputs from. All it ever uses is the model’s outputs on the calibration set, never its internals. It requires no retraining: the model already running in production stays exactly as it is, and conformal prediction is bolted on afterward. It is cheap, costing essentially one pass over the calibration set and a single sort, after which each new prediction costs almost nothing. Its guarantee is a theorem, not a hopeful observation from a test run, which in a regulated industry is a categorically stronger kind of evidence. And its output is understandable by a human expert: “the diagnosis is one of these three, and statements like this are correct 95% of the time” is something a doctor can act on, in a way that “the softmax value was 0.87” never was.
Against these strengths stand the costs we have been honest about throughout: exchangeability must genuinely hold; the guarantee is an average rather than a per-input promise; you must set aside some labeled data for calibration; and a weak underlying model yields large, uninformative sets. None of these costs is hidden, and each has a known remedy or workaround developed in the chapters ahead. That combination — real strengths, honestly-stated costs, known remedies — is what earned the method its place.
Key Takeaways — Chapter 2
Conformal prediction reframes the hard question “how likely is this answer correct?” into the easier question “how strange would this answer make my data look?” — measured against a calibration set the model has never seen.
The method has three steps: grade the model on the calibration set to get a “how badly did it do” score for each example; find the threshold below which your target fraction of those scores fall; and for a new input, keep every candidate answer whose score falls below that threshold. The kept answers are the prediction set.
A quantile is just a cutoff at a chosen position in a sorted list — the 0.9 quantile is the value 90% of the numbers fall below. The threshold is a quantile of the calibration scores.
The central bargain: model quality does not affect whether the 90% guarantee holds, only the size of the sets needed to hold it. A bad model gives valid but huge sets; a good model gives valid and small ones.
The method’s one assumption is exchangeability — that the order of the data carries no information. It is mild but real, and it is broken by time-ordered data, by deployment on a shifted population, and by accidentally reusing calibration data in tuning. Check it before deploying.
The guarantee is exact for any calibration set size (finite-sample), but small calibration sets make the achieved coverage wobble around the target. It guarantees coverage on average across all inputs (marginal coverage); guaranteeing it for every subgroup (conditional coverage) is impossible in general, and the practical fix is to calibrate separately within the groups you care about.
Top comments (0)