pith. sign in

arxiv: 2601.13969 · v2 · submitted 2026-01-20 · 💻 cs.AI · cs.IR· cs.LG

Autonomous Knowledge Graph Exploration with Adaptive Breadth-Depth Retrieval

Joaqu\'in Polonuer (1 , 2) , Lucas Vittor (1) , I\~naki Arango (1) , Ayush Noori (1 , 3) , David A. Clifton (3 , 4)
show 36 more authors
Luciano Del Corro (5 6) Marinka Zitnik (1 7 8 9) ((1) Department of Biomedical Informatics Harvard Medical School Boston MA USA (2) Departamento de Computaci\'on FCEyN Universidad de Buenos Aires Buenos Aires Argentina (3) Department of Engineering Science University of Oxford Oxford UK (4) Oxford Suzhou Centre for Advanced Research Suzhou Jiangsu China (5) ELIAS Lab Departamento de Ingenier\'ia Universidad de San Andr\'es Victoria (6) Lumina Labs (7) Kempner Institute for the Study of Natural Artificial Intelligence Allston (8) Broad Institute of MIT Harvard Cambridge (9) Harvard Data Science Initiative USA)
This is my paper

Pith reviewed 2026-05-16 12:49 UTC · model grok-4.3

classification 💻 cs.AI cs.IRcs.LG
keywords knowledge graph retrievaladaptive retrievaltool usebreadth-depth tradeofftraining-free methodsmodel distillationSTaRK benchmarkmulti-hop traversal
0
0 comments X

The pith

ARK gives language models an adaptive toolset to explore knowledge graphs by switching between global lexical search and local neighborhood expansion without any training or fixed depth limits.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper presents ARK as a training-free retriever that lets an off-the-shelf language model control the breadth-depth tradeoff when pulling evidence from knowledge graphs. It supplies two composable operations: global lexical search over node descriptors for broad coverage and one-hop neighborhood exploration that builds multi-hop paths on demand. The model decides which operation to invoke next based on whether the query is language-heavy or relation-heavy. On the STaRK benchmark this yields 59.1 percent average Hit@1 and 67.4 average MRR, with gains of up to 31.4 points in Hit@1 over prior retrieval and agent baselines. The same trajectories are then distilled into an 8B model, lifting its Hit@1 by 7 to 26 points on three additional datasets while preserving most of the teacher's accuracy.

Core claim

ARK is a tool-using KG retriever in which the language model autonomously alternates between global lexical search over node descriptors and one-hop neighborhood exploration; the two operations compose into multi-hop traversal without requiring seed-node selection, preset hop limits, or any retrieval-specific training. The model adapts its choice of tool to query characteristics, applying global search to language-heavy inputs and neighborhood expansion to relation-heavy inputs. This produces 59.1 percent average Hit@1 and 67.4 average MRR on STaRK, outperforming prior training-free methods by up to 31.4 points in Hit@1 and 28.0 points in MRR. Distilling the resulting tool-use trajectories,

What carries the argument

Two-operation toolset of global lexical search over node descriptors and one-hop neighborhood exploration that the language model composes adaptively.

If this is right

  • Retrieval accuracy improves by up to 31.4 points in average Hit@1 and 28.0 points in average MRR over retrieval-based and agent-based training-free baselines on STaRK.
  • Distillation of ARK trajectories raises Hit@1 by 7.0, 26.6, and 13.5 points on AMAZON, MAG, and PRIME while keeping up to 98.5 percent of the teacher's performance in an 8B model.
  • No pre-set hop depth or fragile seed-node selection is required because the language model composes one-hop steps on demand.
  • Tool choice adapts automatically: global lexical search for language-heavy queries and neighborhood expansion for relation-heavy queries.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same adaptive alternation pattern could be tested on dynamic or streaming knowledge graphs where node descriptors change over time.
  • If the decision rule generalizes, smaller models might achieve competitive retrieval without ever seeing explicit supervision on tool selection.
  • The approach suggests a broader pattern: any graph-structured evidence source could be queried by giving the model a small set of composable local operations rather than a single fixed retriever.

Load-bearing premise

An off-the-shelf language model can reliably decide on its own when to apply global lexical search versus neighborhood exploration based on query characteristics without any training or supervision.

What would settle it

On a held-out KG query set, a non-adaptive baseline that always uses global search or always uses neighborhood expansion matches or exceeds ARK's Hit@1 and MRR.

Figures

Figures reproduced from arXiv: 2601.13969 by 2), (2) Departamento de Computaci\'on, 3), (3) Department of Engineering Science, 4), (4) Oxford Suzhou Centre for Advanced Research, (5) ELIAS Lab, 6), (6) Lumina Labs, 7, (7) Kempner Institute for the Study of Natural, 8, (8) Broad Institute of MIT, 9) ((1) Department of Biomedical Informatics, (9) Harvard Data Science Initiative, Allston, Argentina, Artificial Intelligence, Ayush Noori (1, Boston, Buenos Aires, Cambridge, China, David A. Clifton (3, Departamento de Ingenier\'ia, FCEyN, Harvard, Harvard Medical School, I\~naki Arango (1), Jiangsu, Joaqu\'in Polonuer (1, Lucas Vittor (1), Luciano Del Corro (5, MA, Marinka Zitnik (1, Oxford, Suzhou, UK, Universidad de Buenos Aires, Universidad de San Andr\'es, University of Oxford, USA, USA), Victoria.

