acceptodds
Under review as a conference paper at ICLR 2027

Disagreement Graph Inference

Abstract

Self-Consistency decoding improves large language model reasoning by sampling multiple Chain-of-Thought chains and selecting the most frequent final answer via majority vote, but treats each chain as an independent vote, discarding shared intermediate reasoning structure. We introduce Disagreement Graph Inference (DI), a training-free framework that replaces majority voting with structured probabilistic inference over intermediate sub-answer variables. DGI decomposes sampled chains into a sub-answer matrix, estimates pairwise dependencies via bias-corrected mutual information with false discovery rate control, constructs an optimal Chow-Liu tree, and performs exact belief propagation to compute posterior marginals. The key mechanism-the rescue effect—allows strong intermediate consensus to override an incorrect final-answer plurality through message passing along dependency edges. We prove formal rescue guarantees on trees, characterize algebraically symmetric conditions under which DGI can harm accuracy, and show that DI strictly generalizes Self-Consistency. Experiments across six reasoning benchmarks and three foundation models demonstrate accuracy improvements of up to 6.3% absolute over Self-Consistency with less than 150 ms overhead per instance, rescue rates up to 39.5%, calibration error reductions exceeding 50%, and graceful degradation on structurally trivial problems.

Primary area:
foundation or frontier models, including LLMs
Keywords:
Large Language Models, Chain-of-Thought Reasoning, Self-Consistency, Structured Inference, Probabilistic Graphical Models, Belief Propagation, Chow–Liu Trees, Inference-Time Reasoning, Reasoning Aggregation, Calibration

Reviews

Among:
Shape:
1234this paper, Bottom 9%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.50 over 4 reviews, above 9% of the others.
Reviewer_ai5fOpenReview ↗
Rating
1
Confidence
3
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

This paper proposes Disagreement Graph Inference, a training-free framework that improves upon Self-Consistency by incorporating intermediate reasoning information from multiple Chain-of-Thought samples. The method extracts and aligns intermediate sub-answers across reasoning chains, estimates their statistical dependencies using mutual information, and constructs a Chow–Liu tree to represent these relationships. It then applies belief propagation to compute the marginal distribution of final answers, aiming to leverage intermediate consensus to correct erroneous majority-vote predictions. Experiments across six reasoning benchmarks and three language models report improvements over Self-Consistency and other aggregation baselines, along with gains in calibration and limited additional inference overhead.

Critical strengths
  1. This paper tries to tackle a limitation of self-consistency. The idea that uses the middle reasoning steps is meaningful and has potential.

  2. This paper reports experiments across six reasoning benchmarks and three LLMs, including one closed-source LLM, and compares against multiple aggregation baselines. Besides, the results show that the proposed method shows consistent improvement.

Critical weaknesses
  1. The proposed rescue effect seems weird in theory. According to the formulation in Eq. (6)–(9), DGI constructs a Chow–Liu tree from empirical distributions and applies belief propagation to compute the marginal probability of the final answer. However, under the standard Chow–Liu factorization with consistent empirical distributions, marginalizing over the intermediate variables should recover exactly the original final-answer distribution used by Self-Consistency. In other words, DGI should produce the same prediction as SC with the current rescue framework written in the paper.

  2. The central idea of leveraging intermediate reasoning consensus and graph structures across multiple CoT trajectories has been explored in prior work [1,2,3,4]. Though the proposed methods are different, this paper should compare with the existing works to show the differences.

[1] Liu, Xiaoou, et al. Diagnosing Multi-step Reasoning Failures in Black-box LLMs via Stepwise Confidence Attribution. ICML 2026.

[2] Cao L. Graphreason: Enhancing reasoning capabilities of large language models through a graph-based verification approach. ACL Workshop 2024

[3] Shi H, Liu Y, Pang B, et al. Ssr: Socratic self-refine for large language model reasoning. Arxiv 2025.

[4] Parulekar A, Lee J, Hakkani-Tür D, et al. Reasoning consensus: Structural ensembling of LLM reasoning via weighted DAG aggregation. arxiv 2026.

Questions for authors
  1. Could the authors address the problem mentioned above?

  2. Since the middle steps were already extracted by the LLM, why is cosine similarity required?

  3. Could the authors provide the computational overhead for pilot chain generation, sub-question enumeration, and potentially LLM-based sub-answer extraction for each reasoning chain?

  4. Could the authors improve the quality of Figure 1?

