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

1. Introduction

• Sampling targets relative weights across the solution space, unlike search for one satisfying assignment, and can provide access to typical-solution observables.The introduction frames this as asking whether random formulas' probabilistic information can be made computationally accessible.Source: §1 · pp. 2–3
• Earlier work reached density 2^k/poly(k) for counting and sampling, but its running-time exponent depended on k and α, leaving the universal-degree question open.At this density, typical clause degree is αk^2; the cited symmetric local-lemma condition reaches only an exponential density around 2^k/2, and maximum degree grows with n.Source: §1 · pp. 3–4

1.1. Our result.

• The analysis uses the occurrence model, which permits repeated variables, tautological clauses, and distinct clause labels with identical contents.The stated constants, including the k cutoff and density power, are described as conservative and not fully optimized.Source: §1.1 · p. 4
• Theorem 1.1 combines density 2^k/poly(k) with a universal polynomial running-time degree, whereas prior work reached that scale with a parameter-dependent degree.The result strengthens separate polynomial-time guarantees for fixed k and α to a bound whose degree is independent of both.Source: §1.1 · p. 4

1.2. Technique overview.

• The algorithm places high-degree variables and variables strongly affected by them in a core, then samples the remaining variables conditional on a core assignment.Core components have at most log^2 n variables with high probability, and each residual formula is a clause-deletion subformula of a fixed good formula.Source: §1.2 · p. 4, The core and residual formulas · p. 5
• The recursive insertion chain replaces 2-trees with ordinary connected violation sets, improving the rooted-set counting bound from O(D^2)^(t−1) to O(D)^(t−1).Joint-moment bounds for correlated lists use expansion for small violation sets and independent good-literal signs for larger sets, uniformly across residual formulas.Source: The recursive insertion chain for good… · p. 5
• Signed-flow energy and state-weighted conditional list costs yield an expected running-time bound with a universal polynomial degree.The analysis adapts the signed-flow and state-weight cost framework to lists generated from a single global product assignment.Source: The recursive insertion chain for good… · p. 5
• The core chain updates one component at a time using estimated extension weights, while a polymer expansion and exploration bound establish a spectral gap of at least n^-2.After the approximate core chain mixes, the algorithm samples the good variables conditional on the resulting core assignment.Source: Rapid mixing of the core dynamics… · p. 5

2.1. Notations.

• The notation covers assignments and events, expectations and variances, total variation, and couplings, while [n] denotes {1, . . . , n}.The paper also defines a random k-SAT instance using n variables and m labeled clauses, each formed from k independently sampled literals.Source: §2.1 · p. 6, §2.2 · p. 6

2.2. Random SAT formula.

• A random k-SAT formula is specified by labeled clauses whose k literals are sampled independently, with µ_F denoting the uniform assignment law conditioned on satisfying F.Variable degrees, incident clause labels, and the formula’s dependency and primal graphs describe its constraint structure.Source: §2.2 · pp. 6–7

2.3. Abstract polymer models and the Kotecký–Preiss criterion.

• The Kotecký–Preiss criterion bounds weighted connected-cluster contributions and, under its stated condition, ensures absolute convergence of the cluster series.Its pinned form bounds the total absolute weight of connected clusters containing a prescribed polymer.Source: §2.3 · pp. 7–8

2.4. Lovász local lemma.

• The asymmetric Lovász local lemma gives a sufficient condition for avoiding all bad events, expressed using their dependency neighborhoods and event-specific parameters.Under the condition, the probability of avoiding all bad events is positive, and the theorem also bounds probabilities of events.Source: §2.4 · p. 8

2.5. The Efron–Stein inequality.

• For independent coordinates, the Efron–Stein inequality bounds total variance by the sum of the average conditional variances from changing one coordinate at a time.The coordinates need not have identical distributions.Source: §2.5 · p. 8

2.6. Markov chains and functional inequalities.

• The paper considers ergodic reversible Markov chains, uses Dirichlet forms to study convergence, and characterizes the spectral gap variationally using the second-largest eigenvalue.The Dirichlet form is introduced as a functional on pairs of test functions.Source: §2.5 · p. 8, §2.6 · pp. 8–9

