Reverse Multi-Choice Dialogue Commonsense Inference with Graph-of-Thought

Li Zheng, Hao Fei, Fei Li, Bobo Li, Lizi Liao, Donghong Ji, Chong Teng

Abstract

Dialogue Commonsense Multi-choice Question Answering (DC-MCQ) presents a significant challenge for Large Language Models (LLMs), requiring an understanding of social norms, intentions, and causal relationships within a conversation. Traditional reasoning methods often fail due to "option saturation"—the difficulty of identifying multiple correct answers—and the "clue labyrinth" of non-linear dialogue dependencies. We present Reverse Exclusion Graph-of-Thought (ReX-GoT), a novel framework that mimics human elimination strategies. By first ruling out unreasonable options and then performing a comparative error analysis via a graph-based structure, ReX-GoT achieves substantial performance gains, including a 39.44% F1 score increase on GPT-3.5.

Introduction: The Challenge of Dialogue Reasoning

Current LLMs excel at many tasks but struggle with the nuances of human conversation. In DC-MCQ tasks, models must select all applicable answers from a list based on a dialogue history. This is significantly harder than single-choice selection because the number of correct options is often unknown.

An example of a dialogue commonsense reasoning task involving Alice and Bob.

Two primary hurdles hinder performance:

  1. Option Saturation: Models biased toward "picking the best" answer often miss secondary valid options.
  2. Clue Labyrinth: Correct inferences depend on subtle, non-linear relationships that standard linear Chain-of-Thought (CoT) reasoning frequently overlooks.

Methodology: Reverse Exclusion Graph-of-Thought (ReX-GoT)

The ReX-GoT framework introduces a three-step process designed to navigate these complexities through a graph-based reasoning structure.

Step I: Option Exclusion

Instead of searching for the truth immediately, the model is prompted to identify which options are unreasonable and explain why. This "reverse" approach narrows the search space and uncovers hidden clues within the distractors, effectively simplifying the decision-making process.

Step II: Error Analysis and Graph Construction

Using insights from the exclusion phase, the model performs a comparative analysis of the remaining candidates. It constructs a "Graph-of-Thought" where nodes represent potential options and edges represent the logical reasoning paths connecting them to the dialogue context. This allows the model to weigh multiple conflicting or supporting clues simultaneously.

Step III: Information Synthesis

The final step involves synthesizing the reasoning paths. A voting mechanism is employed to select the optimal path through the graph, leading to the final selection of all correct answers. Unlike linear CoT, this method justifies "error" to reach a more robust "truth."

Experimental Evaluation

The researchers evaluated ReX-GoT on three major benchmarks:

  • CICERO: Covers causality, consequence, premise, motivation, and emotional reaction.
  • CICEROv2: Focuses on multi-choice questions with an uncertain number of correct answers.
  • CICERO-Multi: A difficult subset containing only questions with multiple correct choices.

Key Results

ReX-GoT consistently outperformed state-of-the-art (SoTA) baselines across all metrics:

  • Zero-Shot Superiority: On CICEROv2, ReX-GoT (using Flan-T5-11B) outperformed the best baseline by 17.67% in F1 score.
  • GPT-3.5 Performance: The framework provided a massive 39.44% F1 score boost compared to standard prompting.
  • Multi-Choice Mastery: In the CICERO-Multi subset, ReX-GoT achieved an Exact Match (EM) score of 53.08, nearly doubling the performance of competing prompt-based methods.

Discussion and Insights

The success of ReX-GoT highlights that elimination is a feature, not a bug in AI reasoning. Forcing a model to explain why an answer is wrong improves its internal representation of the problem. Furthermore, Graphs > Chains; dialogue is inherently messy and non-linear, making graph-based structures far more suitable than linear chains for capturing complex social dynamics.

Conclusion and Future Work

ReX-GoT demonstrates that the structure of the reasoning process is as vital as the underlying training data. While multi-choice commonsense remains a complex frontier, this framework provides a clear path forward. Future research will focus on scaling the method to larger models like GPT-4, improving computational efficiency through distillation, and applying reverse exclusion logic to specialized domains like law and medicine.

Summary updated

Abstract

With the proliferation of dialogic data across the Internet, the Dialogue Commonsense Multi-choice Question Answering (DC-MCQ) task has emerged as a response to the challenge of comprehending user queries and intentions. Although prevailing methodologies exhibit effectiveness in addressing single-choice questions, they encounter difficulties in handling multi-choice queries due to the heightened intricacy and informational density. In this paper, inspired by the human cognitive process of progressively excluding options, we propose a three-step Reverse Exclusion Graph-of-Thought (ReX-GoT) framework, including Option Exclusion, Error Analysis, and Combine Information. Specifically, our ReX-GoT mimics human reasoning by gradually excluding irrelevant options and learning the reasons for option errors to choose the optimal path of the GoT and ultimately infer the correct answer. By progressively integrating intricate clues, our method effectively reduces the difficulty of multi-choice reasoning and provides a novel solution for DC-MCQ. Extensive experiments on the CICERO and CICERO_v2 datasets validate the significant improvement of our approach on DC-MCQ task. On zero-shot setting, our model outperform the best baseline by 17.67% in terms of F1 score for the multi-choice task. Most strikingly, our GPT3.5-based ReX-GoT framework achieves a remarkable 39.44% increase in F1 score.
BibTeX
@inproceedings{zheng2024reverse,
  author = {Li Zheng and Hao Fei and Fei Li and Bobo Li and Lizi Liao and Donghong Ji and Chong Teng},
  title = {{Reverse Multi-Choice Dialogue Commonsense Inference with Graph-of-Thought}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2024},
  doi = {10.1609/aaai.v38i17.29942},
}
Figure