When we work with machine learning models, we constantly turn probabilities into discrete choices.

Which ad do we show? Which action do we sample in a reinforcement learning policy? Which word comes next in a language model?

All these problems share the same core operation:

We have a list of options, each with an associated probability, and we want to randomly pick one option according to those probabilities.

There is a very common way to do this (using cumulative sums and a uniform random number), but one could instead imagine an algorithm that looks like this:

Independently noise each option’s score, then simply take the argmax of the noised scores.

Here it is not obvious that there is even a “right” way to noise the scores so that we get exactly the correct distribution. It turns out there is one, known as the Gumbel-Max trick:

1. Take the log of the scores (or probabilities) for each category.
2. Add independent Gumbel noise to each log-probability.
3. Pick the index with the largest noisy log-probability.

The magic is that the index you get is exactly a sample from the categorical distribution defined by your original probabilities.

Here, if you have no idea what a “Gumbel” variable is, don’t worry. It is just a specific distribution on a continuous random variable; we will get back to it later.

And there is more: we can also draw several samples without replacement from the same categorical distribution with the same trick. For that, simply return the items ordered by their decreasing noisy score. That’s all.

The figure below illustrates the sampling on an example:

The usual proof that Gumbel-Max works consists of computing some ugly integrals involving the Gumbel pdf, to conclude after a page of calculus that “it outputs each item with the right probability”. But this proof gives no intuition about why it works.

In this post, I will:

1. Reformulate the Gumbel-Max trick with the more commonly used exponential distribution, to get an “exponential-min trick”.
2. Link the exponential to arrival times, using a simple Autobus / Bike / Car example, to get an intuitive explanation of why it works.
3. Explain why sorting the noisy scores gives sampling without replacement.

From the Gumbel-Max trick to the Exp-Min trick

I have personally never encountered a “Gumbel” random variable except in this “Gumbel-Max trick”. Fortunately, we can define it using the more familiar Exponential distribution.

Gumbel: What is it?
Take an exponential random variable with rate 1, written X ~ Exp(1). Define:

G = −log X

Then G has the standard Gumbel distribution.

As a reminder, one way to generate X ~ Exp(1) is:

• draw U ~ Uniform(0, 1)
• set X := −log U

This means G can be sampled as G := −log(-log(U))

Let’s see how we can use this definition to reformulate the Gumbel-Max trick without ever mentioning Gumbel again

Gumbel-Max trick algorithm:

• Draw an independent Gumbel Gᵢ for each item i.
• Return: Argmaxᵢ [ log pᵢ + Gᵢ ].

From the Gumbel definition: Gᵢ = −log Xᵢ with Xᵢ ~ Exp(1)

Noting that:

• log pᵢ + Gᵢ = −log(Xᵢ / pᵢ).
• −log(·) is strictly decreasing,

therefore the index that maximizes (log pᵢ + Gᵢ) is the same index that minimizes (Xᵢ / pᵢ). So we obtain the Exp-Min trick:

• Draw independent Xᵢ ~ Exp(1) for each item i.
• Return: Argminᵢ [ Xᵢ / pᵢ ].

This algorithm is clearly equivalent to the Gumbel-Max trick. We will now explain why it works by interpreting Xᵢ / pᵢ as the first arrival time for category i.

1. Counting passing vehicles

To explain why this sampling trick works, we will consider a seemingly unrelated setting in which the categorical distribution arises naturally:

We observe vehicles passing by and assume that on this street there are:

• Autobus: on average 10 per hour
• Bikes: on average 60 per hour
• Cars: on average 30 per hour

We assume:

• Arrivals are random and uniform in time.
• What happens in disjoint time intervals is independent.

Formally, the arrivals of Autobuses follow a Poisson process with rate λa = 10 per hour (similarly for Bikes and Cars).

• This means that in any time interval of length t hours, the number of passing buses is a Poisson random variable with mean 10·t.

If you don’t know what a Poisson process is, we can instead use the following discrete approximation:

• During each second, there is a probability p that an Autobus passes.
• “10 Autobuses per hour on average” means: p = 10 / 3600.
• What happens at any second is independent of what happens before or after.

We could refine this approximation by using smaller time steps (milliseconds, microseconds, …); the Poisson process is what we get when letting the time step tend to 0.

We thus have 3 independent Poisson processes defining the arrivals of Autobuses, Bikes, and Cars, with per‑second probabilities roughly:

• Autobus: 10 / 3600
• Bike: 60 / 3600
• Car: 30 / 3600

What is the probability that the first passing vehicle is an Autobus?
Intuitively, since all arrivals are independent, the chance that a bus is the first kind of vehicle we see should be proportional to how many buses arrive per hour.

So: P(“Autobus first”) = 10 / (10 + 60 + 30) = 0.1.

This is exactly the categorical distribution of our first example:

• Autobus: 0.1
• Bike: 0.6
• Car: 0.3

Key idea one:
The first passing vehicle is a sample from a categorical distribution with probabilities proportional to the arrival rates (vehicles per hour).

If you are not convinced that this is true: 
Let’s further assume that there are 10 lines of buses, 60 colors of bikes, and 30 brands of cars, for a total of 100 sub-categories; and that in each sub-category the arrivals follow a Poisson process with rate “one per hour“. This is compatible with the previous description, because the sum of independent Poisson processes is still a Poisson process (i.e., the Poisson process counting buses is the sum of the processes counting each bus line). By symmetry, it should be clear that each sub-category has the same chances to be the first, so 1%. Then the probability of observing “a bus first“ is 10 times the probability of one sub‑category, and thus 0.1.

