Letting a Solver Settle the Debate: Moving the Reasoning Threshold from Global to Local Judgments

When several small language models argue about a logic puzzle, the debate usually ends with whatever answer the majority already held, even when a lone agent is right. The standard explanation is that small models are simply too weak to reason. This proposal tests a sharper hypothesis. Small models may be able to make local judgments that they cannot combine. Asked "does argument A contradict argument B?", a small model may answer reliably. Asked to weigh a whole tangle of mutually attacking arguments and decide which set survives, it fails. That second, global step is exactly the problem formal argumentation theory studies. It models a dispute as a directed graph whose nodes are arguments and whose edges are attacks, and it asks which subsets of arguments are internally consistent and can defend themselves against every attacker. For graphs of debate size, exact solvers answer this question cheaply.

We therefore let small agents debate and then make only pairwise attack judgments. An exact argumentation solver decides the outcome, not a vote or a model acting as judge. The central question is whether this moves the emergent reasoning threshold, the model size below which multi-step reasoning is near chance. The hope is that it pushes the threshold down to the scale at which models can make single local judgments. A second question follows: whether the structure of the resulting attack graph predicts where plain debate fails. Useful structural measures are the number of attack cycles, the size of the largest strongly connected component, and how far the graph is from being acyclic.

Core Claim

The claim has two parts. First, for sub-threshold models, the ceiling on debate comes mainly from aggregation, not from local reasoning. Handing global resolution to an exact solver should recover a large share of the gap to much larger models. Second, the structural complexity of the attack graph a debate produces is what separates debates that plain aggregation can settle from debates it cannot.

A back-of-envelope argument motivates the first part and makes it falsifiable. The research file notes that a chain of $n$ dependent steps, each correct with probability $P$, succeeds with probability about $P^n$. That compounding is what produces sharp, threshold-like curves. Under solver adjudication, the status of the target claim depends only on the $k$ attack edges on its attack–defense paths. If each edge is labeled correctly with probability $q$, success is at least

$$ \Pr[\text{correct}] \gtrsim q^{k}, $$

where $k$ is set by the graph's structure rather than by the length of the reasoning chain. The prediction is that $q$ exceeds $P$ at small scales and that $k$ stays small for most instances. The bound is loose, because some edge errors do not flip the outcome. Its value is that it tells us what to measure: edge accuracy $q$ as a function of model size, and decision-relevant edge count $k$ as a function of puzzle structure.

Relation to Prior Work

Three debate studies motivate the proposal by documenting the aggregation failure.

  • Can LLM Agents Really Debate? ran controlled debates on 1,800 Knight–Knave–Spy puzzles. It found that more than 97% of majority agents never move, that correct minorities cave, and that "intrinsic reasoning strength" dominates. It resolves outcomes by majority or a supervisor model.
  • Examining Inter-Consistency of LLM Collaboration via Debate introduced a formal debate protocol with an LLM judge. It found that weaker agents can derail stronger ones, and that a GPT-4 judge adds only about 0.6% accuracy.
  • Sparse Communication Topology shows that the graph of which agents talk to whom matters.

None of the three examines the graph of what the agents say, and none replaces the judge with formal semantics. We keep their debate protocols and replace only the resolution step.

The threshold literature constrains the design. Self-Verification, Self-AMPLIFY, and TMLU all show that asking small models to verify, explain, or reason step by step can make them worse. So our agents are never asked to verify a whole solution, only single pairwise relations. Computational Reasoning of LLMs places a state-tracking threshold near 4B parameters. That motivates keeping each query stateless. Minimal Parameter Budget for Implicit Reasoning ties capacity to graph search entropy but does not model mutual refutation. We test whether attack-graph structure plays the analogous role for defeasible reasoning.

The method comes from the argumentation literature:

  • PrefSat encodes three-valued labellings into a SAT solver and solved all tested graphs of up to 200 arguments. We use it for preferred semantics.
  • Backdoor-treewidth supplies argBTW and the structural parameters we record. Backdoor-treewidth measures how close a graph is to a tractable class once a small, well-structured set of arguments is deleted.
  • Parallel SCC recursion supplies the decomposition into strongly connected components.
  • The claim-centric view matters because many arguments in a debate support the same answer. We therefore evaluate acceptance of claims, not of individual arguments.

Research Program

The debate phase. Each agent proposes an answer and breaks its reasoning into atomic arguments. An atomic argument is a single claim with its stated support, such as "player 3 is a knave, because if truthful, statement 3 contradicts statement 5". Agents then exchange arguments over several rounds under the protocol of Can LLM Agents Really Debate?, optionally on a sparse ring topology.

Attack labeling. For candidate pairs of arguments, a model answers one isolated question: does A undermine B? No transcript history is included. Candidate pairs are those sharing an entity or claim, which avoids quadratic cost.

Resolution. The labeled edges form an argumentation graph. We compute two outcomes. The grounded extension is the unique, skeptical outcome and is computable in polynomial time. The preferred extensions are the maximal self-defending sets and are computed via PrefSat. The final answer is the claim accepted under the chosen semantics. We record which fallback applies when no candidate answer is accepted.

