Non-Rigid Parity Constraints for Hash-Based Solution Counting

Many combinatorial solvers attach random parity (XOR) constraints to a problem. Counting methods use them as hash functions that cut the solution space roughly in half each time, and streamlining methods use them to steer search. The usual hash matrix is a random dense 0/1 matrix, so every parity constraint touches about half the variables. That causes two problems. If the solver splits each constraint into short clauses, it can only deduce something once nearly all of a constraint's variables are fixed. If it instead keeps the whole system intact and runs Gaussian elimination, it pays a cubic cost at every search node. This note proposes a third option taken from complexity theory. Choose the hash matrix from a family that is provably random enough for counting yet algebraically non-rigid, meaning it equals a low-rank matrix plus a sparse correction. Then encode the constraints through that split. The low-rank part becomes a handful of new "bottleneck" parity variables shared by all rows. Once those are set, every original constraint collapses to a short one that ordinary unit propagation (the solver's basic step of forcing a variable when only one value remains consistent) handles well.

In two sentences: random dense XOR hashes are maximally rigid, which is exactly why they are expensive to decompose. Toeplitz-type hash families give the same pairwise-independence guarantee but are suspected to be non-rigid, so we can trade dense rows for a few shared auxiliary variables plus sparse rows, without changing the set of solutions or the statistical guarantee.

Core Claim

Write the hash constraints as $Ax = b$ over the two-element field $\mathbb{F}_2$. Here $A$ is an $m \times n$ 0/1 matrix, $x$ holds the problem's Boolean variables, and $b$ is a random offset. Suppose $A = UV + S$, where $U$ is $m \times r$, $V$ is $r \times n$ with $r \ll m$, and $S$ is sparse. Introduce $r$ auxiliary variables $y = Vx$. The system becomes

$$Vx = y, \qquad Uy + Sx = b,$$

which has exactly the same solutions in $x$, because $y$ is determined by $x$. The encoding then contains $r$ dense parities plus $m$ rows, each touching at most $r$ auxiliary variables and the few $x$-variables in its row of $S$. Its total size drops from about $mn/2$ to about $r(n+m) + \mathrm{nnz}(S)$, where $\mathrm{nnz}(S)$ is the number of nonzero entries of $S$.

The more important claim concerns propagation. A clausal parity on $k$ variables forces a value only after $k-1$ of them are assigned. After the substitution, each hash row has length about $r + s_i$, where $s_i$ is the number of nonzeros in row $i$ of $S$, rather than about $n/2$. Once the solver has committed to the $r$ bottleneck variables, rows start propagating almost immediately. Because the solution set is untouched, the hashing guarantee is untouched too: universality is a property of the distribution over $A$, not of how $A$ is encoded.

This structure is the same one that makes Hall-interval decompositions work. Bessiere et al.'s decompositions of ALL-DIFFERENT and GCC recover the global constraint's filtering by adding auxiliary 0/1 variables that carry information across the whole scope. We obtain the auxiliary variables from an algebraic split rather than from interval combinatorics.

Where This Sits

The proposal is motivated by the decomposition literature's central finding. Splitting a global constraint into local pieces destroys reasoning across the pieces. Bessiere et al. argue this in general, and Sang et al. show that implications stop crossing component boundaries.

The closest prior work is Gomes et al.'s generalized XOR counting. It showed that treating parity systems globally, with Gaussian elimination over $\mathbb{F}_2$, beats filtering each XOR separately. It reports a lower bound of $4.5 \times 10^{42}$ solutions on the games120 coloring instance in under a minute, against $1.4 \times 10^6$ in 30 minutes for the earlier method. On order-17 spatially balanced Latin squares it reports over 1,000 solutions in 14 minutes, where pure CSP search found none in an hour. Gomes et al. take the hash matrix as given and dense, and pay for full elimination. We change the matrix family so that a cheap decomposition exists.

The method comes from Alman and Rao. They turned the non-rigidity of the $8\times 8$ Hadamard matrix into shared intermediate sums, cutting its operation count from 24 to 23 and giving a $\tfrac{23}{24}N\log N$ Walsh–Hadamard transform. They were counting arithmetic operations. We count encoding size and propagation delay, and we apply the idea to constraint matrices rather than transforms. Dvir and Liu show that Toeplitz and circulant matrices are non-rigid, and Alman's Kronecker-product results and Dvir and Edelman extend this kind of rank collapse to other structured families and to finite fields. Together these supply the reason to expect structured hash families to decompose well.

Two results constrain the design. First, those non-rigidity theorems are asymptotic and say nothing guaranteed about $\mathbb{F}_2$ matrices with tens of rows and hundreds of columns. Whether usable splits exist at practical sizes is therefore an empirical question, and we test it first. Second, Fomin et al. show that deciding exact rigidity is W[1]-hard in the number of changed entries alone, though it becomes tractable when parameterized by both the target rank and the number of changes. We therefore search for decompositions heuristically, offline, once per hash family and size. We do not search per instance.

The ill-posedness result of Tanner, Thompson and Vary concerns norms that blow up over the reals. It does not arise over a finite field, which is one reason to work in $\mathbb{F}_2$.

Graph-structural alternatives offer no escape here. Ganian et al. show that a single dense constraint makes primal treewidth blow up. Carbonnel and Hébrard's kernelization propagator (Propagation via Kernelization: The Vertex Cover Constraint) loses its advantage on dense structure. Dense hash rows are exactly that case.

Research Program