Reviewer_Uqy5OpenReview ↗
Rating
2(−1)
Confidence
3
Informativeness
3
Presentation
2
Soundness
2
Read review
Paper summary

The paper proposes Disagreement Graph Inference (DGI), which replaces Self-Consistency’s majority vote over complete reasoning chains with structured probabilistic inference over intermediate sub-answers. DGI extracts and aligns sub-answers from K sampled CoT chains, estimates pairwise dependencies with bias-corrected mutual information under FDR control, constructs a Chow-Liu tree factor graph, and runs belief propagation to obtain the posterior marginal of the final-answer variable. Theoretically, the paper gives a rescue guarantee on trees (Proposition 1), anti-rescue conditions (Theorem 4), and a reduction to Self-Consistency when no significant dependencies are detected (Proposition 2).

Critical strengths
  1. Formalizing SC aggregation as structured inference over intermediate variables is a genuinely novel and well-motivated framing. The use of a Chow-Liu tree to guarantee exact BP marginals, together with rescue/anti-rescue propositions and an exact reduction to SC, gives the method a testable theoretical boundary rather than a purely heuristic ensemble. This is the strongest reason to consider acceptance.

  2. The empirical evidence chain is multi-angle and the ablation localizes the mechanism. Table 3’s additive build-up shows that sub-answer extraction alone or tree construction alone yields modest gains, while activating PMI-ratio potentials with BP produces a discontinuous jump. The controlled edgeless-graph experiment directly validates Proposition 2, and the oracle-extraction and alignment-noise analyses credibly address whether extraction errors are a systemic bottleneck. These substantially increase confidence that the reported gains are not an artifact of extra sampling alone.

Critical weaknesses
  1. The comparison’s total inference budget is not sufficiently specified, which affects the core claim of efficiency and fairness. DGI draws K=40 chains plus K_pilot=5 pilot chains, and may use LLM-based extraction in unstructured domains. The paper emphasizes that the non-LLM pipeline costs below 50 ms at K=40 (and at most 142 ms at K=80), but does not clearly report total LLM calls/tokens/latency relative to the SC baseline under an equal total budget. If SC were given the same total sampling budget, the magnitude of the reported gains and the “negligible overhead” claim could change. This is fixable but material to the fairness of the main comparison.

  2. Statistical reporting and the theory-empirics link are underdeveloped. Table 1 reports only ten-seed means without standard deviations or confidence intervals, and the main tables do not report paired significance tests; the text mentions Holm-Bonferroni and McNemar results in places, but they are not systematically reported in Tables 1–2. Table 2’s “SC Wrong (n)” contains non-integer values (e.g., 71.2, 265.0); if n is the ten-seed average number of SC errors, this is not necessarily an error, but the definition of n should be stated explicitly. Moreover, Propositions 1 and Theorem 4 are stated for a given tree/estimated parameters, but the paper does not report the fraction of actual K=40 estimated trees satisfying the rescue/anti-rescue conditions, nor connect condition satisfaction to observed rescue/harm instances. These are repairable but currently limit the strength of the conclusions.

Questions for authors

Please specify the total sampling/call budget. Does DGI use K_pilot=5 and LLM-based extraction in addition to the K=40 chains used by SC? Were SC baselines given the same total LLM calls/tokens/latency? Please report total cost per method, including pilot and extraction calls, not only non-LLM overhead.

Please provide means ± standard deviations or 95% CIs for Tables 1 and 2, along with paired significance tests (e.g., McNemar/Holm) for the main and rescue results. Also clarify why “SC Wrong (n)” is non-integer and give its precise definition; if it is a ten-seed average, please state that explicitly.

The claim that K_pilot=5 recovers ≥95% of sub-questions appearing in the full K=40 sample: is this verified across all six datasets and three models? What is the pilot failure rate in more open-ended or unstructured domains? The main text currently reports this as an empirical finding and points to Appendix C.1.

For the actual estimated Chow-Liu trees at K=40, what fraction of instances satisfy the conditions of Proposition 1 and Theorem 4? Can you relate condition satisfaction to the observed rescue and harm cases?

CoT-Verify is a fine-tuned baseline while DGI is training-free. Was the comparison conducted under matched sampling and inference budgets? Please clarify.

Reviewer_GrT6OpenReview ↗
Rating
1
Confidence
2
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

