How Benchmark Graph Construction Shapes Multi-Hop KG Navigation: A Controlled Audit of PathQuestion and PathQuestion-Large

Abstract

Multi-hop knowledge-graph question answering (KGQA) benchmarks are often treated as fixed language-and-reasoning tasks, but for navigation-based methods, difficulty also depends on the graph in which those tasks are instantiated. This makes graph construction a consequential but often entangled part of the navigation task. To isolate this effect, we audit PathQuestion (PQ) and PathQuestion-Large (PQL) as graph-navigation benchmarks under a controlled intervention: we hold questions, topic entities, released answers, released path annotations, and family-level splits fixed while replacing each released task-filtered graph with the larger source KG distributed with the benchmark. Source restoration expands the effective navigation search space and graph-consistent answer and path multiplicity while sharply reducing unguided reachability to released answers. We evaluate whether these structural changes persist across navigation policies using structural references, frozen small-language-model navigation policies, and trained MINERVA policies. Across both frozen and trained policies, restoration substantially reduces released-answer accuracy and trajectory fidelity, while graph-consistent evaluation recovers only part of the loss. These results show that benchmark graph construction is part of the navigation task specification rather than merely an implementation detail and can materially shape measured behavior even when the released QA task is held fixed.

The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.

More in Computation & Language / NLP

• arXiv preprint · 19 October 2026

  Cognitive Maps in Large Language Models

  Albert Qin, Jonathan Cohen and Gautam Reddy
• arXiv preprint · 20 October 2026

  The Router Already Knows

  Andrew Bistras and Marty Johnson
• arXiv preprint · 19 October 2026

  Text Dominance in Paralinguistic Conflict: Tracing Suppression Through Audio LLM Circuits

  Ankur Banerjee, Vishnu Guntakala, Danity Pike and 3 others
• arXiv preprint · 20 October 2026

  Harness Self-Evolution for Long-Horizon Terminal Agents

  Ruhan Wang, Yucheng Shi, Zongxia Li and 6 others
• arXiv preprint · 19 October 2026

  Curriculum Learning Teaches LLMs Long-Horizon Implicit Reasoning, Up To A Limit

  Jimson Huang, Maxwell Nickell, Ruowang Zhang and 1 other

All new papers in Computation & Language / NLP