Skip to content

Agent Steerable Search for Knowledge Graph Question Answering

Conference: ACL 2025
Area: Graph Learning
Keywords: Knowledge Graph Question Answering, Steerable Search, Agent, Graph Search Strategy, Reasoning Path

TL;DR

This paper proposes an agent-based steerable knowledge graph search framework, enabling LLM agents to dynamically adjust graph search strategies (such as search depth, direction, and pruning rules) based on question types and reasoning requirements, achieving fine-grained control over the knowledge graph question answering process.

Background & Motivation

Background: Knowledge Graph Question Answering (KGQA) requires systems to retrieve relevant triples from a knowledge graph to answer natural language questions. Current methods are primarily divided into two categories: retrieval-based methods (retrieving subgraphs first, then reasoning) and reasoning-based methods (answering after multi-hop traversal on the graph). Recent LLM-based agent methods allow agents to interact with knowledge graphs, completing QA through multi-step search and reasoning.

Limitations of Prior Work: Existing agent-based KGQA methods typically employ fixed search strategies—either breadth-first or depth-first—with search depths and pruning thresholds serving as preset global parameters. This leads to redundant search and noise introduction for simple single-hop questions, while under-searching and missing critical information for complex questions requiring deep reasoning.

Key Challenge: Different types of questions require vastly different search strategies: factual queries require precise, short-path searches; comparative questions require broad, multi-path searches; and reasoning chain questions require deep, directed searches. A single strategy cannot simultaneously optimize across all question types.

Goal: To empower LLM agents with the capability to dynamically adjust knowledge graph search strategies, including search direction, depth, width, and pruning rules, enabling the search process to adaptively adjust according to specific questions.

Key Insight: To treat knowledge graph search as a parameterizable process, where search parameters (depth, width, direction, etc.) act as a "steering wheel" controlled by the agent, which configures these parameters based on its comprehension of the question.

Core Idea: To replace fixed search strategies with agent-steered parametric search strategies, allowing the agent to dynamically generate search plans based on question semantics.

Method

Overall Architecture

Given a natural language question, the question analysis module first extracts entities and determines the question type and complexity. Then, the agent generates a search plan (containing parameter configurations of the search strategy) based on the analysis results, and the search executor retrieves relevant subgraphs on the knowledge graph according to the plan. The retrieved subgraphs are integrated and fed into the reasoning module to generate the final answer. The entire process can be iterative—if the initial search results are insufficient, the agent can adjust the strategy and search again.

Key Designs

  1. Search Plan Generator:

    • Function: Generates parametric search plans based on question characteristics.
    • Mechanism: Defines the search plan as a structured set of parameters, including: search mode (BFS/DFS/hybrid), maximum depth \(d\), maximum expansion width per layer \(w\), relation filters (specifying preferred relation types for search), and relevance pruning threshold \(\theta\). The agent sets these parameters by analyzing the semantic structure of the question (e.g., how many entities are involved, how many reasoning hops are needed, whether it contains constraints).
    • Design Motivation: To avoid "one-size-fits-all" search strategies, ensuring each question receives the most appropriate search configuration.

  2. Adaptive Search Executor:

    • Function: Executes the search on the knowledge graph according to the plan and collects relevant triples.
    • Mechanism: The executor traverses the graph according to the search mode specified by the agent. At each node, it decides whether to expand in that direction based on the relation filter and the semantic relevance threshold. Semantic relevance is evaluated via a quick judgment by the LLM on "whether this relation is relevant to the original question". A priority queue is maintained during the search to prioritize path exploration most relevant to the question.
    • Design Motivation: To balance efficiency and recall by combining structured search with semantic guidance.

  3. Iterative Refinement:

    • Function: Allows the agent to adjust strategies and re-search when initial search results are unsatisfactory.
    • Mechanism: The agent evaluates the adequacy of the search results—if it finds key information missing (e.g., specific attributes of an entity are not covered), it can generate a supplementary search plan, increasing the search depth or width in the relevant direction. The maximum number of iterations is controlled by a hyperparameter to prevent infinite loops.
    • Design Motivation: A single search is rarely perfect; iterative refinement gives the system an opportunity to retrieve missed information.