Structural record. For every instance we store the SCC sizes, cycle counts, backdoor-treewidth relative to acyclic graphs, and the decision-relevant edge count $k$.

Gold edges. On Knight–Knave–Spy puzzles, each atomic argument's consistency with the true assignment is mechanically checkable. This gives gold attack labels, so we can measure edge accuracy $q$ exactly and separate labeling errors from resolution errors.

Baselines

Naive reference. The naive reference point is a single agent answering once. Its pre-debate accuracies on Knight–Knave–Spy are reported in Can LLM Agents Really Debate?: 17.33% at size 4 and 3.33% at size 8.

Strongest debate baseline. The strongest debate baseline is that paper's own debate with majority resolution, reported at 69.33% at size 4 and 36.00% at size 8. It is the strongest competitor because it uses the same task, a similar protocol, and simpler aggregation. We rerun it with our model roster rather than comparing against the published figures, since the model sets differ.

Self-consistency. Self-consistency means sampling many independent solutions and voting. It is run at matched total generated tokens, with the attack-labeling calls counted against our method's budget. No reported result was found on Lacuna for self-consistency on Knight–Knave–Spy.

LLM judge. The LLM-judge baseline follows FORD and uses the largest model in the roster as judge.

Formal-reasoning baselines. On FOLIO, the strongest cited systems are Logic-LM and DetermLR with GPT-4, at about 77–78% accuracy according to FOLIO. Few-shot GPT-4 reaches about 70%. On AR-LSAT, the neuro-symbolic ARM reaches 30.9% according to AR-LSAT.

Key ablation. The ablation that isolates the key ingredient is an LLM judge that is given the same extracted attack graph in text form and asked to resolve it. If this matches the solver, the benefit came from structuring the arguments, not from exact resolution. A second ablation swaps grounded for preferred semantics. This tests whether the harder, cycle-handling semantics pays off precisely on cyclic graphs.

What counts as beating a baseline. The method must beat majority-resolved debate and the matched-budget self-consistency at a fixed small model size. The gain must be largest on instances with nontrivial SCCs. The method must also beat the graph-reading judge.

Why not just…?

Why not just use self-consistency or majority voting? Voting aggregates final answers and cannot tell when a minority holds a decisive refutation. That is exactly the failure documented in Can LLM Agents Really Debate?. Still, at equal compute, self-consistency could win on easy puzzles where most samples are already right. The matched-token comparison, broken down by puzzle size and SCC structure, settles where each regime lies. We expect voting to hold up on acyclic, shallow instances and to fall behind on tangled ones.

Why not just let a large model judge the debate? FORD found that a GPT-4 judge added about 0.6%. FOLIO shows GPT-4 dropping from 75.43% to 53.10% as logical depth grows, which suggests judges degrade on exactly the deep instances where resolution matters. The graph-reading judge ablation tests this directly.

Why not just translate the whole problem into logic and call a SAT solver? This is the most serious threat. On Knight–Knave–Spy puzzles, full formalization is nearly mechanical and will likely beat our method outright. We will report that honestly. The case for our approach rests on domains where full translation is brittle. On FOLIO, GPT-4 reaches only 65.21% execution accuracy when translating to first-order logic, and ARM's parsers break on single errors in AR-LSAT. Our method needs only pairwise judgments, not a complete formal model. If Logic-LM-style translation with the same small models matches us on FOLIO and AR-LSAT, the claim fails outside synthetic puzzles.

Why not just distill reasoning into the small model? Specializing Smaller LMs lifted Flan-T5 11B to 27.1% on GSM8K but lost almost all chain-of-thought ability on BigBench Hard. Our approach trains nothing, so it pays no such tax. We also check BigBench Hard to confirm there is no side effect.

Proposed Experiments

Models span roughly 1B to 70B parameters within open families, so that size is the varied factor. The benchmarks are the 1,800 Knight–Knave–Spy puzzles at sizes 4–9, FOLIO, and AR-LSAT. The metrics are task accuracy, edge accuracy $q$, decision-relevant edge count $k$, and tokens used.

Decisive check one: the threshold shift. We plot accuracy against model size for majority debate versus solver adjudication. The hypothesis predicts that the solver curve's knee sits at a smaller size, and that it tracks the size at which $q$ becomes high, not the size at which $P^n$ does.

Decisive check two: structure as a predictor. We fit a logistic regression of plain-debate success on model size, puzzle size, and graph structure. The structural terms should add predictive power beyond puzzle size. The solver's advantage should concentrate on graphs with cycles or high backdoor-treewidth.

Decisive check three: exact resolution matters. The solver must beat the graph-reading judge, and preferred semantics must beat grounded semantics specifically on cyclic instances.

Failure mode. If edge accuracy $q$ at small scale is no better than whole-solution accuracy, the local-versus-global story is wrong. That is the result to report.