Fast Almost-Uniform Sampling of Random k-SAT Solutions

Abstract

We study approximately uniform sampling of satisfying assignments from random k-SAT formulas. Fix a constant B>0. For every k≥ 2²⁰ and density 0<α≤ 2^k/k¹⁶, we prove that, with high probability over a random formula on n variables, every accuracy n^−B≤ε≤ 1/2 admits a sampler whose output distribution is within total variation distance ε of the uniform distribution on satisfying assignments with expected running time Õ_B(poly(k,α+1)n^2+η), 0<η≤ 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/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.

Random Sampling of Almost Periodic Stochastic Processes
David Berger, Maximilian Strobel
arXiv16 Oct 2026PreprintCC BY 4.0Full textProbabilityarXiv
Non-Uniform Random Scans in Gibbs Sampling and CAVI
Sam Power
arXiv1 Sep 2026PreprintCC BY 4.0Full textStatisticsarXiv
Quasi-uniform designs from random candidates: optimal candidate complexity and farthest-point sampling
Takashi Goda, Hengjun Xu
arXiv5 Sep 2026PreprintCC BY-NC-ND 4.0Full textNumerical analysis & scientific computingarXiv
Efficient sampling of the unlabeled structure of uniform random mappings and surjections
Arnaud Carayol, Pablo Rotondo
arXiv15 Oct 2026PreprintCC BY 4.0Full textProbabilityarXiv
Uniform oscillation properties of almost periodic functions
Alain Haraux
HAL4 Oct 2026PreprintLicence Ouverte 2.0Full textAnalysis & PDEsHALarXiv

Cite

BibTeX RIS

BibTeX

@misc{he2026fast,
  title = {{Fast Almost-Uniform Sampling of Random $k$-SAT Solutions}},
  author = {Kun He and Zhidan Li and Kuan Yang},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.10474},
  eprint = {2610.10474},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.10474},
  note = {CC BY 4.0},
}

RIS

TY  - UNPB
TI  - Fast Almost-Uniform Sampling of Random k-SAT Solutions
AU  - Kun He
AU  - Zhidan Li
AU  - Kuan Yang
PY  - 2026
DA  - 2026/10/07
PB  - arXiv
DO  - 10.48550/arxiv.2610.10474
UR  - https://arxiv.org/abs/2610.10474
AB  - We study approximately uniform sampling of satisfying assignments from random k-SAT formulas. Fix a constant B>0. For every k≥ 2^20 and density 0<α≤ 2^k/k^16, we prove that, with high probability over a random formula on n variables, every accuracy n^−B≤ε≤ 1/2 admits a sampler whose output distribution is within total variation distance ε of the uniform distribution on satisfying assignments with expected running time Õ_B(poly(k,α+1)n^2+η), 0<η≤ 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/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.
ER  -

Abstract

Related

Cite