acceptodds
Under review as a conference paper at ICLR 2027

ComplexLogicalQA: Benchmarking Knowledge Graph Question Answering Beyond Chain-like Reasoning

12 views

Abstract

Knowledge Graph Question Answering (KGQA) benchmarks have substantially advanced the evaluation of multi-hop reasoning. However, our structural audit shows that widely used benchmarks remain heavily skewed toward chain-like queries, with limited coverage of nested logical compositions and no union structures in our sampled analysis. To address this gap, we introduce ComplexLogicalQA (CLQ), a structure-balanced diagnostic benchmark covering nine Existential Positive First-Order Logic (EPFO) query structures. CLQ is constructed through structure-constrained subgraph sampling, followed by LLM-based verbalization and multi-stage verification to preserve executable logical validity while improving linguistic diversity. Experiments across four KGQA paradigms reveal a clear and consistent trend: performance degrades as queries move beyond chain-like projections, with the largest and most stable drops on nested compositions. Union structures are not uniformly hardest under every metric, but they consistently expose weaknesses in complete answer-set recovery. These trends remain visible after controlling for multiple observable non-structural factors. Further diagnostic analyses reveal paradigm-specific bottlenecks in evidence acquisition, graph exploration, and logical-form grounding. CLQ thus serves as a diagnostic testbed for developing more structure-aware KGQA systems.

Primary area:
datasets and benchmarks
Keywords:
Knowledge Graph Question Answering, Logical Reasoning, Benchmark, Compositional Reasoning, Complex Query Answering

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_wdoROpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper introduces ComplexLogicalQA (CLQ), a diagnostic benchmark for evaluating KGQA beyond chain-like reasoning. It covers nine EPFO query structures, including intersection, union, and nested compositions, and evaluates representative KGQA methods on these structures. The results show that current systems struggle particularly with nested queries and complete answer-set recovery for union queries.

Critical strengths
  • Meaningful research problem. Existing KGQA benchmarks mainly focus on chain-like multi-hop reasoning, so their results may not fully reflect model ability on more complex logical queries.

  • Clear motivation and simple idea. The need to balance different logical structures is easy to understand, and the benchmark construction pipeline is clearly presented.

  • Well written and well structured. The paper presents the benchmark construction, controlled analysis, and failure diagnosis in a clear order.

Critical weaknesses
  • Limited evaluation beyond Freebase. Freebase is relatively dated and less representative than Wikidata. The 90-question Wikidata pilot in the appendix is a useful first step, but it only evaluates ToG and is too small to establish the generality of the conclusions. Even a small-scale Wikidata evaluation with several baselines would be helpful.

  • Limited coverage of complex logic. The nine EPFO structures are a useful move beyond chain-like reasoning, but they still cover only a limited part of real-world complex KGQA. Such questions often involve multiple interacting constraints. Constructing questions with richer combinations of constraints would provide a stronger test of model reasoning ability.

  • Several relevant baselines are missing. Recent methods such as LPKG, which also studies structured complex reasoning and introduces the CLQA-Wiki benchmark, as well as DoG and CoG, are not included. This weakens the empirical comparison. Adding these baselines, or explaining why they cannot be evaluated on CLQ, would make the claims more convincing.

If these concerns are addressed, I would consider raising my score.

Questions for authors

See above.

Reviewer_kJxTOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper introduces ComplexLogicalQA (CLQ), a structure-balanced diagnostic benchmark covering nine Existential Positive First-Order Logic (EPFO) query structures. It is constructed through structure-constrained subgraph sampling, followed by LLM-based verbalization and multi-stage verification to preserve executable logical validity while improving linguistic diversity. Experiments across four KGQA paradigms reveal that performance degrades as queries move beyond chain-like projections, with the largest and most stable drops on nested compositions.

Critical strengths
  1. It conducts a structural audit of mainstream KGQA benchmarks and quantify their bias toward chain-like query structures. 2.CLQ’s construction is principled and goes beyond naive synthetic generation.
