Autonomous Knowledge Graph Exploration with Adaptive Breadth-Depth Retrieval

• URL: http://arxiv.org/abs/2601.13969v1
• Date: Tue, 20 Jan 2026 13:46:37 GMT
• Title: Autonomous Knowledge Graph Exploration with Adaptive Breadth-Depth Retrieval
• Abstract summary: ARK: Adaptive Retriever of Knowledge, gives a language model control over this breadth-depth tradeoff.<n>ARK alternates between breadth-oriented discovery and depth-oriented expansion without depending on a fragile seed selection.<n>ARK reaches 59.1% average Hit@1 and 67.4 average MRR, improving average Hit@1 by up to 31.4% and average MRR by up to 28.0% over retrieval-based and agentic training-free methods.
• Score: 26.815539094904278
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Retrieving evidence for language model queries from knowledge graphs requires balancing broad search across the graph with multi-hop traversal to follow relational links. Similarity-based retrievers provide coverage but remain shallow, whereas traversal-based methods rely on selecting seed nodes to start exploration, which can fail when queries span multiple entities and relations. We introduce ARK: Adaptive Retriever of Knowledge, an agentic KG retriever that gives a language model control over this breadth-depth tradeoff using a two-operation toolset: global lexical search over node descriptors and one-hop neighborhood exploration that composes into multi-hop traversal. ARK alternates between breadth-oriented discovery and depth-oriented expansion without depending on a fragile seed selection, a pre-set hop depth, or requiring retrieval training. ARK adapts tool use to queries, using global search for language-heavy queries and neighborhood exploration for relation-heavy queries. On STaRK, ARK reaches 59.1% average Hit@1 and 67.4 average MRR, improving average Hit@1 by up to 31.4% and average MRR by up to 28.0% over retrieval-based and agentic training-free methods. Finally, we distill ARK's tool-use trajectories from a large teacher into an 8B model via label-free imitation, improving Hit@1 by +7.0, +26.6, and +13.5 absolute points over the base 8B model on AMAZON, MAG, and PRIME datasets, respectively, while retaining up to 98.5% of the teacher's Hit@1 rate.

Related papers

• CoEvoKG: Co-Evolving Knowledge Graphs with Self-Evolving Search Agents [24.448485225924106]
  CoEvoKG turns a knowledge graph into a source of verifiable training tasks and a persistent evidence memory for agent evolution.<n>When a search succeeds, CoEvoKG verifies and deduplicates the retrieved evidence, then writes it back to the corresponding graph nodes and edges.
  arXiv  Detail & Related papers  (2026-08-03T08:39:16Z)
• SLMs as Multi-Agent Routers: A Progressive SFT and Reinforcement Learning Approach [35.31208793946578]
  Specialised retrieval agents typically surface higher quality results than general-purpose search.<n>Current approaches route queries based on inferred topic or intent, but it does not incorporate signal from retrieved content.<n>We address this by training a small language model via supervised fine-tuning followed by reinforcement learning.
  arXiv  Detail & Related papers  (2026-07-15T11:11:39Z)
• STAR: Semantic-Tuned and Tail-Adaptive Retriever for Graph-Augmented Generation [69.66045538889777]
  We propose STAR, a semantic-tuned and tail-adaptive retriever for GraphRAG.<n> STAR consistently outperforms baselines, achieving average retrieval performance gains of 1.8%.
  arXiv  Detail & Related papers  (2026-04-11T10:16:51Z)
• Can Small Language Models Use What They Retrieve? An Empirical Study of Retrieval Utilization Across Model Scale [0.0]
  We evaluate five model sizes from 360M to 8B across three architecture families SmolLM2 Qwen2.5 and Llama 3.1.<n>We find that for models below 7B parameters the main limitation of RAG is context utilization rather than retrieval quality.
  arXiv  Detail & Related papers  (2026-03-12T03:59:42Z)
