acceptodds
Under review as a conference paper at ICLR 2027

SPARK: Unifying Structure-Aware Path-Prefix-Conditioned Tree Search and Graph-Grounded Generation for Knowledge Graph Question Answering

Abstract

Knowledge Graph Question Answering requires retrieving compact and coherent multi-hop evidence from large-scale knowledge graphs and reasoning over it to produce accurate answers. Existing methods either invoke a large language model (LLM) repeatedly during graph exploration or use lightweight retrievers whose local decisions need not remain consistent with the full reasoning prefix. Furthermore, serializing graph evidence into verbose natural language weakens structural information and increases context length. We propose SPARK, which couples prefix-conditioned evidence retrieval with a graph-grounded generator. Its retriever factorizes each expansion into relation and entity decisions, scores each action jointly with the question and complete prefix, and labels an action as positive only when the extended trajectory remains a prefix of an answer path. For generation, we operationalize Knowledge Graph Language (KGL) as a question-specific interface that compactly encodes retrieved paths using a typed symbol dictionary and ordered symbol sequences; projected entity and relation representations replace the corresponding KGL-symbol embeddings in the LLM input. The two-stage collaborative training strategy further coordinates retrieval and generation through a shared graph encoder. Finally, extensive experiments on WebQSP and CWQ confirm that SPARK achieves significant performance gains compared to the state-of-the-art (SOTA) baselines.

Primary area:
other topics in machine learning (i.e., none of the above)
Keywords:
KGQA, Structure-Aware Path-Prefix-Conditioned Tree Search, Graph-Aware Answer Generation, Knowledge Graph Language Prompting, Large Language Models

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_rq5sOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes SPARK, which addresses knowledge graph question answering by combining structure-aware, path-prefix-conditioned tree search with graph-aware KGL answer generation. It selects relations and then entities while conditioning each expansion on the full reasoning prefix, and uses a shared graph encoder in a two-stage training strategy to coordinate retrieval and generation. Experiments on WebQSP and CWQ report improvements in retrieval and answer quality.

Critical strengths
  1. The hierarchical relation-entity policy evaluates candidate expansions against the complete reasoning trajectory. It offers a principled way to search for coherent multi-hop evidence.

  2. The typed symbols and ordered paths provide a compact representation of retrieved evidence, while projected entity and relation embeddings supply fine-grained graph information to the generator. The two-stage strategy first learns a retrieval policy, then uses a shared graph encoder to coordinate the retrieval and generation objectives.

  3. Experiments on WebQSP and CWQ report improvements in retrieval and answer quality.

Critical weaknesses
  1. The paper presents prefix-consistent supervision as a key contribution, but does not clearly report a direct comparison with edge-level positive labeling based on answer-path membership. The "without full-prefix conditioning" ablation in Table 5 tests a different design choice and does not isolate the effect of the labeling rule.

  2. Table 3 compares full graph-aware KGL with plain text using the same retrieved paths, which supports the effectiveness of the overall interface but does not isolate the contribution of graph-embedding injection. A focused ablation that retains the KGL dictionary and ordered paths while removing the injected entity and relation embeddings would clarify this contribution.

  3. The introduction (lines 51–53) motivates SPARK partly by the latency and computational cost of repeated LLM calls. Table 1 compares retrieval time across retrievers, and Table 3 compares generation time and token counts between gKGL and a plain-text variant. If end-to-end efficiency is a central claim, the paper should additionally compare total latency and LLM-call counts with competing KGQA systems under matched conditions.

  4. The presentation and organization of this paper could be clearer.

(1) Notations in method

  • qq denotes both the natural-language question and its encoded vector;
  • the state (ev,χv)(e_v,\chi_v) repeats eve_v, which is already the final entity in χv\chi_v.

(2) Result presentation

  • Table 2 provides broad method categories, but still mixes closed models, open models of different sizes, and different retrieval paradigms. Grouping results more clearly by generator, scale, and retrieval method would make SPARK’s contribution easier to assess.
Questions for authors

Please refer to Critical Weaknesses.

10 comments

We sincerely thank you for your time and constructive comments. We are excited that you found our paper worthy of publication. Below, we provide detailed replies to your comments to resolve your concerns.

Q1: The paper presents prefix-consistent supervision as a key contribution, but does not clearly report a direct comparison with edge-level positive labeling based on answer-path membership. The "without full-prefix conditioning" ablation in Table 5 tests a different design choice and does not isolate the effect of the labeling rule.