Critical weaknesses
  1. The H@1 metric is underspecified for multi-answer queries, especially unions.
  2. The anchor entities are drawn from existing benchmarks, but the paper does not report overlap with those benchmarks’ test sets.
  3. The matched analysis is useful but the matched subsets are small and the controls are limited.
  4. The evaluation protocols across paradigms are heterogeneous, but the paper does not fully disentangle protocol effects from structural effects.
Questions for authors

Refer to the weaknesses.

Reviewer_YqqUOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper audits 3,000 sampled questions from WebQSP, CWQ, and GrailQA and finds that most are chain-like, with no union queries. It then builds ComplexLogicalQA (CLQ), a Freebase benchmark with 1,000 questions for each of the nine EPFO query types used in complex query answering (1p, 2p, 3p, 2i, 3i, 2u, ip, pi, up). Each instance comes from a sampled subgraph that must match the target structure and in which every branch must change the answer set. GPT-5 turns the subgraph into a question, and symbolic checks plus a Gemini auditor filter the results. The paper evaluates 14 methods from four paradigms: direct LLM reasoning, retrieval, agents, and semantic parsing. Performance drops beyond chain-like queries, most on nested queries, while union queries mainly lower F1. A matched analysis on non-structural factors and per-paradigm failure analyses are offered as support.

Critical strengths
  1. Careful instance construction. Every instance is executed on Freebase, and the branch constraints make it irreducible to a simpler query: each intersection branch must strictly shrink the answer set, and each union branch must add answers the other lacks. This is what makes per-structure scores meaningful, and it is the paper's main asset.

  2. A useful audit and a broad evaluation. The audit puts concrete numbers on a known bias, including zero union queries in 3,000 sampled questions. The evaluation covers 14 methods across four paradigms, so the trends do not rest on one system.

Critical weaknesses
  1. The structure effect is confounded with depth and answer-set size. In Table 4, 3p is a chain query but is about as hard as the nested ones (ToG F1: 3p 0.42; ip 0.40, pi 0.34, up 0.41). Intersections, in turn, are about as easy as 2p (ChatKBQA F1: 2i 0.63, 3i 0.62, 2p 0.65). Difficulty therefore tracks the number of projection hops more than whether a query is chain-like. The matched analysis (Table 5) controls question length, answer-set size, and triple count, but not hop depth, and its Chain side includes the easy 1p queries. For unions, 2u questions have 5.6 answers on average, so high H@1 with low F1 is largely mechanical. Once answer-set size is matched, the Chain–Union gap falls to between −0.02 and 0.13. These are the paper's two headline findings, so this confound drives my rating.

  2. Limited novelty, and the claimed advantage over CQA is not shown. The nine structures are the standard CQA query types, and building questions from sampled graph queries is how GraphQuestions (App. A.2) and GrailQA were constructed. The paper criticizes CQA queries for coming "from graph topology rather than realistic information needs", but CLQ is also sampled from graph topology and then verbalized. Questions such as "What is the hex triplet of the color associated with the team that Lou Seal is the mascot for?" (Table 13) show the same problem. Neither the human evaluation (fluency and logical consistency) nor Table 7 (length, entity mentions, WH-words) tests whether questions reflect real information needs. The remaining findings are expected, and the failure analyses are thin, for example 50 manually inspected TARGA failures per family.

Questions for authors

Please report a depth-matched comparison, such as 2p versus ip, pi, and up, or add hop depth to the matching in Table 5. If nested queries stay clearly harder than 2p at equal depth, weakness 1 would be largely resolved.

Every 95% CI in Table 5 has a half-width of 0.03–0.04 with 161–214 instances per side. If per-instance F1 has a standard deviation near 0.4, as is typical when many instances score 0 or 1, an independent bootstrap would give about ±0.08. What exactly was resampled, and were the two sides treated as paired?

  1. What corpus do BM25 and dense retrieval search over: all of Freebase, or a neighborhood of the anchors? This determines whether their scores are comparable to the other paradigms.

  2. The filtering goes from 15,803 candidates to exactly 9,000, with exactly 1,000 per structure. Was there a per-structure downsampling step, and how did filter rates differ by structure? If the auditor drops more nested or union candidates, the retained set may favor easier instances of those types.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.