Figure 1
Figure 1. 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 targ… view at source ↗
Figure 2
Figure 2. Figure 2: Thin bars show the share of text- vs. relation [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Retrieval quality and latency as a function of inference-time budget. Heatmaps report Hit@1, Recall@20, [PITH_FULL_IMAGE:figures/full_fig_p008_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Evaluation of the same ARK pipeline on the STaRK test sets while varying only the LLM backbone (Qwen3-4B/8B base, Qwen3-4B/8B distilled, or GPT-4.1). “Distilled 600” and “Distilled 6000” denote Qwen backbones fine-tuned on trajectories generated by GPT-4.1 from 600 or 6000 training queries per graph, respectively (three trajectories per query; tool calls and observations only; no label supervision). 0 10 2… view at source ↗
Figure 5
Figure 5. Figure 5: Distribution of the number of neighborhood [PITH_FULL_IMAGE:figures/full_fig_p008_5.png] view at source ↗
read the original 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, a tool-using 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 agent-based 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 1 minor

Summary. The manuscript introduces ARK, a training-free KG retriever in which an off-the-shelf LM is given two tools—global lexical search over node descriptors and one-hop neighborhood expansion—and is prompted to choose between them adaptively according to whether a query is language-heavy or relation-heavy. The central empirical claims are that this yields 59.1% average Hit@1 and 67.4 MRR on STaRK (up to +31.4 pp Hit@1 and +28.0 pp MRR over prior retrieval- and agent-based baselines) and that label-free distillation of the resulting trajectories into an 8B model recovers most of the teacher performance while improving the base 8B model by +7.0 to +26.6 pp Hit@1 on three additional datasets.

Significance. If the autonomous routing mechanism proves reliable, the work would supply a simple, training-free way to balance breadth and depth in KG retrieval and a practical distillation recipe for smaller models. The reported absolute gains are large enough to be practically interesting, but they rest entirely on the unverified assumption that prompt-induced tool selection works as intended.

major comments (1)
  1. [Abstract] Abstract (and presumably §3–4): the central claim that the LM “adapts tool use to queries, using global search for language-heavy queries and neighborhood exploration for relation-heavy queries” is load-bearing for all reported gains, yet the manuscript supplies no decision-accuracy metric, confusion matrix, or oracle-vs-autonomous ablation. Without such evidence it is impossible to determine whether the 31.4 pp Hit@1 lift is due to correct adaptive routing or to other factors.
minor comments (1)
  1. [Abstract] Abstract: experimental details (exact baselines, statistical significance, number of runs, prompt templates, and failure cases) are absent, preventing assessment of the soundness of the benchmark numbers.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for highlighting the need to validate the adaptive routing mechanism. We agree this is central to interpreting the gains and will add supporting analyses in the revision.

read point-by-point responses

  1. Referee: [Abstract] Abstract (and presumably §3–4): the central claim that the LM “adapts tool use to queries, using global search for language-heavy queries and neighborhood exploration for relation-heavy queries” is load-bearing for all reported gains, yet the manuscript supplies no decision-accuracy metric, confusion matrix, or oracle-vs-autonomous ablation. Without such evidence it is impossible to determine whether the 31.4 pp Hit@1 lift is due to correct adaptive routing or to other factors.

    Authors: We agree that explicit verification of the routing decisions is needed. A full confusion matrix is not feasible because the manuscript defines language-heavy vs. relation-heavy queries only qualitatively and provides no ground-truth labels for them. However, we will add the following in the revision: (1) quantitative statistics on tool-selection frequencies broken down by manually annotated query categories on a held-out sample, (2) an ablation comparing autonomous ARK against fixed-tool baselines (always-global, always-neighborhood) and random selection, and (3) qualitative case studies showing how the LM chooses tools on representative queries. These additions will isolate the contribution of adaptive routing to the reported gains while remaining consistent with the training-free setting. revision: yes

Circularity Check

0 steps flagged

No circularity: empirical method evaluated on external benchmarks

full rationale

The paper describes ARK as a prompt-driven tool-using retriever that lets an unmodified LM alternate between global lexical search and neighborhood expansion. All performance numbers (Hit@1, MRR on STaRK; distillation gains on AMAZON/MAG/PRIME) are measured against independent prior methods and standard datasets. No equations, fitted parameters, or self-referential quantities appear in the provided text; the adaptation rule is stated as an emergent prompt behavior rather than a derived identity. No load-bearing self-citation chain or ansatz-smuggling is present. The derivation is therefore self-contained against external evidence.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The approach rests on standard assumptions from LLM tool-use literature; no free parameters, new axioms, or invented entities are introduced in the abstract.

axioms (1)
  • domain assumption Large language models can effectively utilize provided tools for information retrieval tasks
    Invoked by the tool-using design of ARK.

pith-pipeline@v0.9.0 · 5797 in / 1249 out tokens · 62227 ms · 2026-05-16T12:49:24.648229+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

24 extracted references · 24 canonical work pages · 3 internal anchors

  1. [1]

    Go for a Walk and Arrive at the Answer: Reasoning Over Paths in Knowledge Bases using Reinforcement Learning

    Reciprocal rank fusion outperforms condorcet and individual rank learning methods. InProceedings of the 32nd international ACM SIGIR conference on Research and development in information retrieval, SIGIR ’09, pages 758–759, New York, NY , USA. Association for Computing Machinery. Rajarshi Das, Shehzaad Dhuliawala, Manzil Zaheer, Luke Vil- nis, Ishan Durug...

    work page internal anchor Pith review Pith/arXiv arXiv 2018

  2. [2]

    From Local to Global: A Graph RAG Approach to Query-Focused Summarization

    From Local to Global: A Graph RAG Ap- proach to Query-Focused Summarization.arXiv preprint. ArXiv:2404.16130 [cs]. Ronald Fagin, Ravi Kumar, and D. Sivakumar. 2003. Efficient similarity search and classification via rank aggregation. InProceedings of the 2003 ACM SIGMOD international conference on Management of data, SIGMOD ’03, pages 301–312, New York, N...

    work page internal anchor Pith review Pith/arXiv arXiv 2003

  3. [3]

    G-retriever: Retrieval-augmented generation for textual graph understanding and question answering,

    G-Retriever: Retrieval-Augmented Generation for Textual Graph Understanding and Question Answering. arXiv preprint. ArXiv:2402.07630 [cs]. Geoffrey Hinton, Oriol Vinyals, and Jeff Dean. 2015. Distill- ing the Knowledge in a Neural Network.arXiv preprint. ArXiv:1503.02531 [stat]. Edward J. Hu, Yelong Shen, Phillip Wallis, Zeyuan Allen-Zhu, Yuanzhi Li, Shea...

    work page arXiv 2015

  4. [4]

    LoRA: Low-Rank Adaptation of Large Language Models

    LoRA: Low-Rank Adaptation of Large Language Models.arXiv preprint. ArXiv:2106.09685 [cs]. Yikuan Hu, Jifeng Zhu, Lanrui Tang, and Chen Huang. 2025a. ReMindRAG: low-cost LLM-guided knowledge graph traversal for efficient RAG.NeurIPS. Yuntong Hu, Zhihan Lei, Zheng Zhang, Bo Pan, Chen Ling, and Liang Zhao. 2025b. GRAG: Graph Retrieval- Augmented Generation. ...

    work page internal anchor Pith review Pith/arXiv arXiv 2025

  5. [5]

    Multi-field adaptive retrieval.arXiv preprint arXiv:2410.20056,

    Dense Passage Retrieval for Open-Domain Ques- tion Answering. InProceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 6769–6781, Online. Association for Com- putational Linguistics. Youmin Ko, Sungjong Seo, and Hyunjoon Kim. 2025. Co- operative retrieval-augmented generation for question an- swering: Mutual ...

    work page arXiv 2020

  6. [6]

    Generative representational instruction tuning

    Generative Representational Instruction Tuning. arXiv preprint. ArXiv:2402.09906 [cs]. Long Ouyang, Jeff Wu, Xu Jiang, Diogo Almeida, Carroll L. Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, John Schulman, Ja- cob Hilton, Fraser Kelton, Luke Miller, Maddie Simens, Amanda Askell, Peter Welinder, Paul Christiano, Jan L...

    work page arXiv 2022

  7. [7]

    Use`search_in_graph`with the full question as the query and size =30 to cast a wide net 13 AMAZON MAG PRIME Method Hit@1 Hit@5 R@20 MRR Hit@1 Hit@5 R@20 MRR Hit@1 Hit@5 R@20 MRR GPT-4o 55.13 76.37 57.18 64.29 67.01 86.67 79.79 75.46 36.01 60.17 60.13 46.44 GPT-4.1 55.82 75.80 60.61 64.77 73.40 87.92 84.47 79.87 48.20 69.57 69.46 57.68 Qwen3-4B 45.69 67.46...

    work page

  8. [8]

    Review all 30 results and select approximately 15 of the most suitable entities to add to the answer ( aim for roughly half of the search results )

    work page

  9. [9]

    product X

    Add the selected entities to the answer with clear reasoning for each ** Important **: The goal is to provide users with multiple relevant options . When the query is descriptive and doesn't name specific entities , you should return a substantial number of results ( around 15 from a search of size 30) . This ensures users have many options to choose from...

    work page

  10. [10]

    ** Entity disambiguation **: First , search for the mentioned entities using`search_in_graph`with the entity name

    work page

  11. [11]

    ** Neighborhood exploration **: Once you've identified the relevant entity nodes , use` search_in_neighborhood`to explore their connections

    work page

  12. [12]

    ** Filtered search **: Use the`query` parameter in neighborhood searches to filter results by keywords from the original question This strategy works well when : - The query mentions specific entities that likely exist in the graph - You need to explore relationships around known entities - The query requires multi - hop reasoning ### Strategy 3: Multi - ...

    work page

  13. [13]

    Start by disambiguating all mentioned entities

    work page

  14. [14]

    Explore neighborhoods of key entities with relevant filters

    work page

  15. [15]

    Find products suitable for outdoor camping

    Combine information from multiple exploration paths ## Examples ### Example 1: Simple broad search ( Strategy 1) ** Query **: " Find products suitable for outdoor camping " ** Approach **: Since no specific products are mentioned , use`search_in_graph ( query =" Find products suitable for outdoor camping " , size =30)`. This will return 30 results . Then ...

    work page

  16. [16]

    BrandX company

    First , search for the brand / company : `search_in_graph (" BrandX company ")`

    work page

  17. [17]

    winter - themed accessories

    Then explore its neighborhood :` s e a r c h _ i n _ n e i g h b o r h o o d ( node_index = < found_brand_index > , query =" winter - themed accessories ")` ### Example 3: Multi - hop reasoning ( Strategy 2) ** Query **: " Can you find other publications from the co - authors of 14 the paper titled'Machine Learning Applications in Healthcare'that relate t...

    work page

  18. [18]

    Machine Learning Applications in Healthcare

    Search for the paper :` search_in_graph (" Machine Learning Applications in Healthcare ")`

    work page

  19. [19]

    Find co - authors :` s e a r c h _ i n _ n e i g h b o r h o o d ( node_index = < paper_index > , node_type = author )`

    work page

  20. [20]

    neural networks

    For each author , search their papers : `s e a r c h _ i n _ n e i g h b o r h o o d ( node_index = < author_index > , query =" neural networks " , node_type = paper )` ### Example 4: Multiple constraints ( Strategy 3) ** Query **: " What medications interact synergistically with DrugX and are also used to treat DiseaseY ?" ** Approach **:

    work page

  21. [21]

    Find DrugX :`search_in_graph (" DrugX ") `

    work page

  22. [22]

    DiseaseY

    Find DiseaseY :`search_in_graph (" DiseaseY ")`

    work page

  23. [23]

    Explore neighborhoods :` s e a r c h _ i n _ n e i g h b o r h o o d ( node_index = < disease_index > , node_type = drug )`and `s e a r c h _ i n _ n e i g h b o r h o o d ( node_index = < drugx_index > , node_type = drug )`

    work page

  24. [24]

    Add the drugs to the answer ## General Guidelines - ** Provide multiple options when appropriate **: For queries without explicit entity mentions , aim to give users many relevant options ( typically 10 -20 entities from a search of size 30) - ** Start broad , then narrow **: Begin with global searches , then focus on specific neighborhoods - ** Use filte...

    work page