R1: Thank you for this precise comment. We agree that the "w/o full-prefix conditioning" ablation removes the prefix conditioning from the scoring mechanism rather than from the supervision rule, and therefore does not isolate the contribution of prefix-consistent labeling itself.

To address this, we have added a controlled ablation to the revised manuscript (Table 5): a variant that keeps the full prefix-conditioned encoder and the same KL + pairwise-ranking objective, but replaces the prefix-consistent labels with edge-level labels, under which an edge is labeled positive whenever it appears in the supervision subgraph Gq⋆\mathcal{G}_q^{\star} , regardless of whether the extended trajectory remains a prefix of an answer path. This isolates the labeling rule while holding everything else fixed. The results confirm the argument in Section 3.1: this variant incurs the largest degradation among the retrieval ablations, dropping TR/AR from 0.912/0.954 to 0.795/0.824 on WebQSP and from 0.926/0.972 to 0.806/0.837 on CWQ, showing that edge-level labeling distributes positive probability mass over branches that diverge from all answer paths, which is exactly the erroneous supervision that the prefix-consistent rule is designed to remove. The new ablation and its discussion are highlighted in red in the revised manuscript.

Q2: Table 3 compares full graph-aware KGL with plain text using the same retrieved paths, which supports the effectiveness of the overall interface but does not isolate the contribution of graph-embedding injection. A focused ablation that retains the KGL dictionary and ordered paths while removing the injected entity and relation embeddings would clarify this contribution.

R2: We thank the reviewer for this comment. Since the gKGL vs. Plain-text comparison changes both the KGL interface and the graph-embedding injection, we have added a focused ablation to Table 3 that isolates the injection alone: KGL w/o graph injection keeps the symbol dictionary and ordered paths unchanged and only replaces the projected graph representation at each KGL symbol position with the mean of the subword token embeddings of that symbol's surface form, since a KGL symbol spans multiple subword tokens under the LLM tokenizer while occupying a single prompt position. With the generator, retrieved paths, and prompt structure held fixed, this variant drops Hits@1/F1 from 91.22/81.87 to 85.67/74.84 on WebQSP and from 76.50/71.01 to 68.29/66.12 on CWQ, which is even below Plain-text, while it retains the efficiency benefits of the KGL interface (325.75 vs. 401.48 average tokens; 9 vs. 13 seconds). The ablation thus yields a clean decomposition: the KGL interface contributes the efficiency gains, whereas the graph-embedding injection contributes the accuracy gains (5.55/7.03 Hits@1/F1 on WebQSP and 8.21/4.89 on CWQ). The new ablation and its discussion are highlighted in red in the revised manuscript.

Q3: The introduction (lines 51–53) motivates SPARK partly by the latency and computational cost of repeated LLM calls. Table 1 compares retrieval time across retrievers, and Table 3 compares generation time and token counts between gKGL and a plain-text variant. If end-to-end efficiency is a central claim, the paper should additionally compare total latency and LLM-call counts with competing KGQA systems under matched conditions.

R3: Thank you for this comment. We would like to clarify what we claim about efficiency and how the existing tables support it.

SPARK's efficiency stems from an architectural property rather than implementation tuning: the tree-search retriever makes no LLM calls, and generation requires a single LLM forward pass per question, so SPARK performs exactly one LLM call per question end-to-end; the manuscript states that SPARK avoids the repeated LLM-controlled retrieval calls required by iterative agent-based methods (Section 4.2). This contrast is also visible in Table 1, where G-Retriever's retrieval alone takes 672s/1530s on WebQSP/CWQ versus 5s/9s for SPTS. Summing the retrieval and generation stages (Tables 1 and 3) yields an end-to-end latency of roughly 13s (5s retrieval + 8s generation) per question on WebQSP and 17s (9s retrieval + 8s generation) on CWQ on our hardware.

We agree that a fully matched end-to-end comparison across competing systems would strengthen the efficiency evidence. We would like to note that the LLM-call count is the more fundamental measure here: wall-clock latency depends heavily on hardware and implementation, whereas the number of LLM calls is implementation-independent and directly quantifies the overhead that the introduction motivates against. On this measure, SPARK's single call per question contrasts sharply with the repeated calls of iterative agent-based methods. A fully matched wall-clock comparison would require re-implementing and re-running the LLM-agent baselines on our hardware, which exceeds the scope of this revision; we consider it important future work.

