No-U-Turn Sampler: Adaptive HMC Trajectory Doubling

No-U-Turn Sampler

Step size ε 0.12

Max tree depth 6

Live Stats

Samples drawn

Tree depth (last)

–

Leapfrog steps (last)

–

Avg depth

–

How it works

NUTS targets a posterior p(θ) by simulating a physical particle on the energy surface U(θ) = −log p(θ), with an auxiliary momentum r and total energy H(θ,r) = U(θ) + ½|r|². Each proposal starts by resampling r ~ N(0,I), then integrates Hamilton's equations with the leapfrog scheme:

r(½) = r − (ε/2)∇U(θ)
θ'   = θ + ε·r(½)
r'   = r(½) − (ε/2)∇U(θ')

Plain HMC fixes a trajectory length L in advance — too short wastes the gradient information, too long doubles back and wastes computation. NUTS removes that tuning knob: it builds a balanced binary tree of leapfrog steps, doubling the trajectory in a random direction (forward or backward) at each level, until the endpoints start turning back toward each other:

stop when (θ⁺ − θ⁻)·r⁻ < 0  or  (θ⁺ − θ⁻)·r⁺ < 0

That is the "no U-turn" criterion — the moment the path would start retracing itself. A sample is then drawn from the states visited along the tree, weighted so the final draw is still a valid sample from p(θ), with no Metropolis rejection of whole trajectories needed.

Draw Sample — runs one NUTS iteration from the current chain position: watch the tree grow (cyan path) across the curved posterior ridge until it self-terminates.
Auto-Sample — keeps drawing automatically so the accumulated samples (violet dots) trace out the true shape of the posterior.
ε (step size) — smaller steps track curvature more faithfully but need more leapfrog evaluations per doubling; larger steps risk numerical divergence.
Max tree depth — a safety cap on how many times the trajectory can double (2^depth leapfrog steps in the worst case) if no U-turn ever triggers.

This is the exact algorithm (Hoffman & Gelman, 2014) that powers Stan, PyMC and NumPyro — the standard engines behind most real Bayesian model fitting today. The bent "banana" ridge below is a classic torture-test posterior: its curving valley is exactly what defeats naive random-walk Metropolis but NUTS glides along with ease.

Drawn samples Leapfrog tree path Current chain position

⚠ Couldn't load the 3D engineThree.js failed to load from the CDN. Check your connection and reload.