3.3. High-degree separation.

• The core starts from high-degree or significantly influenced variables and grows by adding variables from clauses with more than 8 distinct variables already in the core.The construction defines Core(S) by repeatedly applying this clause-based addition rule.Source: §3 · p. 9, §3.3 · p. 12

3.1. Expansion of random SAT formulae.

• With high probability, the expansion lemma gives a uniform expansion property for every set of at most r clauses.The lemma assumes k ≥ 30 and n^2 ≥ 2n0.Source: §3.1 · p. 9

3.2. Estimate for incident clauses.

• With probability at least 1 − n^-3, every connected variable subset U has fewer than CINC|U| + 4 ln n incident clauses.Source: §3.2 · p. 10

3.3.1. Small components in the bad core.

• Under the joint structural event, every connected component of the bad-variable core has size at most log2 n.Source: §3.3.1 · p. 13
• For each bad-core component and each L in [log2 n, r], at most L core clauses meet that component.Source: §3.3.1 · p. 14
• The core formula is satisfiable for any literal signs, and its feasible assignments factor into the feasible sets of its bad-core components.Each component’s feasible set consists of assignments satisfying the core clauses meeting that component.Source: §3.3.1 · pp. 14–15

3.3.2. Extension from the core formula to good variables.

• The good formula has dependency-graph maximum degree at most k∆, and every feasible core assignment extends to a satisfying assignment of the original formula.Source: §3.3.2 · pp. 15–16
• E_a uses variables disjoint from every clause in T.This disjointness is used in the extension argument.Source: §3.3.2 · p. 16
• ν(E_a | Good(F)) ≤ p*/(1 − ep*)^d ≤ ep*.The denominator bound is obtained using the chain rule.Source: §3.3.2 · p. 16
• After fixing a partial assignment σ on the core formula, a good formula is either already satisfied by σ or retains exactly its clause of Ψ.In either case, the passage states that satisfiability under σ and the identity of conditional law are immediate.Source: §3.3.2 · p. 16

• The algorithm adapts recursive insertion-chain sampling to ordinary connected constraint sets and generates their lists from a global product sample.Source: §4 · p. 16
• For every constraint subset F and ε in (0, 1), the theorem gives an ε-accurate sampler supported on Good(F) with polynomial expected running time.The sampler's output law is within ε in total variation distance of µF.Source: §4 · p. 17
• The running-time bound has an absolute polynomial degree in the full input length I.Source: §4 · p. 17

4.1.1. The connected-set identity.

• The connected-set identity gives a pointwise formula, and under condition (15) it also bounds Z−/ZF by 1 + K0.The identity is presented as an analogue of [JMP26, Theorem 2.4].Source: §4.1.1 · p. 17

4.1.2. Parity pairing.

• Parity pairing toggles one explored violating constraint to map a connected set to an opposite-parity partner, and applying the map twice returns the original set.When the assignment violates only a, the only possible connected set is {a}.Source: §4.1.2 · pp. 18–19

4.1.3. Random lists.

• Each corridor label e = (S, u) appears in a random list with probability qe, and conditioning on its appearance has the same law as fixing σ(VS) = u.The list can be enumerated in polynomial time in the input length and its size.Source: §4.1.3 · p. 19

4.2. The recursive state space and transition rules.

• The state space is built recursively with set states, ordered layers, and embedded copies of smaller insertion constructions.Each layer adds a constraint from the closed neighborhood of the connected set, and each embedded copy is attached to a corridor label.Source: §4.2 · p. 20
• The transition rules use forward, backward, and reset moves, including resampling on variable sets and random-list resets.At the final layer, a forward move generates a list conditioned to contain the current corridor label and chooses a uniform label from it.Source: §4.2 · pp. 20–21
• The base kernel is reversible with respect to w, while Kβ is reversible with respect to π = ew/M.Conditioned on outer output states, π gives the distribution µ+.Source: §4.2 · p. 21
• Under assumptions (15) and (16), Lemma 4.8 bounds the distance between π and µ+.The coupling argument relates total variation distance to the probability of being outside the outputs.Source: §4.2 · pp. 22, 24

