# ArcaneQA: Dynamic Program Induction and Contextualized Encoding for Knowledge Base Question Answering

arXiv: https://arxiv.org/abs/2204.08109 · HTML: https://mlsanity.com/paper/2204.08109/

## Key facts

- Cited by 48 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 48 references that are in the map.
- First posted on arXiv 17 Apr 2022.

## Builds on (most cited first, 25 of 25)

- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [Exploring the Limits of Transfer Learning with a Unified Text-to-Text Transformer](https://mlsanity.com/paper/1910.10683/) (2019)
- [Neural Machine Translation by Jointly Learning to Align and Translate](https://mlsanity.com/paper/1409.0473/) (2014)
- [Sequence to Sequence Learning with Neural Networks](https://mlsanity.com/paper/1409.3215/) (2014)
- [Spider: A Large-Scale Human-Labeled Dataset for Complex and Cross-Domain Semantic Parsing and Text-to-SQL Task](https://mlsanity.com/paper/1809.08887/) (2018)
- [Seq2SQL: Generating Structured Queries from Natural Language using Reinforcement Learning](https://mlsanity.com/paper/1709.00103/) (2017)
- [RAT-SQL: Relation-Aware Schema Encoding and Linking for Text-to-SQL Parsers](https://mlsanity.com/paper/1911.04942/) (2019)
- [PICARD: Parsing Incrementally for Constrained Auto-Regressive Decoding from Language Models](https://mlsanity.com/paper/2109.05093/) (2021)
- [AllenNLP: A Deep Semantic Natural Language Processing Platform](https://mlsanity.com/paper/1803.07640/) (2018)
- [UnifiedSKG: Unifying and Multi-Tasking Structured Knowledge Grounding with Text-to-Text Language Models](https://mlsanity.com/paper/2201.05966/) (2022)
- [Beyond I.I.D.: Three Levels of Generalization for Question Answering on Knowledge Bases](https://mlsanity.com/paper/2011.07743/) (2020)
- [Language to Logical Form with Neural Attention](https://mlsanity.com/paper/1601.01280/) (2016)
- [Task-Oriented Dialogue as Dataflow Synthesis](https://mlsanity.com/paper/2009.11423/) (2020)
- [Case-based Reasoning for Natural Language Queries over Knowledge Bases](https://mlsanity.com/paper/2104.08762/) (2021)
- [Neural Symbolic Machines: Learning Semantic Parsers on Freebase with Weak Supervision](https://mlsanity.com/paper/1611.00020/) (2016)
- [SmBoP: Semi-autoregressive Bottom-up Semantic Parsing](https://mlsanity.com/paper/2010.12412/) (2020)
- [A Comprehensive Exploration on WikiSQL with Table-Aware Word Contextualization](https://mlsanity.com/paper/1902.01069/) (2019)
- [RnG-KBQA: Generation Augmented Iterative Ranking for Knowledge Base Question Answering](https://mlsanity.com/paper/2109.08678/) (2021)
- [Editing-Based SQL Query Generation for Cross-Domain Context-Dependent Questions](https://mlsanity.com/paper/1909.00786/) (2019)
- [Robust Text-to-SQL Generation with Execution-Guided Decoding](https://mlsanity.com/paper/1807.03100/) (2018)
- [SPARQA: Skeleton-based Semantic Parsing for Complex Questions over Knowledge Bases](https://mlsanity.com/paper/2003.13956/) (2020)
- [Learning to Paraphrase for Question Answering](https://mlsanity.com/paper/1708.06022/) (2017)
- [UHop: An Unrestricted-Hop Relation Extraction Framework for Knowledge-Based Question Answering](https://mlsanity.com/paper/1904.01246/) (2019)
- [Universal Semantic Parsing](https://mlsanity.com/paper/1702.03196/) (2017)
- [Learning an Executable Neural Semantic Parser](https://mlsanity.com/paper/1711.05066/) (2017)

## Built on by (most cited first, 30 of 48)

- [AgentBench: Evaluating LLMs as Agents](https://mlsanity.com/paper/2308.03688/) (2023)
- [Reasoning on Graphs: Faithful and Interpretable Large Language Model Reasoning](https://mlsanity.com/paper/2310.01061/) (2023)
- [Graph Retrieval-Augmented Generation: A Survey](https://mlsanity.com/paper/2408.08921/) (2024)
- [KG-Agent: An Efficient Autonomous Agent Framework for Complex Reasoning over Knowledge Graph](https://mlsanity.com/paper/2402.11163/) (2024)
- [DecAF: Joint Decoding of Answers and Logical Forms for Question Answering over Knowledge Bases](https://mlsanity.com/paper/2210.00063/) (2022)
- [Few-shot In-context Learning for Knowledge Base Question Answering](https://mlsanity.com/paper/2305.01750/) (2023)
- [Can ChatGPT Replace Traditional KBQA Models? An In-depth Analysis of the Question Answering Performance of the GPT LLM Family](https://mlsanity.com/paper/2303.07992/) (2023)
- [TrustAgent: Towards Safe and Trustworthy LLM-based Agents](https://mlsanity.com/paper/2402.01586/) (2024)
- [TIARA: Multi-grained Retrieval for Robust Question Answering over Large Knowledge Bases](https://mlsanity.com/paper/2210.12925/) (2022)
- [Don't Generate, Discriminate: A Proposal for Grounding Language Models to Real-World Environments](https://mlsanity.com/paper/2212.09736/) (2022)
- [FlexKBQA: A Flexible LLM-Powered Framework for Few-Shot Knowledge Base Question Answering](https://mlsanity.com/paper/2308.12060/) (2023)
- [ChatKBQA: A Generate-then-Retrieve Framework for Knowledge Base Question Answering with Fine-tuned Large Language Models](https://mlsanity.com/paper/2310.08975/) (2023)
- [Middleware for LLMs: Tools Are Instrumental for Language Agents in Complex Environments](https://mlsanity.com/paper/2402.14672/) (2024)
- [FiDeLiS: Faithful Reasoning in Large Language Model for Knowledge Graph Question Answering](https://mlsanity.com/paper/2405.13873/) (2024)
- [SPINACH: SPARQL-Based Information Navigation for Challenging Real-World Questions](https://mlsanity.com/paper/2407.11417/) (2024)
- [Knowledge Base Question Answering: A Semantic Parsing Perspective](https://mlsanity.com/paper/2209.04994/) (2022)
- [KBQA-o1: Agentic Knowledge Base Question Answering with Monte Carlo Tree Search](https://mlsanity.com/paper/2501.18922/) (2025)
- [An Empirical Study of Pre-trained Language Models in Simple Knowledge Graph Question Answering](https://mlsanity.com/paper/2303.10368/) (2023)
- [Graph-based Approaches and Functionalities in Retrieval-Augmented Generation: A Comprehensive Survey](https://mlsanity.com/paper/2504.10499/) (2025)
- [Uni-Parser: Unified Semantic Parser for Question Answering on Knowledge Base and Database](https://mlsanity.com/paper/2211.05165/) (2022)
- [GraphQ IR: Unifying the Semantic Parsing of Graph Query Languages with One Intermediate Representation](https://mlsanity.com/paper/2205.12078/) (2022)
- [Code-Style In-Context Learning for Knowledge-Based Question Answering](https://mlsanity.com/paper/2309.04695/) (2023)
- [SUQL: Conversational Search over Structured and Unstructured Data with Large Language Models](https://mlsanity.com/paper/2311.09818/) (2023)
- [Bring Your Own KG: Self-Supervised Program Synthesis for Zero-Shot KGQA](https://mlsanity.com/paper/2311.07850/) (2023)
- [Right for Right Reasons: Large Language Models for Verifiable Commonsense Knowledge Graph Question Answering](https://mlsanity.com/paper/2403.01390/) (2024)
- [BYOKG-RAG: Multi-Strategy Graph Retrieval for Knowledge Graph Question Answering](https://mlsanity.com/paper/2507.04127/) (2025)
- [Temporal Knowledge Graph Question Answering: A Survey](https://mlsanity.com/paper/2406.14191/) (2024)
- [Make a Choice! Knowledge Base Question Answering with In-Context Learning](https://mlsanity.com/paper/2305.13972/) (2023)
- [iQUEST: An Iterative Question-Guided Framework for Knowledge Base Question Answering](https://mlsanity.com/paper/2506.01784/) (2025)
- [EPERM: An Evidence Path Enhanced Reasoning Model for Knowledge Graph Question and Answering](https://mlsanity.com/paper/2502.16171/) (2025)

## Abstract (arXiv)

Question answering on knowledge bases (KBQA) poses a unique challenge for semantic parsing research due to two intertwined challenges: large search space and ambiguities in schema linking. Conventional ranking-based KBQA models, which rely on a candidate enumeration step to reduce the search space, struggle with flexibility in predicting complicated queries and have impractical running time. In this paper, we present ArcaneQA, a novel generation-based model that addresses both the large search space and the schema linking challenges in a unified framework with two mutually boosting ingredients: dynamic program induction for tackling the large search space and dynamic contextualized encoding for schema linking. Experimental results on multiple popular KBQA datasets demonstrate the highly competitive performance of ArcaneQA in both effectiveness and efficiency.