Prior Knowledge Makes It Possible: From Sublinear Graph Algorithms to LLM Test-Time Methods
Avrim Blum, Daniel Hsu, Cyrus Rashtchian, Donya Saless · 2025
Read Prior Knowledge Makes It Possible: From Sublinear Graph Algorithms to LLM Test-Time Methods by Avrim Blum, Daniel Hsu, Cyrus Rashtchian, Donya Saless (2025) 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-2510-16609.txt.
Introduction
Avrim Blum leads three co-authors in a 2025 study on how much a model must know to answer well. Test-time aids, like search or tools, fetch facts while a model works. The team asks how much built-in knowledge a model needs for few fetches. They cast multi-step thought as a path hunt on a knowledge graph. A graph links facts as nodes joined by edges.
Built-in knowledge is a part graph, which may hold wrong edges. Each fetch asks a true source for one real edge. A sharp phase shift marks the line between hard and easy hunts. Split knowledge forces a vast count of fetches per path. Past a density line, a giant linked chunk forms and paths take few fetches.
Catalog record
| CREATOR | Avrim Blum, Daniel Hsu, Cyrus Rashtchian, Donya Saless |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 81 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2510-16609
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Prior Knowledge Makes It Possible: From Sublinear Graph Algorithms to LLM Test-Time Methods Avrim Blum, Daniel Hsu, Cyrus Rashtchian, Donya Saless Abstract 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 s - t 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 n vertices is disconnected into small components, then finding a path via augmentation is inefficient and requires Ω ( n ) \Omega(\sqrt{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. † † footnotetext: Authors listed in alphabetical order. 1 Introduction Generating accurate and helpful answers with Large Language Models (LLMs) often involves a combination of thinking about the user query and retrieving relevant information from external sources. For reasoning problems, the LLM can produce a chain-of-thought, analyzing intermediate sub-problems before arriving at a final solution Comanici et al., 2025 ; Mirtaheri et al., 2025 ; Yang et al., 2025 ; DeepSeek-AI et al., 2025 . For information seeking queries, the LLM can retrieve from databases or knowledge graphs to expand its grasp of new facts ( Gutiérrez et al., 2025 ; Lewis et al., 2020 ; Min et al., 2019 ; Zhou et al., 2025 ; Vu et al., 2023 ) . A common thread for these scenarios is that the LLM needs to augment its pre-training knowledge with additional information (either self-generated or external) before being able to adequately answer a question ( Joren et al., 2024 ; Su et al., 2024 ; Wei et al., 2024a ) . However, this interplay between parametric and user-provided or externally-retrieved contextual knowledge remains poorly understood. We develop a graph-theoretic framework to study the ability of LLMs to solve multi-step problems. Using our abstract model, we can shed light on some fundamental questions. For instance, we explore how properties of the pre-training knowledge can facilitate or impede the ability to solve a multi-step problem. Then, as one of our results we show that when prior quality is above a certain threshold, a constant expected number of augmentation steps suffices, and below this threshold, any strategy requires superconstantly many queries using external information. Of course, representing an LLM’s vast, nuanced parametric knowledge as an unweighted subgraph is a significant simplification. Nonetheless, our model provides a formal lens on a key principle: we support the conjecture that efficient retrieval-augmented generation (RAG) requires a richness of parametric knowledge ( Guu et al., 2020 ; Pan et al., 2024 ; Wei et al., 2024b ; Xie et al., 2024 ; Liu et al., 2025 ) . In other words, if LLMs are to succeed in RAG tasks, then they need to both process language and have a sufficient density of world knowledge from their pre-training data. Similarly, we provide further evidence that the best reasoning models require a deep knowledge of mathematical facts ( Ma et al., 2025 ) . Figure 1 : The left graph depicts that in our basic framework, we have a prior graph G , which is a subset of the true graph G^{*} . We illustrate two example knowledge graphs, where finding a path between nodes can answer the given question. Often the algorithm must query dotted edges from G^{*}\setminus G that are outside of G . We also consider various ways to sample G and G^{*} , as well as cases where edges in G may be noisy and need verification. 1.1 Graph-theoretic Framework for Solving Multi-step Problems Given that an LLM with test-time augmentation is a very complex system to study, we focus on a few key components. At a high level, we consider a knowledge graph G^{*} where nodes are entities in the world and edges represent relationships or facts that involve two entities. For example, consider a simple fact composition scenario in knowledge graphs: if we know “A is connected to B” and “B is connected to C,” we can deduce “A is connected to C.” Such chaining of local facts into a global conclusion lies at the heart of deductive reasoning. One interpretation is that “A is connected to B” corresponds to “A is equivalent to B” and we want to deduce other equivalence relations. Another is that a connection corresponds to a co-occurrence in a sentence ( Yang et al., 2024 ) . We provide further examples in Figure 1 . A core component of our framework is that we aim to formalize the difference between the partial knowledge that the model knows from pre-training and the potential facts that it could know through reasoning-based thinking or external retrieval mechanisms. We abstract this as designating a subgraph G of G^{*} . In graph terms, we frame “good” prior knowledge as exhibiting well-connectedness, expansion, and edge reliability. We use G to capture the fact that a pre-tained LLM will have only partial information about an unknown ground-truth graph G^{*} . Furthermore, each edge of G may or may not correspond to a true edge in G^{*} , and the number of edges in G will be a small fraction of the total in G^{*} . We want to find trade-offs where a model knows G but also requires some access to G^{*} to correctly answer a question. The model will access G^{*} using “oracles” that provide information. From a theoretical point of view, our work complements much literature on sub-linear time graph algorithms ( Goldreich and Ron, 2011 ) . In particular, the algorithm starts with the prior knowledge of G , rather than with no information about G^{*} , leading to a new twist on classical problems. To study test-time augmentation, we define two query models: (i) given a vertex v , the retrieval oracle returns a random neighbor of v in G^{*} (and our lower bound also holds for a stronger oracle that given a vertex v , returns all neighbors in G^{*} of the connected component in G that contains v ) and (ii) given a pair u,v , the verifier oracle returns whether \{u,v\} is an edge in G^{*} or not. These oracles capture different aspects of test-time augmentations based on a knowledge graph. In a RAG setting, a retrieval mechanism provides information about the query. Often this is done through a similarity search (e.g., BM25 or embeddings) based on the entities in the query. However, we cannot guarantee exactly what information the retriever returns. Hence, in the retrieval oracle,