Q4: The presentation and organization of this paper could be clearer.

R4: Thank you for this feedback. Although the comment is general, we have taken it as an opportunity to re-examine the manuscript and have made a series of concrete improvements to its presentation and organization:

  1. Terminology. We shortened the framework name and title to a compact form and unified the terminology throughout the paper; the full-name definition in the Introduction now matches the revised title ("Prefix-Conditioned"), and the manuscript consistently describes the retrieval–generation integration as "coordination" rather than "unifying", reflecting the actual design.
  2. Clarity of ablations. We gave every ablation variant a self-descriptive name that states exactly which design is removed (e.g., "w/o prefix-consistent labeling", "KGL") and aligned the accompanying text with the tables (five core SPTS designs now match the table rows).
  3. Organization. The paper now provides a roadmap at the start of Section 3 that maps each subsection to the pipeline stages in Fig. 1, and an interpretability analysis in the appendix (a case study of path selection and an attention-based analysis of graph-embedding influence), with expanded implementation details in the appendix.

We would be happy to address any particular aspect the reviewer finds unclear, and we welcome specific pointers for further polishing.

Q5: Notations in method

  • 1)qq denotes both the natural-language question and its encoded vector;
  • 2)the state (ev,χv)(e_v,\chi_v) repeats eve_v, which is already the final entity in χv\chi_v.

R5: Thank you for the careful notation check. We address the two points as follows.

(1) We use plain qq for the natural-language question and bold q\mathbf{q} for its encoded vector, following the standard convention that plain symbols denote inputs and boldface symbols denote their learned representations (as with EE\mathbf{E}_{\mathcal{E}} and ER\mathbf{E}_{\mathcal{R}}). To make this distinction explicit and remove any ambiguity, we have added a sentence in Section 2 stating this convention at first use.

(2) Writing the search state as (ev,χv)(e_v,\chi_v) is deliberate: although eve_v already appears as the last element of χv\chi_v, keeping it explicit emphasizes that all expansions are taken from the current entity and that χv\chi_v ends with an entity rather than a relation. We have added a clarifying remark in the paper noting that eve_v is the final entity of χv\chi_v.

Both revisions are highlighted in red in the revised manuscript.

Q6: Result presentation

  • Table 2 provides broad method categories, but still mixes closed models, open models of different sizes, and different retrieval paradigms. Grouping results more clearly by generator, scale, and retrieval method would make SPARK’s contribution easier to assess.

R6: Thank you for this suggestion. We have reorganized Table 2 accordingly: within each category, methods are now grouped by generator family and scale with dashed separators, and the SPARK variants are collected in a separate final block for direct same-scale comparison. The revised table is included in the revised manuscript.

Reviewer_NGB9OpenReview ↗
Rating
2
Confidence
4
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes SPARK, a framework for knowledge graph question answering that combines graph retrieval with LLM generation. For retrieval, it uses a tree search that picks relations and entities step by step, guided by the question and the path explored so far. For generation, it feeds the LLM both the retrieved reasoning paths and graph embeddings. The two parts are trained together through a shared graph encoder.

Critical strengths
  1. The proposed tree search conditions each expansion on the complete reasoning prefix, addressing inconsistencies introduced by locally selected graph transitions.
  2. The hierarchical relation-entity search and KGL representation improves inference efficiency.
Critical weaknesses
  1. The paper has an incremental novelty. The core components builds upon established techniques (NuTrea graph encoding, KGL representations, path encoding, and hierarchical retrieval). The contribution feels like a integration and adaptation to KGQA, rather than a conceptual breakthrough.
  2. Although SPARK claims to unify retrieval and generation, the two components are primarily connected through a shared graph encoder. The generation loss does not directly optimize retrieval decisions, making it feel more like a conventional two-stage pipeline.
  3. The paper would benefit from interpretability analysis. It reports gains, but provides limited insight into how its retriever selects different reasoning paths compared to baseline retrievers, and how the graph embeddings influence the LLM's final answers.
Questions for authors

see weaknesses

8 comments

We sincerely thank you for your time and constructive comments. We are excited that you found our paper worthy of publication. Below, we provide detailed replies to your comments to resolve your concerns.

Q1: The paper has an incremental novelty. The core components builds upon established techniques (NuTrea graph encoding, KGL representations, path encoding, and hierarchical retrieval). The contribution feels like a integration and adaptation to KGQA, rather than a conceptual breakthrough.

