acceptodds
Under review as a conference paper at ICLR 2027

Are Hypervectors Enough? Single-Call LLM Reasoning over Knowledge Graphs

Abstract

Recent advances in large language models (LLMs) have enabled strong reasoning over structured and unstructured knowledge. When grounded on knowledge graphs (KGs), however, prevailing pipelines rely on neural encoders to embed and score symbolic paths, incurring heavy computation, high latency, and opaque decisions, which are limitations that hinder faithful, scalable deployment. We propose a lightweight, economical, and transparent KG reasoning framework, PathHD, that replaces neural path scoring with hyperdimensional computing (HDC). PathHD encodes relation paths into block-diagonal GHRR hypervectors, retrieves candidates via fast cosine similarity with Top-K pruning, and performs a single LLM call to produce the final answer with cited supporting paths. Technically, PathHD provides an order-aware, invertible binding operator for path composition, a calibrated similarity for robust retrieval, and a one-shot adjudication step that preserves interpretability while eliminating per-path LLM scoring. Extensive experiments on WebQSP, CWQ, and the GrailQA split show that PathHD (i) achieves comparable or better Hits@1 than strong neural baselines while using one LLM call per query, (ii) reduces end-to-end latency by 40-60% and GPU memory by 3-5 thanks to encoder-free retrieval, and (iii) delivers faithful, path-grounded rationales that improve error diagnosis and controllability. These results demonstrate that HDC is a practical substrate for efficient KG-LLM reasoning, offering a favorable accuracy-efficiency-interpretability trade-off.

Primary area:
foundation or frontier models, including LLMs
Keywords:
Large Language Models, Efficient Reasoning, Knowledge Graphs, Hyperdimensional Computing

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_1jeYOpenReview ↗
Rating
2(+1)
Confidence
4
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes PathHD, a lightweight and encoder-free KG reasoning framework that replaces neural path scoring with hyperdimensional computing and uses only a single LLM call per query. To be specific, PathHD encodes relation paths into block-diagonal GHRR hypervectors, ranks candidates with blockwise cosine similarity and Top-K pruning, and then performs a one-shot LLM adjudication to produce the final answer together with cited supporting paths. Extensive experiments demonstrate the effectiveness of the proposed method.

Critical strengths
  1. This paper focuses on knowledge graph question answering, which is a well-motivated research direction.
  2. This paper proposes GHRR, which is non-commutative and distinguishes same multiset but different order.
  3. This paper conducts extensive experiments and provides theoretical analysis.
Critical weaknesses
  1. This paper may lack some recent state-of-the-art baseline methods for comparison, such as GCR [1], PoG [2], ToG 2 [3]. It would be beneficial to add these methods.
  2. The improvements are modest, as shown in Table 2.
  3. It would be beneficial to provide more detailed explanations for some concepts to improve the readability, such as specify the question-to-relation mapping and plan-selection procedure.
  4. It would be beneficial to polish the figures to improve readability.

[1] Luo, Linhao, et al. "Graph-constrained reasoning: Faithful reasoning on knowledge graphs with large language models." ICML 2025. [2] Chen, Liyi, et al. "Plan-on-graph: Self-correcting adaptive planning of large language model on knowledge graphs." Advances in Neural Information Processing Systems 37 (2024): 37665-37691. [3] Ma, Shengjie, et al. "Think-on-graph 2.0: Deep and faithful large language model reasoning with knowledge-guided retrieval augmented generation." International Conference on Learning Representations. Vol. 2025. 2025.

Questions for authors

Please refer to the Weaknesses section. Main concerns mainly involve the detailed introduction to the proposed method and recent SOTA baseline methods.

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

The paper proposes PathHD for knowledge graph question answering. It symbolically constructs relation plans and candidate paths, encodes them with fixed, order-sensitive GHRR hypervectors, ranks paths using blockwise cosine similarity and calibration, and passes the top-K paths to one final LLM call for answer selection and supporting-path citations. Experiments on WebQSP, CWQ, and GrailQA report competitive accuracy, operator and pruning ablations, and efficiency comparisons.

Critical strengths
  1. The proposed retrieval stage is computationally attractive. Fixed hypervectors and parallel path scoring could reduce dependence on learned path encoders, while non-commutative binding explicitly preserves relation order. This is a useful design direction if its retrieval quality and complete inference cost are established under controlled comparisons.
