MIDGARD : Self-Consistency Using Minimum Description Length for Structured Commonsense Reasoning (2024)

Abstract: We study the task of conducting structured reasoning as generating a reasoning graph from natural language input using large language models (LLMs). Previous approaches have explored various prompting schemes, yet they suffer from error propagation due to the autoregressive nature and single-pass-based decoding, which lack error correction capability. Additionally, relying solely on a single sample may result in the omission of true nodes and edges. To counter this, we draw inspiration from self-consistency (SC), which involves sampling a diverse set of reasoning chains and taking the majority vote as the final answer. To tackle the substantial challenge of applying SC on generated graphs, we propose MIDGARD (MInimum Description length Guided Aggregation of Reasoning in Directed acyclic graph) that leverages Minimum Description Length (MDL)-based formulation to identify consistent properties among the different graph samples generated by an LLM. This formulation helps reject properties that appear in only a few samples, which are likely to be erroneous, while enabling the inclusion of missing elements without compromising precision. Our method demonstrates superior performance than comparisons across various structured reasoning tasks, including argument structure extraction, explanation graph generation, inferring dependency relations among actions for everyday tasks, and semantic graph generation from natural texts.

## introduction while large language models (llms) have showcased impressive performance in fewshot/zero-shot scenarios across diverse reasoning tasks @xcite @xcite @xcite , it is still challenging to apply these models for structured commonsense reasoning which involves generating task-specific reasoning as a graph, such as extracting argument structures from argumentative text @xcite @xcite @xcite , generating structured explanations that lay out commonsense knowledge to connect an argument to a belief @xcite , and inferring dependencies among events for everyday activities @xcite . there are two main challenges for structured reasoning tasks. (1) style discrepancy: conventional approaches for structured response generation represent the graphs as flattened strings @xcite @xcite , leading to subpar performance due to output style mismatch @xcite . (2) error propagation: any incorrect decisions made earlier in the autoregressive decoding process can influence later generation steps @xcite . recently, @xcite propose cocogen to address the issue of style mismatch in structured reasoning tasks, by using programming scripts as prompts for llms. it still suffers from error propagation, since it generates variable declarations and function calls in order to describe the nodes and edges within the graph. any error in these declarations/calls can affect the subsequent generations. to address these issues, we take inspiration from the self-consistency (sc) @xcite strategy that samples diverse reasoning paths and then takes a majority vote as the final answer. the intuition behind sc is that sampling distinct reasoning chains leads to higher confidence in the correctness of a consistent answer. therefore, we hypothesize that sampling diverse graphs from an llm can construct a more accurate aggregate graph and alleviate error propagation for structured reasoning tasks as any errors made in one sample are less likely to persist across all the generated graphs. a crucial distinction between sc and our desiderin this example, our objective is to infer dependency relations among items in the "action list" to achieve the specified "objective". cocogen uses greedy decoding and exhibits errors in the output, e.g., "decided to run errands during a break in the rain" is not connected with "drive to errand location and complete". in contrast, our approach midgard (within the orange rectangle) aggregates relevant information across different samples, resulting in more accurate inference. for this example, our algorithm improved the performance of greedy decoding from 66.7 to 85.7 in edge f 1 -score. to achieve this, we propose midgard 1 , based on minimum description length guided aggregation of reasoning in directed acyclic graph. we employ the principle of minimum description length (mdl) @xcite which seeks to find the hypothesis with shortest description length of the observations. while mdl has been implemented for model selection @xcite , causal structure learning @xcite , data clustering @xcite , and dimensionality reduction @xcite , to the best of our knowledge, its use in automatically merging graph samples has never been explored before. assuming that graph properties consistent across multiple generated samples are more likely to be accurate, we define the description length of a graph sample as the weighted sum of the transformations required to convert a hypothesis into the given sample. by constructing a hypothesis that minimizes the description length across all the 1 our code is publicly available at https://github.com/ launchnlp/midgard . ## background and notations in structured reasoning, a labeled data point is denoted as (t , g), where t represents the input and g is the task-specific graph output that captures the necessary reasoning knowledge. for example, in the task of argumentative structure extraction @xcite , t can be an essay, and g represents the associated argumentative structure. to solve this task, we employ llm in the few-shot prompting mode where n labelled data- ## the midgard method midgard is based on the principle of minimum description length (mdl), which succinctly captures the regularities in the given data by finding the hypothesis with the shortest description length. in graph aggregation, mdl can be used as a selfconsistency strategy to merge multiple reasoning graph samples into a single aggregate graph. the core idea is to define a description length for each graph sample, which is proportional to the number of transformations required to convert a hypothesis into the given sample. by minimizing the description length for samples {g ′ i } t @xmath0, mdl encourages the inclusion of graph properties that are common across different samples. this means that properties that appear frequently in the generated samples are more likely to be accurate and reflect the underlying structure. conversely, properties that are only present in a few samples tend to be wrong. in many structured reasoning tasks, the graphs typically do not have singleton nodes. for example, in argumentative structures of essays @xcite , nodes are either supported or attacked by other nodes, or they themselves support or attack other nodes. we begin by defining the description length of a graph g ′ based on the hypothesis g when the graphs do not contain singleton nodes in §3.1. next, we derive the expression for the expected description length in §3.2 assuming that g ′ is sampled from an llm. based on this, we formulate an objective that aims to minimize the expected description length of the sampled graphs ## experiments and analysis we evaluate on three major tasks for reasoning graph generation: task 1-argument structure extraction on essays @xcite , abstrct @xcite , and cdcp @xcite ; task 2-generating structured explanations on explagraphs @xcite ; task 3-script planning on pro-script @xcite ; and task 4semantic graph generation on kelm @xcite , webnlg @xcite , and genwiki @xcite . thereafter, we evaluate how the performance of our approach changes when using different numbers of samples generated from the llm. additionally, we examine the capability of our approach in handling graphs with varied complexities. finally, we assess the influence of varying the number of few-shot examples and examine how close our automatically chosen hyperparameters are in comparison with the best possible ones. we also analyze the influence of varying the number of few-shot examples. unless stated otherwise, we generate @xmath1. base llms. we evaluate our approach with (a) gpt-3.5-turbo 2 , a general purpose instructiontuned llm and (b) code-llama (roziere et al., 2023), a code-llm pretrained over general purpose programming languages. the 16k context length associated with these llms allows us to employ few-shot prompting for long sequence inputoutput tasks such as argument structure extraction. comparisons. we first consider a greedy baseline that represents each graph as a semantically equivalent programming script and samples only one generation from the llm, which is decoded greedily as done in cocogen. our main model, midgard applies the objective described in §3.4. as the graphs in all the considered tasks are directed acyclic in nature except semantic graph generation, we additionally incorporate the dag constraints discussed in §3.3. for semantic graph generation, we analyse the performance of different variants without dag constraints. we further compare with three variants of midgard: (a) midgard w/o node trns: we use the objective described in §3.3 along with the dag constraints. by excluding the term that incorporates node transformations in this formulation, we can evaluate its impact on the overall performance. specifically, this approach is implemented by retaining only those edges that occur more than 1λ 1 fraction of times while ensuring there are no cycles. thereafter, only the nodes present in the retained edges are kept. (b) midgard (λ = 0.5): we apply the objective proposed by @xcite by assuming equal description length of addition and deletion. (c) midgard w/o dag constraints. ## conclusion we proposed a novel approach for enhancing the performance of structured reasoning problems which involve generating task-specific graphs. taking inspiration from self-consistency, we sample multiple graphs from the llm and devise a mechanism to construct aggregated graph. through rigorous experimentation, we have demonstrated the effectiveness of our approach across various structured commonsense reasoning tasks.