R1: Thank you for this assessment. We agree that SPARK builds upon established techniques (i.e., NuTrea graph encoding, KGL, path encoding, and tree-search retrieval) and we do not claim a conceptual breakthrough; we view the paper as a systems-level contribution to KGQA. However, we believe the novelty lies in several non-trivial design choices that make the integration work, and each of them is validated by ablations:

  1. Prefix-consistent supervision. Instead of labeling any edge in the supervision subgraph as positive, an action is labeled positive only if the extended trajectory remains a prefix of an answer path, with a KL + pairwise ranking objective. This explicitly addresses a failure mode that prior lightweight retrievers do not handle. Ablations show that removing full-prefix conditioning causes the largest retrieval deterioration (TR/AR drop from 0.912/0.954 to 0.816/0.847 on WebQSP).

  2. Hierarchical action factorization. We factorize the triple-level action space into relation-then-entity decisions, each scored jointly with the question and the complete prefix, which avoids modeling a large flat action space.

  3. Graph-aware KGL for KGQA. We extend KGL (originally designed for KG completion) into a question-specific typed symbol dictionary with ordered path serialization, and inject projected graph representations at the symbol positions. This jointly exploits symbolic semantics, path ordering, and fine-grained graph structure in a compact input, improving Hits@1/F1 by 4.85/5.74 points on WebQSP over plain-text serialization while reducing the input length by 23.5%.

  4. Two-stage collaborative training through a shared graph encoder. This coordinates retrieval and generation at the representation level; ablations (No-RP, Frozen-SE, Unshared-GE) confirm that each design element contributes.

Combined, these mechanisms yield new SOTA F1 on both WebQSP and CWQ. We believe that carefully designed, thoroughly ablated mechanisms that produce consistent and sizable gains over strong baselines constitute a solid contribution, even if incremental in nature.

Q2: Although SPARK claims to unify retrieval and generation, the two components are primarily connected through a shared graph encoder. The generation loss does not directly optimize retrieval decisions, making it feel more like a conventional two-stage pipeline.

R2: Thank you for this precise observation. You are right that the generation loss does not directly backpropagate to the retrieval policy. This is a deliberate design choice rather than an oversight. Because the tree search over a discrete KG is non-differentiable, directly optimizing the retriever from the generation signal would require continuous relaxations, which prior work has found can destabilize optimization. We therefore keep the optimization boundary explicit (as stated in Contribution 3 and Section 3.3) and do not claim end-to-end differentiable unification.

What we do claim is representation-level coordination, which we believe is stronger than a conventional two-stage pipeline in two respects. First, the shared graph encoder receives gradients from both objectives: generation gradients update the very representations that the retriever consumes, and retrieval gradients update those that the generator consumes. Ablations support this: replacing the shared encoder with independent encoders (Unshared-GE) drops F1 from 81.87 to 78.98 on WebQSP and from 71.01 to 68.23 on CWQ, and freezing the encoder in Stage 2 (Frozen-SE) similarly degrades performance. Second, the two objectives are optimized jointly with a tuned weight λ\lambda in Stage 2 rather than in isolated sequential stages; removing the retrieval objective (λ=0\lambda=0) degrades both retrieval and generation metrics, showing that the two objectives genuinely interact.

To avoid overclaiming, we have revised the manuscript to consistently describe the framework as "coordinating" retrieval and generation (e.g., the revised title no longer contains "Unifying") and to explicitly state the optimization boundary. Meanwhile, we adjusted the title of the paper. All the adjusted parts are highlighted in red in the revised manuscript. Directly optimizing the retriever with the generation signal (e.g., via reinforcement learning) is an important direction that we leave for future work.

Q3: The paper would benefit from interpretability analysis. It reports gains, but provides limited insight into how its retriever selects different reasoning paths compared to baseline retrievers, and how the graph embeddings influence the LLM's final answers.

R3: Thank you for this suggestion. We agree that interpretability analysis would strengthen the paper, and we have added a dedicated interpretability section to the revised manuscript (Appendix E) with two analyses, highlighted in red.

First, a case study comparing the paths retrieved by SPTS and baseline retrievers (e.g., SubgraphRAG, QSRAG) on representative multi-hop questions from CWQ, illustrating how prefix-consistent scoring prunes locally plausible but globally inconsistent branches that baselines tend to retain. Second, an analysis of how graph embeddings affect the LLM: since each KGL symbol occupies a single token position, we can inspect the LLM's attention over graph-embedded positions and compare the attention patterns and generated answers with and without graph embeddings, revealing where the LLM relies on the injected graph representations.

