Crake: Causal-Enhanced Table-Filler for Question Answering over Large Scale Knowledge Base

Minhao Zhang, Ruoyu Zhang, Yanzeng Li, Lei Zou

TL;DR

Crake introduces a novel two-stage framework for Knowledge Base Question Answering (KBQA) that models semantic parsing as a simultaneous table-filling task rather than an autoregressive sequence generation process. By explicitly capturing the causal relationship between node extraction and graph composition via a differentiable label-transfer mechanism, Crake eliminates sequence ambiguity and exposure bias. This approach delivers a massive 17.9% absolute improvement in F1 score over previous state-of-the-art methods on the LC-QuAD 1.0 benchmark while remaining highly efficient.

What Problem Does This Paper Address?

Knowledge Base Question Answering (KBQA) systems allow users to query massive databases (like DBpedia) using natural language. A dominant approach is semantic parsing, where a question is converted into an executable query graph (such as a SPARQL query). This pipeline typically involves three steps: Node Extraction (NE) to find entities and variables in the text, Graph Composition (GC) to connect them with unlabeled edges, and Relation Extraction (RE) to map those edges to specific database predicates.

The authors identify two critical flaws in how previous systems handle this pipeline:

  1. Ignoring Subtask Causality: There is a strict causal dependency between NE and GC—edges can only validly exist between nodes that have actually been extracted. Previous methods treat these tasks as independent or loosely coupled, failing to model this structural causality.
  2. The Sequence Generation Trap: Most existing methods generate graph edges sequentially. However, a graph's edge set is inherently unordered. Forcing a graph into an arbitrary sequence introduces sequence ambiguity (which confuses the model during training) and exposure bias (where early generation errors compound rapidly at inference time).

Additionally, traditional relation extraction algorithms scale exponentially with query complexity, making multi-hop questions on large-scale knowledge bases computationally prohibitive.

Methods

Crake addresses these challenges by splitting semantic parsing into two highly optimized stages:

Figure 1: Generating a query graph (bottom) by two stages to represent the SPARQL (right-top). At graph structure generation stage, node-extraction generates all graph nodes while graph-composition adds unla- beled edges between proper nodes. Then, the relation extraction stage decides the specific predicate of each edge.

1. Graph Structure Generation (GSG)

Instead of predicting edges one by one, Crake uses a Biaffine Attention Table-Filler to predict the existence of all undirected edges simultaneously across a 2D matrix of token pairs. This parallel prediction completely bypasses sequence ambiguity and exposure bias.

To enforce the causal dependency between node extraction and edge composition, the authors introduce a Label Transfer Mechanism. The token-level predictions from the NE sequence labeler are passed through a differentiable Gumbel-Softmax layer and embedded directly into the hidden features used by the GC table-filler. This explicitly routes the causal influence of node detection directly into the edge decision matrix.

Figure 2: Causal-enhanced table-filling model for graph structure generation. The label-to-node and table-to-edge correspondence is illustrated by the poker and fruit symbols respectively.

2. Relation Extraction (RE)

To handle large-scale knowledge bases efficiently, Crake utilizes a Beam-Search RE Algorithm. Instead of retrieving all candidate predicates for the entire graph globally, it alternates between candidate retrieval and ranking edge-by-edge. By starting with edges anchored to concrete entities and expanding outward, the algorithm constrains the candidate search space linearly $O(n)$ relative to the node degree, rather than exponentially $O(n^k)$.

Datasets

  • LC-QuAD 1.0: A standard open-domain English KBQA benchmark based on DBpedia (2016-04), consisting of 5,000 questions split into a 4,800/200/1000 train/dev/test distribution.
  • Node-to-Mention Annotations: Because LC-QuAD 1.0 does not natively map SPARQL graph nodes to specific text spans in the questions, the authors recruited 9 annotators to manually add these text-mention alignments to train the sequence labeler.

Key Insights and Ideas

  • Graphs are Sets, Not Sequences: Modeling graph composition as a simultaneous table-filling problem rather than an autoregressive sequence task drastically reduces model complexity. Crake's table-filling decoder requires only 1/100th of the parameters of a standard sequence-to-sequence decoder while achieving superior accuracy and faster convergence.
  • Differentiable Causality: Simply sharing an encoder (standard multi-task learning) is insufficient for capturing strict subtask dependencies. Explicitly feeding the NE label distributions into the GC module allows gradients to flow back through the causal chain, improving the performance of both subtasks.
  • Local Search Pruning: Dynamically pruning the search space during a beam search over the graph structure prevents the exponential explosion of candidate predicates on massive KBs.

Key Results

  • New State-of-the-Art: Crake achieves an F1 score of 0.715 on the LC-QuAD 1.0 test set, outperforming the previous best independent pipeline (STaG-QA at 0.536) by an absolute margin of 17.9%. It also comfortably beats complex methods that rely on heavy auxiliary tools like Abstract Meaning Representation (AMR).
  • Massive Speedups: For complex 3-hop queries, Crake's beam-search RE algorithm takes an average of just 2.72 seconds, compared to 84.2 seconds for the baseline approach—representing a 31x speedup.
  • Ablation Validation: Incorporating the causal label transfer mechanism improved the Graph Structure Generation exact-match (EM) accuracy from 0.728 to 0.755, confirming that explicit causal modeling directly translates to structural precision.

Limitations and Future Work

  • Query Expressiveness: Crake currently focuses on constructing core triple patterns in multi-hop query graphs. It does not yet support more complex SPARQL operations such as FILTER constraints, aggregations, or complex property paths.
  • Annotation Bottleneck: The framework relies on expensive manual annotations mapping graph nodes to specific text mentions. The authors note that exploring few-shot or active learning techniques will be crucial to reducing this overhead and scaling the system to other datasets.

Summary updated

Abstract

Semantic parsing solves knowledge base (KB) question answering (KBQA) by composing a KB query, which generally involves node extraction (NE) and graph composition (GC) to detect and connect related nodes in a query. Despite the strong causal effects between NE and GC, previous works fail to directly model such causalities in their pipeline, hindering the learning of subtask correlations. Also, the sequence-generation process for GC in previous works induces ambiguity and exposure bias, which further harms accuracy. In this work, we formalize semantic parsing into two stages. In the first stage (graph structure generation), we propose a causal-enhanced table-filler to overcome the issues in sequence-modelling and to learn the internal causalities. In the second stage (relation extraction), an efficient beam-search algorithm is presented to scale complex queries on large-scale KBs. Experiments on LC-QuAD 1.0 indicate that our method surpasses previous state-of-the-arts by a large margin (17%) while remaining time and space efficiency. The code and models are available at https://github.com/AOZMH/Crake.
BibTeX
@inproceedings{zhang2022crake,
  author = {Minhao Zhang and Ruoyu Zhang and Yanzeng Li and Lei Zou},
  title = {{Crake: Causal-Enhanced Table-Filler for Question Answering over Large Scale Knowledge Base}},
  booktitle = {Conference of the North American Chapter of the Association for Computational Linguistics},
  year = {2022},
  doi = {10.18653/v1/2022.findings-naacl.136},
}
Figure