Neural networks trained with a logical constraint on their outputs, such as "the predicted edges form a single path" or "the predicted preferences form a consistent ranking", often settle on an answer that obeys the rule but is wrong. Our hypothesis is that this has a simple discrete cause. To move from one rule-obeying answer to another, the output usually has to pass through answers that break the rule, and the constraint loss punishes exactly those intermediate answers. We propose to measure that obstacle directly, as the height of a "reconfiguration barrier" in the graph whose nodes are valid answers and whose edges are single-bit changes. We then remove the obstacle with a principled curriculum. Training starts with the constraint loosened to "within $k$ bit-flips of valid", with $k$ set to the measured barrier, and $k$ is annealed to zero.
The opportunity comes from two literatures that have not spoken to each other. Combinatorial reconfiguration studies whether the solution space of a discrete problem stays connected under small local moves, and how much rule-breaking a path between two solutions must tolerate. Asymptotically Optimal Inapproximability of Ek-SAT Reconfiguration treats this "worst point along the path" as the central quantity for satisfiability. Neuro-symbolic learning compiles logical constraints into differentiable losses but treats the constraint as fixed from the first epoch. A Semantic Loss Function for Deep Learning with Symbolic Knowledge notes that its loss is sensitive to how the network starts out. The proposal makes one falsifiable claim. Entrapment and sensitivity to the random seed in constraint-trained networks should track the reconfiguration barrier of the constraint's encoding, and relaxing by exactly that barrier should beat relaxations of equal strength that ignore it.
Core Claim
Let $\alpha$ be a constraint over $n$ binary outputs, written in a finite-domain first-order fragment (for example, transitivity of a ranking, or path connectivity on a grid). Let $d(s,\alpha)$ be the Hamming distance from an output vector $s$ to the nearest assignment satisfying $\alpha$. For two satisfying assignments $y$ and $y'$, the reconfiguration barrier is
$$b(y,y') = \min_{\text{flip paths } y=s_0,\dots,s_T=y'} \; \max_t \; d(s_t,\alpha),$$
which is the least amount of rule-breaking any single-flip path from $y$ to $y'$ must tolerate. Define the relaxed constraint $\alpha_k = \{s : d(s,\alpha)\le k\}$. By construction, $y$ and $y'$ lie in the same connected component of the single-flip graph of $\alpha_k$ exactly when $b(y,y')\le k$.
Semantic loss is the negative log-probability that the network's output satisfies the constraint. We claim that training with semantic loss on $\alpha_{k_t}$, with $k_t$ annealed from the barrier level down to zero, does two things. It removes the valid-but-wrong traps that static semantic loss and its entropy-regularized variant create. It also reduces variance across random initializations. Neither effect should appear when the constraint's flip graph is already connected at $k=0$.
The last condition is the sharpest test, and the benchmarks already in use give us one case of each kind. Under a pairwise-order encoding, swapping two adjacent items in a ranking flips exactly one bit and keeps the ranking valid, so the barrier is zero everywhere. Simple paths on a grid cannot be rerouted by any single edge flip without breaking validity, so their barrier is at least one. Our theory therefore predicts entrapment on grid and Warcraft paths but not on pairwise-encoded sushi rankings. If entrapment is equally severe on both, the theory is wrong.
Relation to Prior Work
Two papers motivate the gap. A Semantic Loss Function for Deep Learning with Symbolic Knowledge compiles constraints into arithmetic circuits (logic circuits that support exact weighted model counting) and takes exact gradients of the probability of satisfaction. Neuro-Symbolic Entropy Regularization additionally lowers the entropy of the output distribution restricted to valid outputs, which pushes the model to commit to one valid answer. Both keep the constraint fixed. The second actively encourages early commitment, which is the behavior our barrier argument predicts will produce traps.
Our method borrows the circuit machinery from these papers but changes the constraint during training. It also replaces their fuzzy-free rigidity with a relaxation that is still exact and semantic: $\alpha_k$ is a Boolean set, not a t-norm, so it respects the objection Xu et al. raise against fuzzy operators.
The reconfiguration literature supplies the measured quantity but stays purely discrete. Asymptotically Optimal Inapproximability of Ek-SAT Reconfiguration shows that bounding the worst violation along a satisfiability reconfiguration path is PSPACE-hard to approximate in general. That result constrains us: we compute barriers exactly only on small encodings, and estimate them elsewhere. On solution discovery via reconfiguration asks whether local moves can reach a valid state within a step budget, again with no learning component. Canonical-state connectivity proofs such as Flips in Odd Matchings show which constraint families have connected flip graphs, and these are candidates for the zero-barrier control.
On the continuous side, A Theoretical Analysis of Optimization by Gaussian Continuation smooths an objective and tracks its minimum as the smoothing is removed. That paper admits the method fails when the tracked minimum disappears partway through. Our curriculum is a discrete analogue in which the smoothing amount is chosen from a computed connectivity property rather than tuned blindly. Recursive Decomposition for Nonconvex Optimization brings satisfiability-style splitting into continuous optimization but never asks whether distinct optima are connected.
Research Program
The first component is a barrier calculator. For constraints with up to roughly 24 binary outputs, such as the 4×4 grid edge variables, we compute $d(\cdot,\alpha)$ for every state by breadth-first search outward from the satisfying set. We then compute $b(y,y')$ as a bottleneck shortest path, the path that minimizes its worst step. For Warcraft-scale grids we use local search to estimate an upper bound on the barrier. We also report the Hirahara–Ohsaka-style conditional-expectation path as a reference construction, while keeping in mind that their guarantees concern clause fractions and not Hamming distance.
The second component compiles $\alpha_k$. We take the circuit for $\alpha$ and pair each output with a "flipped" indicator, then add a cardinality constraint allowing at most $k$ flips. We expect circuit size to grow roughly in proportion to $k$ and will report the measured growth. This is the main engineering risk.
The third component is the training procedure. Semantic loss on $\alpha_{k_t}$ is combined with the supervised loss. We compare two schedules. In the first, $k_0$ is the 90th percentile of measured barriers between the model's current valid prediction and the target. In the second, $k_t$ drops a level whenever the fraction of examples whose prediction is valid but wrong stops falling.
The fourth component is a diagnostic study, run before any method comparison. For each training example under static semantic loss we record two things: whether the example ends in a valid-but-wrong state that persists for the final epochs, and the barrier between that state and the target. The core prediction is that persistence rises with barrier height.
Baselines
The naive reference point is the same network trained with cross-entropy alone. The cited papers report a 4×4 grid valid-path rate of 6.99% for the plain multilayer perceptron, and sushi coherent accuracy of 1.01% (Xu et al.). On Warcraft, ResNet-18 reaches 44.8% coherent accuracy (Ahmed et al.).
The strongest within-family competitor is static semantic loss and its entropy-regularized version, reimplemented with the same circuits, architecture, epochs, and hyperparameter search budget as our method. The reported figures are 69.89% valid paths on 4×4 grids and 13.59% sushi coherent accuracy for semantic loss (Xu et al.). With entropy regularization they are 55.0% Warcraft coherent accuracy and 96.04% sushi constraint satisfaction (Ahmed et al.). Because the two papers may use different task setups, we rerun both in our own pipeline rather than comparing against copied numbers.
The strongest overall system on Warcraft is blackbox solver differentiation (Differentiation of Blackbox Combinatorial Solvers). It runs Dijkstra inside the network and reports about 94–96% path-optimality accuracy. We do not expect to beat it on Warcraft, because a solver in the loop guarantees validity and bypasses the barrier entirely. We include it as a ceiling and to make clear that our claim concerns constraint-loss training, which is the setting where no polynomial solver exists for the constraint.
Two ablations isolate the key ingredient. The first anneals the semantic-loss weight from zero up to its final value, which gives a relaxation of comparable "softness" that knows nothing about barriers. The second anneals $k$ from a fixed, arbitrary starting level rather than the measured barrier. Our method beats these baselines if three things hold together. Over at least ten seeds, it must improve coherent accuracy over tuned static semantic loss and entropy regularization on grid paths. It must narrow the gap between the best and worst seeds. And it must beat both ablations at an equal tuning budget.
Why not just…?
Why not just anneal the weight on the semantic loss? This is the most serious threat. Down-weighting the constraint early also lets outputs pass through invalid states. The difference is that weight annealing loosens the constraint uniformly, while $\alpha_k$ still forbids outputs far from validity, so structure is kept while traps are opened. The two diverge only where barriers are high. If weight annealing matches our method on grid paths, the barrier-specific part of the idea fails, and we would report the diagnostic study alone.
Why not just use random restarts or a seed ensemble? Restarts address sensitivity to initialization by brute force. Recursive Decomposition for Nonconvex Optimization shows they scale poorly in rugged continuous problems, but we know of no evidence about them for constraint-trained networks. We will give the ensemble the same total compute as our method and compare its best-of-seeds and mean results.
Why not just put a combinatorial solver in the network? Where a fast linear solver exists, it wins, as the 94–96% Warcraft figure shows. Our target is the constraints such solvers do not cover: first-order relational rules with non-linear or non-optimization structure, where semantic-loss training is the available tool. We say this plainly rather than claim to compete everywhere.
Decisive Checks
The decisive checks run on the 4×4 grid, the Warcraft 12×12 shortest-path benchmark, and sushi preference ranking, each trained over ten or more seeds.
The first check is the diagnostic. Under static semantic loss, the per-example persistence of valid-but-wrong predictions on grids should rise with the computed barrier. The sushi rankings, encoded with pairwise bits so the barrier is zero, should show little persistence. As a deliberate control, the same rankings encoded as a position-assignment matrix, where swapping two items breaks validity for intermediate steps, should show more persistence.
The second check is the intervention. Barrier-calibrated annealing of $k$ should raise grid and Warcraft coherent accuracy and shrink variance across seeds relative to static semantic loss, entropy regularization, weight annealing, and the arbitrary-$k$ ablation. It should give no gain on pairwise-encoded sushi.
The third check is circuit cost. We will report how compiled size and training time grow with $k$, so readers can judge whether the method is practical beyond small grids.
If the diagnostic correlation is absent, the core claim is false regardless of any accuracy gains.
References
- Asymptotically Optimal Inapproximability of Ek-SAT Reconfiguration
- A Semantic Loss Function for Deep Learning with Symbolic Knowledge
- Neuro-Symbolic Entropy Regularization
- On Solution Discovery via Reconfiguration
- Flips in Odd Matchings
- A Theoretical Analysis of Optimization by Gaussian Continuation
- Recursive Decomposition for Nonconvex Optimization - IJCAI-15 Distinguished Paper
- Differentiation of Blackbox Combinatorial Solvers