2. Sampling the first arriving item by sampling arrival times

From time “0”, we can look at the first arrival time for each vehicle type:

• Ta: time of the first Autobus
• Tb: time of the first Bike
• Tc: time of the first Car

The event “Autobus is the first vehicle” is exactly:

P(“Autobus first”) = P( Ta = minᵢ Tᵢ ).

Note: In the discrete “per-second” model, two vehicles might arrive in the same second, which complicates things. But this is an artifact of the discretization: in the continuous-time Poisson model, the probability that two vehicles arrive exactly at the same time is 0, so we can safely ignore ties.

Because arrivals of each vehicle type are independent, these arrival times are independent.

Key idea two:
We can sample directly the arrival times Ta , Tb and Tc of each vehicle types

The type with the lowest arrival time is a sample of ‘the first passing vehicle’, and thus a sample from a categorical distribution with probabilities proportional to the arrival rates (vehicles per hour).

All we need to know is the shape of the distributions of Ta, Tb, and Tc.

3. Law of first arrival time

Property (law of first arrival time).
Let Ta be the time of the first Autobus when the rate is λa = 10 per hour.

Then: Ta is an exponential variable of Exp(λ = 10).
That is: P(Ta > t) = exp(−10 t), for t ≥ 0.

Sketch of proof (optional calculus):

In the per-second model, the probability of a bus in a given second is p = 10 / 3600.

The probability of seeing no bus in the first n seconds is: (1 − p)^n.

Time t in hours corresponds to n = 3600 · t seconds, so:

P(Ta > t) ≈ (1 − p)^n = (1 − 10 / 3600)^(3600 t).

If instead of discretizing per second, we make the time step (here 1/3600) go to 0, this expression converges to: exp(−10 t).

This is exactly the survival function of an exponential variable with rate ’10 per hour’.

Of course, the same holds for Bikes and Cars, with their respective rates.

Let us also note that Exp(λ = 10) = Exp(λ = 1)/10 .

Indeed, let X ~ Exp(1). Then P(X / 10 > t) = P(X > 10 t) = exp(−10 t).

We can thus sample the arrival time of the first bus like this:

• Draw Xa ~ Exp(1)
• Return: Xa / 10

4. Exp-Min trick as sampling the first arrival

Putting together the algorithm idea of section 2 and the result of section 3, we get the following:

Sampling time of arrival and returning the category arriving first:

• Draw independent variables Xa, Xb, Xc ~ Exp(1)
• Let the times of arrival of the first autobus, bike, and car be: 
  Ta := Xa / 10
  Tb := Xb / 60
  Tc := Xc / 30
• Return the category with the least arrival time

By the property of Section 1, the output of this algorithm follows the desired categorical distribution on A, B, and C.

Now compare this to the “Exp-Min trick” defined before: it is exactly the same algorithm! 🤯

Conclusion: the Exp-Min trick works because it samples the first arrival times Ti for each category and returns the category arriving first.

Similarly, the Gumbel-Max trick samples −log Tᵢ and returns the category with the highest value.

5. Sampling several items without replacement

Now, assume the first vehicle was a bus, arriving one minute after we started to wait. We now ignore all buses after that, and wonder whether we will then observe a Bike before a Car.

Because in our model, what happens after “t = one minute” is independent of what happened before, this conditioning changes nothing (this is often formulated as saying that Poisson processes are memoryless).

So the probability that Bike beats Car next is still:

P(“first Bike before first Car” | “both arrive after first Autobus”) = 60 / (60 + 30). Let us note that this is exactly the conditional probability of sampling a Bike as the second item, given that the first was an Autobus, when we take several samples without replacement.

And of course, the event “first Bike before first Car” is equivalent to 
Tb < Tc.

This means that the category corresponding to the second smallest arrival time is a sample from the categorical distribution restricted to the remaining items.

More generally, if we sort categories by their sampled arrival times Tᵢ, we obtain a random permutation where the first element is a sample from the full categorical distribution, the second is a sample from the distribution restricted to the remaining items, and so on.

That is exactly sampling without replacement.

This explains why, in the Gumbel-Max version, if we add Gumbel noise once to each log pᵢ , and then sort categories by their noisy scores, we obtain several samples without replacement from the original categorical distribution.

…and why is it useful?

At first sight, Gumbel‑Max looks like a convoluted way to do something we can already do with a uniform random number and a cumulative sum. So why should we care?

• It is sometimes an efficient choice for sampling, for example, in https://arxiv.org/pdf/1903.06059
• It is sometimes used as a reparametrisation trick to make a model learnable (turning a discrete sampling step into a differentiable operation, via the “Gumbel‑Softmax” or related tricks).
• And it can be useful for otherwise intractable computations. A nice example is computing the probability that an item is among the first (K) samples when sampling without replacement from a multinomial, as in https://harrieo.github.io/files/2025-consequences-propensities.pdf

This last use case is the one I was interested in at Criteo: building a counterfactual estimator for our recommender system, which requires computing exactly those probabilities. But the details would take us too far for this blog post!

Finally, here is a small exercise:

You have a stream of incoming items, each with an associated weight, which you see one by one.
The stream is very large, and you cannot remember or store all the items (you can only store a few).
Once you have seen all the items, you must return two of them, sampled without replacement from the categorical distribution defined by the weights.

Can you do it with the Gumbel‑Max trick? 🤔
Can you do it without the Gumbel‑Max trick (or the equivalent Exp‑Min trick)? Good luck — this one is not simple. 😅