• AgentIR: Reasoning-Aware Retrieval for Deep Research Agents [76.29382561831105]
  Deep Research agents generate explicit natural language reasoning before each search call.<n> Reasoning-Aware Retrieval embeds the agent's reasoning trace alongside its query.<n>DR- Synth generates Deep Research retriever training data from standard QA datasets.<n>AgentIR-4B achieves 68% accuracy with the open-weight agent Tongyi-DeepResearch.
  arXiv  Detail & Related papers  (2026-03-04T18:47:26Z)
• Think Before You Retrieve: Learning Test-Time Adaptive Search with Small Language Models [28.80331720382804]
  We introduce Orion, a training framework that enables compact models to perform iterative retrieval through learned search strategies.<n>Orion combines synthetic trajectory generation and supervised fine-tuning to encourage diverse exploration patterns in models.<n>Despite using only 3% of the training data available, our 1.2B model achieves 77.6% success on SciFact.
  arXiv  Detail & Related papers  (2025-11-10T19:49:55Z)
• MemSearcher: Training LLMs to Reason, Search and Manage Memory via End-to-End Reinforcement Learning [73.27233666920618]
  We propose MemSearcher, an agent workflow that iteratively maintains a compact memory and combines the current turn with it.<n>At each turn, MemSearcher fuses the user's question with the memory to generate reasoning traces, perform search actions, and update memory to retain only information essential for solving the task.<n>We introduce multi-context GRPO, an end-to-end RL framework that jointly optimize reasoning, search strategies, and memory management of MemSearcher Agents.
  arXiv  Detail & Related papers  (2025-11-04T18:27:39Z)
• Search-on-Graph: Iterative Informed Navigation for Large Language Model Reasoning on Knowledge Graphs [26.0585592684229]
  Large language models (LLMs) have demonstrated impressive reasoning abilities yet remain unreliable on knowledge-intensive, multi-hop questions.<n>We propose Search-on-Graph (SoG), a simple yet effective framework that enables LLMs to perform iterative informed graph navigation.<n>We demonstrate particularly strong gains on Wikidata benchmarks (+16% improvement over previous best methods) alongside consistent improvements on Freebase benchmarks.
  arXiv  Detail & Related papers  (2025-10-09T21:20:16Z)
• Optimized Text Embedding Models and Benchmarks for Amharic Passage Retrieval [49.1574468325115]
  We introduce Amharic-specific dense retrieval models based on pre-trained Amharic BERT and RoBERTa backbones.<n>Our proposed RoBERTa-Base-Amharic-Embed model (110M parameters) achieves a 17.6% relative improvement in MRR@10.<n>More compact variants, such as RoBERTa-Medium-Amharic-Embed (42M) remain competitive while being over 13x smaller.
  arXiv  Detail & Related papers  (2025-05-25T23:06:20Z)
• Tool-Augmented Reward Modeling [58.381678612409]
  We propose a tool-augmented preference modeling approach, named Themis, to address limitations by empowering RMs with access to external environments. Our study delves into the integration of external tools into RMs, enabling them to interact with diverse external sources. In human evaluations, RLHF trained with Themis attains an average win rate of 32% when compared to baselines.
  arXiv  Detail & Related papers  (2023-10-02T09:47:40Z)
• UniKGQA: Unified Retrieval and Reasoning for Solving Multi-hop Question Answering Over Knowledge Graph [89.98762327725112]
  Multi-hop Question Answering over Knowledge Graph(KGQA) aims to find the answer entities that are multiple hops away from the topic entities mentioned in a natural language question. We propose UniKGQA, a novel approach for multi-hop KGQA task, by unifying retrieval and reasoning in both model architecture and parameter learning.
  arXiv  Detail & Related papers  (2022-12-02T04:08:09Z)
• IRLI: Iterative Re-partitioning for Learning to Index [104.72641345738425]
  Methods have to trade between obtaining high accuracy while maintaining load balance and scalability in distributed settings. We propose a novel approach called IRLI, which iteratively partitions the items by learning the relevant buckets directly from the query-item relevance data. We mathematically show that IRLI retrieves the correct item with high probability under very natural assumptions and provides superior load balancing.
  arXiv  Detail & Related papers  (2021-03-17T23:13:25Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.