Measuring Where AC-Unification Actually Explodes: A Polyhedral Cost Oracle for Equational Provers

Many automated theorem provers spend most of their time matching and unifying terms, that is, finding variable substitutions that make two symbolic expressions equal. The cost becomes severe when an operator is associative and commutative (AC), like $+$ or $\times$, because the order and grouping of arguments stop mattering. AC-unification is known to reduce to solving linear Diophantine equations (integer equations whose unknowns must be non-negative integers). Its worst-case behaviour is grim: matching is NP-complete, and a complete set of unifiers can be doubly exponential in size. What nobody has measured is which of these worst cases actually occur inside real proofs, and why. The theory has bounds and no measurements. The prover literature has measurements, but on ten hand-picked problems from 1985 and 1995.

This note proposes to close that gap using polytope decomposition, the practice of cutting a cone or polytope into simplices so that counting and enumeration become manageable. Unification can blow up in two different places. The first is the size of the Diophantine "basis," the minimal solutions. Polyhedral geometry bounds this by the determinants of simplicial pieces of the solution cone. The second is the number of ways those basis vectors combine into complete unifiers. We will log every AC-unification problem a prover generates on public equational benchmarks, measure both quantities, and test whether a cheap determinant-based estimate predicts which unification calls will explode. If it does, the prover can use that estimate to postpone or skip those calls.

Core Claim

Our hypothesis is that the AC-unification problems arising in practice almost all sit in a regime of small subdeterminants. Variable multiplicities are mostly 1 or 2, so the minimal-solution basis stays small and nearly equals the cone's extreme rays. When explosion happens, it comes mainly from the second stage, where basis elements combine into complete unifiers.

We make two predictions. First, a bound computed from a triangulation of the solution cone will separate cheap calls from explosive ones far better than the syntactic proxies provers use now, such as argument counts. Second, a scheduler that uses this bound will reduce total prover time on AC-heavy problems. Writing $C$ for the cone of non-negative solutions, $\{\sigma\}$ for a triangulation of $C$ into simplicial cones, and $G_\sigma$ for the integer generator matrix of cone $\sigma$, every minimal solution lies in some fundamental parallelepiped. That gives

$$|H(C)| \le \sum_\sigma \big(|\det G_\sigma| + \dim C\big),$$

where $H(C)$ is the set of minimal solutions. The bound follows from the standard fact that the half-open parallelepiped of $\sigma$ contains exactly $|\det G_\sigma|$ lattice points.

The novelty lies in three places. The decomposition is used as a measuring instrument and as a predictor of cost, not merely as a solver. The question is posed against measured prover workloads. And the work tests, for the first time, whether the bounded-subdeterminant assumptions of polyhedral enumeration theory hold in a real application.

Prior Work and Where This Sits

Three papers motivate the reduction. Associative-Commutative Rewriting and A Complete Unification Algorithm for Associative-Commutative Functions map AC-unification onto minimal non-negative solutions of linear Diophantine systems, using flattened multiset terms. They solve those systems by search and never ask what geometric structure the systems have in practice. We take their reduction unchanged and study the systems it produces.

Two papers supply the method. Enumerating Integer Points in Polytopes with Bounded Subdeterminants reduces integer-hull enumeration to simplices with bounded facet widths, enumerated slice by slice. Its polynomial guarantee requires bounded subdeterminants and all $n\times n$ minors non-zero, and the paper contains no experiments at all. A Polynomial Time Algorithm for Calculating Fourier-Dedekind Sums uses a modular Barvinok decomposition into simplicial cones, a way to count lattice points without listing them. Its prototype is described as "under construction." We reuse the triangulate-then-count idea. We also report, as a side result, whether the bounded-subdeterminant and non-zero-minor conditions hold on the cones that AC-unification actually generates. Neither paper could answer that question about its own assumptions.

Two papers constrain the design and serve as competitors. Experiments with Associative-Commutative Discrimination Nets speeds up one-directional AC-matching with a polynomial-time linear filter and precompiled automata up to rank 5. It does not address unification with variables on both sides, which is what critical-pair generation needs. Equational Reasoning using AC Constraints sidesteps flattened AC-unification by constraining terms to AC-minimal representatives. Its pruning conditions are only sufficient, and it was evaluated on ten instances.

Learned guidance is a third line of work. Learning Equational Theorem Proving guides equational provers with tree-structured neural networks and treats the prover's unification engine as a black box. It also reports that standard Transformers failed to converge in this setting. That result constrains our learned baseline to a tree-structured model.

Research Program

The first component is instrumentation. We will take an open AC-completion prover and log every AC-unification call during runs on public suites. For each call we record:

  • the Diophantine system;
  • the minimal-solution basis;
  • the number of complete unifiers;
  • the wall-clock time;
  • whether any resulting critical pair was ever used in the final proof.

This produces, as far as the file shows, the first public corpus of real AC-unification instances.

