Autonomous Knowledge Graph Exploration with Adaptive Breadth-Depth Retrieval

Joaquín Polonuer, Lucas Vittor, Iñaki Arango, Ayush Noori, David A. Clifton, Luciano Del Corro, Marinka Zitnik · 2026

Read Autonomous Knowledge Graph Exploration with Adaptive Breadth-Depth Retrieval by Joaquín Polonuer, Lucas Vittor, Iñaki Arango, Ayush Noori, David A. Clifton, Luciano Del Corro, Marinka Zitnik (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-13969.txt.

Introduction

Joaquín Polonuer and co-authors teach language models to search knowledge graphs in a smarter way in 2026. Retrieving evidence from a knowledge graph needs breadth and depth at once. Similarity-based retrievers give coverage but stay shallow. Traversal methods follow links, but must pick seed nodes to start from, which can fail.

Queries that span many entities and relations expose that flaw. Their method explores the graph with adaptive breadth-depth retrieval. The search adjusts how wide and how deep it goes as it learns. Better graph search could ground model answers in firm, linked facts.

Catalog record

CREATORJoaquín Polonuer, Lucas Vittor, Iñaki Arango, Ayush Noori, David A. Clifton, Luciano Del Corro, Marinka Zitnik
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE45 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2601-13969

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Autonomous Knowledge Graph Exploration with Adaptive Breadth-Depth Retrieval Joaquín Polonuer, Lucas Vittor, Iñaki Arango, Ayush Noori, David A. Clifton, Luciano Del Corro, Marinka Zitnik 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. Figure 1: Overview of Adaptive Retriever of Knowledge . ARK interacts with a KG through a minimal two-tool interface: (a) For text-dominant queries, ARK emphasizes breadth by issuing Global Search to retrieve a broad set of candidates. (b) For relation-focused queries, ARK applies Neighborhood Exploration starting from a previously retrieved node (in this case, a drug) and expanding to related entities, enabling targeted relational retrieval. (c) For relation-dominant queries, ARK performs multi-hop retrieval by alternating Global Search and Neighborhood Exploration : it retrieves an initial node (e.g., an article), expands to related entities (e.g., co-authors), and continues expanding and filtering (e.g., papers connected to each author that match query keywords) to recover an ordered set of relevant evidence. 1 Introduction Large language models rely on knowledge retrieval to ground and align their outputs in external evidence Ren et al. 2025 ; Wang et al. 2025a ; Xia et al. 2025a ; Zhang et al. 2024 , from retrieval-augmented generation (RAG) to systems and memory modules that operate over semi-structured knowledge bases (SKB) that mix text with relational information Lewis et al. 2020 ; Guu et al. 2020 ; Karpukhin et al. 2020 ; Izacard and Grave 2021 ; Mavromatis and Karypis 2025 ; Chen et al. 2025 ; Li et al. 2025c . Knowledge graphs (KGs) are a natural data representation for this setting because they organize evidence around entities and typed edges, support reuse across queries, and enforce relational constraints that a flat text index cannot express. This has motivated graph-aware retrievers and graph-grounded generation methods, including graph-based RAG and SKB retrievers that combine text and relational data Edge et al. 2025 ; Zhu et al. 2025b ; Xia et al. 2025b ; Yao et al. 2025 ; Jeong et al. 2025 . Retrieving evidence from KGs is challenging because it requires coordinating two competing search modes Wu et al. 2024b ; Lee et al. 2025 ; Zhu et al. 2025a . Many queries require breadth : they mention multiple entities or loosely connected concepts, so the retriever must cover the graph broadly to reach the right region. Other queries require depth : the supporting evidence only appears after following specific multi-hop relational paths. Similarity-based retrievers provide global coverage but often remain shallow and underuse relational structure, whereas traversal-based methods can be brittle because they must choose seed entities to start exploration; when seeds are incomplete or ambiguous, the search stays local and misses evidence elsewhere. Existing work tackles these breadth-depth requirements in isolation rather than jointly Ko et al. 2025 ; Ma et al. 2025 ; Wang et al. 2025b . Structure-aware retrievers extend text-based retrieval with relational structure, for example, by learning node embeddings that aggregate information from nearby neighbors or by generating candidates using a local graph neighborhood before ranking them Lee et al. 2025 ; Zhu et al. 2025b ; Lei et al. 2025 . These methods capture local structure, but they typically encode a fixed neighborhood around each node, so deeper multi-hop queries require expanding the encoded context or stacking additional message-passing and retrieval stages, which increases complexity and cost Wan et al. 2025 ; Hu et al. 2025a ; Verma et al. 2024 . By contrast, traversal-based approaches perform multi-hop exploration, but they depend on identifying a small set of seed entities from which exploration begins Markowitz et al. 2024 ; Sun et al. 2024 . When seeds are incomplete or ambiguous, exploration stays local and misses relevant information elsewhere in the graph Liu et al. 2025 ; Ma et al. 2025 . Many systems also rely on task- or graph-specific training to learn traversal or scoring policies, which limits transfer across domains and graph schemas Li et al. 2025a ; Lei et al. 2025 ; Wu et al. 2024a ; Yu et al. 2025 . As a result, existing methods struggle to combine global search with targeted relational reasoning for adaptive retrieval. Present work. We introduce ARK : Adaptive Retriever of Knowledge , an agentic KG retriever that gives a language model control over evidence discovery using a minimal set of tools for global lexical search and neighborhood exploration Yao et al. 2023 ; Schick et al. 2023 . ARK does not require selecting seed entities to start exploration or establishing a maximum hop depth in advance; instead, the model alternates between broad global search and targeted multi-hop traversal based on the query and what it has retrieved so far. We evaluate ARK on the heterogeneous graphs in the STaRK retrieval benchmark and show consistent gains across all settings. We further study compute-accuracy tradeoffs by varying the tool-call budget and the number of parallel agents, and we distill ARK ’s tool-use policy into an 8B model via label-free trajectory imitation, preserving most of the performance of teacher model at substantially lower inference cost Kang et al. 2025 . Our contributions are threefold. (i) We introduce Adaptive Retriever of Knowledge , a training-free retrieval framework that equips language models with a minimal but expressive tool interface for adaptive retrieval from KGs. (ii) We show that ARK balances breadth-oriented retrieval with depth-oriented multi-hop traversal without task- or graph-specific training, achieving strong performance on STaRK. (iii) We distill ARK ’s tool-use policy without labeled supervision into a compact Qwen3-8B model Yang et al. 2025a ; Kang et al. 2025 , preserving retrieval quality while reducing inference cost. 2 Related Work Knowledge graphs for document-centric RAG. Retrieval-augmented generation (RAG) grounds LLM outputs in external evidence by retrieving relevant context from a corpus or index Lewis et al. 2020 ; Guu et al. 2020 . Recent work injects structure by building graphs over textual units and using connectivity to aggregate evidence. GraphRAG performs local-to-global retrieval over an entity-centric graph Edge et al. 2025 , while KG-guided methods steer

Read the complete text