Critical weaknesses
  1. Limited novelty and accuracy advantage over existing methods. Existing approaches, such as SubgraphRAG (Li et al., ICLR 2025) and KG-CoT (Zhao et al., IJCAI 2024), have already demonstrated knowledge graph question answering with only a single LLM call per question by using lightweight models for knowledge retrieval and reasoning path generation. Under the same single-call setting, the proposed PathHD framework does not demonstrate a clear advantage in either computational cost or answer accuracy over these existing methods.

  2. Unclear initial relation-plan selection mechanism. Section 2.4 and Algorithm 1 describe how candidate relation plans are enumerated, but do not clearly explain how the initial relation plan is selected from a natural-language question without using an LLM or a trained semantic encoder. Since randomly initialized relation hypervectors cannot directly capture semantic alignment between questions and relations, this crucial step requires further clarification.

Questions for authors
  1. How does PathHD map a natural-language question to the initial relation plan without using an LLM or a trained semantic encoder? Section 2.4 and Algorithm 1 describe the enumeration of candidate relation plans but do not clearly explain how the correct plan is selected based on the question's semantics. Please clarify the exact selection mechanism and how it ensures that the retrieved paths are relevant to the question.

  2. Evidence needed to establish the contribution: How does PathHD compare with SubgraphRAG and a lightweight learned or symbolic retriever(KG-COT) using the same final LLM, prompt, and token budget? Please provide measured end-to-end latency, input/output tokens, and peak memory, distinguishing local GPU use from remote API inference and analytical estimates.

  3. As shown in Table 2, PathHD achieves 71.5 Hits@1 and 65.8 F1 on CWQ, underperforming GoG (75.2 Hits@1) and KG-Agent (72.2 Hits@1, 69.8 F1). Why does PathHD fail to demonstrate a clear performance advantage on CWQ despite its strong results on WebQSP and GrailQA? Could the authors analyze whether this limitation is related to the complexity of multi-hop reasoning, relation-plan selection, or candidate path retrieval?

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

This paper introduces PathHD: Path HyperDimensional Retrieval, a knowledge-graph question answering (KGQA) framework that aims to reduce the computational cost of KG- LLM reasoning. The key idea is to replace neural path encoders and per-candidate LLM scoring with hyperdimensional computing (HDC) representations, while retaining a single final LLM call for answer generation. The proposed system follows a Plan —> Encode —> Retrieve —> Reason pipeline. Candidate KG paths are encoded as hypervectors using Generalized Holographic Reduced Representations (GHRR), a non-commutative binding operation designed to preserve relation order and direction. The RQ “Are hypervectors enough for single-call LLM reasoning over knowledge graphs?” The paper operationalizes "enough" as achieving comparable QA performance while reducing latency, GPU memory, and LLM calls. But the question itself doesn't state those criteria. Experiments on WebQSP, CWQ, and GrailQA show that PathHD achieves performance comparable to or better than several recent KG-LLM baselines while reducing inference latency and computational overhead. Additional ablation studies suggest that the proposed GHRR binding operator outperforms alternative HDC composition operators and that a final LLM adjudication step improves over purely vector-based retrieval.

Critical strengths

The paper introduces a distinctive retrieval architecture that replaces neural path encoders with GHRR-based hypervector representations and performs candidate ranking through lightweight vector operations before a single LLM adjudication step. This is a meaningful departure from the dominant trend of increasingly complex neural retrieval pipelines and offers a conceptually elegant alternative for KGQA. The idea is technically interesting, easy to understand, and has the potential to stimulate further research on HDC-based reasoning systems beyond the specific benchmarks considered. A key contribution is demonstrating that an encoder-free retrieval stage combined with a single final LLM call can achieve competitive or state-of-the-art results on WebQSP, CWQ, and GrailQA while reducing latency and computational cost. The paper supports this claim through comparisons across multiple baselines, efficiency analyses, and ablations. Even if some mechanistic claims would benefit from stronger validation, the empirical finding that a substantially simpler retrieval pipeline can remain competitive with multi-step KG- LLM systems is consequential and forms the strongest argument for acceptance.

Critical weaknesses