The second component is geometric characterization. For each logged system we compute:

  • the dimension of the solution cone;
  • its extreme rays;
  • a triangulation;
  • the determinants $|\det G_\sigma|$;
  • the maximum subdeterminant;
  • whether all minors are non-zero.

We then measure separately how much of the observed cost comes from basis size and how much from combining basis elements into unifiers.

The third component is the cost oracle. We compute the determinant bound above, plus a second estimate of the combination stage, and then use them in two ways. The first use is to rank unification calls by predicted size. The second is a scheduler that postpones calls predicted to be explosive, the same way provers already postpone large clauses. Postponing is not discarding, so the prover stays complete under fair processing.

The fourth component is an implementation of the slice-based simplex enumeration from Jiang and Basu, used to compute the basis inside each simplicial cone. We benchmark it against the prover's native solver. This is a direct empirical test of an algorithm that has only ever existed on paper.

Baselines

The do-nothing reference is the unmodified prover. It uses its native AC-unification solver and processes calls in its default order, on the same machine, time limits and problems. Every speedup is reported relative to this run.

The strongest existing competitor for overall prover performance is consistent unfailing completion from Equational Reasoning using AC Constraints. On problem E6 it reports "5928 critical pairs and 64 rules," against "over 15000 critical pairs and 137138 rules" without AC constraints. We will reimplement it, or run it if available, on the same Lusk–Overbeek and ring problems. Beating it means fewer critical pairs or lower wall-clock time at equal solve rate. The fairer target, since the two methods are complementary, is whether adding our scheduler on top of AC constraints improves it further.

For the matching layer, Experiments with Associative-Commutative Discrimination Nets reports "up to 2.2x" total runtime reduction and 88% full rejection on uqsl2. We keep discrimination nets switched on in every configuration, so that our gains are measured on unification only and are not confused with gains in matching.

For the predictor, three baselines compete with the determinant bound on the same logged corpus:

  • a syntactic baseline that predicts cost from the product of argument counts and the maximum multiplicity;
  • the actual size of the extreme-ray set, which ablates away the parallelepiped term;
  • a tree-structured network in the style of Learning Equational Theorem Proving, trained on the same logged calls with matched tuning budget.

The syntactic baseline is the most important ablation, because it isolates whether geometry adds anything. On AIM, that paper reports 70.2% success for 3SIL against 65.5% for Waldmeister within 60 seconds. We use AIM as a control set for the scheduler. We found no reported runtime result on Lacuna for any AC-unification solver on real prover-generated systems.

Why not just…?

Why not just count arguments to predict explosion? This is the real threat. If multiplicities are almost always 1, the cone is close to unimodular and the determinant term adds nothing. The predictor experiment settles the question directly. If the syntactic proxy matches the determinant bound in rank correlation and in scheduler gains, we will say so. In that case the contribution narrows to the empirical characterization, which still has value.

Why not just use discrimination nets? They address matching, where one side has no variables. Their automata stop at rank 5. Critical-pair generation requires unification with variables on both sides, which these nets do not handle. Our instrumentation will report what fraction of AC time goes to unification versus matching. If unification is a negligible fraction, this proposal's practical claim fails.

Why not just avoid AC-unification with AC constraints? Marché's pruning conditions are only sufficient. Even with them, E6 still produced 5928 critical pairs, and the method was tested on ten instances. We run both methods and their combination. If AC constraints alone dominate on the larger suite, the scheduler is unnecessary for that prover style.

Why not just call a general integer solver or LattE? That would replace the solver, but it would not answer which calls to make at all. Our oracle runs before any solving. In the enumeration benchmark, LattE-style triangulation is treated as an additional engine, not as a rival to the predictor.

Proposed Experiments

The suites are:

  • the Lusk–Overbeek E1–E6 problems;
  • the ring problems wos21, RNG015-6, RNG023-6 and RNG024-6;
  • the REVEAL domains (Gröbner bases, group theory and Robbins algebra, including uqsl2);
  • the roughly 3,500 AIM theorems as a control with little AC content.

The logged corpus is split by problem to train the learned predictor.

The first decisive check is the regime claim. It holds if the median maximum subdeterminant is small, below about 4, and if the combination stage accounts for most explosive calls. Either result is publishable as the first measurement of this kind.

The second check is prediction quality. We compare predictors by Spearman correlation with the true number of unifiers and true time, and by precision at catching the top 5% most expensive calls. The determinant bound must beat the syntactic proxy by a clear margin across three random problem splits.

The third check is end-to-end. We report solve rate, total time, and critical pairs at fixed time limits, for the baseline prover, AC constraints, our scheduler, and AC constraints with our scheduler. As a negative control, the scheduler must cost nothing measurable on AIM.

The fourth check asks whether the slice-based simplex enumeration ever beats the native solver in wall-clock time. We report its constant factors honestly, whatever they turn out to be.