The paper proposes Disagreement Graph Inference (DGI), a training-free method that aims to improve how language models select final answers from multiple reasoning attempts. Instead of simply choosing the most common final answer, the method also considers the intermediate answers produced during reasoning. It first identifies common sub-questions across different reasoning attempts, then builds a graph to capture relationships between their answers. The authors use belief propagation on this graph to select the final answer, with the goal of correcting cases where majority voting gives an incorrect result. The method is evaluated on six reasoning benchmarks using three language models, and the authors report improvements over existing approaches.

Critical strengths
  1. The paper explores an interesting idea of using intermediate reasoning steps to improve final answer selection instead of relying only on majority voting. The problem itself is worth investigating.

  2. The authors evaluate their method on six benchmarks using three different language models. They also include ablation studies to examine the different parts of their method, which is a positive aspect of the paper.

Critical weaknesses

The overall idea is interesting, but the theoretical foundation of the method is not sufficiently explained or justified. In particular, Sections 3.3, 3.4, and 3.5 introduce several mathematical terms, equations, and theoretical results without clearly explaining why these specific formulations are chosen or how each term helps the proposed method work. Since these mathematical formulations are central to the paper's contribution, the lack of motivation and justification makes it difficult to evaluate whether the method is theoretically sound or whether the claimed improvements actually follow from the proposed formulation. This is a major concern because the paper does not clearly establish why its theoretical approach should work in the first place.

Questions for authors
  1. Sections 3.3 and 3.4: Could you explain the intuition behind the mathematical terms introduced in these sections? In particular, why are these specific formulations chosen, and how does each term contribute to improving the final answer selection?

  2. Section 3.5: Could you clarify how the theoretical results justify the effectiveness of the proposed method? In particular, how do the assumptions and conclusions of the propositions relate to the actual procedure?

  3. Theoretical validity: Are the theoretical guarantees still expected to hold when incorrect intermediate answers receive substantial support? If so, could you explain how the analysis accounts for such cases?

Reviewer_fuTQOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
1
Read review
Paper summary

This paper proposes Disagreement Graph Inference (DGI), a training-free method for improving Self-Consistency (SC) decoding. Instead of voting only on final answers, DGI extracts intermediate sub-answers from sampled reasoning chains and models their dependencies. It estimates pairwise mutual information, builds a Chow–Liu tree, and uses belief propagation (BP) to infer the final answer. The authors argue that intermediate agreement can help correct wrong final-answer majorities. The paper also provides theoretical analyses of when DGI helps or hurts accuracy. Experiments on six benchmarks and three language models report improvements of 2.1–6.3 percentage points over SC, along with ablations and robustness results.

Critical strengths
  1. The idea of using intermediate reasoning results for answer aggregation is interesting. DGI provides a training-free approach based on graphical inference.

  2. The experiments cover six benchmarks and three language models, with comparisons against several baselines. The authors analyze both the rescue and anti-rescue cases, and examine when DGI reduces to standard SC.

Critical weaknesses
  1. Figure 1 is difficult to read, and look AI-generated, while the AI Use Statement says that AI tools were not used to create figures. Could the authors clarify this?

  2. The paper does not sufficiently discuss closely related work, such as Multi-Chain Reasoning (Yoran et al., 2023), Reasoning Consensus (Parulekar et al., 2026), CRAFT (Ling et al., 2026), and MGRS (Yang et al., 2025). These studies also explore aggregating intermediate reasoning information across multiple chains. The authors should better clarify the novelty of DGI relative to these methods.

  3. I am not fully convinced by the explanation of the rescue effect. In a Chow–Liu tree with consistent marginal distributions, exact BP should preserve the original final-answer marginal. Since DGI does not appear to condition on observed intermediate answers, it is unclear how BP changes the final prediction compared with SC. Could the authors clarify what drives the reported improvements?

  4. The theoretical treatment of missing data may need further justification. Lemma 1(b) in Appendix B claims that the complete-case estimator is consistent under MAR, but this may not hold when missingness depends on other correlated variables. Could the authors clarify the assumptions needed for this result and whether potential estimation bias affects DGI's performance?

  5. Some experimental results are unclear. In Table 3, unary-only aggregation improves over SC, although it seems that both should produce the same predictions. Also, the rescue rate in Table 2 does not seem consistent with the accuracy gains in Table 1.

Questions for authors

Included in the weaknesses above.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.