REVIEW
Pointwise Score Evaluation from Succinct Boolean Descriptions: SAT Equivalence for Strongly Log-Concave Gaussian Mixtures
Computational Complexity · Submitted 2 Nov 2026 · 9 references
Pith's verdict: A clean, checkable SAT-equivalence for pointwise score evaluation under strong log-concavity; the math holds and it deserves a serious referee.
Why Pith says this
Highlight any text to comment on it.
Referee report
The paper
The paper claims
Computing one score coordinate of a strongly log-concave Gaussian mixture to constant accuracy is equivalent, in polynomial time, to solving SAT.
The reading
What carries the argument
The central object is a Gaussian location mixture indexed by the satisfying assignments of a CNF formula: a marked atom at each satisfying hypercube vertex plus one auxiliary atom with a distinct first coordinate, all convolved with unit Gaussian noise. The identity that carries the argument is the posterior form of the score, $s_F(y) = E[A \mid Y = y] - y$, whose Jacobian is $\operatorname{Cov}(A \mid Y = y) - I_d$; at the origin, equal atom norms make the posterior equal to the prior, so the first score coordinate collapses to the rational function $(2Z_F - 1)/(2Z_F + 1)$ of the satisfying-assignment count. Compressing the atoms to squared norm at most $1/2$ turns the posterior-covariance bound into the uniform curvature bound $\frac{1}{2}I_d \preceq \nabla^2(-\log \tilde p_F)(y) \preceq I_d$, delivering strong log-concavity with a smoothness-to-strong-convexity ratio of at most $2$. The converse direction runs on the standard SAT-to-witness machinery: self-reduction to find at most two (or four) satisfying assignments, blocking clauses to certify exhaustion, and exact evaluation of the rational identity when the count is small enough.
Extended reading notes
Core claim
For a CNF formula $F$ with $Z_F$ satisfying assignments, the paper defines a point distribution on the hypercube: one atom per satisfying assignment plus one auxiliary atom that keeps the mixture a probability measure when $Z_F = 0$, smoothed by unit Gaussian noise in dimension $n+1$. Because every atom has the same squared norm, all likelihoods coincide at the origin, where the posterior equals the prior; the Gaussian score identity $s_F(y) = E[A \mid Y = y] - y$ then yields the exact formula $h(F) = (2Z_F - 1)/(2Z_F + 1)$ for the first score coordinate — a value of $-1$ for unsatisfiable formulas and at least $1/3$ for satisfiable ones. A deterministic polynomial-time algorithm outputting this coordinate to absolute error $1/4$ exists if and only if $P = NP$: the error budget cleanly separates the two cases by the sign of the output, and conversely a SAT decider supplies the value by bounded witness enumeration with blocking clauses (Theorem 4.2). Compressing the atoms by rational factors into a ball of squared radius at most $1/2$ preserves the gap while forcing the negative log density to be $\frac{1}{2}$-strongly convex and $1$-smooth, with the same constant-accuracy equivalence and with the SAT signal persisting throughout a query ball of radius $1/24$ independent of dimension (Theorem 6.1 and Corollary 6.2). The paper anchors the equivalence in the formula-access model: with independent samples instead of the formula, the same value becomes a dimension-independent mean with exponential concentration, and any formula-to-sampler algorithm would collapse NP into RP. The existence of a general efficient formula-access evaluator is left open.
Load-bearing premise
The load-bearing premise is the formula-access input model: the evaluator receives only the CNF string $F$, with no sampling, SAT, counting, or trained-parameter oracle and no nonuniform advice, because once independent sample access is granted the paper itself shows the same target becomes a dimension-independent mean-estimation problem with exponential concentration.
Editorial extensions
If this is right
- Score-based pipelines for Boolean-constrained distributions must pay for score access explicitly: in the constructed family, obtaining a single pointwise score value from the formula is exactly as hard as SAT, even though the curvature constants match those under which fast sampling is provable in oracle models.
- A geometric route to solving SAT by noise-smoothing the assignment set fails at a fixed query: no deterministic polynomial-time procedure can decode satisfiability from one score coordinate at a constant-radius ball in the formula-access model, unless $P = NP$.
- The hardness is calibrated by accuracy: error $1/4$ is equivalent to SAT decision, inverse-polynomial error is achievable with polynomially many SAT queries, and only exponentially small error (about $2^{-2n-4}$, rescaled in the compressed family) recovers the exact satisfying-assignment count, tying fine precision to #SAT.
- Under independent sample access the same target is a dimension-independent mean-estimation problem, so the construction separates representation hardness from statistical hardness: it concerns extracting a value from a formula, not learning from data.
- The parity family $F_b$ gives an exact restricted-model separation: every real polynomial of degree below $k$ in the raw Boolean features has squared error at least $4/9$ against the target, even though parity itself costs $O(k)$ Boolean operations, separating polynomial degree from circuit size and runtime.
Reading between the lines
- Editorial inference: the equal-norm encoding is a general template, so any NP-complete property that can be attached to hypercube vertices with a fixed-norm embedding should yield the same score-evaluation hardness, plausibly extending the result beyond CNF satisfiability to other constraint families.
- Editorial inference: the persistence of the gap on a constant-radius ball suggests the obstruction is not a singularity at the origin; a natural testable extension is whether the SAT gap survives when the score is queried along an actual reverse-time diffusion trajectory, which the paper does not address.
- Editorial inference: read as a statement about generative modeling, the formula-to-sampler implication predicts that any end-to-end algorithm that provably outputs samples near the mixture from the formula alone would imply $NP = RP$, marking a sharp divide between sampling guarantees stated under oracle access and sampling algorithms run on the description itself.
- Editorial inference: the accuracy ladder (constant error to decision, inverse-polynomial error to bounded witness enumeration, exponential precision to exact counting) suggests a phase diagram for approximate counting through scores that could yield conditional hardness results for intermediate precision regimes.
Original abstract
Score-based generative models rely on access to accurate scores, but the cost of computing those scores depends on how the underlying distribution is represented. Can smoothness and strong log-concavity make score evaluation efficient when a distribution is specified by Boolean constraints? I investigate this question by separating geometric encoding from computational extraction. I construct a succinctly specified Gaussian mixture whose score at a fixed query location encodes whether a Boolean formula is satisfiable. The construction has rational component means and uniform strong log-concavity, yet deterministic polynomial-time approximation of the designated score coordinate to constant absolute accuracy is equivalent to polynomial-time solvability of Boolean satisfiability. This equivalence remains valid throughout a neighborhood whose radius is independent of dimension. I further characterize how numerical precision connects bounded witness enumeration to exact counting, and show that independent sample access turns the same target into a dimension-independent mean-estimation problem. An explicit parity construction also separates low-degree approximation from efficient computation. Together, these results show that favorable geometry alone does not resolve the computational cost of extracting scores from compact descriptions. They identify the precise extraction requirement in this formulation while leaving the existence of a general efficient evaluator open.
The compiled record
The paper's own sentences, arranged, kept beside the review and separate from it. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
The abstract, sentence by sentence
Score-based generative models rely on access to accurate scores, but the cost of computing those scores depends on how the underlying distribution is represented. Can smoothness and strong log-concavity make score evaluation efficient when a distribution is specified by Boolean constraints? I investigate this question by separating geometric encoding from computational extraction. I construct a succinctly specified Gaussian mixture whose score at a fixed query location encodes whether a Boolean formula is satisfiable. The construction has rational component means and uniform strong log-concavity, yet deterministic polynomial-time approximation of the designated score coordinate to constant absolute accuracy is equivalent to polynomial-time solvability of Boolean satisfiability. This equivalence remains valid throughout a neighborhood whose radius is independent of dimension. I further characterize how numerical precision connects bounded witness enumeration to exact counting, and show that independent sample access turns the same target into a dimension-independent mean-estimation problem. An explicit parity construction also separates low-degree approximation from efficient computation. Together, these results show that favorable geometry alone does not resolve the computational cost of extracting scores from compact descriptions. They identify the precise extraction requirement in this formulation while leaving the existence of a general efficient evaluator open.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | Score-based generative models rely on access to accurate scores, but the cost of computing those scores depends on how the underlying distribution is represented. | background 1.00 | 0.07 | 0.03 | asserted 1.00 |
| s1 | Can smoothness and strong log-concavity make score evaluation efficient when a distribution is specified by Boolean constraints? | gap 0.60 | 0.06 | 0.03 | unclear 0.54 |
| s2 | I investigate this question by separating geometric encoding from computational extraction. | method 0.85 | 0.92 | 0.03 | asserted 0.88 |
| s3 | I construct a succinctly specified Gaussian mixture whose score at a fixed query location encodes whether a Boolean formula is satisfiable. | contribution 0.60 | 0.95 | 0.07 | asserted 1.00 |
| s4 | The construction has rational component means and uniform strong log-concavity, yet deterministic polynomial-time approximation of the designated score coordinate to constant absolute accuracy is equivalent to polynomial-time solvability of Boolean satisfiability. | result 0.99 | 0.92 | 0.53 | asserted 1.00 |
| s5 | This equivalence remains valid throughout a neighborhood whose radius is independent of dimension. | result 1.00 | 0.88 | 0.06 | asserted 1.00 |
| s6 | I further characterize how numerical precision connects bounded witness enumeration to exact counting, and show that independent sample access turns the same target into a dimension-independent mean-estimation problem. | result 0.66 | 0.91 | 0.05 | asserted 1.00 |
| s7 | An explicit parity construction also separates low-degree approximation from efficient computation. | result 0.71 | 0.90 | 0.04 | asserted 1.00 |
| s8 | Together, these results show that favorable geometry alone does not resolve the computational cost of extracting scores from compact descriptions. | interpretation 0.95 | 0.91 | 0.85 | asserted 1.00 |
| s9 | They identify the precise extraction requirement in this formulation while leaving the existence of a general efficient evaluator open. | interpretation 0.56 | 0.87 | 0.17 | asserted 0.96 |
What was examined, and what was not
- arXiv listing abstract v1
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
References
Discussion
Disagree with the review, or know something it missed? Leave a comment, highlight any passage above to comment on it, or challenge this review formally.