CRAFT: Building Better Reasoning Chains Through Consensus Knowledge Graphs

Paper: 2604.14121 Authors: Zipeng Ling, Shuliang Liu, Shenghong Fu, Yuehao Tang, Seonil Son, Yao Wan, Xuming Hu Categories: cs.CL

The Gap

Chain-of-Thought (CoT) prompting made LLMs show their work, but the reasoning traces are messy. Prior work focused on either filtering bad traces or using ground-truth labels to guide generation. The filtering approach (self-consistency, majority voting) only picks from existing flawed candidates. The label-guidance approach seems intuitive but—counterintuitively—the authors show it doesn’t improve reasoning quality at all.

The real problem: reasoning traces contain two types of flaws. Step Internal Flaws (hallucinations, logical errors within a step) and Step-wise Flaws (overthinking with redundant steps, underthinking with missing steps). These flaws vary by sample, so one-size-fits-all filtering fails. No prior method addresses both flaw types simultaneously while synthesizing new, higher-quality traces.

Problem: LLM reasoning traces have internal + structural flaws
    |
    v
Assumption: Consensus across multiple traces = reliable knowledge
    |
    v
Method: Build knowledge graph from consensus, generate via topology
    |
    v
Evidence: +10% accuracy, better trace quality across dimensions
    |
    v
Conclusion: Graph-based synthesis > filtering or label-guidance

The Increment

One sentence: Before CRAFT, we chose the least-bad reasoning trace from a flawed set; after CRAFT, we synthesize a new trace from the consensus knowledge across multiple candidates.

Core Mechanism

CRAFT operates in three stages. First, generate multiple candidate reasoning traces for a question using standard CoT prompting. Second, extract consensus knowledge: parse each trace into reasoning steps, identify which steps appear consistently across candidates (consensus steps), and organize them into a Reasoning Knowledge Graph (RKG) where nodes are steps and edges represent logical dependencies. Third, synthesize a new trace by traversing the RKG topologically—start from the question node, follow edges to consensus steps in logical order, and generate the final answer.

The RKG acts as a filter and scaffold simultaneously. It filters out sample-specific flaws (steps that appear in only one or two traces are likely hallucinations or overthinking). It scaffolds generation by providing a dependency structure—the model knows which steps must come before others, preventing underthinking (skipped steps) and overthinking (redundant loops).

Input Question
    |
    v
[Generate N candidate traces via CoT]
    |
    +---> Trace 1: Step A -> Step B -> Step C -> Answer
    +---> Trace 2: Step A -> Step D -> Step C -> Answer  
    +---> Trace 3: Step A -> Step B -> Step E -> Answer
    |
    v
[Extract Consensus Steps]
    |
    v
Reasoning Knowledge Graph (RKG):
    Question
       |
       v
    Step A (appears in all 3)
      / \
     v   v
  Step B  Step D (both appear 2x)
     |     |
     v     v
    Step C (appears 2x)
       |
       v
    Answer
    |
    v
[Topological Generation: traverse graph to synthesize trace]
    |
    v
Final Trace: Question -> Step A -> Step B -> Step C -> Answer

Think of CRAFT like Wikipedia’s edit history for a single article. Multiple editors (candidate traces) write different versions of the same story (reasoning chain). Some add unnecessary tangents (overthinking), some skip crucial context (underthinking), some make factual errors (internal flaws). CRAFT is the consensus engine: it identifies which sentences appear across multiple versions (consensus steps = reliable knowledge), maps how those sentences logically connect (RKG = article structure), then generates a clean final version by following that structure (topological generation = synthesized trace). The final article isn’t just the most popular version—it’s a new synthesis built from the stable, agreed-upon parts.

Key Concepts

• Consensus Steps: A reasoning step that appears in multiple candidate traces, indicating it’s likely correct and necessary. Not about exact string matching—CRAFT uses semantic similarity to identify when different phrasings express the same logical step. Example: “Calculate the area of the rectangle” and “Find the product of length and width” are the same consensus step. This filters out hallucinations (appear in only one trace) and overthinking (redundant steps unique to one candidate).

