Paperlane

no. 7 · Tuesday 3 November 2026

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

Kun He, Zhidan Li and Kuan Yang

math.PR · v2

Abstract

We study approximately uniform sampling of satisfying assignments from random $k$-SAT formulas. Fix a constant $B>0$. For every $k\ge 2^{20}$ and density $0<α\le 2^k/k^{16}$, we prove that, with high probability over a random formula on $n$ variables, every accuracy $n^{-B}\le\varepsilon\le 1/2$ admits a sampler whose output distribution is within total variation distance $\varepsilon$ of the uniform distribution on satisfying assignments with expected running time $$\widetilde O_B\left(\mathrm{poly}(k,α+1)n^{2+η}\right),\quad 0<η\le 2^{16-k}.$$ In particular, the exponent of $n$ is $2+O(2^{-k})$ while the dependence on the width and density is polynomial with a universal degree. This improves the parameter-dependent polynomial exponent of the sampling algorithm of Chen, Lonkar, Wang, Yang, and Yin (STOC 2025) in the density regime $2^k/\mathrm{poly}(k)$. Our algorithm separates a high-degree core from the remaining variables. Every residual formula on the good variables is a deletion subformula of a common bounded-dependency formula. Adapting the rejection–repair framework of Liu, Wang, Yin, Zhang and Zhou (arXiv 2026), we construct an executable sampler for all such residual formulas using ordinary connected violation sets replacing weighted 2-tree witnesses and use it to simulate approximate block heat-bath updates on the core. To analyze the resulting core chain, we integrate out the good variables, represent the core marginal by an absolutely convergent polymer expansion and combine a component-swap variance comparison with an adaptive exploration bound. Absorbing single-component interactions into the local weights leaves interactions of cluster size at least two; retaining their additional decay gives a spectral gap of at least $1/(2s n^{2^{12-k}})$ where $s$ counts core components. Together with the residual sampler, this yields the stated running time.

comments
A revised version with fast expected running time
fields
Probability
pdf ↗ page arXiv:2610.10474 ↗