LLM-MatLogic: Executable Exchange Contracts for Knowledge-Graph Query Answering with Scoped Negation

LLM-to-KG systems frequently fail on exclusion-rich questions because natural-language negation is both scope-sensitive and evidence-dependent: it may constrain only one subgoal/branch and only certain supporting paths, yet such attachment is rarely explicit in text. We propose the Executable Exchange Contract (EEC) to bridge this gap, specifying scope-bound exclusions as executable control metadata exchanged between a specifier and an executor. Our executor, MatLogic, compiles exclusions into scope-local masks applied during multi-hop propagation and executes requests under a unified P$\rightarrow$N$\rightarrow$C/D schedule, ensuring exclusions are enforced before witness loss and branch entanglement. The system can also return compact witness pointers to keep support types distinguishable when needed. We evaluate on both structured complex queries and end-to-end natural-language KGQA, and introduce contract-aligned diagnostics that isolate errors from specification versus execution and verify the necessity of scoped enforcement.

LLM-KG question-answering systems use large language models (LLMs) to understand a user’s question and knowledge graph (KG) to search over connected factual data. However, these systems often struggle with questions that contain negation. The difficulty is that the negation may not apply to the whole answer, but only to a specific entity, condition, or reasoning branch. If the system applies the negation too late, or applies it to the wrong part of the graph search, it may remove valid answers or keep answers that should have been excluded. This paper introduces a clear instruction layer, called EEC, between the LLM and the executor. The LLM uses its natural-language understanding to identify what is negated and where the negation should apply. The executor then follows a unified procedure that works across different query structures, applying the negation during graph reasoning before supporting evidence is lost or different reasoning branches are mixed together. This makes LLM-KG question answering more reliable for questions involving negation.