Fast Almost-Uniform Sampling of Random $k$-SAT Solutions

We study approximately uniform sampling of satisfying assignments from random $k$-SAT formulas. For every sufficiently large $k$ and density $0<\alpha \le 2^k\mathrm{/}{k}^{16}$, we prove that, with high probability over the formula, there is a sampler whose output distribution is within total variation distance $\epsilon$ of the uniform distribution on satisfying assignments and whose expected running time is at most $(nk(\alpha +1)\mathrm{/}\epsilon {)}^C$, for a universal constant $C$. Our algorithm improves the counting and sampling algorithms obtained by Chen, Lonkar, Wang, Yang, and Yin (STOC 2025) at the density $2^k\mathrm{/}\mathrm{poly}(k)$ with running time $(n\mathrm{/}\epsilon {)}^{\mathrm{poly}(k,\alpha )}$. Our result achieves this density region for sampling with a polynomial degree independent of both the width and the density. Our algorithm separates a high-degree core from the remaining variables, and combines a recursive sampler for the residual formulas with approximate block heat-bath updates on the core. We adapt the recursive insertion-chain framework of Jain, Mizgerd, and Pham (2026) from $2$-trees to ordinary connected violation sets. Expansion and random literal signs yield uniform moment bounds for the resulting correlated lists across all residual formulas, allowing the signed-flow analysis to give a universal polynomial running-time degree. A polymer expansion and an exploration bound establish a polynomial spectral gap for the core dynamics.