Dear Reviewer NGB9:

We sincerely appreciate your careful review and valuable feedback, which have significantly contributed to the improvement of our paper. We hope our response resolves your concerns and to hear your feedback. If you have further questions, we are always here to respond. Thank you again.

Best,

Authors.

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

This paper proposes SPARK, a structure-aware path-prefix-conditioned tree search and graph grounded generation framework for KGQA. SPARK consists of two main stages. The first stage SPTS explores reasoning paths from topic entities to the answer. SPTS first leverage NuTrea as a graph encoder, and obtain the embedding of the query and the embeddings of entities and relations relevant to the query. During exploration, each search step is divided into two decisions, relation selection and neighboring entity selection. For each candidate relation/entity, SPTS concatenates them with the full reasoning paths, serializes them, adds position and type embeddings, and input them into a light-weighted transformer. The hidden representation of the last position is leveraged to score the candidate relation/entity with an MLP. The training signal comes from the shortest paths between the topic entities and the answer node. A candidate action is labeled as positive only if the concatenation of the traversed path and that action remains a prefix of at least one shortest path. In the answer generation (KGL) stage, the retrieved reasoning paths are rewritten into a symbolized format. The prompts for LLM are organized by four parts: the task (system prompt), a symbol dictionary mapping each symbol to its corresponding graph elements, the reasoning paths organized by symbols, and the question to be resolved. Prior to input the sequence to the LLM, the embedding of tokens correspond to each KGL symbol is replaced by a mapped entity/relation embedding. The two stages are trained in a synergistic manner. The first training stage optimizes the graph encoder and retriever, while the second trains the embedding projection layer and finetunes the LLM with LoRA.

Critical strengths
  1. The proposed question-conditioned, structure-aware path encoding effectively captures interactions between entities and relations along a path, as well as the structural knowledge encoded by entities in the knowledge graph.

  2. Compared with ToG’s approach of relying solely on an LLM to select relations and entities, the proposed search policy is expected to be more stable and yield higher retrieval precision.

  3. Compared with GNN-based retrieval methods such as RoG, it achieves higher recall.

  4. The proposed method is evaluated with various types of base LLMs with different numbers of parameters.

  5. The ablation studies are comprehensive.

Critical weaknesses
  1. The full name of the proposed framework is quite long, and difficult to understand. Please consider describing it in a concise and compact way.

  2. The proposed path-prefix supervision addresses structural consistency, in other words, the gold solution path should connect the topic entity to the answer node in a limited number of hops. Nevertheless, such shortest paths may not always reflect the correct solution to the query. Using these paths as the “pseudo golden solution” does not ensure alignment with the semantic meaning inherent in the query.

  3. There is a minor citation format mistake in line 144-145.

  4. The datasets adopted in this manuscript are somewhat outdated. WebQSP and CWQ are built upon the Freebase KG, which has already been deprecated in 2015. The knowledge stored in the Freebase KG may not reflect the reality of today’s world. In case, there are many conflicts between Freebase and the internal knowledge of the LLM obtained from pretraining. Although they have been widely used for a long time, it is questionable whether they are still suitable for evaluating KGQA systems.

  5. The manuscript lacks necessary implementation details for experiment replication.

Questions for authors
  1. How do you deal with the embeddings for reversed relations?

  2. How are the position embeddings and type embeddings initialized?

  3. Did you consider the hierarchies of relationships within the Freebase KG?

  4. How do you deal with the CVT node within the Freebase knowledge graph?

  5. How do you deal with the knowledge conflicts between the outdated Freebase KG and the LLM?

5 comments

We sincerely thank you for your time and constructive comments. We are excited that you found our paper worthy of publication. Below, we provide detailed replies to your comments to resolve your concerns.

Q1: The full name of the proposed framework is quite long, and difficult to understand. Please consider describing it in a concise and compact way.

R1: Thank you for this helpful suggestion. We agree that the original full name was lengthy and hard to parse. After further discussion, we have revised the title to a more concise form:

SPARK: Structure-Aware Prefix-Conditioned Tree Search and Graph-Grounded Generation for KGQA

We have updated the title. All the revised parts are highlighted in red in the revised manuscript.

