When a language model turns a word problem into formal logic and hands it to a theorem prover, the prover's answer can only be as good as the translation. Current systems try to catch bad translations by having several model instances argue about them, a setup called multi-agent debate. Debate, though, is settled by persuasion or by a majority vote, and both are known to fail. Agents cave to confident majorities, and several agents often share the same wrong reading of a sentence. We propose a different way to settle these arguments. When two agents translate the same sentence differently, first "lift" each translation into a general rule by replacing names like Alice or seat 3 with placeholder variables. Then have the solver build the smallest concrete world, populated with fresh, meaningless entity names, in which the two rules disagree. The dispute becomes one local yes/no question: does this sentence allow this tiny situation? Judging that question is far easier than judging the whole problem, and it does not depend on who argued louder.
In two sentences for a colleague: debate over formal translations should end with a solver-built counterexample, not a vote. Stripping the entity names out first makes those counterexamples small, unbiased, and reusable across problems. The note tests whether this adjudication step beats the strongest existing debate-plus-solver system and its simpler alternatives, especially when entity names and problem domains shift.
Core Claim
Lifting constants to variables has a long history as a way to separate the structure of a rule from the particular things it mentions. Bottom-up propositionalisation replaces the constants shared between examples and background facts with variables, and this shrinks an inductive-logic search space enormously. Unification Networks learn which symbols should become variables and then reuse the resulting template on unseen examples, sometimes from as few as 50 training examples. We borrow the lifting operation from this work but use it for a new job: as a checking step inside a debate, not as a learning step inside a single model.
The claim is specific. Give two candidate formalizations of one premise sentence, $\Phi_A$ and $\Phi_B$, each lifted so that its constants are variables. Take the background constraints $\mathcal{B}$ already agreed for the problem. A distinguishing witness is a binding $\sigma$ of those variables to fresh entity names, together with a small world $w$, such that
$$ w \models \mathcal{B} \wedge \Phi_A(\sigma) \wedge \neg \Phi_B(\sigma), $$
or the same with $A$ and $B$ swapped. The satisfiability solver (Z3) finds $w$. The world is then rendered back into a short scenario, and agents judge only whether the original sentence permits that scenario. We predict that witness adjudication will pick the correct formalization more often than majority vote over the same candidate pool. We also predict that it will lift final accuracy above the best single agent. Lastly, we predict that it will degrade much less than ground-level debate when entity names or domains are replaced.
Relation to Prior Work
The closest system is MAD-Logic. Its agents translate a problem into logic programming, first-order logic, and satisfiability formats and debate the translations. Five agents then debate the answer, and a majority vote decides. MAD-Logic motivates our work in two ways. It shows that debate helps translation. It also reports three limits: accuracy drops on out-of-distribution logical structures, extra rounds past about three corrupt formulas that were already correct, and when the solver hits a syntax error the model is asked to simulate the solver, which brings back ungrounded reasoning. Our design differs at the point where disputes are resolved. MAD-Logic debates ground translations and aggregates socially. We localize each dispute to a sentence, lift it, and let a solver-built witness decide.
Logic-LM is the single-agent ancestor. It translates text into logic, solves with Z3, Prover9, or Pyke, and repairs syntax errors from solver logs. It supplies our solver pipeline. It also shows the gap we target: a translation that is syntactically valid but unfaithful to the text passes through unchallenged. AR-LSAT's Analytical Reasoning Machine uses a fixed set of about 20 hand-written functions to express logic-game rules. Our lifted sentence schemas are a learned, open-ended counterpart to that set.
Two debate studies constrain the design. The controlled Knight–Knave–Spy study finds three things: debate is bounded by the best agent's own ability, agents in a majority stay put more than 97% of the time, and arguments that follow valid reasoning correct peers more than 90% of the time. That is why we give dissenters a checkable artifact rather than rhetoric. FORD documents the compromise-under-pressure behavior. The diagnostic study of real-world debates shows that consensus is a poor proxy for correctness, which motivates ending debate on validity rather than agreement.
Context-hygiene methods are complementary and serve as baselines, not as rivals in mechanism. Memory masking filters out erroneous earlier turns. RUMAD learns which agents should talk to which. Both manage who hears what; neither changes what counts as evidence.
Research Program
The system has four parts.
The first part is per-sentence translation with lifting. Two or three agents, preferably from different model families, independently translate each premise into first-order logic over a shared vocabulary. A deterministic post-processor then replaces constants with typed variables and normalizes predicate names. Two translations that differ only in naming therefore compare as identical, which cuts down on false disputes.
The second part is dispute localization and witness construction. Wherever the lifted schemas are not logically equivalent under the agreed background (checked with Z3), the solver searches for a smallest distinguishing world over fresh nonce entities, such as "Zorvil" or "Pask." A template-based renderer, not a language model, verbalizes the world, so the scenario cannot be silently changed in rendering.
The third part is local adjudication. Each agent, plus an independent judge instance that has not seen the debate, answers whether the sentence permits the scenario. Answers are aggregated. If the answer is ambiguous, the sentence is marked genuinely ambiguous and both readings are carried into solving. Winning schemas are fixed, so later rounds cannot reopen them. This locking is our proposed fix for over-deliberation: evidence only accumulates and is never re-debated.
The fourth part is a lifted schema library. Adjudicated sentence–schema pairs, stored with constants removed, are retrieved as few-shot examples for later problems. We measure whether this reuse helps on held-out structures rather than only on near-duplicates.
Along the way we will analyze three things: how often disputes are purely naming disputes, how often witness judgments agree with the gold formula, and whether disagreement-driven witnesses carry more information than randomly sampled worlds.
Baselines
The naive reference points are single-agent chain-of-thought and single-pass Logic-LM. Both use the same backbone models and the same few-shot examples. On FOLIO, FOLIO reports GPT-4 translation at about 65.21% execution accuracy, and specialized solver methods, including Logic-LM with GPT-4, at around 77–78% accuracy. On AR-LSAT, Logic-LM reports GPT-4 improving from about 35% to over 43%.
The strongest existing method is MAD-Logic. The file gives only a relative figure for it: over 2% better than the best prior multi-agent methods on AR-LSAT, with no absolute AR-LSAT or FOLIO number on Lacuna. We will therefore re-run it ourselves with our backbones, round limit, and token budget. Beating it means higher final accuracy on FOLIO and AR-LSAT at equal or lower token cost, and a smaller accuracy drop on the renamed and domain-shifted splits.
A self-consistency baseline samples the same total number of formalizations and takes a majority vote over the solver's answers. It uses exactly the same candidate pool as our method, so any difference comes from adjudication alone. We also run a memory-masking variant of debate, following Memory masking, under the same budget.
Three ablations isolate the key ingredients. The first uses witnesses built with the problem's original constants instead of fresh ones, which tests the lifting step. The second uses randomly sampled worlds that satisfy one schema but are not chosen to separate the two, which tests targeting. The third replaces witness adjudication with free-text debate over the disputed sentence, which tests whether the artifact, rather than the extra attention, does the work. All methods share tuning budgets, chosen on a common development split.
Why not just…?
Why not just take a majority vote over several sampled translations? Voting fails exactly when errors are shared. The diagnostic study found that when the initial majority is wrong, outcome-only aggregation locks in the error, whereas better deliberation recovers the correct answer 74% of the time. Our pool-matched self-consistency baseline tests this directly on FOLIO, where gold formulas let us score which candidate each method selects.
Why not just use Logic-LM's self-refinement? Its feedback comes from solver error logs, so it catches syntax errors but not a valid formula that says the wrong thing. That kind of error is plausibly behind much of the roughly one-third of GPT-4 FOLIO translations that fail to execute correctly. Our translation-accuracy metric will show whether refinement alone closes that gap.
Why not just check whether answers stay the same when entities are renamed? This is the most serious threat, because it needs no debate at all. A renaming check flags that a translation is unstable, but it cannot say which competing reading is right, and it misses stable but wrong translations. We include it as a baseline, both as a filter and as a selector. If it matches witness adjudication, the debate component is unnecessary and we will report that.
Why not just use one stronger model? The Knight–Knave–Spy study suggests debate cannot exceed its best agent. Our hypothesis is that witness adjudication can, because a local yes/no judgment is easier than solving the whole problem. We test this by comparing against the best single member of each agent team. If we fail to exceed it, that finding is itself informative.
Proposed Experiments
The primary benchmarks are FOLIO, including its WikiLogic and HybLogic splits (GPT-4 scores 75.43% and 53.10% on them respectively), and AR-LSAT. We add ProofWriter for depth and Knight–Knave–Spy for measuring how often agents switch from right to wrong answers and back. LogicalDeduction and ProntoQA are sanity checks only, since MAD-Logic already reports 100% on both.
To measure distribution shift, we build three variants. The first renames every entity on FOLIO and AR-LSAT to a nonce token. The second moves AR-LSAT games into new surface domains. The third holds out one AR-LSAT game type (ordering, grouping, or assignment) when building the schema library.
We report five metrics: final accuracy, translation execution accuracy against gold FOLIO formulas, witness-judgment agreement with the gold formula, flip rates, and accuracy as a function of round count against tokens used.
Four results would decide the question. The first is whether witness adjudication selects gold-equivalent translations more often than voting over an identical pool. The second is whether the fresh-constant ablation loses accuracy, especially on the renamed splits. The third is whether accuracy keeps rising or holds steady past three rounds, rather than falling as MAD-Logic reports. The fourth is whether the full system exceeds both re-run MAD-Logic and the renaming-consistency baseline at matched cost. If the renaming baseline matches us, or the fresh-constant ablation makes no difference, the lifting claim fails.
References
- Reduction of ILP Search Space with Bottom-Up Propositionalisation
- Learning Invariants through Soft Unification
- MAD-Logic: Multi-Agent Debate Enhances Symbolic Translation and Reasoning
- Logic-LM: Empowering Large Language Models with Symbolic Solvers for Faithful Logical Reasoning
- AR-LSAT: Investigating Analytical Reasoning of Text
- Can LLM Agents Really Debate? A Controlled Study of Multi-Agent Debate in Logical Reasoning
- Examining Inter-Consistency of Large Language Models Collaboration: An In-depth Analysis via Debate
- A Diagnostic Study of Multi-Agent LLMs for Real-World Debates
- Multi-Agent Debate with Memory Masking
- RUMAD: Reinforcement-Unifying Multi-Agent Debate
- FOLIO: Natural Language Reasoning with First-Order Logic