4.3. Flow method.

• The flow analysis assigns capacities to transitions and sums energy contributions across direct, resampling, return, and recursive-copy edges.Source: §4.3 · pp. 24–26
• Lemma 4.9 constructs a signed flow with divergence µ− − µ+ and bounds its energy.The flow is built inductively over corridor labels and smaller embedded copies.Source: §4.3 · pp. 24–25
• For a finite lazy reversible kernel, a signed flow of energy at most A yields a bound on convergence in total variation distance.Source: §4.3 · pp. 26–27

4.4. The insertion routine.

• The insertion routine adapts the framework of [JMP26] to these settings.The step cost is bounded using state updates, pairing, constraint testing, resampling, and fresh-list generation.Source: §4.4 · p. 27, Expected one-step cost · p. 28
• The routine starts from an initialized state and simulates N steps of Kβ, interrupting if the running cost exceeds a threshold and otherwise returning τ only when the final state is in O(τ).An interrupted or invalid simulation returns ⊥.Source: §4.4 · p. 27
• The expected cost of one step is polynomial in the input size.The analysis also accounts for list-generation costs across active smaller copies.Source: Expected one-step cost · p. 28

4.5. The sampling algorithm.

• Each trial draws σ from ν and successively applies the insertion routine for clauses a1 through am, aborting the trial if any insertion returns ⊥.The tolerance is set to δ = ε/(4(m + 1)).Source: §4.5 · p. 29
• If a trial has expected cost τ and failure probability f, the expected cost until success is bounded by τ/(1 − f).The proof uses this retry bound to bound the sampler’s total expected cost.Source: §4.5 · p. 29
• The sampler outputs an assignment within TV-distance ε of the uniform law and has expected running time polynomial in the stated parameters.The proof bounds one trial’s failures by mδ ≤ ε/4 and the expected number of trials by 4/3.Source: §4.5 · p. 29

5. Fast Sampling for Good Variables

• Formula generation separates variable-occurrence structure and the division into bad and good variables from independent random sign choices for each group.The dependency and primal graphs depend only on the structure generation.Source: §5 · p. 30
• With probability at least 1 − ζ over good-variable signs, the section bounds Aa + Ta for every a ∈ Cgood by ρ.The displayed bound is Aa + Ta ≤ e C*·D(1 − z) + 1/C*·D ≤ ρ.Source: §5 · p. 30
• For every F ⊆ Cgood, GoodSampler returns a satisfying assignment of Ψ[F] within total variation error δ, with expected cost polynomial of universal degree in I and δ^-1.The resulting sampler applies to every such F and every δ in (0, 1).Source: §5 · p. 31
• The moment analysis uses connected sets containing a, and pairing moments count ordered connected-set pairs through their connected union.A fixed union U has at most 3^{|U|−1} such representations.Source: §5 · pp. 30–31

6.1. The core marginal and its polymer representation.

• With probability at least 1 − o_n(1), the polymer-root estimate holds, enabling an absolutely convergent expansion of the core marginal’s log partition function with bounded total interaction weight at each clause.The cluster terms are regrouped by core components and truncated to obtain finite-interaction measures.Source: §6.1 · pp. 32, 34, 36, §6.2 · p. 37

6. Rapid Mixing of Heat-bath Dynamics for the Bad Core

• Under the core feasibility and structural assumptions, for n ≥ 2 and k ≥ 30, the core heat-bath chain has spectral gap at least 1/(sn).If there is only one feasible core configuration, the variance inequality holds automatically and the gap is conventionally 1.Source: §6 · pp. 31–32, §6.1 · p. 33

6.2. Variance tensorization for finite-interaction measures.

• For finite-interaction measures, a component-swap comparison bounds global variance by coordinatewise conditional variances weighted by expected sizes and interaction strengths of connected components in an associated random hypergraph.This comparison is applied to finite truncations of the cluster expansion before passing to the limit.Source: §6.2 · pp. 37–38
• Variance tensorization reduces block variance control to product-reference conditional variances, while comparison with independent ζ-components yields the interaction bound in (50).For a fixed C, the event that C is a component of g implies C is contained in the ζ-component Aj of any j in C; the proof then uses R(C) ≤ R(Aj) and counts subsets of Aj containing j.Source: §6.2 · pp. 41, 43, 44

