Source-linked AI summary
Case-based Reasoning for Natural Language Queries over Knowledge Bases
Rajarshi Das, Manzil Zaheer, Dung Thai, Ameya Godbole, Ethan Perez, Jay-Yoon Lee, Lizhen Tan, Lazaros Polymenakos, Andrew McCallum
TL;DR
Complex KBQA is difficult to solve from scratch, especially when case retrieval and solution synthesis are challenging. CBR-KBQA combines a case memory with a parametric logical-form generator, achieves competitive results across multiple benchmarks, and outperforms the best system on CWQ by over 11% points while reusing newly injected cases without fine-tuning.
Problem
Finding similar cases and synthesizing solutions is challenging for case-based reasoning systems, motivating neural methods for complex KBQA.
Method
CBR-KBQA uses a nonparametric memory of question–logical-form cases and a parametric model that generates logical forms conditioned on retrieved similar questions.
Results
Over 11% points on the hidden CWQ test set, CBR-KBQA outperforms the best system and achieves competitive results on multiple KBQA benchmarks.
Takeaways & Limitations
Without further fine-tuning, CBR-KBQA can use a few injected simple cases to compose logical forms with relations unseen during training.
Takeaways & Limitations
The model relies on supervised logical forms such as SPARQL queries, which can be expensive to annotate at scale.
Abstract
from arXiv · showhide
It is often challenging to solve a complex problem from scratch, but much easier if we can access other similar problems with their solutions -- a paradigm known as case-based reasoning (CBR). We propose a neuro-symbolic CBR approach (CBR-KBQA) for question answering over large knowledge bases. CBR-KBQA consists of a nonparametric memory that stores cases (question and logical forms) and a parametric model that can generate a logical form for a new question by retrieving cases that are relevant to it. On several KBQA datasets that contain complex questions, CBR-KBQA achieves competitive performance. For example, on the ComplexWebQuestions dataset, CBR-KBQA outperforms the current state of the art by 11\% on accuracy. Furthermore, we show that CBR-KBQA is capable of using new cases \emph{without} any further training: by incorporating a few human-labeled examples in the case memory, CBR-KBQA is able to successfully generate logical forms containing unseen KB entities as well as relations.
1 Introduction
CBR-KBQA applies case-based reasoning to KBQA by retrieving similar queries and reusing their logical forms, with revision to address missing or mismatched relations. It achieves competitive results on complex KBQA benchmarks and can incorporate new cases without retraining.
- 1 Introduction: CBR-KBQA retrieves similar queries and reuses components of their logical forms to generate a logical form for a new query.The approach uses a neural retriever and a parametric generator over a nonparametric case memory.
- 1 Introduction: CBR-KBQA handles questions requiring novel combinations of knowledge-base relations by reusing relations from multiple retrieved cases.The paper reports competitive results on WebQuestionsSP, ComplexWebQuestions, and CompositionalFreebaseQuestions.
- 1 Introduction: The revise step aligns missing or mismatched relations with semantically similar edges available in the knowledge base.This addresses cases where generated logical forms fail to execute because required edges are absent or domains differ.
- 1 Introduction: Over 11% points: CBR-KBQA outperforms the best system on the hidden test set of ComplexWebQuestions.The reported comparison concerns accuracy on the challenging CWQ dataset.
- 1 Introduction: Without further fine-tuning, CBR-KBQA can use injected simple cases to compose logical forms containing relations unseen during training.A human-in-the-loop experiment shows that expert-provided cases can be retrieved and reused at inference time.
- 1 Introduction: The paper positions CBR-KBQA as useful for deployment because its behavior can be controlled by adding relevant cases to memory.The authors connect this controllability to real-world QA deployment settings.
2 Model
CBR-KBQA retrieves similar query–logical-form cases, reuses their components to generate a logical form, and revises it to improve executability against a knowledge base. Its model combines neural retrieval and generation with relation alignment, sparse attention, and regularization from a query-only model.
- Case representation: A case pairs a natural-language query with an executable logical form containing entities, relations, and free variables.The experiments use SPARQL programs as logical forms; equivalent representations include SPARQL, SQL, S-expressions, and graph queries.
- 2.1 Retrieve: The retrieval module encodes queries independently, trains similarity using logical-form relation overlap, and returns the top-k cases from the training set.Entity masking reduces the effect of entity identity during retrieval, while relation-overlap F1 supplies distant supervision.
- 2.2 Reuse: The reuse module generates an intermediate logical form from multiple retrieved query–logical-form cases using a sequence-to-sequence transformer.The query and cases are concatenated as encoder input, with entity identifiers appended to entity mentions.
- 2.2 Reuse: BIGBIRD reduces transformer memory complexity from quadratic to linear, enabling CBR-KBQA to process more retrieved cases than standard full-attention models.This addresses the length of concatenated queries and potentially long executable SPARQL programs.
- 2.2 Reuse: A KLD regularizer keeps case-conditioned predictions close to query-only predictions, while the revise step aligns generated relations with edges near the query entity.The alignment uses pretrained TransE relation embeddings, surface-form similarity, and beam search when multiple missing edges require alignment.
3 Experiments
CBR-KBQA is evaluated on three KBQA datasets using exact-match answer accuracy and related metrics, with analyses of entity linking, revision, and adaptation to unseen relations. It outperforms strong baselines across benchmarks and can incorporate new cases without retraining.
- Experimental setup: Experiments use full Freebase and evaluate CBR-KBQA on WebQSP, ComplexWebQuestions, and CompositionalFreebaseQuestions.Full Freebase contains over 45 million entities and 3 billion facts.
- Evaluation: The evaluation reports strict exact-match accuracy by comparing executed predicted and gold answer lists, alongside precision, recall, and F1.A prediction is correct only when the two answer lists match exactly.
- KBQA results: More than 6 points of strict exact-match accuracy separate CBR-KBQA from the best WebQSP model, while it also outperforms baselines on the hidden CWQ test set and all CFQ MCD splits.The paper also reports that CBR-KBQA outperforms T5-11B on CFQ despite having orders of magnitude fewer parameters.
- Efficacy of Revise step: The revise step consistently improves accuracy on WebQSP and CWQ, with TransE alignment outperforming RoBERTa-based alignment.The results suggest graph-structure information is more useful than surface-form similarity for aligning relations.
- Performance on Unseen Relations: Adding a few simple cases lets CBR-KBQA use relations unseen during training without fine-tuning, reaching 70.6% accuracy on 86 held-out queries.The baseline transformer requires fine-tuning and suffers catastrophic forgetting unless original examples are mixed with new ones.
- Additional analysis: Performance improves as the number of retrieved cases increases, and retrieved cases are especially beneficial on WebQSP compared with a model lacking case-memory retrieval.These comparisons isolate the contribution of retrieving similar cases and varying retrieval breadth.
4 Related Work
CBR-KBQA differs from retrieval-augmented and nearest-neighbor QA by using multiple similar queries and their logical forms to generate new programs.
- CBR-KBQA differs from retrieval-augmented QA models, which retrieve relevant paragraphs from nonparametric memory for a reader.
- CBR-KBQA retrieves similar queries and uses their logical forms to derive a new solution.
- Unlike nearest-neighbor QA, CBR-KBQA generates a new program from the programs of multiple retrieved queries.Nearest-neighbor QA returns the answer to a retrieved question and does not generalize to other scenarios.
- Prior program-repair approaches use syntax, sketches, or debuggers, whereas CBR-KBQA uses multiple retrieved similar queries to generate the target program.The paper also distinguishes its use of semantic relation similarity for aligning relations.
5 Limitations and Future Work
The paper presents neuralized CBR for KBQA and identifies supervised logical-form annotation and separately trained retrieval and reuse components as limitations.
- CBR-KBQA is presented as the first neuralized case-based reasoning approach for KBQA.
- The model is effective for handling complex questions over knowledge bases.
- CBR-KBQA relies on supervised logical forms such as SPARQL queries, which can be expensive to annotate at scale.The authors plan to explore learning directly from question-answer pairs.
- The retrieve and reuse components are trained separately rather than end to end.The authors identify end-to-end learning for CBR as future work.
A.1 Data
The evaluation uses WebQSP, CWQ, and CFQ, with SPARQL logical forms executed against Freebase, alongside specified validation, model, and infrastructure settings.
- CWQ extends WebQSP into a complex multi-hop dataset with composition, conjunction, comparative, and superlative questions requiring up to four reasoning hops.The question types comprise 45% composition, 45% conjunction, 5% comparative, and 5% superlative examples.
- CFQ is explicitly developed to measure compositional generalization, while all listed datasets use executable SPARQL queries as logical forms.The queries are executed against the Freebase knowledge base to obtain answer entities.
- WebQSP lacks a validation split, so 300 training instances are selected for validation.The retriever is evaluated by the percentage of gold logical-form relations in the top-k retrieved cases.
- The generator uses BIGBIRD with six encoding and six decoding sparse-attention layers initialized from BART-base weights.Validation accuracy after executing generated programs selects the optimal setting and checkpoint.
- All datasets use k=20 retrieved cases and beam size 5, with WebQSP trained for 15K steps and other models for 40K steps.
- Experiments run on NVIDIA RTX 2080 Ti and RTX 8000 GPUs, with Revise also running on CPU when using TRANSE; Table 12 reports validation scores.
B Further Experiments and Analysis
Retriever fine-tuning improves retrieval recall over an untuned ROBERTA-base model, with gains reported on WebQSP and CFQ.
- Fine-tuning ROBERTA with the distant-supervision objective improves overall retrieval recall over ROBERTA-base without fine-tuning.
- 86.6% to 90.4% recall is reported on WebQSP after fine-tuning the retriever.
- 94.8% to 98.4% recall is reported on CFQ after fine-tuning the retriever.
B.2 Performance on Unseen Entities
CBR-KBQA copies unseen entities from the input question more accurately than the baseline trans-former model on WebQSP, without requiring additional injected cases.
- 86.8% (539/621) of unseen entities were copied correctly by CBR-KBQA from WebQSP questions.
B.3 Analysis of the Revise Step
The revise step attempts to repair predicted logical forms that fail during knowledge-base execution by aligning clauses with relations near query entities.
- The revise step fixes predicted programs that fail because they are syntactically incorrect or impose unsatisfiable conditions.
- CBR-KBQA focuses on repairs that align program clauses with relations in the local neighborhoods of query entities.The paper reports both successful and failed TransE-based alignment examples.
C Details on Held-Out Experiments
The held-out experiment tests whether CBR-KBQA can handle relations absent from training without further model training, reflecting knowledge bases that gain new relation types.
- The experiment targets adaptation to new knowledge-base relations without further training or fine-tuning.The setting is motivated by real-world knowledge bases that are updated with new kinds of relations.
- The experiment holds out every question containing a selected relation from the datasets.
- Table 13 reports each held-out relation type and the number of natural-language queries removed for that relation.
D Details on Automated Case Collection and Human-in-the-Loop Experiments
The held-out evaluation adds simple cases for missing relations through automated collection and human annotation, then tests whether CBR-KBQA can reuse them to answer complex queries. The experiment also motivates interpretability and controllability through inspectable retrieval and targeted case additions.
- Human-in-the-Loop Experiment: WebQSP test queries with relations absent from training enable human-in-the-loop evaluation of added cases.
- Automated Case Collection: SimpleQuestions provides over 100K simple queries, each mapping to a single Freebase relation, for automatically collecting cases for missing relations.
- Automated Case Collection: Missing-relations cases can also be manually created as natural-language questions paired with SPARQL queries, using relation descriptions when SimpleQuestions lacks coverage.The examples include questions such as “Who developed the TCP/IP reference model?” and corresponding simple SPARQL queries.
- Automated Case Collection: 3.87 new cases per query were added overall, including 292 SimpleQuestions cases and 72 manually created WebQSP cases.
- Case Construction: The added cases contain simple questions paired with executable logical forms, making their SPARQL queries easy to construct from a relation and entity identifier.
- Interpretability and Controllability: The experiment demonstrates interpretability through inspecting retrieved nearest neighbors and controllability through adding cases for new relations without retraining.