no-u-turn sampler (nuts)
No-U-Turn Sampler (NUTS) is an adaptive extension of Hamiltonian Monte Carlo that automatically tunes the trajectory length by building a balanced binary tree of leapfrog steps and stopping when the trajectory begins to turn back on itself (a "U-turn"), eliminating HMC's most critical and difficult-to-tune hyperparameter. NUTS also adapts the step size during warm-up to achieve a target acceptance rate, making it a nearly tuning-free MCMC algorithm.
Why NUTS Matters in AI/ML:
NUTS removes the primary barrier to practical HMC usage—trajectory length tuning—making efficient gradient-based MCMC accessible to practitioners without expertise in sampler configuration, and enabling it as the default algorithm in probabilistic programming frameworks like Stan, PyMC, and NumPyro.
• U-turn criterion — NUTS detects when a trajectory starts returning toward its origin by checking whether the dot product of the momentum with the displacement (p · (θ - θ₀)) becomes negative, indicating the trajectory has begun to curve back and further simulation would waste computation
• Doubling procedure — NUTS builds the trajectory by repeatedly doubling its length (1, 2, 4, 8, ... leapfrog steps), alternating between extending forward and backward in time; this exponential growth efficiently finds the right trajectory length without trying every possible value
• Balanced binary tree — The doubling procedure creates a balanced binary tree of states; the next sample is drawn uniformly from the set of valid states in the tree (those satisfying detailed balance), ensuring proper MCMC semantics
• Dual averaging step size adaptation — During warm-up, NUTS adjusts the step size ε using dual averaging (Nesterov's primal-dual method) to achieve a target acceptance probability (typically 0.8 for NUTS), automatically finding the largest stable step size
• Mass matrix estimation — NUTS estimates the posterior covariance during warm-up to construct a diagonal or dense mass matrix that preconditions the Hamiltonian dynamics, matching the sampler's geometry to the posterior shape
| Feature | NUTS | Standard HMC | Random Walk MH |
|---|---|---|---|
| Trajectory Length | Automatic (U-turn) | Manual (L steps) | 1 step |
| Step Size | Auto-tuned (warm-up) | Manual or auto | Auto (proposal scale) |
| Gradient Required | Yes | Yes | No |
| Mixing Efficiency | Excellent | Good (if well-tuned) | Poor |
| Tuning Required | Minimal (warm-up iterations) | Significant (ε, L) | Moderate (proposal) |
| ESS per Gradient | High | Variable | Very Low |
NUTS is the breakthrough algorithm that made gradient-based MCMC practical for everyday Bayesian analysis, automatically adapting trajectory length and step size to achieve near-optimal sampling efficiency without manual tuning, establishing itself as the default MCMC algorithm in modern probabilistic programming and enabling routine Bayesian inference for complex hierarchical models.