Circular Traps: Mapping the Energy Landscape of Logic Programs Under Foundedness

When a local-search solver minimizes the number of violated rules in a logic program, it can come to rest in a state that satisfies every rule yet is still wrong. The rules $A \leftarrow B$ and $B \leftarrow A$ are fully satisfied by setting both atoms true, but in Answer Set Programming (ASP, a logic-programming formalism whose solutions, the "stable models," must have every true atom derived from facts) that state is invalid. $A$ and $B$ only hold each other up. Such a cluster is called an unfounded set. This proposal borrows a tool from glass physics, inherent structure mapping, to measure how often a solver's descent ends in these circular traps. Inherent structure mapping takes snapshots of a system at some temperature and slides each one straight downhill to its nearest local minimum, so that a continuous trajectory becomes a sequence of discrete basins. The claim is that the share of the landscape draining into circular traps is a measurable quantity that is distinct from model counts and loop counts. We expect it to explain when non-tight programs become hard for completion-based search. Non-tight programs are those with positive dependency cycles.

The opportunity is concrete. ASP research attributes the difficulty of non-tight programs to the exponential number of loops, and handles circularity syntactically, through loop formulas or nogoods. Physics has a mature way to ask a different question: not how many bad configurations exist, but how much of the space flows into them under descent. Nobody has asked that question for logic programs. Answering it gives a hardness diagnostic. It also suggests a modified quench that removes circular minima from the landscape without enumerating loops.

Core Claim

Take the energy $E(x)$ of a truth assignment $x$ to be the number of violated clauses of Clark's completion, the classical translation that turns each atom's rules into an if-and-only-if definition. Every zero-energy state is a supported model. Some of these are stable models. The rest are supported-but-unfounded, and these are the circular traps. Define the trap fraction at temperature $T$ as

$$\phi_U(T) = \Pr\left[\, q(x_T) \text{ is a zero-energy state containing an unfounded set} \mid E(q(x_T)) = 0 \,\right],$$

where $x_T$ is a snapshot from a Metropolis random walk on $E$ at temperature $T$, and $q$ is a greedy single-flip descent to the nearest local minimum. We claim three things. First, $\phi_U$ differs measurably from the naive ratio (unfounded supported models)/(all supported models), because circular traps have larger basins of attraction than their numbers suggest. Second, $\phi_U$ predicts the time completion-based local search needs to reach a stable model, and it does so after controlling for model counts and loop counts. Third, adding a cheap foundedness step to the quench removes these traps and improves local search on non-tight benchmarks. The foundedness step falsifies the greatest unfounded set of the current assignment, which takes polynomial time for normal programs.

Relation to Prior Work

The ASP side supplies the semantics and the strongest solvers. ASSAT runs a SAT solver on the completion, checks the result for stability, adds loop formulas for unsupported loops, and restarts. Its WalkSAT variant is the closest existing local search over this landscape. A Model-Theoretic Counterpart of Loop Formulas proves that answer sets are exactly the completion models in which every loop is externally supported. That result is what lets us label a zero-energy minimum as a trap. CMODELS2 and clasp move loop checks inside conflict-driven search. We treat them as reference solvers, not as competitors to the diagnostic. Ordering-based encodings (Ben-Eliyahu and Dechter, ordered completion) eliminate circularity by adding index variables, at the cost of larger theories. Our quench keeps the original variables instead.

The physics side supplies the method. Sastry quenches binary Lennard-Jones snapshots and identifies an onset temperature below which inherent-structure energies fall and dynamics turn activated. Baity-Jesi and Parisi apply direct quenches to vector spin glasses and track minimum energies and overlaps. We reuse their protocol on a discrete landscape. The closest work bridging logic and physics is Li, Ma and Zhou, who measure the cluster entropy reached by Survey Propagation and WalkSAT on 3-SAT. They report $s \approx 0.064$, between the dominating ($0.068$) and most abundant ($0.060$) clusters. Their finding motivates ours, since it shows that algorithms land in clusters that are neither the most numerous nor the most dominant. Their setting, however, is classical SAT, where mutual implication is a legitimate solution. Survey Propagation shares this blindness to foundedness. Neural compilations such as Answer Set Networks filter unstable models after message passing. They do not characterize where descent dynamics end up.

Research Program

We first build the mapping tool. Each ground normal program is converted to its completion. We run Metropolis dynamics on $E$ across a temperature ladder and quench snapshots at fixed intervals with steepest single-flip descent, breaking ties randomly. Discrete landscapes have plateaus, which is the quench ambiguity the physics literature also faces. We therefore record two things: the first minimum reached, and the connected equal-energy plateau containing it, explored by bounded flood-fill. We report results under both definitions of an inherent structure. Every zero-energy minimum is checked for unfounded sets with the standard polynomial greatest-unfounded-set computation. This yields $e_{IS}(T)$, $\phi_U(T)$, and the number of distinct stable and trap minima visited.

