Research map / Large language models / Retrieval and knowledge
Is Complex Query Answering Really Complex?
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows that most test queries in standard CQA benchmarks (FB15k-237 and NELL995 based) reduce to simpler link-prediction queries, and introduces harder, balanced benchmarks (FB237-H, NELL-H, ICEWS-H) plus a hybrid solver CQD-Hybrid.
Problem
Standard complex query answering (CQA) benchmarks on incomplete knowledge graphs contain mostly queries whose answers can be reached with only one missing link, so they overstate progress on genuinely multi-hop reasoning.
Approach
Classify each query answer pair by how many links in its reasoning tree are truly missing (partial vs full inference), show most pairs reduce to 1p, and rebuild benchmarks with equal numbers of pairs per reduction level, plus a temporal split (ICEWS) and new 4p/4i query types.
Key results
- Up to 98% of QA pairs in some query types on FB15k-237 and NELL995 reduce to 1p link prediction; full-inference pairs are only 0.1% to 4% (FB) and 0.1% to 6% (NELL).
- On the new benchmarks MRR drops sharply, e.g., QTO 3i MRR on FB237-H is 10.1 versus 54.6 on original FB15k-237.
- CQD-Hybrid, a simple hybrid solver that sets score 1 for training links, matches or beats several neural SoTA models on original benchmarks (wins 9/14 settings).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use training links during inference | CQD on FB15k-237 · 2i1p | MRR: 20.7 -> 24.0 | Helped |
| Use training links during inference | CQD on NELL · 2p | MRR: 22.0 -> 23.8 | Helped |
| Evaluate only full-inference QA pairs, where every reasoning-tree link is missing | CQA models on FB15k-237 · 3p | MRR: 11.8 -> 4.8 | Hurt |
| Evaluate only full-inference QA pairs, where every reasoning-tree link is missing | CQA models on FB15k-237 · 2i1p | MRR: 24.7 -> 8.1 | Hurt |
| Balance partial-inference and full-inference QA pairs in the benchmark | CQA evaluation on FB15k-237-H · 3i | MRR: 54.6 -> 10.1 | Hurt |
| Use a temporal split with past links for training and future links for evaluation | CQA benchmark construction on ICEWS-H · CQA query types | MRR | Hurt |
| Filter union-query answers whose reasoning trees contain non-existing links | CQA models on FB15k-237 · 2u | MRR: 16.2 -> 40.7 | Helped |
| Filter union-query answers whose reasoning trees contain non-existing links | CQA models on NELL · 2u | MRR: 15.4 -> 34.8 | Helped |
| Increase the number of existing intermediate entities | CQD on FB15k-237 and NELL · Queries with intermediate variables | MRR | Hurt |
Surprising findings
- Reported hardness of union queries is largely an artifact of non-existing links in reasoning trees.
- No single model is SoTA across most query types on the new benchmarks.
Limitations
- Only queries with a single target variable are considered.
- Benchmarks rely on existing train/test splits for FB237-H and NELL-H; ICEWS-H split is the only realistic one.
- Full-inference pairs are scarce in original benchmarks, so comparisons on them are noisy.
Experimental setup
Datasets: FB15k-237 NELL995 ICEWS18
Benchmarks: FB237-H NELL-H ICEWS-H FB15k-237 (original) NELL995 (original)
Metrics: mean reciprocal rank (MRR)
Baselines: GNN-QE ULTRAQ CQD ConE CLMPT QTO
Builds on: CQD BetaE QTO GNN-QE ConE
Closest papers by meaning
- A Foundation Model for Zero-shot Logical Query Reasoning (NeurIPS 2024 · similarity 0.90)
- Diagnosing and Addressing Pitfalls in KG-RAG Datasets: Toward More Reliable Benchmarking (NeurIPS 2025 · similarity 0.88)
- Rethinking Complex Queries on Knowledge Graphs with Neural Link Predictors (ICLR 2024 · similarity 0.88)
- Consistent Query Answering over Existential Rules with Open and Closed Predicates (AAAI 2025 · similarity 0.87)
- Bayesian Inference with Complex Knowledge Graph Evidence (AAAI 2024 · similarity 0.86)
- Context-aware Inductive Knowledge Graph Completion with Latent Type Constraints and Subgraph Reasoning (AAAI 2025 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.