Q2: The proposed path-prefix supervision addresses structural consistency, in other words, the gold solution path should connect the topic entity to the answer node in a limited number of hops. Nevertheless, such shortest paths may not always reflect the correct solution to the query. Using these paths as the “pseudo golden solution” does not ensure alignment with the semantic meaning inherent in the query.

R2: Thank you for this insightful comment. We agree that shortest paths are a structural prior and may not always coincide with the semantically correct reasoning chain, and that this is an important issue.

We would like to highlight that our supervision scheme is designed to be tolerant of imperfect paths, through two mechanisms. First, we do not commit to a single "pseudo-golden" path: we collect all shortest paths from the seed entities to each answer entity and normalize the labels into a distribution over prefix-consistent expansions (Section 3.1), so the retriever spreads probability mass over all structurally valid branches rather than being forced to replicate any one specific path. Second, the retrieved paths serve only as intermediate evidence: the final answer is produced by the LLM conditioned on the retrieved evidence, which acts as an additional semantic check before answer generation. Empirically, the strong retrieval results (TR/AR of 0.912/0.954 on WebQSP and 0.926/0.972 on CWQ) and the consistent downstream KGQA gains indicate that this scheme is sufficiently reliable in practice.

Nevertheless, we fully agree that supervision quality is a valuable direction to improve: we believe semantically aligned supervision would bring further performance gains, and we plan to investigate it in future work. We have revised the Conclusion of the manuscript accordingly.

Q3: There is a minor citation format mistake in line 144-145.

R3: Thank you for this careful check. We have re-examined lines 144–145 of the LaTeX source: all citations in the manuscript are produced with the standard \cite command under the official ICLR 2027 bibliography style, which renders them consistently in the required author–year format, and we did not find a citation-format error in this region.

Q4: The datasets adopted in this manuscript are somewhat outdated. WebQSP and CWQ are built upon the Freebase KG, which has already been deprecated in 2015. The knowledge stored in the Freebase KG may not reflect the reality of today’s world. In case, there are many conflicts between Freebase and the internal knowledge of the LLM obtained from pretraining. Although they have been widely used for a long time, it is questionable whether they are still suitable for evaluating KGQA systems.

R4: Thank you for raising this important point. We agree that WebQSP and CWQ, which are built on the deprecated Freebase KG, have known limitations: the stored knowledge is dated and may conflict with the internal knowledge of LLMs.

We adopted these datasets for two reasons. First, they remain the de facto standard for KGQA evaluation: to the best of our knowledge, nearly all recent state-of-the-art methods report results on them, and using the same benchmarks is necessary for direct and fair comparison with these systems. Second, although Freebase is no longer maintained, these benchmarks still provide a controlled testbed for the core capabilities studied in this paper, multi-hop evidence retrieval and graph-grounded reasoning over a fixed knowledge base, because the gold answers are defined with respect to the KG rather than current world knowledge.

We would also like to note that the knowledge-conflict issue you raised is one of the motivations of our graph-grounded design: SPARK grounds answer generation in retrieved graph evidence, which reduces reliance on potentially stale parametric knowledge. Nevertheless, we fully agree that evaluation on up-to-date, continuously maintained KGs is a valuable direction, and we plan to extend our evaluation to newer benchmarks in future work.

Q5: The manuscript lacks necessary implementation details for experiment replication.

R5: Thank you for pointing this out. To facilitate replication, we provide our complete implementation (including data preprocessing scripts, training and inference configurations, and evaluation code) in an anonymous repository at https://anonymous.4open.science/r/SPARK-974B/. The code will be made publicly available upon acceptance of the paper. We have added the code link to the abstract of the revised manuscript, highlighted in red. We are also happy to provide any additional implementation details upon request.

Q6: How do you deal with the embeddings for reversed relations?

R6: Thank you for requesting this clarification. In our NuTrea-based graph encoder, we construct forward and reverse relation representations separately. Specifically, we split each relation name into words and encode the original and reversed word sequences using the same BERT encoder, followed by a shared learnable linear projection and attention pooling. The forward representation is used for head-to-tail message passing, whereas the reverse representation is used for tail-to-head propagation. The graph expansion module additionally uses separate learned relation-index embeddings for the two directions, allowing direction-specific behavior even when the textual representations coincide. We will clarify this construction and parameter sharing in the graph-encoding appendix.

Q7: How are the position embeddings and type embeddings initialized?