Loss & Training

A few-shot learning approach is adopted to fine-tune the agent's plan generation capability on a small number of annotated question-search plan pairs. The search executor does not require training and is a rule-based graph traversal engine. The overall system uses the accuracy of the final answer as a feedback signal to fine-tune the agent's strategy selection preference using DPO.

Key Experimental Results

Main Results

Dataset Metric Agent Steerable ToG KG-Agent StructGPT Gain
WebQSP Hits@1 78.6 74.2 72.8 70.3 +4.4
CWQ Hits@1 65.3 60.1 58.7 55.9 +5.2
GrailQA Hits@1 71.8 67.5 65.2 63.6 +4.3
SimpleQA Hits@1 89.2 88.1 87.5 86.3 +1.1

Ablation Study

Configuration CWQ(Hits@1) Average Search Steps Description
Full model 65.3 4.2 Full steerable search
Fixed BFS 60.8 6.7 BFS for all questions
Fixed DFS 58.3 5.1 DFS for all questions
No relation filtering 62.1 7.3 No filtering of relation types
No iterative refinement 63.0 3.8 Search only once

Key Findings

  • The search plan generator makes the largest contribution; the strategy of dynamically switching between BFS/DFS outperforms any fixed strategy by more than 5 points.
  • The relation filter is highly effective in reducing search steps (4.2 vs. 7.3) while also improving accuracy by 3.2 points, indicating that removing noisy relations is crucial.
  • The advantage is minor on simple questions (+1.1) but significant on complex multi-hop questions (+5.2), validating that steerable search is more valuable for complex reasoning.
  • The iterative refinement mechanism brings an improvement of approximately 2.3 points, with 72% of the refinements occurring when the initial search depth is insufficient.

Highlights & Insights

  • Parameterizing the search strategy and handing control over to the agent is an elegant design, automating "search hyperparameter tuning" into the agent's decision-making process. This approach can be transferred to any scenario requiring search over structured data.
  • The combination of semantically guided pruning and structured search achieves a win-win in both accuracy and efficiency.

Limitations & Future Work

  • Search plan generation depends on the LLM's question comprehension ability; it may generate inappropriate plans for semantically ambiguous questions.
  • The parameter space of the search strategy is currently discrete. Future work could explore continuous parameterization for finer control.
  • Currently, it only supports typical knowledge graphs like Freebase/Wikidata, and its generalizability to domain-specific KGs (such as biomedical KGs) has not been verified.
  • The maximum number of iterative search rounds is a hyperparameter; automatically determining when to stop searching remains an open problem.
  • The search strategy learning can be combined with stronger graph neural networks, utilizing graph structural information to assist search decisions.
  • Currently, it only supports Freebase/Wikidata, and its generalizability to specific domains of KGs (such as biomedical KGs) has not been verified. Differences in relation types and graph structures across various domains might require different search strategies.
  • vs ToG (Think-on-Graph): ToG uses a fixed graph reasoning workflow, whereas ours allows the agent to dynamically control search parameters, offering higher flexibility.
  • vs KG-Agent: KG-Agent provides graph search tools but the search strategy is preset, whereas ours hands the strategy itself over to the agent to decide.
  • vs StructGPT: StructGPT accesses KGs via interface calls but does not control the search process, whereas ours achieves steerability at the search level.

Rating

  • Novelty: ⭐⭐⭐⭐ The idea of parameterizing search strategies is novel
  • Experimental Thoroughness: ⭐⭐⭐⭐ Multiple KGQA benchmarks
  • Writing Quality: ⭐⭐⭐⭐ The methodology is clearly described
  • Value: ⭐⭐⭐⭐ Direct inspiration for the design of KGQA systems