Most claims are not well adressed. The paper's central motivation is that existing methods suffer from"path-query mismatch" due to order-insensitive encodings and weak directionality, and it claims that GHRR-based hypervectors reduce this mismatch through non-commutative, order-sensitive binding. However, when I look for evidence that specifically supports that claim, I find mostly indirect evidence. The problem is that better QA accuracy ≠ evidence of reduced path-query mismatch. To support that claim directly, I'd expect something like: retrieval recall of the gold path, ranking position of the gold path, percentage of relation-direction errors, percentage of order-confusion errors, a comparison of path-match quality before and after GHRR, examples showing the same candidates ranked differently. None of these appear in the sections available here. The claim that the paper would be solving the problem of per-path LLM evaluation is misleading. Undirectly, the paper claim that PathHD is the first or uniquely important method to eliminate per-path LLM scoring but this would be difficult to defend from the recent KG+LLM literature. Several prior KG+LLM systems already avoid explicitly scoring every candidate path with a separate LLM call. For example, StructGPT uses iterative structured-data retrieval and reasoning rather than per-candidate path scoring (Jiang et al., 2023). RoG ("Reasoning on Graphs") retrieves graph reasoning paths and grounds LLM reasoning on these paths rather than independently evaluating each candidate path via separate LLM calls (Luo et al., 2023). Jiang, J., Zhou, K., Dong, Z., Ye, K., Zhao, W. X., & Wen, J. R. (2023). StructGPT: A General Framework for Large Language Model to Reason over Structured Data. arXiv:2305.09645. Luo, L., Li, Y.-F., Haffari, G., & Pan, S. (2023). Reasoning on Graphs: Faithful and Interpretable Large Language Model Reasoning (RoG). arXiv:2310.01061. Sui, Y., He, Y., Liu, N., He, X., Wang, K., & Hooi, B. (2024). FiDeLiS: Faithful Reasoning in Large Language Model for Knowledge Graph Question Answering. arXiv:2405.13873. A central claim of the paper is that the proposed GHRR-based hyperdimensional representation reduces path-query mismatch by providing more discriminative, order-sensitive path encodings. While the downstream improvements in Hits@1 are encouraging, the paper does not directly quantify the discriminative properties of the proposed representation. The "discriminative power" of an HDC/VSA representation can be quantified several ways, ranging from classical capacity results to retrieval-theoretic measures. It can be done with Separation of similarity distribution, Probability of collision, Retrieval-theoretic view, Path-order discriminability or Mutual information. At present, the paper only shows a downstream Hits@1 improvement. That demonstrates usefulness, but not why. A margin analysis, order-discriminability metric, or collision-rate analysis would provide actual mathematical evidence that the hypervectors have superior discriminative power. The literature review and empirical positioning with respect to the state of the art appear incomplete. More recent systems such as EMBRAG (86.4 Hits@1 on WebQSP), GraphWalker (79.6 Hits@1 on CWQ), and KBQA- o1 (78.5 F1 on GrailQA) are not discussed or included in the experimental comparison. As a result, the paper's claims regarding competitiveness and state-of-the-art performance are difficult to assess in the context of the current literature. HDC remains a potentially valuable research direction still.

EMBRAG: Embedding-based Graph Retrieval-Augmented Generation for Knowledge Base Question Answering, 2026.

GraphWalker: GraphWalker: Multi-hop Trajectory Exploration for Knowledge Graph Question Answering, 2026.

KBQA-o1: KBQA-o1: Test-Time Scaling and Monte Carlo Tree Search for Knowledge Base Question Answering, 2025.

Questions for authors

The paper repeatedly argues that PathHD reduces path-query mismatch through order-sensitive GHRR binding, but the evidence presented is indirect (mainly downstream QA performance and operator ablations). Could the authors provide a direct measurement of mismatch reduction, such as:

  • gold-path retrieval recall,
  • rank of the gold path,
  • relation-direction error rate,
  • path-order confusion rate, or
  • similarity margins between correct and incorrect paths?

A positive answer would substantially strengthen the paper's main motivation. The paper claims that non-commutative GHRR produces more faithful path representations than commutative alternatives. Can the authors provide a representation-level analysis (rather than only Hits@1/F1), e.g.,

  • similarity distributions for positive vs. negative paths,
  • retrieval margins,
  • collision rates,
  • separation between r1 → r2r_1 !\to! r_2r1→r2 and r2 → r1r_2 !\to! r_1r2→r1,
  • or another quantitative measure of discriminative power?

Without such evidence it is difficult to attribute the improvements specifically to reduced path ambiguity. The paper motivates PathHD partly by criticizing per-candidate LLM scoring. However, several prior KG+LLM systems (e.g., RoG, StructGPT, FiDeLiS, KG-Agent) appear to rely on retrieval, planning, verification, or agent-style reasoning rather than explicit path-by-path LLM scoring. Could the authors clarify:

  • Which baselines actually perform per-path LLM evaluation?
  • Which component of those methods is being replaced by PathHD?
  • Whether the novelty claim is "eliminating per-path scoring" or "achieving a single-call retrieval-and-reasoning pipeline"?

This clarification would affect my assessment of novelty.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.