Clause-Level Consensus: Solving Logic Puzzles from Noisy LLM Translations with Weighted MaxSAT

A common way to make language models reason reliably is to have the model translate a problem into formal logic and hand that logic to an exact solver. Logic-LM and LINC do this with Z3 and Prover9. The weak link is the translation. One mistranslated clue makes the solver return "unsatisfiable" or a confidently wrong answer, and the chance that a whole translation is error-free shrinks quickly as problems grow.

We propose treating each translated clue as a soft, violable constraint rather than a hard fact. We sample several translations of every clue and turn their agreement into a penalty weight. A weighted MaxSAT solver (a solver that finds the assignment minimizing the total weight of violated constraints) then picks the jointly most consistent reading of all the clues together. This idea comes from 1990s constraint-based parsing. There, statistical guesses entered a symbolic grammar as penalties the grammar could override, and entering them as hard rules was disastrous. We move it to the setting where LLM reasoning currently breaks down: large logic-grid puzzles.

Core Claim

Voting over whole answers or whole formal programs fails when every sample contains some error, even if each error sits in a different clue. Voting at the level of individual clues can recover the correct solution in exactly that case, because the puzzle's structure lets the solver reject the minority misreadings.

A simple estimate shows the stakes. Suppose each clue is mistranslated independently with probability $p$ and a puzzle has $m$ clues. Then a single translation is fully correct with probability $(1-p)^m$, which decays exponentially in $m$. Voting over whole programs inherits this decay. Clause-level consensus needs only that, for most clues, the correct reading is the most frequent one, and that the puzzle's hard constraints rule out the wrong readings that remain. We therefore predict that the gap between the two methods widens with puzzle size. That is the regime where ZebraLogic shows even reasoning models plateau.

Relation to Prior Work

The mechanism is borrowed from weighted constraint parsing. Eliminative Parsing with Graded Constraints scores a candidate analysis by multiplying the weights of the constraints it violates. Guiding a Constraint Dependency Parser with Supertags added a statistical tagger's predictions to such a parser, with these results on German text:

  • as soft constraints (penalty 0.9), unlabelled accuracy rose from 89.6% to 91.8%;
  • as hard constraints (penalty 0.0), the result was "disastrous."

That paper supplies our design principle. The LLM plays the role of the tagger, and the puzzle's structural rules play the role of the grammar that can veto it.

The motivating evidence comes from benchmarks. ZebraLogic and LR²Bench show accuracy collapsing as search spaces grow. ZebraLogic names solver integration as future work but never runs it.

Three lines of work constrain the design:

  • Logic-LM and LINC use hard solvers. Logic-LM repairs only syntax and runtime errors by feeding solver messages back to the model. Neither weighs competing readings.
  • SoLA/DiLA relaxes SAT into continuous MaxSAT with an LLM warm start. It is built for satisfiable, unweighted instances and assumes the translation is correct, so it speeds up solving rather than fixing translations.
  • LLM Routing as Reasoning: A MaxSAT View uses weighted MaxSAT, but for choosing which model to call, not for resolving the content of a reasoning problem.

Self-Consistency Preference Optimization votes over final answers. We vote over the meanings of individual clues.

Research Program

Take a puzzle with a known typed vocabulary, such as ZebraLogic's houses and attributes. The puzzle's generic structure is encoded as hard constraints: each attribute value is used exactly once and each house gets one value. The model translates each clue $i$ separately, $N$ times, into a small formal language.

Candidate formulas for a clue are grouped by meaning, not by surface form. Two formulas count as the same reading if a solver shows them equivalent under the hard constraints. This gives clue $i$ a set of distinct readings $k$, each with empirical frequency $f_{ik}$.

We add one selector variable per reading and require that each clue chooses at most one reading. Choosing reading $k$ costs $-\log f_{ik}$. Choosing no reading at all costs a large penalty $\lambda$, which lets a hopelessly mistranslated clue be dropped rather than poisoning the solution. The solver then solves

$$\min_{x,\,s}\ \sum_i \sum_k s_{ik}\,(-\log f_{ik}) \;+\; \lambda \sum_i \Big(1-\sum_k s_{ik}\Big)$$

subject to the hard puzzle constraints and to each selected reading holding under the grid assignment. Here $x$ is the grid assignment and $s_{ik}\in\{0,1\}$ selects reading $k$ of clue $i$. Exponentiating the negated objective recovers the multiplicative score of Heinecke et al., so this is their parser's objective applied to clue interpretation.

We use Z3's optimization mode. Two further steps follow the solve:

  • Uniqueness check. Pin the selected readings and test whether a second solution exists. Well-formed puzzles have unique solutions, so a non-unique optimum flags a likely dropped or wrong clue. We report such cases as abstentions or low-confidence outputs.
  • Weight variants. Besides frequency weights, we test token log-probability weights and uniform weights. The uniform variant isolates whether the weighting carries information or whether soft constraints alone do the work.

