# Which bird does not have wings: Negative-constrained KGQA with Schema-guided Semantic Matching and Self-directed Refinement

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in Knowledge- and tool-augmented reasoning, one of 17 directions in LLM reasoning.
- Builds on 30 of its 46 references that are in the map.
- First posted on arXiv 16 Apr 2026.

## Placed in

- LLM reasoning / [Knowledge- and tool-augmented reasoning](https://mlsanity.com/lr/knowledge-and-tool-augmented-reasoning/)

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

- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [GPT-4 Technical Report](https://mlsanity.com/paper/2303.08774/) (2023)
- [The Llama 3 Herd of Models](https://mlsanity.com/paper/2407.21783/) (2024)
- [Retrieval-Augmented Generation for Knowledge-Intensive NLP Tasks](https://mlsanity.com/paper/2005.11401/) (2020)
- [Billion-scale similarity search with GPUs](https://mlsanity.com/paper/1702.08734/) (2017)
- [SimCSE: Simple Contrastive Learning of Sentence Embeddings](https://mlsanity.com/paper/2104.08821/) (2021)
- [Qwen2.5-Coder Technical Report](https://mlsanity.com/paper/2409.12186/) (2024)
- [DeepSeek-V2: A Strong, Economical, and Efficient Mixture-of-Experts Language Model](https://mlsanity.com/paper/2405.04434/) (2024)
- [StructGPT: A General Framework for Large Language Model to Reason over Structured Data](https://mlsanity.com/paper/2305.09645/) (2023)
- [Think-on-Graph: Deep and Responsible Reasoning of Large Language Model on Knowledge Graph](https://mlsanity.com/paper/2307.07697/) (2023)
- [Beyond I.I.D.: Three Levels of Generalization for Question Answering on Knowledge Bases](https://mlsanity.com/paper/2011.07743/) (2020)
- [RnG-KBQA: Generation Augmented Iterative Ranking for Knowledge Base Question Answering](https://mlsanity.com/paper/2109.08678/) (2021)
- [DecAF: Joint Decoding of Answers and Logical Forms for Question Answering over Knowledge Bases](https://mlsanity.com/paper/2210.00063/) (2022)
- [KQA Pro: A Dataset with Explicit Compositional Programs for Complex Question Answering over Knowledge Base](https://mlsanity.com/paper/2007.03875/) (2020)
- [Few-shot In-context Learning for Knowledge Base Question Answering](https://mlsanity.com/paper/2305.01750/) (2023)
- [Language models are not naysayers: An analysis of language models on negation benchmarks](https://mlsanity.com/paper/2306.08189/) (2023)
- [Code4Struct: Code Generation for Few-Shot Event Structure Prediction](https://mlsanity.com/paper/2210.12810/) (2022)
- [TIARA: Multi-grained Retrieval for Robust Question Answering over Large Knowledge Bases](https://mlsanity.com/paper/2210.12925/) (2022)
- [ArcaneQA: Dynamic Program Induction and Contextualized Encoding for Knowledge Base Question Answering](https://mlsanity.com/paper/2204.08109/) (2022)
- [Paths-over-Graph: Knowledge Graph Empowered Large Language Model Reasoning](https://mlsanity.com/paper/2410.14211/) (2024)
- [Lambda Dependency-Based Compositional Semantics](https://mlsanity.com/paper/1309.4408/) (2013)
- [Harnessing Large Language Models for Knowledge Graph Question Answering via Adaptive Multi-Aspect Retrieval-Augmentation](https://mlsanity.com/paper/2412.18537/) (2024)
- [ScoNe: Benchmarking Negation Reasoning in Language Models With Fine-Tuning and In-Context Learning](https://mlsanity.com/paper/2305.19426/) (2023)
- [CoTKR: Chain-of-Thought Enhanced Knowledge Rewriting for Complex Knowledge Graph Question Answering](https://mlsanity.com/paper/2409.19753/) (2024)
- [Investigating and Addressing Hallucinations of LLMs in Tasks Involving Negation](https://mlsanity.com/paper/2406.05494/) (2024)
- [Paraphrasing in Affirmative Terms Improves Negation Understanding](https://mlsanity.com/paper/2406.07492/) (2024)
- [Beyond Seen Data: Improving KBQA Generalization Through Schema-Guided Logical Form Generation](https://mlsanity.com/paper/2502.12737/) (2025)
- [Robust Training for Conversational Question Answering Models with Reinforced Reformulation Generation](https://mlsanity.com/paper/2310.13505/) (2023)
- [Assessing Step-by-Step Reasoning against Lexical Negation: A Case Study on Syllogism](https://mlsanity.com/paper/2310.14868/) (2023)
- [Applying the Closed World Assumption to SUMO-based FOL Ontologies for Effective Commonsense Reasoning](https://mlsanity.com/paper/1808.04620/) (2018)

## Abstract (arXiv)

Large language models still struggle with faithfulness and hallucinations despite their remarkable reasoning abilities. In Knowledge Graph Question Answering (KGQA), semantic parsing-based approaches address the limitations by understanding constraints in a user's question and converting them into a logical form to execute on a knowledge graph. However, existing KGQA benchmarks and methods are biased toward positive and calculation constraints. Negative constraints are neglected, although they frequently appear in real-world questions. In this paper, we introduce a new task, NEgative-conSTrained (NEST) KGQA, where each question contains at least one negative constraint, and a corresponding dataset, NestKGQA. We also design PyLF, a Python-formatted logical form, since existing logical forms are hardly suitable to express negation clearly while maintaining readability. Furthermore, NEST questions naturally contain multiple constraints. To mitigate their semantic complexity, we present a novel framework named CUCKOO, specialized to multiple-constrained questions and ensuring semantic executability. CUCKOO first generates a constraint-aware logical form draft and performs schema-guided semantic matching. It then selectively applies self-directed refinement only when executing improper logical forms yields an empty result, reducing cost while improving robustness. Experimental results demonstrate that CUCKOO consistently outperforms baselines on both conventional KGQA and NEST-KGQA benchmarks under few-shot settings.