Counting and sampling random $k$-SAT up to the clustering threshold: does the tractability boundary for counting and sampling coincide with the search threshold?

For random $k$-SAT at clause density $\alpha$, the satisfiability threshold is known to be $2^k\ln 2-(1+\ln 2)/2+o_k(1)$ for large $k$, and the best search algorithms find satisfying assignments up to $(1-o_k(1))\,2^k\ln k/k$ — the density at which statistical physics predicts the solution space fragments into exponentially many well-separated clusters (the clustering threshold $\alpha_{\mathrm{clust}}$). Chen, Lonkar, Wang, Yang, and Yin (STOC 2025) gave the first efficient approximate-counting and almost-uniform-sampling algorithms for random $k$-SAT up to densities $\alpha\le 2^k/k^c$ for an undetermined constant $c$, together with the first rigorous proofs of replica symmetry and non-reconstruction at such densities, and posed the central question of whether counting and sampling are tractable all the way up to the algorithmic threshold for searching. The question remains open in both its algorithmic and structural strands: no algorithm improves the $2^k/\mathrm{poly}(k)$ regime toward $2^k\ln k/k$, no intractability result separates counting or sampling from search below the clustering threshold for any sparse random constraint satisfaction problem, and the clustering and condensation thresholds of random $k$-SAT remain unlocated rigorously.

Background