R7: Thank you for requesting this clarification. Both positional and type embeddings are learnable lookup tables randomly initialized using Xavier uniform initialization. The positional table provides a vector for each supported path position, while the type table contains two vectors corresponding to entities and relations. Each vector has dimension dn=256d_n=256. Both tables are shared across the relation-selection and entity-selection branches and optimized jointly with the path encoder during retriever training. When loading a trained retriever checkpoint, their learned values are restored. We will explicitly document these initialization details in Appendix D of the revised manuscript, with the revisions highlighted in red.

Q8: Did you consider the hierarchies of relationships within the Freebase KG?

R8: Thank you for this question. We did not explicitly model the Freebase relation-type hierarchy; in SPARK, relations are treated as atomic, fine-grained candidates in the search policy. However, hierarchical information is captured implicitly in three ways: (i) relation representations are initialized by encoding their textual descriptions with BERT (Appendix B), and Freebase relation names such as location.country.official_language retain their hierarchical domain paths in the surface form, allowing the encoder to capture relatedness among relations sharing the same domain; (ii) our type embeddings differentiate entity and relation positions along each path; and (iii) the RF-IEF initialization weights relation types by their discriminativeness across the whole KG. We would also like to clarify that the "hierarchical" relation→entity factorization in SPTS refers to decomposing the action space (selecting a reasoning direction first, then a specific graph branch), rather than the schema hierarchy of Freebase.

Empirically, this fine-grained treatment achieves strong retrieval results (TR/AR of 0.912/0.954 on WebQSP and 0.926/0.972 on CWQ), suggesting that the path encoder discriminates relations adequately without explicit hierarchy modeling. We agree that explicitly exploiting the relation hierarchy (e.g., hierarchical relation representations or parameter sharing among sibling relations) is a promising direction for further improvement, which we leave for future work.

Q9: How do you deal with the CVT node within the Freebase knowledge graph?

R9: We do not apply special preprocessing to CVT (compound value type) nodes; they are treated as ordinary entities throughout the pipeline. Specifically, the tree search expands through a CVT node in the same way as through any other entity: the retriever first selects the relation pointing to the CVT node, the CVT node then becomes the current search state, and subsequent relation–entity expansions traverse its value relations. In this way, n-ary facts are naturally retrieved as multi-hop chains through the CVT node, and the maximum search depth (D=4D=4 on CWQ) accommodates the additional hop introduced by the CVT structure.

Two design choices further support this treatment. First, the supervision paths are computed as shortest paths on the full KG (including CVT nodes), and our prefix-consistent labeling applies to intermediate CVT states exactly as to ordinary entities, so supervision covers CVT-mediated facts without any special handling. Second, since CVT nodes lack meaningful surface names, our graph encoder (NuTrea) initializes entity representations from neighboring relations via RF-IEF (Appendix B), which endows CVT nodes with informative embeddings derived from their surrounding structure. Empirically, CWQ contains many CVT-mediated questions, and SPARK achieves an AR of 0.972 on CWQ, indicating that CVT-mediated answers are well covered by the retrieved evidence.

Q10: How do you deal with the knowledge conflicts between the outdated Freebase KG and the LLM?

R10: Handling the conflict between the (potentially outdated) KG and the LLM's parametric knowledge is one of the motivations of our graph-grounded design, and we address it through three mechanisms.

First, the generator is conditioned on retrieved KG evidence: the task instruction in the generation prompt explicitly directs the LLM to infer the answer from the provided symbol dictionary and reasoning paths, rather than from its own memory (Appendix C). Second, the KGL interface anchors generation to the graph: at each KGL symbol position, the ordinary token embedding is replaced by a projected graph representation learned by NuTrea, so the LLM directly consumes graph-derived evidence representations. Third, the generator is trained with teacher forcing on canonical answer texts derived from the gold answers of the KG, which teaches it to follow the retrieved evidence instead of parametric knowledge.

Empirically, this grounding is effective: the LLM-only baselines that rely on parametric knowledge (GPT-4o and GPT-4o+CoT) achieve only 61.80/43.60 and 74.12/64.25 Hits@1/F1 on WebQSP, far below SPARK's 91.99/83.56, which is consistent with the knowledge-conflict concern you raised and shows that grounding the LLM in retrieved KG evidence largely resolves it. We acknowledge that conflicts may persist when the evidence is incompletely retrieved, and we regard further improving retrieval robustness as an important direction for future work.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.