6.3. The exploration bound and the spectral gap.

• A polymer interaction’s value is determined by assignments to the core blocks touched by its clauses, defining its geometric scope JΓ.The passage defines JΓ from the core-component indices touched by clauses in UΓ and notes that YΓ depends only on the restriction of the assignment to those blocks.Source: §6.3 · p. 44
• A deterministic good-clause exploration identifies Aj exactly, checking candidate hyperedges only when they touch the growing component.It starts from j, adds the vertices of retained hyperedges, and stops when every incident good clause has been used; the resulting set is RQ = Aj.Source: §6.3 · pp. 44–45
• The exploration cost satisfies E e^(T/2−2ρQ) ≤ 1, and its component bounds relate R(A) to ρI(WA) and provide a connected set containing W of size at most |W| + T.These lemmas support the subsequent pointwise estimate for the component exploration.Source: §6.3 · p. 45

6.4. Proof of Theorem 6.1.

• The finite-truncation measures converge to µbad, allowing their Poincaré inequality to pass to the target measure.Absolute summability controls the truncation limit, including convergence of conditional probabilities and point masses.Source: §6.4 · pp. 48–49
• The heat-bath chain has gap(K) ≥ 1/(sn) ≥ n^-2, since the s nonempty disjoint blocks satisfy s ≤ n.The variance inequality gives the first bound; the block-count bound gives the second.Source: §6.4 · pp. 49–50
• The irreducible chain has simple eigenvalue 1, and every eigenvalue of P on the mean-zero subspace lies in [0, 1 − 1/(sn)], establishing spectral contraction.Source: §6.4 · p. 50

7.1. Approximate marginal heat-bath updates

• The approximate marginal estimator controls every estimated clause probability to relative error ε/(4ℓ), and its expected running cost has a universal polynomial degree.The estimates are used to simulate the heat-bath updates.Source: §7.1 · p. 52
• Each core-component update returns a feasible assignment within η total variation distance of the conditional law, with a deterministic polynomial cost cap.The cap is bounded by P2(I, η^-1).Source: §7.1 · p. 52

7.2. Design and analysis of the main sampler

• FastSampler constructs the high-degree and bad-variable sets, forms bad components and a good residual formula, then simulates core updates before sampling the residual.If there are no bad components, it calls GoodSampler directly; otherwise it performs T_bad updates and then calls GoodSampler on Dσ.Source: §7.2 · p. 54
• With high probability over the formula, FastSampler returns a satisfying assignment within 5ε/16 total variation distance of the uniform law, with expected cost at most (I/ε)^C2 for universal C2.The input length I is bounded in terms of n, k, and α, giving a universal polynomial running-time degree.Source: §7.2 · pp. 54–55
• The final joint output has total variation distance at most 5ε/16 from the uniform satisfying-assignment law.The proof combines an ε/8 residual-sampling error with a 3ε/16 update error.Source: §7.2 · p. 55

A.1. Missing proofs in Section 6.

• Swapping sample-pair coordinates on a union of connected components is a bijection within each hypergraph fiber and preserves pair probabilities.The swap leaves the edge indicators unchanged, so it maps each fiber to itself.Source: §A.1 · p. 59
• The exploration procedure returns exactly the component containing its starting vertex in the retained hypergraph.Every reached vertex is connected to the start, and every retained hyperedge meeting the explored set is fully included.Source: §A.1 · p. 62
• The exploration process yields a nonnegative supermartingale, and its number of steps is bounded by the number of good clauses.Each step uses a distinct clause, so Q ≤ |Cgood| ≤ m.Source: §A.1 · p. 63
• A polymer-linked expansion of bad-variable blocks is connected in the original formula’s primal graph.Connector variables along a spanning tree join the clauses, and adjoining intersecting blocks preserves connectivity.Source: §A.1 · p. 64