Technical Summary: Bounded Path Context in LLM-Based KGQA

Problem Statement

In LLM-based Knowledge Graph Question Answering (KGQA), systems typically delegate graph traversal to a language model (LLM) controller. At each step of the search, the controller prompts the LLM to select the next relation to follow. A prevalent design pattern involves serializing the complete partial path (the entire history of entities and relations traversed so far) into every routing prompt.

The authors argue this is an untested default assumption. While the graph controller maintains the full path as an exact symbolic state in memory, repeatedly feeding this text into the LLM prompt serves two conflated roles:

1. Control Context: Exact bookkeeping for the system (which the code already possesses).
2. Explanation Context: Optional disambiguating text for the LLM.

This practice incurs significant costs: it consumes KV-cache memory, limits local batching, increases latency, and forces the model to attend to potentially stale or irrelevant historical information that competes with current relation candidates. The core question is whether the complete symbolic path is necessary for the LLM's local routing decision, or if a bounded suffix suffices.

Methodology: Bounded Path Context (BPC)

The paper introduces Bounded Path Context (BPC), a prompt-interface intervention that decouples the controller's symbolic state from the text visible to the LLM during relation selection.

Core Mechanism

• Symbolic State: The controller retains the full path $p_t = (e_0, r_1, e_1, \dots, r_t, e_t)$ in memory for answer extraction and auditing.
• Visible History: The prompt exposed to the LLM for relation selection includes the question, the current entity, the outgoing relation candidates, and only the last $K$ hops of the path.
  • $K=0$: No previous hops are shown.
  • $K=1$: Only the immediate previous hop is shown.
  • $K=\text{full}$: The complete path is serialized (the conventional baseline).

Experimental Setup

• Datasets: WebQSP and ComplexWebQuestions (CWQ), using RoG-aligned local graph neighborhoods.
• Models: Qwen3.5-9B-AWQ and Qwen3.5-4B-AWQ, served locally via vLLM.
• Controls: The study fixes graph neighborhoods, beam width, search depth, relation caps, and decoding temperature. The only variable is the visible path history length ($K$).
• Metrics: Answer-set F1, Hits@1, input token counts, and wall-clock time.

Key Results

1. Performance vs. Full History

Contrary to the intuition that more context is better, bounded histories match or exceed full-history prompting:

• Qwen3.5-9B:
  • WebQSP: $K=1$ achieved the highest F1 (0.487), outperforming full history (0.472). $K=0$ was nearly tied (0.485).
  • CWQ: $K=0$ achieved the highest F1 (0.287), outperforming full history (0.274).
• Efficiency: Bounded contexts significantly reduced input tokens (up to 12.1% reduction on CWQ) and, in some cases, reduced wall-clock time.

2. Model Size Interaction

The optimal $K$ depends on model capacity:

• 9B Scale: Bounded histories ($K=0$ or $K=1$) generally outperformed full history.
• 4B Scale: Full history performed better than $K=0$, suggesting smaller models benefit from some path context. However, $K=1$ remained the strongest setting across both datasets for the 4B model, outperforming both $K=0$ and full history.

3. Error Analysis

• Stability: 71–84% of examples produced identical final F1 scores regardless of history length, indicating that most routing decisions are robust to context truncation.
• Failure Modes:
  • Full History Wins: Often occurred when a previous hop was necessary to disambiguate the current entity.
  • Bounded Wins: Often occurred when full history introduced "stale" entity names or irrelevant earlier relation labels that distracted the model.
• Random Controls: Random relation selection scored significantly lower, confirming that the gains are due to learned relation selection and graph grounding, not merely reduced noise.

Key Contributions

1. Interface Decoupling: Defined BPC as a method to separate deterministic symbolic state (controller memory) from model-visible communication (prompt text).
2. Empirical Evidence: Demonstrated that full-path serialization is not a uniformly superior default. On WebQSP and CWQ, bounded histories ($K=0$ or $K=1$) achieved higher F1 scores with fewer tokens.
3. Model-Size Nuance: Identified that while smaller models (4B) benefit from some context, a single visible hop ($K=1$) is a consistently competitive setting across different model scales.
4. Diagnostic Controls: Validated that the results are not artifacts of graph access or random chance, but stem from the specific interaction between path length and LLM attention.

Significance and Claims

The paper claims that path serialization length should be treated as a tunable interface variable rather than a fixed default assumption in LLM-based graph controllers.

• System Design: BPC allows system designers to reduce input token load and latency without sacrificing (and often improving) accuracy.
• Theoretical Insight: The results suggest that for local routing decisions, the "question + current entity + relation candidates" encode strong local signals. Older hops can be helpful for disambiguation but often act as distractions by introducing irrelevant surface forms.
• Auditability: By keeping the full path in symbolic memory, BPC maintains the ability to audit evidence and extract answers from complete paths, even if the routing prompts are truncated.

The authors conclude that while full history is not the highest-F1 setting in their runs, the specific boundary ($K=1$) offers a robust, efficient default that balances local disambiguation with prompt economy.