Signed Consensus: Aggregating Debating LLM Agents with Squared Probabilistic Circuits

When several language models argue about a multi-step problem, the final answer is usually settled by a majority vote or by another model acting as judge. Both steps are social rather than logical. Controlled studies show that agents in the majority almost never change their minds, and that a lone correct agent usually gives in. We propose to replace the vote with a small probabilistic model that computes the consensus exactly. Each agent's proposal is treated as a probability distribution over complete "worlds", meaning full truth assignments to the sub-questions a query breaks into. These distributions are combined with weights that may be negative, so a refuted world can have probability removed rather than only having probability added elsewhere. The combination is then squared, which keeps every probability non-negative, and multiplied by the known logical constraints. A structural property from knowledge compilation, structured decomposability, makes exact inference on this combined model take polynomial time.

The two-sentence version: the query's decomposition tree fixes the order in which variables are split, and every agent's belief is written as a small circuit over that same split order. Agents' beliefs can then be added, subtracted, squared, and conditioned on hard constraints, all with exact arithmetic. The question is whether this signed, constraint-aware aggregation recovers correct minority answers, and answers no single agent proposed, better than voting, debate, solvers, or learned aggregators do.

Core Claim

Recent work on subtractive mixtures, Subtractive Mixture Models via Squaring, introduces squared non-monotonic probabilistic circuits ($NPC^2$). A probabilistic circuit is a computation graph of sums and products that represents a probability distribution. The paper shows that mixtures with negative weights, squared to stay non-negative, can be exponentially more compact than purely additive mixtures. It also shows they stay exactly normalizable when the circuit is structured-decomposable. That paper uses the idea only for density estimation. We claim the same algebra fits multi-agent aggregation over a decomposed query.

Let $x$ be a joint truth assignment to the leaf propositions of a decomposition tree. Let $c_i(x)$ be agent $i$'s belief circuit, a mixture over the handful of complete worlds it proposed together with its stated confidences. Let $w_i \in \mathbb{R}$ be a signed reliability weight, and let $K(x) \in \{0,1\}$ be a compiled constraint circuit. The consensus is

$$p(x) \propto K(x)\left(\sum_{i=1}^{N} w_i\, c_i(x)\right)^2 .$$

Here $N$ is the number of agents. Each agent and each refutation can also contribute more than one component. All circuits share one variable tree, or vtree, which is the fixed order in which variables are split into disjoint groups. That vtree is derived from the decomposition tree. Sharing it is what makes the cross-terms of the square, and the product with $K$, integrable in polynomial time (Darwiche et al. (2002), New Compilation Languages Based on Structured Decomposability).

A refutation raised in debate enters the model as a negatively weighted component centred on the refuted world. The skeptic persona therefore has a precise meaning: it is the subtractive part of the mixture. This speaks to the loss of interpretability that the $NPC^2$ paper lists as an open problem, because each negative component now corresponds to a named argument. The most probable world under $p$ can differ from every individual agent's proposal. That is the mechanism by which the method might exceed the "reasoning ceiling" that Can LLM Agents Really Debate? attributes to debate.

This differs from the closest work in three ways. Analytica decomposes a query into a proposition tree and aggregates leaf probabilities with a linear weighted average. It chose that rule because it showed Boolean AND/OR gates flip the root on small leaf errors. A linear average, however, cannot represent mutual exclusion or conjunction. Our aggregator keeps hard logic in $K$ and puts the soft, noisy part in the squared mixture. BeliefBank enforces constraints with a MaxSAT solver, which produces a single repaired assignment at solver cost. We produce a full calibrated distribution with exact marginals. LOCO-LM supplies our constraint-compilation technique, semantic loss computed on Boolean circuits. It bakes consistency into one model's weights at training time. We apply the same compiled circuits at inference time across several agents without retraining any of them.

Research Program

Building the per-query circuits. For each query, a decomposer model produces the leaf propositions. Role assignments are the leaves in logic puzzles; facts about an entity are the leaves in belief benchmarks. We build a balanced vtree that follows the decomposition tree. Sub-questions often share variables, which is exactly the regime When Splitting Makes Stronger identifies as the one where divide-and-conquer prompting breaks. We place shared variables near the root of the vtree, so the subtrees below them are conditionally independent given those variables. This is the standard way compiled circuits handle overlap. It is not a free lunch: the cost grows with the number of shared variables, and we will report that growth.

Turning agents into components. Each agent, and each debate round, is converted into circuit components. An agent's initial proposal becomes positive components over the worlds it proposed, weighted by its confidence. A step-level refutation, in the style of ChainLM's per-step debate (ChainLM), becomes a component over the partial assignment it attacks, with a weight whose sign we learn. Leaves that a code or search tool can verify, as in Analytica's grounder, become evidence we condition on exactly.

Learning the weights. The signed weights are a few dozen scalars per agent type and argument type. We fit them by maximum likelihood on training-split ground-truth worlds. We compute everything with the signed log-sum-exp evaluation from the $NPC^2$ paper, which tracks sign and magnitude separately for numerical stability. The tractable regularizers of Tractable Regularization of Probabilistic Circuits guard against the overfitting that the $NPC^2$ paper reports.

