Self-consistency is a simple way to make language models more reliable. You sample many independent chains of reasoning and take a majority vote over their final answers. It works well when the answer is a single number or a single option letter. Many real tasks instead ask for several linked decisions at once: the position of every object in a logic puzzle, the truth value of several conclusions drawn from the same premises, or the intermediate quantities in a word problem. Here majority voting breaks in two familiar ways. If you vote on each sub-answer separately, you can assemble a combination that no sampled chain produced and that violates the task's own constraints. Social choice theory calls this the multiple election paradox. If you instead vote on whole answer tuples, the space of tuples grows exponentially, so with a few dozen samples almost every tuple is unique and the vote is mostly ties.
We propose to treat the sub-answers as interdependent issues in an election and to borrow the standard fix from combinatorial voting. That fix is to find which issues depend on which, vote on the upstream issues first, and then vote on each downstream issue conditional on the upstream winners. The new part is how the dependencies are found. Reading them off the chain of thought would be unreliable, because a model's written reasoning is often a rationalization produced after the answer is already decided. We therefore measure them by intervention: force one sub-answer to a value and resample the rest. The result is a decoding rule that only outputs coherent combinations, spends its sampling budget on targeted conditional queries instead of blind full samples, and produces as a by-product a measurement of how far the model's stated reasoning structure differs from its actual one.
Core Claim
For multi-part reasoning outputs, sequential conditional voting along an interventionally estimated dependency graph should beat two alternatives at equal token budget: issue-wise majority voting and its coherence-repaired variants on joint exact-match accuracy, and whole-tuple plurality voting as well. The gain should concentrate on instances where the estimated graph has real edges and should vanish on separable instances. A graph estimated from what the chain of thought claims should do worse than the interventional graph exactly where the two disagree.
The method draws on four bodies of work, each playing a different role. Lang's decomposition result in Vote and Aggregation in Combinatorial Domains with Structured Preferences supplies the aggregation mechanism. It shows that when voters share an acyclic dependency graph, an election over all $2^n$ outcomes reduces to $n$ local votes in topological order. Lang assumes the graph is known in advance; we must estimate it from a model's behavior. Hypercubewise Preference Aggregation in Multi-Issue Domains and Condorcet Winners and Anscombe's Paradox Under Weighted Binary Voting motivate the problem. They document how issue-wise majority produces combinations that most voters reject, and show that even checking whether the issue-wise majority is a Condorcet winner is co-NP-hard. The post-hoc rationalization literature constrains how the graph may be estimated. How Likely Do LLMs with CoT Mimic Human Reasoning? finds that "common cause" behavior dominates: the prompt drives both the trace and the answer, and the trace does not drive the answer. That rules out trusting dependencies the trace asserts. The combinatorial auction literature supplies the budget discipline. Prices, Bids, Values: One ML-Powered Combinatorial Auction to Rule Them All shows that over an exponential bundle space one should first run broad queries that reveal structure and then targeted queries that pin down the chosen allocation. It also adds a final "bridge bid" check on the chosen bundle. We copy that two-phase shape directly.
The nearest decoding work is Ranked Voting based Self-Consistency of Large Language Models. It replaces plurality with ranked voting rules (instant-runoff, Borda) and reports gains, but over a flat single-issue candidate set. Our work keeps a simple vote at each step and changes what is voted on and in what order. The two are complementary, and ranked rules could be used inside each local vote.
Research Program
Each task instance has $n$ sub-answers $y_1,\dots,y_n$, which we call issues. In a logical-ordering puzzle, issue $i$ is an object's position. In FOLIO, issue $i$ is the label of one conclusion attached to a shared premise set.
Phase 1: structure discovery. We draw a small pool of ordinary chain-of-thought samples at nonzero temperature. Analogous to demand queries, these show which values are competitive for each issue.
Phase 2: dependency estimation. For each candidate edge $i \to j$, we take two competing values $a, a'$ of issue $i$ that appear in the pool. We force each value into the reasoning prefix as an established intermediate result, at the point where the model would state it, and resample only the continuation. We then score the edge as
$$D(i \to j) = \mathrm{TV}\big(P(y_j \mid \mathrm{do}(y_i = a)),\; P(y_j \mid \mathrm{do}(y_i = a'))\big),$$
where $\mathrm{TV}$ is total-variation distance between the empirical distributions of issue $j$'s value under the two forced settings. An edge is kept when $D$ exceeds a threshold calibrated on separable control instances. Candidate edges are pruned using the Phase 1 pool: issues whose values are perfectly correlated, or that never vary, are not probed. This keeps the number of conditional queries roughly linear in $n$ instead of quadratic.
Phase 3: sequential voting. We vote on the root issues using the pool. Then, in topological order, we resample each child issue conditional on its parents' winning values and take a plurality vote among those conditional samples. If the estimated graph has cycles, each strongly connected component is merged into one composite issue and voted on jointly. The cost then grows exponentially only in the component size. This mirrors the degree-dependent penalty in Proportionality Guarantees in Elections with Interdependent Issues, whose bounds scale as $d^{\Delta+1}$ in domain size $d$ and maximum in-degree $\Delta$.
Bridge check. Following the auction design, we force the fully assembled joint answer into the prefix and sample a short verification continuation. If the model rejects the combination at a high rate, we fall back to the best-supported fully sampled tuple. A tuple that never appeared among the samples is never output without this check.
Faithfulness by-product. For each sample we also parse the dependencies the chain of thought claims, for example "since A is first, B must be...". We compare this stated graph with the interventional graph. Edges that are stated but have no causal effect are decorative. Edges that have an effect but are never stated are hidden. This extends the step-level causal analysis of Thought Anchors: Which LLM Reasoning Steps Matter? and the step-replacement interventions of FRIT from single traces to an ensemble-level graph over sub-answers. Unlike FRIT, we use the interventions at inference time and do not train on them.
Baselines
The naive reference point is greedy decoding with one chain of thought. It costs one sample and calibrates how much any voting helps.
Issue-wise majority self-consistency samples $K$ chains, extracts each sub-answer, and takes a majority on each issue independently. This is the natural extension of the maj1@k protocol in Solving Quantitative Reasoning Problems with Language Models, which reports 78.5% on GSM8K with Minerva 540B. It is the default practitioners would use and the method whose paradoxes motivate us.
Whole-tuple plurality treats each full joint answer as one candidate. It is coherent by construction but sparse.
Ranked-voting self-consistency (Wang et al. (2025)) applies Borda and instant-runoff to joint tuples. It reports a 4.95% average accuracy gain over majority voting for Qwen-2.5-3B on single-issue tasks.
The strongest sampling-only competitor is the medoid tuple: the sampled joint answer that minimizes total Hamming distance to all other samples. It is always a combination the model actually produced, and it uses the cross-sample agreement that issue-wise majority uses.
On logic tasks the strongest external competitor is Logic-LM (Pan et al. (2023)). It translates the problem into a solver language and runs a solver. For GPT-4 it reports 78.1% on FOLIO (FOLIO), nearly 90% on LogicalDeduction, and 43% on AR-LSAT, against about 35% for chain of thought. We found no reported result on Lacuna for self-consistency of any kind on FOLIO, LogicalDeduction, or AR-LSAT, so those numbers will be established here.
Three ablations isolate the key ingredients. The first is sequential voting along the order in which issues appear in the text, which tests whether the estimated graph matters at all. The second is sequential voting along the stated (chain-of-thought-parsed) graph, which tests whether the interventional estimate matters. The third removes the bridge check.
Fairness. All sampling methods run on the same open-weight models (Qwen3-8B, Mistral-7B, Qwen-2.5-3B), the same prompts, and the same temperature grid. Each gets the same total budget of generated tokens; conditional resamples count toward ours. Each method gets the same small tuning set for thresholds and $K$.
Beating a baseline. We count it as beating a baseline when joint exact-match accuracy is higher at matched tokens, with a paired bootstrap interval excluding zero across three seeds, and with no loss in the coherence rate. Against Logic-LM, we do not expect to win on LogicalDeduction outright. The claim is narrower: the method should recover a substantial share of the instances where translation or solving fails, and the union of the two methods should exceed Logic-LM alone.
Why not just…?
Why not just pick the medoid sample? This is the most serious threat. It is cheap, coherent, and uses the same agreement signal. Its weakness is predictable. When the model errs on an upstream issue, downstream answers in the same sample are derived from that error. The medoid inherits an entire trace, so it cannot combine a correct upstream value from one group of samples with downstream values recomputed from that correct value. Conditional resampling can. The experiment that settles this is to stratify instances by the depth of the estimated graph. If the medoid matches our method even on deep-dependency instances, the conditional machinery is not earning its cost, and we would report it as a measurement tool for faithfulness, not as a decoder.
Why not just vote on whole tuples, perhaps with more samples? On FOLIO, a premise set carries about three conclusions on average (1,435 conclusions over 487 premise sets). Ordering puzzles have factorially many joint answers. The number of samples needed for a non-tied tuple plurality therefore grows with the joint space. We will plot tuple-plurality accuracy and tie rate against $K$ up to the largest budget we can afford. If tuple plurality closes the gap at a cost that is practical, the case for our method narrows to the regime of many issues.
Why not just hand the problem to a symbolic solver? For cleanly formalizable puzzles, Logic-LM is likely better. Han et al. note that a solver fails completely on small semantic mistranslations even when about 93% of translations are syntactically valid. Our method needs no formal translation and also applies to word problems whose sub-answers are quantities. The comparison above, including the run on solver failures, is meant to show complementarity, not dominance.
Why not just order the votes by the dependencies the reasoning states? That is our second ablation. Bao et al. find decorative reasoning to be the norm, and Ley et al. (2024) report that stronger models are often less faithful. Together these predict that stated graphs will contain spurious edges and miss real ones. If the stated graph performs as well as the interventional one, that would itself be evidence that sub-answer-level reasoning in these models is more faithful than step-level studies suggest, and it would remove most of our intervention cost.
Proposed Experiments
The primary benchmarks are LogicalDeduction and AR-LSAT, both used in Pan et al. (2023), and FOLIO with all conclusions per premise set answered jointly. Ordering and assignment puzzles have hard coherence constraints, so the coherence rate (for example, whether the output is a valid permutation) is directly measurable. On GSM8K and MATH we treat the intermediate quantities as issues, using the reference solution to define them. Accuracy and coherence are reported alongside the Minerva figures (78.5% and 50.3%) for scale only, since those come from a far larger model. Metrics are joint exact match, per-issue accuracy, coherence rate, generated tokens, and, for the faithfulness analysis, precision and recall of stated edges against interventional edges.
Three decisive checks follow from the core claim. First, at matched token budget, conditional voting should beat issue-wise majority and the medoid on joint exact match. The margin should grow with estimated graph depth and be near zero on instances whose estimated graph is empty. A flat margin across depth would falsify the mechanism.
Second, on SciAux (Zhao et al. (2025)), Qwen3-8B falls from 96.22% clean accuracy to 77.03% with two misleading snippets and thinking enabled. We treat the snippet-relevant judgment and the final answer as two issues and test a specific prediction. Misleading context acts as a common cause, so forcing the snippet-relevant judgment to its correct value should change the final answer much less than it would if the answer genuinely depended on that judgment. If so, the interventional graph flags these instances as rationalized, and conditional voting should not inherit the collapse as much as plain majority voting does. If conditional voting collapses equally, interventions on the prefix are themselves being absorbed into the rationalization, which limits the method.
Third, we test robustness to faithfulness drift. We run the full pipeline before and after FRIT-style preference training on Mistral-7B, for which FRIT reports a 7.6-point GSM8K gain. This asks whether interventional graphs, and the decoding advantage they give, survive post-training that is known to reshape the link between reasoning and answers.
References
- Vote and Aggregation in Combinatorial Domains with Structured Preferences
- Hypercubewise Preference Aggregation in Multi-Issue Domains
- Condorcet Winners and Anscombe's Paradox Under Weighted Binary Voting
- How Likely Do LLMs with CoT Mimic Human Reasoning?
- Prices, Bids, Values: One ML-Powered Combinatorial Auction to Rule Them All
- Ranked Voting based Self-Consistency of Large Language Models
- Proportionality Guarantees in Elections with Interdependent Issues
- Thought Anchors: Which LLM Reasoning Steps Matter?
- FRIT: Using Causal Importance to Improve Chain-of-Thought Faithfulness
- Solving Quantitative Reasoning Problems with Language Models
- Logic-LM: Empowering Large Language Models with Symbolic Solvers for Faithful Logical Reasoning
- FOLIO: Natural Language Reasoning with First-Order Logic
- On the Hardness of Faithful Chain-of-Thought Reasoning in Large Language Models
- Thinking in a Crowd: How Auxiliary Information Shapes LLM Reasoning