This post is from Bob
This one’s a big deal.
Bou-Rabee, Nawaf. 2026. Persistence Pays: Square-root condition-number dependence for Metropolis-adjusted kinetic Langevin Monte Carlo with a non-reversibly updated accept/reject uniform. arXiv 2610.35781.
Abstract: We prove accelerated mixing for a Metropolis-adjusted kinetic Langevin sampler: the OBABO splitting with friction 2 * sqrt(m), adjusted with Neal’s non-reversibly updated uniform, which is redrawn after every epoch of E steps. For targets exp(−U) on ℝ^d with m * I ⪯ ∇^2 U ⪯ L * I and an L_H-Lipschitz Hessian, started from a Gaussian at an approximate minimizer, the chain reaches total variation accuracy ε after Õ(sqrt(κ * d) + sqrt(L_H) * (d/m)^0.75) gradient evaluations, where κ=L/m and Õ hides logarithmic factors. The sqrt(κ) term is necessary, already on Gaussian targets. The proof discretizes Lu’s entropic hypocoercivity by means of an entropy inequality for free transport, so that the relative entropy of the unadjusted chain decays at a rate of order sqrt(m) up to a discretization bias. With the non-reversibly updated uniform, the leading energy errors of velocity Verlet telescope along a path. A coupling argument combines the two. On Bayesian logistic regression posteriors for two standard data sets, which satisfy these assumptions, the gradient cost of the chain with the non-reversibly updated uniform grows roughly like the square root of the condition number at the posterior mode, and that of standard adjusted OBABO roughly like its 3/4 power.
Note the square-root in the condition-number dependence. This is the tightest result we know for a discrete-step, adjusted sampler (i.e., one we can implement as a black-box). The full set of concavity and Lipschitz assumptions are in the abstract above (strongly log concave, Lipschitz in the Hessian). For what it’s worth, Claude (5.5 medium effort) concurs that nobody has proved a result this tight in condition number before.
The scales here get confusing, pardon my pun, so let’s establish some intuition from simple cases (skip this paragraph and the next if you know condition numbers). Suppose we have a multivariate normal distribution. The Hessian (matrix of second partial derivatives) of the negative log density is constant around the density and equal to the inverse of the covariance matrix. In general (i.e., not just for normals) for a point that is log concave (i.e., the Hessian is positive definite), the condition number is the ratio of the largest eigenvalue of that Hessian to the smallest eigenvalue. To simplify even further, suppose the covariance is diagonal, so that Sigma[m,m] represents the variance of variable m and all the off diagonal entries are zero (i.e., zero correlation). In that case, the eigenvalues are just the Sigma[m,m] and the condition number is just the ratio of the largest eigenvalue to the smallest eigenvalue. The problem for sampling with algorithms like random-walk Metropolis, Langevin, or Hamiltonian Monte Carlo, is that their run time is multiplied by the condition number. For a standard normal, where Sigma[m,m] is 1 for every m, the condition number is 1, and that’s the fastest we can get, because condition numbers are >= 1 by construction. That’s why we try to precondition our target posteriors with mass matrixes to make them (or their gradients in the case of Nutpie) look more normal (e.g., with non-centered parameterizations).
Why is posterior exploration time proportional to the condition number? It’s because we have to set the step size to accommodate the direction of highest curvature, then we have to take a number of steps traverse the scale of the direction of lowest curvature. For all of these samplers, traversing a distance takes quadratic time. So the algorithm is quadratic in the ratio of scales, which makes it linear in the condition number.
This is why reducing the condition number is so appealing. Sparse NUTS, from Cole Monnahan, works exceptionally well for mixed-effects models by preconditioning with a sparse Hessian located at the max marginal likelihood estimate (e.g., the estimate produced by lme4 or TMB). Note to Stan devs: We should adapt this for brms through TMB—it’s too model specific for Stan and we don’t have the linear algebra tools we need built into C++.
Why is this paper such a breakthrough? The assumptions on which the guarantee is based are standard in theoretical work, namely that the density must be strictly log concave with Lipschitz-bounded Hessians. Bou-Rabee establishes that generalized Hamiltonian Monte Carlo with one step (aka “kinetic Langevin”) has run time that grows only with the square root of the condition number! This kinetic or generalized part of the algorithm refers to the way momentum is refreshed. Rather than fully refreshing momentum, a new momentum is taken and averaged with the existing momentum at a fixed mixing rate (which could presumably be randomized, but not made dependent on state). The bottom line is that run time for a fixed level of accuracy grows with the ratio of scales (i.e., the square root of the condition) rather than the ratio of squared scales (i.e., the condition number). And unlike something like NUTS or WALNUTS, swapping in a new acceptance probability sequence couldn’t be much easier to implement.
Why is this a big deal? The main obstacle to Stan’s sampling, as I’ve just realized while building Walnuts and Walnutpie and evaluating on a ton of real-world models, is that the condition number remains high in most posteriordb models and models Andrew’s suggested, even after diagonal preconditioning with a mass matrix using either the NUTS or Nutpie divergence target. A ratio of scales as low as 10 will cause a 100-fold slowdown in sampling. That is, if I sample normal(0, diag_matrix([1, 10]’)) in Stan, it’s 100 times slower than if I sample normal(0, diag_matrix[1, 1]). The low-rank and diagonal approach from Nutpie helps here where it’s stable, but so far I haven’t found it to be as stable as the diagonal preconditioned in my evaluations.
The algorithm that Bou-Rabee analyzed was introduced by Radford Neal in the following paper, which I thought I had discussed here before, but can’t find any trace.
Neal, Radford. 2020. Non-reversibly updating a uniform [0,1] value for Metropolis accept/reject decisions. arXiv 2001.11950.
This paper is typical of Neal’s paper, introducing a very simple idea with a profound effect that’s explained so that a beginner can understand it and code it. We used it as a reference for my work with Gilad Turok and Chirag Modi (and also Alex Barnett) on delayed rejection generalized HMC, which I’ve blogged as Multiscale generalized HMC with delayed rejection.
I’m still a bit confused about how the regular condition number works compared to the one Langmore et al. generated for normal targets in HMC, which I blogged about as Condition numbers for HMC and the funnel. Nawaf told me before that Langmore’s work was only for normals, but it still seems relevant.
I better get busy adding this algorithm to Walnutpie. I’d planned to do it at some future date, but it looks like this is probably the sampler we should be using everywhere. Stay tuned for more evaluation.





