mlsanityData to 7 Oct 2026

Prior Knowledge Makes It Possible: From Sublinear Graph Algorithms to LLM Test-Time Methods

arXiv 2510.16609 ↗First posted 18 Oct 2025cs.LG cs.AI cs.CCcited by 0

On the map: Retrieval-augmented generation → Knowledge-graph and structured-knowledge RAG

Abstract (arXiv)

Test-time augmentation, such as Retrieval-Augmented Generation (RAG) or tool use, critically depends on an interplay between a model's parametric knowledge and externally retrieved information. However, the theoretical underpinnings of this relationship remain poorly understood. Specifically, it is not clear how much pre-training knowledge is required to answer queries with a small number of augmentation steps, which is a desirable property in practice. To address this question, we formulate multi-step reasoning as an s-t connectivity problem on a knowledge graph. We represent a model's pre-training parametric knowledge as a partial, potentially noisy subgraph. We view augmentation as querying an oracle for true edges that augment the model's knowledge. Then, we characterize the necessary and sufficient number of augmentation steps for the model to generate an accurate answer given partial prior knowledge. One key result shows a phase transition: if the prior knowledge graph over n vertices is disconnected into small components, then finding a path via augmentation is inefficient and requires Omega(√n) queries. On the other hand, once the density of correct knowledge surpasses a threshold, forming a giant component, we can find paths with an expected constant number of queries.

Key facts. No citing papers in the map yet (data through 7 Oct 2026). Placed in Knowledge-graph and structured-knowledge RAG, one of 15 directions in Retrieval-augmented generation. Builds on 46 of its 54 references that are in the map. First posted on arXiv 18 Oct 2025.

Builds on

46 of 54 references.

Closest ancestors · 1

Same direction, newest first

  1. 2025In-depth Analysis of Graph-based RAG in a Unified Framework6 Mar

Other references · 45

  1. 2020Retrieval-Augmented Generation for Knowledge-Intensive NLP Taskscited by 9,160
  2. 2025Qwen3 Technical Reportcited by 8,195
  3. 2025Gemini 2.5: Pushing the Frontier with Advanced Reasoning, Multimodality, Long Context, and Next Generation Agentic Capabilitiescited by 3,655
  4. 2023Let's Verify Step by Stepcited by 3,598
  5. 2023Tree of Thoughts: Deliberate Problem Solving with Large Language Modelscited by 3,155
  6. 2020REALM: Retrieval-Augmented Language Model Pre-Trainingcited by 2,126
  7. 2023Self-RAG: Learning to Retrieve, Generate, and Critique through Self-Reflectioncited by 1,800
  8. 2025Understanding R1-Zero-Like Training: A Critical Perspectivecited by 1,276
  9. 2022Solving math word problems with process- and outcome-based feedbackcited by 871
  10. 2023Unifying Large Language Models and Knowledge Graphs: A Roadmapcited by 663
  11. 2023Enabling Large Language Models to Generate Text with Citationscited by 584
  12. 2024Measuring short-form factuality in large language modelscited by 345
33 more
  1. 2023Adaptive Chameleon or Stubborn Sloth: Revealing the Behavior of Large Language Models in Knowledge Conflictscited by 333
  2. 2023FreshLLMs: Refreshing Large Language Models with Search Engine Augmentationcited by 308
  3. 2022RARR: Researching and Revising What Language Models Say, Using Language Modelscited by 286
  4. 2024Rewarding Progress: Scaling Automated Process Verifiers for LLM Reasoningcited by 267
  5. 2025From RAG to Memory: Non-Parametric Continual Learning for Large Language Modelscited by 223
  6. 2024BRIGHT: A Realistic and Challenging Benchmark for Reasoning-Intensive Retrievalcited by 153
  7. 2024Long-form factuality in large language modelscited by 146
  8. 2025On the Theoretical Limitations of Embedding-Based Retrievalcited by 98
  9. 2023PRODIGY: Enabling In-context Learning Over Graphscited by 97
  10. 2024AvaTaR: Optimizing LLM Agents for Tool Usage via Contrastive Reasoningcited by 69
  11. 2024Sufficient Context: A New Lens on Retrieval Augmented Generation Systemscited by 69
  12. 2019Knowledge Guided Text Retrieval and Reading for Open Domain Question Answeringcited by 59
  13. 2024Synthetic continued pretrainingcited by 56
  14. 2024Privacy-Preserving Retrieval-Augmented Generation with Differential Privacycited by 38
  15. 2024Measuring and Enhancing Trustworthiness of LLMs in RAG through Grounded Attributions and Learning to Refusecited by 33
  16. 2016Learning-Theoretic Foundations of Algorithm Configuration for Combinatorial Partitioning Problemscited by 30
  17. 2019How much data is sufficient to learn high-performing algorithms? Generalization guarantees for data-driven algorithm designcited by 27
  18. 2025Metastable Dynamics of Chain-of-Thought Reasoning: Provable Benefits of Search, RL and Distillationcited by 25
  19. 2022Few-shot Relational Reasoning via Connection Subgraph Pretrainingcited by 18
  20. 2025Taming Imperfect Process Verifiers: A Sampling Perspective on Backtrackingcited by 13
  21. 2025Let Me Think! A Long Chain-of-Thought Can Be Worth Exponentially Many Short Onescited by 12
  22. 2025From Reasoning to Super-Intelligence: A Search-Theoretic Perspectivecited by 9
  23. 2020Vector-Matrix-Vector Queries for Solving Linear Algebra, Statistics, and Graph Problemscited by 8
  24. 2019Finding a planted clique by adaptive probingcited by 6
  25. 2025On Learning Verifiers and Implications to Chain-of-Thought Reasoningcited by 6
  26. 2021Average-Case Communication Complexity of Statistical Problemscited by 5
  27. 2025Benchmarking Abstract and Reasoning Abilities Through A Theoretical Perspectivecited by 4
  28. 2017Edge Estimation with Independent Set Oraclescited by 3
  29. 2025Dynamic and Parametric Retrieval-Augmented Generationcited by 3
  30. 2019Nearly optimal edge estimation with independent set queriescited by 2
  31. 2021A tight bound for the clique query problem in two roundscited by 2
  32. 2023Sublinear Time Shortest Path in Expander Graphscited by 1
  33. 2024A Sublinear Algorithm for Approximate Shortest Paths in Large Networkscited by 1

Built on by

Not cited yet.

Similar, not cited

Close in wording, no citation either way

  1. 2026A Storage-Retrieval Gap in Parametric Knowledge Graph Memory
  2. 2025You Don't Need Pre-built Graphs for RAG: Retrieval Augmented Generation with Adaptive Reasoning Structures
  3. 2025GRAIL:Learning to Interact with Large Knowledge Graphs for Retrieval Augmented Reasoning
  4. 2025Deliberation on Priors: Trustworthy Reasoning of Large Language Models on Knowledge Graphs
  5. 2024Simple Is Effective: The Roles of Graphs and Large Language Models in Knowledge-Graph-Based Retrieval-Augmented Generation
  6. 2025Reasoning by Exploration: A Unified Approach to Retrieval and Generation over Graphs
  7. 2025Graph-Augmented Reasoning: Evolving Step-by-Step Knowledge Graph Retrieval for LLM Reasoning
  8. 2025What Breaks Knowledge Graph based RAG? Benchmarking and Empirical Insights into Reasoning under Incomplete Knowledge