  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.
