What is No-U-Turn Sampler?
No-U-Turn Sampler is an adaptive Hamiltonian Monte Carlo algorithm that builds a reversible trajectory and stops expanding it when continued motion begins to double back toward previously explored states.
Quick Facts
| Specification | Official Specification |
|---|
How It Works
Stop before a Hamiltonian trajectory turns back
For trajectory endpoints q_minus and q_plus with momenta p_minus and p_plus, the Euclidean U-turn check examines whether the displacement has negative inner product with either endpoint momentum. If so, continuing is unlikely to explore new territory efficiently.
Hoffman and Gelman's NUTS paper builds trajectories by recursive doubling and samples from valid states without favoring points merely because they appeared earlier in tree construction. The original method also introduces dual-averaging step-size adaptation.
Adapt trajectory length without eliminating tuning
NUTS adapts how long each trajectory runs, but step size and mass matrix still determine numerical stability and geometry. Modern implementations learn them during warmup. A small step size can make each transition expensive; a poor metric can force long trees; a large step size can create divergences before a useful U-turn is reached.
Maximum tree depth is a computation guard, not a convergence target. Frequent saturation means trajectories are being truncated or exploration is inefficient; increasing the limit may only spend more compute unless the model and parameterization are also examined.
Read NUTS diagnostics as a joint contract
The Stan reference implementation combines NUTS with warmup adaptation and reports divergences and trajectory-depth behavior. Diagnose those warnings together with rank-normalized split R-hat, bulk and tail ESS, Monte Carlo error, energy behavior, and multiple-chain traces.
NUTS can still miss isolated modes, struggle with funnels or heavy tails, and cannot directly update discrete parameters. Reparameterization and model revision are often more effective than merely requesting more iterations.
Key Characteristics
- Adapts HMC trajectory length during each transition
- Detects retracing with endpoint displacement and momentum
- Builds candidate states through reversible tree expansion
- Usually adapts step size and metric during warmup
- Reports divergences and maximum tree-depth events
- Still requires continuous differentiable target parameters
Common Use Cases
- Default continuous-parameter sampling in probabilistic programs
- Hierarchical Bayesian models after reparameterization
- Posteriors where a fixed HMC path length is hard to tune
- Automated inference requiring robust trajectory selection
- Reference posterior sampling for approximation validation
Example
Loading code...Frequently Asked Questions
What problem does NUTS solve in Hamiltonian Monte Carlo?
Standard HMC requires a fixed leapfrog-step count or integration time. Too short produces random-walk behavior and too long wastes work by retracing. NUTS adapts trajectory length by detecting U-turns during reversible tree expansion.
Does NUTS eliminate all HMC tuning?
No. It removes manual path-length selection, but step size and mass matrix still need adaptation or configuration. Warmup length, target acceptance, maximum tree depth, initialization, and parameterization remain consequential.
What does reaching maximum tree depth mean?
It means expansion stopped at the configured computation limit before satisfying the ordinary stopping behavior. Occasional events may be tolerable, but frequent saturation calls for efficiency and geometry investigation rather than an automatic larger limit.
Are NUTS divergences harmless rejected proposals?
No. A divergence indicates that numerical integration failed to follow local posterior geometry accurately and can correspond to biased exploration. Locate affected regions and consider smaller steps, reparameterization, stronger priors, or model revision.
Can NUTS guarantee discovery of every posterior mode?
No. Gradient trajectories can remain within one isolated mode. Use dispersed chains, domain-informed initializations, predictive checks, R-hat and ESS, and specialized multimodal methods when mode separation is plausible.