The analysis centres on the tension noted in the file. DiLA reports LLM initial guesses "up to 99% correct," while ZebraLogic reports near-zero accuracy on large puzzles. We will measure per-clue translation accuracy as a function of puzzle size. We expect it to stay high even where end-to-end accuracy collapses, which would place the failure in search rather than in reading the clues. If per-clue accuracy also collapses, clause-level consensus has nothing to work with. That is a clean negative result we will report.

Baselines

Direct answering. The naive reference is the same open model (Llama-3 8B and 70B) and GPT-4o answering directly with chain-of-thought. For comparison, the file reports non-reasoning models at "0% or 1%" on ZebraLogic X-Large.

Reasoning models. The strongest end-to-end competitor is test-time-compute reasoning models. ZebraLogic reports:

  • o1-full at 81.0% overall accuracy;
  • DeepSeek-R1 at 78.7% overall;
  • o1-preview at 17% on X-Large.

We treat these reported figures as the headline bar. Beating it means our pipeline with a non-reasoning translator exceeds 17% on X-Large, and matches or exceeds 81.0% overall. The overall target is ambitious, and falling short of it while winning on X-Large would still be informative.

Hard-solver pipeline. The strongest method in the same family is a Logic-LM-style pipeline: one translation, a hard Z3 solve, and self-refinement on solver errors. We run it with the same translator and give it the same total number of translation calls, $N$ per clue spent on refinement rounds. On ZebraLogic we found no reported result on Lacuna for Logic-LM or any solver-aided pipeline. On AR-LSAT, Logic-LM with GPT-4 reports 43%, versus about 35% for chain-of-thought. On LogicalDeduction it reports "nearly 90%." Those are the numbers we must beat on those datasets.

Program-level voting. The strongest ablation samples $N$ whole formal programs, solves each with a hard solver, and takes a majority vote over the resulting solutions. It uses exactly our samples and differs only in where voting happens. A second ablation keeps our pipeline but sets uniform weights.

Fairness. Every method gets the same translator, the same sample budget, the same solver timeout, and prompts tuned on the same held-out split of 50 puzzles.

Why not just…?

Why not just use a reasoning model? LR²Bench reports average exact match of 23.6% for o1-preview and 20.0% for DeepSeek-R1. ZebraLogic reports under 50% on the hardest tiers, with models looping in the "redundancy trap." Reasoning models are still a real competitor on small and medium puzzles, where they are near ceiling. Our claim is limited to large instances, and the per-tier comparison will show where the crossover lies.

Why not just take a majority vote over answers or over full translations? Answer-level Best-of-N "failed to break the complexity barrier" on ZebraLogic's hardest puzzles. Program-level voting over formalizations is the real threat, because it uses a solver and many samples just as we do. The two methods differ only when no sample is fully correct but each clue's plurality reading is. The decisive experiment below isolates exactly those instances. If program-level voting matches us there, the weighted formulation adds nothing, and we will say so.

Why not just refine the translation until the solver stops complaining, as Logic-LM does? Self-refinement reacts to syntax and runtime errors. A well-formed but wrong clue produces no error message: it yields either an unsatisfiable result with no pointer to the culprit, or a wrong unique answer. The weighted solve localizes the culprit automatically, because the dropped or overridden clue is part of the output. We will count how often refinement converges to a satisfiable but wrong program.

Why not just train the model to follow constraints better, as in curriculum DPO? Step-by-Step Mastery gains 5.5% on FollowBench L5. Its authors note that failures persist when the model lacks the underlying reasoning. Training could improve per-clue translation accuracy, but that is complementary: a better translator only raises the frequencies $f_{ik}$ our method consumes.

Proposed Experiments

Benchmarks. Our primary benchmark is ZebraLogic, all 1,000 puzzles, with results broken down by tier, search-space size, and Z3 conflict count. We add the Logic Puzzles subset of LR²Bench, including its 4x7 instances where the best models fall below 10%. Using Logic-LM's datasets, LogicalDeduction and AR-LSAT, lets us compare against its published numbers.

Metrics. We report puzzle exact match, cell accuracy, abstention rate from the uniqueness check, and per-clue translation accuracy against gold formalizations derived from ZebraLogic's generator.

Decisive check 1: the no-correct-sample subset. We isolate puzzles where none of the $N$ full translations is correct. On this subset, program-level voting and hard-solver pipelines are near zero by construction. Our method's accuracy there directly measures clause-level recovery.

Decisive check 2: controlled noise injection. We corrupt gold formalizations clause by clause at rates $p$ from 0.02 to 0.3. For program-level voting, we test whether accuracy tracks $(1-p)^m$. For our method, we test whether it stays flat until per-clue plurality accuracy fails.

Decisive check 3: the weighting ablation. Frequency weights must beat uniform weights. Separately, any hard encoding, which is the $\lambda\to\infty$ limit with a single reading, must lose. This replicates the supertag result in the LLM setting.

Decisive check 4: conflicting premises. We add one contradictory distractor clue to ZebraLogic puzzles. We then test whether the solver drops that clue rather than returning unsatisfiable, a situation hard pipelines cannot handle by design.