Why NUTS Chooses a Trajectory Length While Sampling
Hamiltonian Monte Carlo (HMC) moves through a posterior distribution by simulating a trajectory in parameter space. A trajectory that is too short may make only a small move; one that is too long may turn back and retrace ground. Standard HMC therefore requires a path length, usually specified through a number of leapfrog steps. Choosing that number well can be difficult for a Bayesian NLME posterior, whose scales and curvature may vary across fixed effects, random effects, and covariance parameters.
No-U-Turn Sampling (NUTS) addresses this choice by extending a trajectory in stages and checking whether its endpoints indicate that it has begun to double back. The trajectory length is not fixed in advance, but the numerical step size is still fixed for an individual transition. NUTS uses the leapfrog integrator and the posterior gradients described in the earlier material on Hamiltonian Monte Carlo and step size selection.
Hamiltonian States and the No-U-Turn Criterion
Write \(q\) for the vector of unconstrained model parameters and \(p\) for its auxiliary momentum. In an NLME analysis, \(q\) may contain population parameters, transformed standard deviations and correlations, and individual random effects. Let \(U(q)\) be the negative log posterior density, up to an additive constant. With a positive-definite mass matrix \(M\), the kinetic energy is \(K(p)=\tfrac{1}{2}p^\mathsf{T}M^{-1}p\), and the Hamiltonian is \(H(q,p)=U(q)+K(p)\). The velocity in parameter space is \(M^{-1}p\).
At each transition, NUTS draws a momentum from its specified Gaussian distribution and begins with the current position and momentum. It uses leapfrog steps of size \(\epsilon\) to generate additional states. Rather than taking a predetermined number of steps, it constructs a tree: at each stage, it doubles the number of steps by extending from one end of the trajectory, choosing the forward or backward direction. A trajectory with \(2^d\) steps is reached after \(d\) doublings under the depth convention used here; software may differ in how it counts the initial state.
Let \(q^-\) and \(q^+\) be the two endpoint positions after an expansion, and let \(p^-\) and \(p^+\) be their momenta. A standard endpoint stopping criterion checks whether \((q^+-q^-)^\mathsf{T}M^{-1}p^-<0\) or \((q^+-q^-)^\mathsf{T}M^{-1}p^+<0\). If either inequality holds, the tree has begun to turn back and should not be extended further. In recursive implementations, checks are also made within subtrees; the exact bookkeeping can vary by implementation.
This geometric criterion is an indicator of trajectory reversal, not a claim that the posterior has a literal boundary or that a proposal is automatically erroneous. The momentum must be scaled by \(M^{-1}\): testing the displacement against raw momentum instead would generally give the wrong geometry when parameters have different scales.
Why the Endpoint Test Detects a Turn
The criterion follows from how the squared distance between the endpoints changes as the trajectory is extended. Set \(r=q^+-q^-\). If the forward endpoint moves a small time \(dt\) in its local velocity \(M^{-1}p^+\), then the derivative of \(\lVert r\rVert^2\) is \(2r^\mathsf{T}M^{-1}p^+\). If this quantity is negative, extending the forward endpoint would reduce the endpoint separation. Extending the backward endpoint backward in time gives the corresponding derivative \(2r^\mathsf{T}M^{-1}p^-\). A negative value there also indicates that the endpoints are closing rather than separating.
The test is a practical stopping rule for a discrete, approximate trajectory. It does not search for a mathematically unique turning point, and it cannot guarantee that every parameter direction has mixed well. Its role is to prevent continued expansion once the joint trajectory has started to retrace its path.
Worked Example: Checking Whether an Endpoint Expansion Is a U-Turn
Consider a hypothetical two-parameter NLME posterior. At one tree expansion, suppose \(M\) is the identity matrix, \(q^+-q^-=(1.2,-0.4)^\mathsf{T}\), \(p^-=(-0.5,0.2)^\mathsf{T}\), and \(p^+=(0.3,0.1)^\mathsf{T}\). Evaluate the endpoint criterion.
Because \(M^{-1}\) is the identity, the backward-endpoint dot product is \(1.2(-0.5)+(-0.4)(0.2)=-0.60-0.08=-0.68\). The forward-endpoint dot product is \(1.2(0.3)+(-0.4)(0.1)=0.36-0.04=0.32\).
At least one dot product is negative, so the criterion detects a U-turn. NUTS stops extending this tree. The positive forward-endpoint value does not override the negative backward-endpoint value; the stated stopping rule is satisfied when either test is negative.
Building the Tree and Choosing a Proposal
A U-turn test determines when to stop growing the trajectory, but a valid NUTS transition also needs a rule for selecting the next position. In the original slice-based formulation, the algorithm draws a slice level and retains states that satisfy the slice condition. It then selects among eligible states using the algorithm's tree-building rules. Other widely used implementations use multinomial selection, assigning states weights related to their Hamiltonian values. These are different proposal-selection details within the broader NUTS approach; the endpoint stopping idea is common, while implementation details should be checked for the software being used.
It would not be sufficient to build an arbitrary path, stop at a chosen point, and always return its endpoint. NUTS is designed so that trajectory construction, stopping, and candidate selection together preserve the target distribution under the algorithm's conditions. In particular, it relies on a valid target density and gradients, a well-defined momentum distribution, and the reversible, volume-preserving structure of leapfrog integration. Numerical integration is approximate, so energy errors can still matter; NUTS does not remove the need to use a suitable step size.
The tree is built by successive doubling rather than by selecting a single endpoint based on an arbitrary fixed number of steps. Because the number of steps can differ from one transition to the next, NUTS adapts the amount of trajectory exploration to the current simulated path. This does not mean it automatically adapts every feature of the sampler during each transition. In particular, step-size and other warmup adaptation are separate procedures.
Worked Example: Interpreting Tree Depth
Suppose a hypothetical sampler uses a maximum tree depth of 5, with the convention that depth \(d\) permits up to \(2^d\) leapfrog steps. A transition reaches depth 3 and then the U-turn test stops expansion. How many steps were available at the attained depth, and what does that stopping event mean?
At depth 3, the trajectory has been expanded to at most \(2^3=8\) leapfrog steps. The maximum allowed under the depth-5 setting would be \(2^5=32\) steps. Since the U-turn criterion stopped the tree at depth 3, the transition ended because the trajectory began to turn back, not because it exhausted the configured depth limit.
This count describes the tree's step budget under the stated convention; it is not a universal reporting convention for every software package. Check the software documentation before translating a displayed depth into an exact number of integrator steps.
Tree Depth and Maximum-Depth Warnings
Tree depth records how many rounds of doubling have been performed, not the number of posterior parameters, the number of NLME subjects, or a direct measure of convergence. A greater depth generally means more leapfrog computation in that transition. A warning that the maximum tree depth was reached means the algorithm hit its configured expansion cap before its usual U-turn stopping rule ended the expansion. It does not, by itself, prove that the returned draw is invalid or that the chain has failed.
Repeated warnings are useful evidence that the current settings often truncate trajectory growth. They may mean that the posterior requires long trajectories at the chosen step size and mass matrix, that the geometry is difficult, or simply that the depth cap is restrictive for this model. The warning alone cannot distinguish these explanations. It is also not equivalent to a divergence warning: maximum depth concerns how far the tree was allowed to grow, whereas a divergence concerns a numerical integration failure. The later material on divergent transitions treats that separate diagnostic.
When warnings occur, begin by checking the model parameterization, scaling, prior calibration, and mass-matrix choices, and confirm that the depth setting is understood for the software in use. Examine whether the warnings are occasional or frequent and whether they concentrate in particular chains or regions of the posterior. Increasing the depth limit can allow longer trajectories, but it increases computation and does not repair poor geometry or an unsuitable step size. A larger limit is not automatically a better sampler.
Tree depth is also not a stand-alone measure of sampling quality. A run without maximum-depth warnings may still explore poorly, and a run with a few warnings may still produce useful draws. It must be interpreted alongside other evidence about sampling and posterior exploration, rather than as a pass/fail test.
Worked Example: Interpreting Repeated Maximum-Depth Warnings
In a hypothetical NLME analysis, the sampler is configured with maximum tree depth 4. Under the convention used here, that permits up to \(2^4=16\) leapfrog steps. Out of 1,000 post-warmup transitions, 120 reach depth 4. What can be concluded, and what should be checked next?
The observed fraction is \(120/1000=0.12\), or 12%. These 120 transitions reached the configured cap, so they stopped expanding because of the limit rather than because the usual U-turn rule had stopped them sooner. This is frequent enough to investigate rather than ignore.
The result does not establish that 12% of the draws are invalid, that the posterior is biased, or that the chain has failed. A reasonable next step is to check parameter scaling and the mass matrix, review the model's parameterization and prior calibration, and inspect whether the warnings cluster in particular chains or parts of the run. Raising the depth limit may be considered if longer trajectories are justified, but the cost and the effect on warnings should then be assessed. The warning count alone does not diagnose the underlying cause.
Common Mistakes and Practical Limits
- Assuming NUTS eliminates all tuning. It removes the need to choose one fixed path length in advance. It still depends on an appropriate step size, a suitable parameter scaling, and valid model gradients.
- Treating maximum depth as the U-turn point. Reaching the cap means the sampler stopped expanding because it was not permitted to go deeper. The U-turn criterion may not yet have been met.
- Reading depth as a convergence statistic. Depth describes trajectory construction and computation. It does not, on its own, show whether the chain has adequately explored the posterior.
- Increasing the cap without investigating. A higher cap can permit longer trajectories, but cannot by itself fix difficult posterior geometry, poor scaling, or numerical problems.
The principal alternative is fixed-length HMC, where the analyst chooses the number of leapfrog steps before the transition. This gives direct control of path length but requires a useful choice that works across the posterior. NUTS replaces that single choice with a trajectory-building and stopping procedure, at the cost of a more involved transition and potentially substantial computation for deep trees. Neither approach guarantees good exploration when the model's posterior geometry is problematic.
Check Your Understanding
Answer each question, then compare your reasoning with the solutions below.
- Why does NUTS use \(M^{-1}p\), rather than \(p\) alone, in its endpoint criterion?
- For \(q^+-q^-=(2,1)^\mathsf{T}\), \(M=I\), \(p^-=(-0.2,0.1)^\mathsf{T}\), and \(p^+=(0.1,0.3)^\mathsf{T}\), does the endpoint criterion detect a U-turn?
- Under the depth convention in this tutorial, how many leapfrog steps are available at depth 6?
- What does it mean if a transition reaches maximum tree depth without the usual stopping rule ending expansion?
- Name two checks to make when maximum-depth warnings recur. Why is simply raising the limit not a complete diagnosis?
Solutions. (1) The velocity in parameter space is \(M^{-1}p\); mass-matrix scaling determines how momentum moves the position, so the unscaled momentum does not generally give the correct geometric test. (2) The backward dot product is \(2(-0.2)+1(0.1)=-0.3\), which is negative. The forward dot product is \(2(0.1)+1(0.3)=0.5\). Since either negative value triggers the criterion, a U-turn is detected. (3) \(2^6=64\) steps. (4) The expansion cap, rather than the usual U-turn stopping rule, ended tree growth; the warning alone does not establish that the draw is invalid. (5) Check parameter scaling or mass-matrix choices and review parameterization or prior calibration. Raising the limit may allow longer trajectories but does not explain or repair difficult geometry, and it can increase computation.