Analysis. We will characterise three things: when the most probable consensus world is one that no agent proposed, how often a minority that proposed the correct answer wins, and how inference cost scales with vtree width and constraint count.

Baselines

Naive references. The first reference point is a single agent answering alone. The second is the initial round of proposals resolved by majority vote with no debate. On Knight-Knave-Spy (KKS) puzzles, Can LLM Agents Really Debate? reports instance accuracy of 17.33% before debate on 4-player puzzles and 3.33% on 8-player puzzles. We will reproduce these with our agent pool so that the numbers are comparable to ours.

Structured multi-round debate. This is the strongest existing method on the logic task, run exactly as in the three-phase protocol of that paper: proposals with confidence, iterative debate, then a vote or supervisor judge. It reports 69.33% instance accuracy on size-4 puzzles and 36.00% on size-8. Our method sees the same transcripts and uses the same models and the same number of LLM calls. Beating it means higher accuracy at matched calls, especially on sizes 8 and 9.

Constraint repair on the belief benchmark. On BeliefBank, the strongest competitor is the MaxSAT feedback-and-repair system of BeliefBank. It reports 86.6% F1 and 97% consistency, up from 69.3% F1 raw. We will run it with the same agents' raw beliefs and the same 2,612 constraints. Beating it means matching its consistency while improving F1 and Brier score, at lower latency.

LOCO-LM reports 0.99 consistency and 0.98 consequent F1 on the T1 split. It is a training-time method on a 770M-parameter model, so we report it as an upper reference for consistency rather than a matched competitor.

Analytica's linear synthesis. This is applied to our decomposition trees with the same leaf estimates, since it is the most direct hierarchical-decomposition competitor. Its reported 71.06% is on its own forecasting set. We found no reported result on Lacuna for it on KKS or BeliefBank.

Ablations of the key ingredient. First, the same aggregator with weights constrained to be non-negative, which is a monotonic mixture times $K$. This removes subtraction and isolates the value of squaring. Second, the aggregator with $K$ removed, which isolates the value of the constraints. Every learned variant gets the same training split and the same hyperparameter search budget.

Why not just…?

Why not just enumerate all worlds and do exact Bayesian aggregation? On KKS this is a genuine threat. A 9-player puzzle has roughly $3^9$ worlds, so brute-force enumeration is cheap. We will run it, and on KKS the circuit's contribution must come from the aggregation rule, not from speed. Enumeration also serves as a correctness check on our inference. On BeliefBank, where one entity carries on the order of a hundred facts, enumeration is impossible. That is where tractability has to pay off, and we will show where enumeration stops being feasible.

Why not just learn a small neural aggregator over leaf probabilities? A small multilayer network can represent XOR-like combinations and would likely match us on root-level accuracy. What it does not provide is a joint distribution. It cannot condition on a newly verified leaf, answer a query about a different fact, or guarantee that the constraints hold. We will train one with the same data and budget. We will then evaluate both methods on held-out conditional queries and on consistency. If the network ties us on those as well, the circuit's case rests on consistency guarantees alone, and we will say so.

Why not just use log-linear opinion pooling with signed exponents? Multiplying agents' beliefs raised to signed powers also lets an agent push probability down. If each agent's belief factorizes over leaves, this pooling is tractable and may be all that is needed. It becomes intractable when agents propose correlated whole-world mixtures, because a power of a mixture does not simplify. KKS proposals are exactly this kind of correlated whole world. We include factorized log-linear pooling as a baseline. If it matches the signed squared mixture, the conclusion is that subtraction matters but squaring does not.

Why not just keep debating, or ask a MaxSAT solver? Debate is limited by majority entrenchment of over 97% (Can LLM Agents Really Debate?, Peacemaker or Troublemaker). A solver returns one repaired world and, as BeliefBank notes, can flip correct low-confidence beliefs. Our minority-recovery and calibration measurements test both weaknesses directly.

Proposed Experiments

The primary benchmark is the 1,800 KKS puzzles, with 4 to 9 players, using heterogeneous open-weight agents. The metrics are instance accuracy, Brier score, and two quantities specific to this proposal. The minority-recovery rate is the fraction of cases with a wrong initial majority and at least one correct proposer that end correct. For reference, A Diagnostic Study of Multi-Agent LLMs reports 74% recovery for high-process debates versus 40% for low-process ones, measured on MMLU-Pro rather than KKS. The beyond-best-agent rate is the fraction of correct answers that no agent proposed.

The second benchmark is BeliefBank. There we measure F1, consistency, calibration, and latency against Z3 as the constraint count grows. A third, exploratory setting uses Matter-of-Fact scientific claims decomposed into sub-claims (Matter-of-Fact). We found no reported result on Lacuna for Matter-of-Fact.

Decisive checks. The method succeeds if four things hold. The signed aggregator must beat its non-negative ablation on 8- and 9-player puzzles. It must raise minority recovery over debate at matched LLM calls. It must match BeliefBank's 97% consistency with higher F1 and lower latency. And it must yield a non-trivial beyond-best-agent rate.

The method fails if any of three things happens. If signed weights give no gain over non-negative weights, squaring is unnecessary. If log-linear pooling ties the full method, subtraction alone explains the gains. If the neural aggregator ties it on conditional queries, the circuit adds nothing beyond its consistency guarantees.