Random $k$-SAT is the canonical random constraint satisfaction problem (CSP). A random formula $\Phi\sim\Phi(k,n,\lfloor\alpha n\rfloor)$ has $n$ Boolean variables and $m=\lfloor\alpha n\rfloor$ clauses, each clause consisting of $k$ literals chosen independently and uniformly at random; $\alpha$ is the clause density. The satisfiability threshold $\alpha_{\mathrm{sat}}$ is the critical density below which a satisfying assignment exists with probability tending to 1 as $n\to\infty$; the Satisfiability Conjecture, confirmed for sufficiently large $k$ by Ding, Sly, and Sun, gives $\alpha_{\mathrm{sat}}=2^k\ln 2-(1+\ln 2)/2+o_k(1)$. For the algorithmic problem of finding a solution, the best efficient algorithm (Coja-Oghlan) works up to $(1-o_k(1))\,2^k\ln k/k$, and message-passing schemes are proved to fail beyond that density, so $2^k\ln k/k$ is believed to be the algorithmic threshold for search. Statistical physics, via the non-rigorous cavity method of message-passing heuristics (Krzakala, Montanari, Ricci-Tersenghi, Semerjian, and Zdeborová), predicts that this same density marks a geometric transition: below the clustering threshold $\alpha_{\mathrm{clust}}\approx 2^k\ln k/k$ the set of solutions forms a single giant, well-connected component, while above it the solutions shatter into exponentially many clusters separated by linear Hamming distance, with frozen variables (variables taking a fixed value throughout a cluster) and long-range correlations between distant variables; at the later condensation threshold $\alpha_{\mathrm{cond}}$ the uniform distribution over solutions — the Gibbs measure of the associated spin system — becomes dominated by $O(1)$ clusters. The resulting overlap gap property — the absence of pairs of solutions at intermediate Hamming distances — is a proven barrier for broad algorithm classes, though currently only at densities above the clustering threshold (Bresler and Huang proved low-degree polynomial algorithms fail only at $4.91\cdot 2^k\ln k/k$). Beyond searching, one may count: output a $(1\pm\varepsilon)$-multiplicative approximation to the number $Z(\Phi)$ of satisfying assignments; and sample: output a random assignment within total-variation distance $\varepsilon$ (the maximum disagreement probability on any event) of the uniform measure $\mu_\Phi$ over solutions. These inference tasks are conjectured to remain tractable throughout the replica-symmetric (unclustered) phase: informally, replica symmetry means two uniformly random variables of a uniform random solution are asymptotically independent, and non-reconstruction means the marginal of a variable cannot be recovered from observations at large hypergraph distance; non-reconstruction is a necessary condition for local Markov chains to mix. Before 2024, counting/sampling algorithms for random $k$-SAT reached only densities exponentially far below the threshold, at best $\alpha\lesssim 2^{k/3}$ (He, Wu, and Yang), while for worst-case $k$-SAT formulas of maximum degree $d$, solutions are findable when $d\lesssim 2^k$ but counting and sampling become intractable already at $d\gtrsim 2^{k/2}$ (Bezáková, Galanis, Goldberg, Guo, and Štefankovič) — so the average-case random model is provably much easier for these tasks. Chen, Lonkar, Wang, Yang, and Yin closed the exponential gap for the random model: via a refined analysis of a recursive coupling of Wang and Yin, replacing the 2-tree witnesses of prior analyses by a denser witness-tree structure, they obtained approximate counting and almost-uniform sampling for random $k$-SAT (and generally for atomic CSPs, where each constraint is violated by exactly one assignment, such as random hypergraph $q$-coloring) up to $\alpha\le 2^k/k^c$, and deduced replica symmetry, non-reconstruction, and looseness (each variable's value can be changed within the solution space while modifying only a small number of other variables) at those densities. Their guarantees still lose polynomial factors in $k$ against the conjectured algorithmic threshold $2^k\ln k/k$, and they pose the question of whether counting and sampling are tractable up to the algorithmic threshold for searching.

Problem Statement

Determine whether approximate counting and almost-uniform sampling of solutions of random $k$-SAT are tractable up to the algorithmic threshold for searching — the conjectured clustering threshold $\alpha_{\mathrm{clust}}=(1+o_k(1))\,2^k\ln k/k$ — and characterize the solution-space geometry that governs the answer. Concretely, for the random formula $\Phi\sim\Phi(k,n,\lfloor\alpha n\rfloor)$ as $k\to\infty$, the algorithmic question asks whether, for every fixed $\varepsilon>0$ and every accuracy $\delta>0$ and all sufficiently large $k$, there exist a deterministic algorithm outputting a $(1\pm\delta)$-multiplicative approximation to the number $Z(\Phi)$ of satisfying assignments and an algorithm outputting an assignment within total-variation distance $\delta$ of the uniform measure $\mu_\Phi$, both running in time polynomial in $n$ and $1/\delta$ (polynomial dependence on $k$ and $\alpha$, as in the guarantees of Chen et al. [1], is admissible) and succeeding with high probability over $\Phi$ for every density $\alpha\le(1-\varepsilon)\,2^k\ln k/k$. A negative answer requires a proof that counting or sampling is intractable for polynomial-time algorithms at some density strictly below the search threshold; barriers established only for a restricted algorithm class (such as local Markov chains with single-variable updates, stable algorithms whose output changes little under small perturbations of the input, or low-degree polynomial algorithms) are relevant partial progress but do not by themselves settle the question. Chen et al. [1] obtain the algorithms and the structural properties (replica symmetry, non-reconstruction, looseness) from the same coupling analysis at whichever density it reaches, and the conjectured coincidence of the counting/sampling threshold with the search threshold is exactly the statement that the tractability boundary sits at $\alpha_{\mathrm{clust}}$. Structural results — for instance, a rigorous asymptotic location (or tight matching bounds) of the clustering and condensation thresholds $\alpha_{\mathrm{clust}}$ and $\alpha_{\mathrm{cond}}$ compared against the physics predictions, or establishing replica symmetry up to $\alpha_{\mathrm{cond}}$ and non-reconstruction up to its conjectured endpoint $\alpha_{\mathrm{clust}}$ — describe the geometry that governs the answer and constitute partial progress, but do not by themselves establish or refute tractability up to the search threshold. Resolving the random $k$-SAT question above is what the objective requires; the analogous question for the other sparse atomic random CSPs treated in Chen et al. [1], such as counting and sampling random hypergraph $q$-colorings between the current $q^k/\mathrm{poly}(k,q)$ frontier and their conjectured clustering thresholds, is context for the same phenomenon rather than a separate requirement.

References

1. Zongchen Chen, Aditya Lonkar, Chunyang Wang, Kuan Yang, Yitong Yin. Counting Random $k$-SAT near the Satisfiability Threshold. Proceedings of the 57th Annual ACM Symposium on Theory of Computing (STOC 2025). DOI: 10.1145/3717823.3718163; arXiv:2411.02980. https://arxiv.org/abs/2411.02980
2. Arnab Chatterjee, Amin Coja-Oghlan, Catherine Greenhill, Vincent Pfenninger, Maurice Rolvien, Pavel Zakharov, Kostas Zampetakis. The random $k$-SAT Gibbs uniqueness threshold revisited. arXiv:2506.01359, 2025. https://arxiv.org/abs/2506.01359
3. Jian Ding, Allan Sly, Nike Sun. Proof of the satisfiability conjecture for large $k$. Annals of Mathematics 196(1):1–388, 2022. DOI: 10.4007/annals.2022.196.1.1; arXiv:1411.0650. https://arxiv.org/abs/1411.0650
4. Amin Coja-Oghlan. A better algorithm for random $k$-SAT. SIAM Journal on Computing 39(7):2823–2864, 2010. DOI: 10.1137/09076516X; arXiv:0902.3583. https://arxiv.org/abs/0902.3583
5. Dimitris Achlioptas, Amin Coja-Oghlan. Algorithmic barriers from phase transitions. Proceedings of FOCS 2008. arXiv:0803.2122. https://arxiv.org/abs/0803.2122
6. Florent Krzakala, Andrea Montanari, Federico Ricci-Tersenghi, Guilhem Semerjian, Lenka Zdeborová. Gibbs states and the set of solutions of random constraint satisfaction problems. PNAS 104(25):10318–10323, 2007. DOI: 10.1073/pnas.0703685104. https://doi.org/10.1073/pnas.0703685104
7. Guy Bresler, Brice Huang. The Algorithmic Phase Transition of Random $k$-SAT for Low Degree Polynomials. Proceedings of FOCS 2022. arXiv:2106.02129. https://arxiv.org/abs/2106.02129
8. Kun He, Kewen Wu, Kuan Yang. Improved Bounds for Sampling Solutions of Random CNF Formulas. Proceedings of SODA 2023, pages 3330–3361. DOI: 10.1137/1.9781611977554.ch128. https://doi.org/10.1137/1.9781611977554.ch128
9. Chunyang Wang, Yitong Yin. A Sampling Lovász Local Lemma for Large Domain Sizes. Proceedings of FOCS 2024. arXiv:2307.14872. https://arxiv.org/abs/2307.14872
10. Ahmed El Alaoui, David Gamarnik. Hardness of Sampling Solutions from the Symmetric Binary Perceptron. arXiv:2407.16627, 2024. https://arxiv.org/abs/2407.16627
11. Victor Bapst, Amin Coja-Oghlan. The condensation phase transition in the regular $k$-SAT model. arXiv:1507.03512, 2015. https://arxiv.org/abs/1507.03512
12. Amin Coja-Oghlan, Charilaos Efthymiou, Nor Jaafari, Mihyun Kang, Tobias Kapetanopoulos. Charting the replica symmetric phase. Communications in Mathematical Physics 359(2):603–698, 2018. DOI: 10.1007/s00220-018-3096-x; arXiv:1704.01043. https://arxiv.org/abs/1704.01043
13. Amin Coja-Oghlan, Tobias Kapetanopoulos, Noela Müller. The replica symmetric phase of random constraint satisfaction problems. Combinatorics, Probability and Computing 29(3):346–422, 2019. DOI: 10.1017/S0963548319000440; arXiv:1802.09311. https://arxiv.org/abs/1802.09311
14. Dingding Dong, Nitya Mani. Random local access for sampling k-SAT solutions. Proceedings of SAT 2024. arXiv:2409.03951. https://arxiv.org/abs/2409.03951
15. Hongyang Liu, Chunyang Wang, Yitong Yin, Yiyao Zhang, Can Zhou. A Counting and Sampling Lovász Local Lemma. arXiv:2608.08616, 2026. https://arxiv.org/abs/2608.08616
16. Ivona Bezáková, Andreas Galanis, Leslie Ann Goldberg, Heng Guo, Daniel Štefankovič. Approximation via Correlation Decay When Strong Spatial Mixing Fails. SIAM Journal on Computing 48(2):279–349, 2019. DOI: 10.1137/16m1083906. https://doi.org/10.1137/16m1083906
17. Jingcheng Liu, Yixiao Yu. Zero-free regions and concentration inequalities for hypergraph colorings in the local lemma regime. arXiv:2601.13796, 2026. https://arxiv.org/abs/2601.13796
18. Jingcheng Liu, Chunyang Wang, Yitong Yin, Yixiao Yu. Phase Transitions via Complex Extensions of Markov Chains. Proceedings of STOC 2025. arXiv:2411.06857. https://arxiv.org/abs/2411.06857
19. Hongyang Liu, Chunyang Wang, Yitong Yin. Local Gibbs sampling beyond local uniformity. arXiv:2502.10795, 2025. https://arxiv.org/abs/2502.10795
20. Alankrita Bhatt, Mukur Gupta, Germain Kolossov, Andrea Montanari. Generating from Discrete Distributions Using Diffusions: Insights from Random Constraint Satisfaction Problems. arXiv:2603.20589, 2026. https://arxiv.org/abs/2603.20589