Aligning Complex Knowledge Graph Question Answering as Knowledge-Aware Constrained Code Generation

Prerna Agarwal, Nishant Kumar, Srikanta Bedathur JagannathCOLING 2025 · OpenReview

Abstract

Generating executable logical forms (LF) using Large Language Models (LLMs) in a few-shot setting for Knowledge Graph Question Answering (KGQA) is becoming popular. However, their performance is still limited due to very little exposure to the LF during pre-training of LLMs, resulting in many syntactically incorrect LF generation. If the LF generation task can be transformed to a more familiar task for the LLM, it can potentially reduce the syntax errors and elevate the generation quality. On the other hand, there exist specialized LLMs trained/fine-tuned on code in many programming languages. They can be leveraged to generate the LF as step-wise constrained code expression generation using modular functions in the LF. Based on this insight, we propose CodeAlignKGQA: a framework that aligns the LF generation as code generation that incorporates LF-specific constraints. We extract the question-specific subgraph information to enable Knowledge-Aware code generation. We additionally introduce a dynamic self-code-correction mechanism, to be applied as required. Our extensive experiments on Complex KGQA benchmarks such as KQA Pro demonstrate the effectiveness of our approach. CodeAlignKGQA surpasses all few-shot baselines on KQA Pro by 21%, achieving a new state-of-the-art.

Introduction: The Syntax and Structural Gap

Answering complex questions using Knowledge Graphs (KGs) typically requires translating natural language into a Logical Form (LF), such as SPARQL or S-Expressions. While LLMs are proficient at general reasoning, they often struggle with this translation for two primary reasons. First, Syntax Sensitivity: LLMs have limited exposure to niche logical forms during pre-training, leading to frequent syntax errors. Second, Structural Blindness: Most models generate a "draft" logical form without knowing the actual structure of the KG, resulting in queries that refer to relations or entities that do not exist in the database.

As questions become more compositional (e.g., "Which person wrote the films acted by the actors in The Gift?"), the probability of a multi-step reasoning chain breaking due to a single syntax error increases exponentially. CodeAlignKGQA addresses these issues by reframing KGQA as a constrained code generation task.

The CodeAlignKGQA Framework

CodeAlignKGQA treats KGQA as Knowledge-Aware Constrained Code Generation. The framework leverages the fact that Large Language Models (LLMs) are far more proficient at writing general-purpose code (like Python) than niche logical forms.

Overview of the CodeAlignKGQA framework vs. traditional LLM prompting methods.

The framework consists of three main stages:

  1. Alignment via Python: Instead of niche query languages, the system uses KoPL (Knowledge Oriented Programming Language) wrapped in Python function definitions. Since Code-LLMs are trained on millions of lines of Python, they are naturally better at following these modular, step-by-step programming instructions.
  2. Knowledge-Aware Prompting: To solve the "structural blindness" problem, the system extracts a question-specific subgraph from the KG to provide the model with a "local map" of relevant facts.
  3. Dynamic Self-Code-Correction: If the generated code fails a syntax check, the system retrieves new demonstrations with similar program syntax to help the LLM correct its logic.

Knowledge-Aware Prompting

To ensure the generated code is grounded in reality, CodeAlignKGQA uses a non-parametric Breadth-First Search (BFS) to extract question-specific facts. This process involves masking the question to identify concepts and using N-gram matching to find relevant attributes and qualifiers within the KG.

Detailed workflow for fact identification and retrieval using BFS and N-grams.

By injecting these facts directly into the LLM's prompt, the model becomes "knowledge-aware" without the massive overhead of fine-tuning or passing the entire graph into the context window. This local context allows the model to select valid relations and entities during the code generation phase.

Experimental Evaluation

The framework was evaluated on three major benchmarks: KQA Pro (complex, multi-hop reasoning), MetaQA (movie-domain multi-hop), and WebQSP (real-world Google queries).

Key results include:

  • New State-of-the-Art: On KQA Pro, CodeAlignKGQA (using Gemini Pro 1.0) achieved 72.70% Hits@1, outperforming the previous best few-shot model (SymKGQA) by 21.5%.
  • Zero Syntax Errors: On the MetaQA and WebQSP datasets, the framework reduced the Syntax Error Rate (SER) to 0.0%, a significant improvement over baselines that often saw 20-30% of queries fail due to formatting.
  • Model Agnostic Performance: The approach showed consistent gains across different LLMs, including CodeLlama, DeepSeek-Coder, and GPT-4, demonstrating that the benefit comes from the framework's alignment strategy rather than a specific model's capabilities.

Conclusion

CodeAlignKGQA demonstrates that the "aha moment" for complex KGQA is not forcing LLMs to learn new query languages, but rather aligning the task with their existing strengths in general-purpose programming. By combining Python-based alignment, local subgraph awareness, and structural self-correction, the framework sets a new standard for few-shot performance in complex knowledge graph reasoning.

Summary updated

Abstract

Generating executable logical forms (LF) using Large Language Models (LLMs) in a few-shot setting for Knowledge Graph Question Answering (KGQA) is becoming popular. However, their performance is still limited due to very little exposure to the LF during pre-training of LLMs, resulting in many syntactically incorrect LF generation. If the LF generation task can be transformed to a more familiar task for the LLM, it can potentially reduce the syntax errors and elevate the generation quality. On the other hand, there exist specialized LLMs trained/fine-tuned on code in many programming languages. They can be leveraged to generate the LF as step-wise constrained code expression generation using modular functions in the LF. Based on this insight, we propose CodeAlignKGQA: a framework that aligns the LF generation as code generation that incorporates LF-specific constraints. We extract the question-specific subgraph information to enable Knowledge-Aware code generation. We additionally introduce a dynamic self-code-correction mechanism, to be applied as required. Our extensive experiments on Complex KGQA benchmarks such as KQA Pro demonstrate the effectiveness of our approach. CodeAlignKGQA surpasses all few-shot baselines on KQA Pro by 21%, achieving a new state-of-the-art.
BibTeX
@inproceedings{agarwal2025aligning,
  author = {Prerna Agarwal and Nishant Kumar and Srikanta Bedathur Jagannath},
  title = {{Aligning Complex Knowledge Graph Question Answering as Knowledge-Aware Constrained Code Generation}},
  booktitle = {International Conference on Computational Linguistics},
  year = {2025},
  url = {https://openreview.net/forum?id=SFbF6A74Ja},
}
Figure