The first component is a decomposition search. For each candidate family and each size $(m, n)$, we sample matrices and run local search over $(U, V, S)$ in $\mathbb{F}_2$ to minimize encoding size at each $r$. The search combines greedy rank-$r$ fitting with flips that sparsify $S$. The result is an empirical rigidity profile: best-found $\mathrm{nnz}(S)$ as a function of $r$. The candidate families are Toeplitz hash matrices, which are 2-universal over $\mathbb{F}_2$ with a random offset, and random row subsets of Hadamard and Kronecker-structured matrices. Random dense matrices serve as the rigid control.

The second component is an encoding plus a branching hint. We encode $Vx=y$ and $Uy+Sx=b$ in clauses, chaining each parity through short Tseitin pieces (a standard way to write a long XOR as a sequence of three-variable XORs using intermediate variables). We give the $y$ variables priority in branching.

The third component is analysis. We bound how many assignments unit propagation needs before each row fires. We also check whether the family remains 2-universal after conditioning on the decomposition. Conditioning matters if the decomposition is chosen depending on the sampled matrix. The plan avoids this by drawing $A$ first and decomposing it afterwards, but the check makes that explicit.

Baselines

The naive reference point is the random dense XOR hash encoded row by row with chained clauses, solved by a standard CDCL solver (a conflict-driven clause-learning SAT solver). This is what the decomposition literature predicts will suffer the pruning gap. We run it on identical instances, with the same number of hash rows $m$, the same solver, the same per-call timeout, and the same number of repetitions per confidence level.

The strongest existing method is global Gaussian filtering over $\mathbb{F}_2$ in the style of Gomes et al., applied to the same hash rows. The reference numbers are the ones it reports, the $4.5\times10^{42}$ bound on games120 in under a minute and over 1,000 order-17 spatially balanced Latin square solutions in 14 minutes. We rerun it on our hardware rather than comparing against the published wall-clock times. We beat it if we reach a lower bound at least as large and at least as confident in less time, or a strictly larger bound within the same time budget.

A third baseline gives the Toeplitz family the naive encoding without decomposition. It separates any effect of the hash family itself from the effect of encoding through $L+S$.

Two ablations isolate the key ingredient. In the first, we add the same number $r$ of dense parity auxiliaries using a random $V$ that is unrelated to $A$, so rows do not get shorter. This tests whether the gain is merely the known benefit of branching on parity combinations. In the second, we apply the full $L+S$ pipeline to random dense matrices. Their best-found splits should be poor, so any remaining gain cannot come from non-rigidity.

All methods receive the same total compute, including the offline decomposition time, which we amortize per family and size and also report separately.

Why not just…?

Why not just run Gaussian elimination, as Gomes et al. did? This is the main threat on small hash systems, where cubic elimination is cheap. Our advantage should appear as $m$ and $n$ grow and per-node elimination dominates runtime. The head-to-head scaling sweep over $m$ settles this. If elimination still wins at the largest sizes we can run, the idea fails for counting. It might survive only as a preprocessing aid, for example running elimination on the $r$-dimensional bottleneck, and we would report it that way.

Why not just use sparse random XORs? Sparse hashes shrink the encoding directly, but they give up the exact pairwise-independence guarantee that the counting bounds rely on. The file contains no reported result for sparse-hash counting on these benchmarks. We treat sparse hashes as an extra baseline and measure both speed and calibration of the bound on instances small enough to enumerate exhaustively. If sparse hashes match our speed with acceptable calibration, the case for non-rigid families shrinks to the guarantee alone.

Why not just apply generic common-subexpression sharing to the XOR rows? Greedy sharing of repeated partial sums is how Alman and Rao realize their savings in practice, so it is a serious competitor for encoding size. Its weakness for our purpose is that it optimizes size without creating a small bottleneck that makes all rows short once it is decided. We include greedy sharing as a baseline with matched encoding size. If it matches our propagation statistics, the "bottleneck" claim is wrong.

Why not just rely on clause learning to recover the lost reasoning? The decomposition literature already answers this for structured problems. Bessiere et al. report 29 seconds and nearly a million backtracks for the binary decomposition on pigeonhole instances with $n=11$, against 0.1 seconds and 10 backtracks for Hall intervals. The naive baseline tests whether the same holds for hash constraints.

Proposed Experiments

The first experiment is decisive, and the project pivots if it fails. Over $\mathbb{F}_2$, with $m$ between 10 and 60 and $n$ between 100 and 1000, we compare best-found rigidity profiles for Toeplitz and Kronecker-structured families against random dense matrices. Success means that at some $r \le m/4$, the encoding cost $r(n+m)+\mathrm{nnz}(S)$ falls below half the dense cost for the structured families but not for random ones. If no such $r$ exists, the asymptotic non-rigidity theorems do not reach practical sizes, and we stop.

The second experiment audits propagation. We sample random partial assignments, compute the full set of literals that Gaussian elimination would force, and record the fraction recovered by unit propagation under each encoding. We also record the number of assignments needed before the first propagation.

The third experiment covers end-to-end counting and streamlining, using the games120 coloring and order-17 spatially balanced Latin square benchmarks from Gomes et al.. We measure the lower bound reached and its confidence within fixed time budgets, along with solver conflicts per hash call. For calibration, we compare bounds on small instances with exhaustively enumerated counts, across all hash families, to confirm that the structured families behave as random ones statistically.

The ablations run alongside the third experiment with matched budgets. The random-$V$ ablation and the rigid-matrix ablation together determine whether non-rigidity itself, rather than auxiliary parity variables in general, explains any gain.