• Reasoning Knowledge Graph (RKG): A directed graph where nodes are consensus steps and edges represent logical dependencies between steps. Built by analyzing which steps consistently follow others across traces. Unlike a simple chain, the graph can have branches (multiple valid next steps) and merges (multiple paths leading to the same step). This structure prevents underthinking—you can’t skip a step if the graph shows it’s a prerequisite for later steps.

• Topological Generation: Traversing the RKG in dependency order to synthesize a new trace. Start at the question node, follow edges to steps whose prerequisites are satisfied, generate text for each step in order. This isn’t template filling—the LLM generates natural language at each node, but the graph constrains the logical flow. Like following a recipe where you can’t add eggs before cracking them, but you can choose how to describe each action.

Framework Shift

Before (filtering/voting):          After (CRAFT):

Question                            Question
   |                                   |
   v                                   v
Generate N traces              Generate N traces
   |                                   |
   +-> Trace 1 (flawed)               v
   +-> Trace 2 (flawed)          Extract consensus
   +-> Trace 3 (flawed)               |
   |                                   v
   v                            Build RKG (graph)
Pick best trace                       |
(still flawed)                        v
                               Synthesize new trace
                               (cleaner, structured)

From selecting the least-bad option to constructing a better option from shared knowledge, the core shift is from voting to synthesis.

Expert Assessment

Problem choice: Real gap. The “correct answer, wrong reasoning” phenomenon is well-documented but under-addressed. Most work optimizes for final accuracy, ignoring trace quality. This matters for interpretability, debugging, and downstream tasks that consume reasoning traces. The counterintuitive finding that ground-truth labels don’t help is valuable—it suggests the problem isn’t lack of supervision but lack of structure.

Method maturity: Clever insight with reasonable execution. The consensus extraction is straightforward (semantic similarity + frequency threshold), and topological generation is standard graph traversal. The innovation is in the combination—using graph structure to guide generation. One concern: the method assumes consensus = correctness, which breaks down when all candidates share the same systematic error. The paper doesn’t deeply explore this failure mode.

Experimental integrity: Baselines are fair (self-consistency, majority voting, label-guided generation). Results are consistent across logical (PrOntoQA, ProofWriter) and mathematical (GSM8K, MATH) benchmarks. The +10% average improvement is substantial. However, the trace quality evaluation relies on GPT-4 as a judge, which introduces bias—GPT-4 might prefer traces that match its own reasoning style. Human evaluation on a subset would strengthen claims.

Writing quality: The abstract and introduction are crisp. The method section is clear but could use more failure case analysis. The related work section is thorough but reads like a literature dump—cutting 30% would improve flow. The biggest missed opportunity: no ablation on the consensus threshold (how many traces must agree for a step to be “consensus”?). This is a critical hyperparameter left unexplored.

Verdict: weak accept — Solid contribution with practical impact, but method assumptions need more scrutiny and evaluation could be more rigorous.

Takeaways

Consensus as a denoising signal: When you have multiple imperfect solutions to the same problem, the parts they agree on are usually correct. This applies beyond reasoning traces—code generation (multiple implementations of the same function), data cleaning (multiple annotators), even design (multiple mockups). Build a graph of shared components, synthesize from that.

Graph topology as a generation constraint: Instead of generating text autoregressively with only local context, use a graph to enforce global structure. Each node is a generation target, edges are dependencies. This prevents the model from wandering off-topic or skipping necessary steps. Applicable to long-form writing, procedural instructions, proof generation.

The label-guidance null result: Providing ground-truth labels during reasoning doesn’t help. This suggests the bottleneck isn’t knowing the right answer but maintaining coherent step-by-step logic. Implications for training: focus on process supervision (rewarding correct intermediate steps) rather than outcome supervision (rewarding correct final answers).