Second, we need instances where circularity can be varied independently of everything else. We will write a generator for random normal programs at fixed atom and rule density in which a single parameter controls the fraction of positive dependency edges that close cycles. We sweep that parameter from tight programs to dense non-tight ones. On small instances, around 40 to 60 atoms, we compute exact counts of supported and stable models by enumeration. This lets us compare basin weight against raw counts.

Third, the intervention. The foundedness quench alternates greedy descent with falsifying the greatest unfounded set of the current assignment, then resumes descent. We compare running it only at the end against interleaving it within each descent. A trap minimum is no longer an absorbing state under this map. The question is whether removing traps this way costs less than learning loop formulas does.

Baselines

The naive reference is plain WalkSAT on the completion with no loop handling. It measures how often local search returns a supported-but-unstable answer, which is exactly the failure the trap fraction quantifies.

The strongest local-search competitor is ASSAT with WalkSAT, which adds loop formulas lazily. On 43 random Hamiltonian-circuit graphs, ASSAT reports that both its Chaff2 and WalkSAT variants solved all 43 within the time limit, while smodels solved 33 and dlv solved 24. We will reimplement it on the same WalkSAT core as our quench, with identical flip budgets, restarts and noise tuning. Beating it means solving a matched Hamiltonian-circuit suite with fewer flips or less wall-clock time at equal success rate, or solving instances at higher cycle density that it fails on. Those 43 graphs are not available to us, so we regenerate random Hamiltonian-circuit graphs under the same protocol. Our comparison is internal, not a comparison to their timings.

The complete-solver reference is clasp. The file gives no specific runtime numbers for it; its paper reports speedups of "multiple orders of magnitude" without numerical text in the file. We will run it with default settings on every instance. Its runtime and its count of learned loop nogoods serve both as a hardness target and as a competing hardness predictor.

For the diagnostic claim, the competing predictors are structural and count-based. They are the number of elementary loops, the size of the largest strongly connected component, induced width, and the exact log-ratio of stable to supported models. A predictor based on $\phi_U$ beats them if it explains significant additional variance in local-search time and clasp conflicts after all of them are included as covariates.

The key ablation is the foundedness quench with interleaving removed, so that unfounded sets are falsified only at the end. This isolates whether trap removal during descent, rather than final repair alone, carries the gain.

Why not just…?

Why not just count supported and stable models exactly? Counting tells you how many traps exist, not how much of the space drains into them. Li, Ma and Zhou's result that algorithms reach intermediate-entropy clusters is direct evidence that these two quantities can come apart (Li, Ma and Zhou). The decisive test compares instances with matched supported-to-stable ratios. If $\phi_U$ adds no predictive power beyond the counts, the landscape view is redundant and we will say so.

Why not just use clasp, which already handles circularity efficiently? For solving normal programs, clasp will likely remain fastest, and we do not claim otherwise. The contribution here is an explanation of hardness and a better local search. Local search still matters where incomplete, parallel or neural solvers are used, as in Answer Set Networks. Clasp's loop-nogood count is included as a rival predictor, so the experiments test directly whether its own statistics already capture what $\phi_U$ measures.

Why not just add loop formulas lazily, as ASSAT does? This is the real threat to the intervention. Loop formulas accumulate clauses and can exhaust memory; CMODELS2 reports ASSAT failing with memory errors on automata benchmarks. The foundedness quench stores nothing. If matched runs show no gain over lazy loop formulas, we will drop the intervention claim and keep the diagnostic.

Why not just use Survey Propagation or whitening? These methods operate on the classical completion, where circular states are valid solutions. They therefore cannot distinguish traps from stable models, and their marginals will include unfounded mass. We will measure that mass directly by labeling SP-decimated solutions on small instances.

Proposed Experiments

The first decisive check is whether traps are over-weighted. On the random-program sweep, we compare $\phi_U$ at high temperature with the exact fraction of supported models that are unfounded. A consistent excess would mean circular traps have larger-than-average basins, which is the central empirical claim.

The second check concerns onset. Following Sastry, we locate for each cycle density the temperature where $e_{IS}(T)$ departs from its high-temperature plateau. We then test whether $\phi_U$ rises sharply below that point as cycle density increases, which would signal that circularity reshapes the low-energy landscape and does more than add minima.

The third check is predictive power. Across the random-program suite, regenerated Hamiltonian-circuit instances and the Blocks World planning instances used by ASSAT, we regress log flips-to-stable-model for WalkSAT with loop formulas, and log clasp conflicts, on $\phi_U$ together with all structural and count covariates. All three checks are reported under both the first-minimum and plateau definitions of an inherent structure, so that conclusions do not depend on quench ambiguity.

The fourth check tests the intervention. On the same suites, at equal flip and time budgets, we compare the foundedness quench, its end-only ablation, ASSAT with WalkSAT, and plain WalkSAT. The comparison uses success rate and median cost to reach a stable model.