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

• URL: http://arxiv.org/abs/2510.16609v1
• Date: Sat, 18 Oct 2025 18:17:25 GMT
• Title: Prior Makes It Possible: From Sublinear Graph Algorithms to LLM Test-Time Methods
• Authors: Avrim Blum, Daniel Hsu, Cyrus Rashtchian, Donya Saless,
• Abstract summary: It is not clear how much pre-training knowledge is required to answer queries with a small number of augmentation steps.<n>We characterize the necessary and sufficient number of augmentation steps for the model to generate an accurate answer given partial prior knowledge.
• Score: 14.581444640667364
• License: http://creativecommons.org/licenses/by/4.0/
• 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$-$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(\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.

Related papers

• Search-on-Graph: Iterative Informed Navigation for Large Language Model Reasoning on Knowledge Graphs [26.0585592684229]
  Large language models (LLMs) have demonstrated impressive reasoning abilities yet remain unreliable on knowledge-intensive, multi-hop questions.<n>We propose Search-on-Graph (SoG), a simple yet effective framework that enables LLMs to perform iterative informed graph navigation.<n>We demonstrate particularly strong gains on Wikidata benchmarks (+16% improvement over previous best methods) alongside consistent improvements on Freebase benchmarks.
  arXiv  Detail & Related papers  (2025-10-09T21:20:16Z)
• PropMEND: Hypernetworks for Knowledge Propagation in LLMs [82.99849359892112]
  We present a hypernetwork-based approach for knowledge propagation, named PropMEND.<n>We show almost 2x accuracy on challenging multi-hop questions whose answers are not explicitly stated in the injected fact.<n>We also introduce a new dataset, Controlled RippleEdit, to evaluate the generalization of our hypernetwork.
  arXiv  Detail & Related papers  (2025-06-10T15:44:19Z)
• Harnessing Large Language Models for Knowledge Graph Question Answering via Adaptive Multi-Aspect Retrieval-Augmentation [81.18701211912779]
  We introduce an Adaptive Multi-Aspect Retrieval-augmented over KGs (Amar) framework.<n>This method retrieves knowledge including entities, relations, and subgraphs, and converts each piece of retrieved text into prompt embeddings.<n>Our method has achieved state-of-the-art performance on two common datasets.
  arXiv  Detail & Related papers  (2024-12-24T16:38:04Z)
• GLaM: Fine-Tuning Large Language Models for Domain Knowledge Graph Alignment via Neighborhood Partitioning and Generative Subgraph Encoding [39.67113788660731]
  We introduce a framework for developing Graph-aligned LAnguage Models (GLaM) We demonstrate that grounding the models in specific graph-based knowledge expands the models' capacity for structure-based reasoning.
  arXiv  Detail & Related papers  (2024-02-09T19:53:29Z)
• Fine-grained Stateful Knowledge Exploration: Effective and Efficient Graph Retrieval with Large Language Models [19.049828741139425]
  Large Language Models (LLMs) have shown impressive capabilities, yet updating their knowledge remains a significant challenge.<n>Most existing methods use a paradigm that treats the whole question as the objective, with relevant knowledge being incrementally retrieved from the knowledge graph.<n>We propose FiSKE, a novel paradigm for Fine-grained Stateful Knowledge Exploration.
  arXiv  Detail & Related papers  (2024-01-24T13:36:50Z)
• ReasoningLM: Enabling Structural Subgraph Reasoning in Pre-trained Language Models for Question Answering over Knowledge Graph [142.42275983201978]
  We propose a subgraph-aware self-attention mechanism to imitate the GNN for performing structured reasoning. We also adopt an adaptation tuning strategy to adapt the model parameters with 20,000 subgraphs with synthesized questions. Experiments show that ReasoningLM surpasses state-of-the-art models by a large margin, even with fewer updated parameters and less training data.
  arXiv  Detail & Related papers  (2023-12-30T07:18:54Z)
• Physics of Language Models: Part 3.1, Knowledge Storage and Extraction [51.68385617116854]
  Large language models (LLMs) can store a vast amount of world knowledge, often extractable via question-answering. We find a strong correlation between the model's ability to extract knowledge and various diversity measures of the training data.
  arXiv  Detail & Related papers  (2023-09-25T17:37:20Z)
• Fast Knowledge Graph Completion using Graphics Processing Units [0.1611401281366893]
  Current knowledge graphs need to be complemented for better knowledge in terms of relations. To add new relations by using knowledge graph embedding models, we have to evaluate $Ntimes N times R$ vector operations. We provide an efficient knowledge graph completion framework on GPUs to get new relations using knowledge graph embedding vectors.
  arXiv  Detail & Related papers  (2023-07-22T12:00:54Z)
• UniKGQA: Unified Retrieval and Reasoning for Solving Multi-hop Question Answering Over Knowledge Graph [89.98762327725112]
  Multi-hop Question Answering over Knowledge Graph(KGQA) aims to find the answer entities that are multiple hops away from the topic entities mentioned in a natural language question. We propose UniKGQA, a novel approach for multi-hop KGQA task, by unifying retrieval and reasoning in both model architecture and parameter learning.
  arXiv  Detail & Related papers  (2022-12-02T04:08:09Z)
• Complex Query Answering with Neural Link Predictors [13.872400132315988]
  We propose a framework for efficiently answering complex queries on incomplete Knowledge Graphs. We translate each query into an end-to-end differentiable objective, where the truth value of each atom is computed by a pre-trained neural predictor. In our experiments, the proposed approach produces more accurate results than state-of-the-art methods.
  arXiv  Detail & Related papers  (2020-11-06T16:20:49Z)
• A Simple Approach to Case-Based Reasoning in Knowledge Bases [56.661396189466664]
  We present a surprisingly simple yet accurate approach to reasoning in knowledge graphs (KGs) that requires emphno training, and is reminiscent of case-based reasoning in classical artificial intelligence (AI) Consider the task of finding a target entity given a source entity and a binary relation. Our non-parametric approach derives crisp logical rules for each query by finding multiple textitgraph path patterns that connect similar source entities through the given relation.
  arXiv  Detail & Related papers  (2020-06-25T06:28:09Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.