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

arXiv: https://arxiv.org/abs/2510.16609 · HTML: https://mlsanity.com/paper/2510.16609/

## Key facts

- No citing papers in the map yet (data through 14 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.

## Placed in

- Retrieval-augmented generation / [Knowledge-graph and structured-knowledge RAG](https://mlsanity.com/rag/knowledge-graph-and-structured-knowledge-rag/)

## Builds on (most cited first, 30 of 46)

- [Retrieval-Augmented Generation for Knowledge-Intensive NLP Tasks](https://mlsanity.com/paper/2005.11401/) (2020)
- [Qwen3 Technical Report](https://mlsanity.com/paper/2505.09388/) (2025)
- [Gemini 2.5: Pushing the Frontier with Advanced Reasoning, Multimodality, Long Context, and Next Generation Agentic Capabilities](https://mlsanity.com/paper/2507.06261/) (2025)
- [Let's Verify Step by Step](https://mlsanity.com/paper/2305.20050/) (2023)
- [Tree of Thoughts: Deliberate Problem Solving with Large Language Models](https://mlsanity.com/paper/2305.10601/) (2023)
- [REALM: Retrieval-Augmented Language Model Pre-Training](https://mlsanity.com/paper/2002.08909/) (2020)
- [Self-RAG: Learning to Retrieve, Generate, and Critique through Self-Reflection](https://mlsanity.com/paper/2310.11511/) (2023)
- [Understanding R1-Zero-Like Training: A Critical Perspective](https://mlsanity.com/paper/2503.20783/) (2025)
- [Solving math word problems with process- and outcome-based feedback](https://mlsanity.com/paper/2211.14275/) (2022)
- [Unifying Large Language Models and Knowledge Graphs: A Roadmap](https://mlsanity.com/paper/2306.08302/) (2023)
- [Enabling Large Language Models to Generate Text with Citations](https://mlsanity.com/paper/2305.14627/) (2023)
- [Measuring short-form factuality in large language models](https://mlsanity.com/paper/2411.04368/) (2024)
- [Adaptive Chameleon or Stubborn Sloth: Revealing the Behavior of Large Language Models in Knowledge Conflicts](https://mlsanity.com/paper/2305.13300/) (2023)
- [FreshLLMs: Refreshing Large Language Models with Search Engine Augmentation](https://mlsanity.com/paper/2310.03214/) (2023)
- [RARR: Researching and Revising What Language Models Say, Using Language Models](https://mlsanity.com/paper/2210.08726/) (2022)
- [Rewarding Progress: Scaling Automated Process Verifiers for LLM Reasoning](https://mlsanity.com/paper/2410.08146/) (2024)
- [From RAG to Memory: Non-Parametric Continual Learning for Large Language Models](https://mlsanity.com/paper/2502.14802/) (2025)
- [BRIGHT: A Realistic and Challenging Benchmark for Reasoning-Intensive Retrieval](https://mlsanity.com/paper/2407.12883/) (2024)
- [Long-form factuality in large language models](https://mlsanity.com/paper/2403.18802/) (2024)
- [On the Theoretical Limitations of Embedding-Based Retrieval](https://mlsanity.com/paper/2508.21038/) (2025)
- [PRODIGY: Enabling In-context Learning Over Graphs](https://mlsanity.com/paper/2305.12600/) (2023)
- [AvaTaR: Optimizing LLM Agents for Tool Usage via Contrastive Reasoning](https://mlsanity.com/paper/2406.11200/) (2024)
- [Sufficient Context: A New Lens on Retrieval Augmented Generation Systems](https://mlsanity.com/paper/2411.06037/) (2024)
- [Synthetic continued pretraining](https://mlsanity.com/paper/2409.07431/) (2024)
- [Knowledge Guided Text Retrieval and Reading for Open Domain Question Answering](https://mlsanity.com/paper/1911.03868/) (2019)
- [In-depth Analysis of Graph-based RAG in a Unified Framework](https://mlsanity.com/paper/2503.04338/) (2025)
- [Privacy-Preserving Retrieval-Augmented Generation with Differential Privacy](https://mlsanity.com/paper/2412.04697/) (2024)
- [Measuring and Enhancing Trustworthiness of LLMs in RAG through Grounded Attributions and Learning to Refuse](https://mlsanity.com/paper/2409.11242/) (2024)
- [Learning-Theoretic Foundations of Algorithm Configuration for Combinatorial Partitioning Problems](https://mlsanity.com/paper/1611.04535/) (2016)
- [How much data is sufficient to learn high-performing algorithms? Generalization guarantees for data-driven algorithm design](https://mlsanity.com/paper/1908.02894/) (2019)

## 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.