揭示大模型推理中先验知识与外部增强的临界关系。
Prior Knowledge Makes It Possible: From Sublinear Graph Algorithms to LLM Test-Time Methods
- 将多步推理建模为知识图谱上的路径搜索问题。
- 当先验知识形成大连通组件时，仅需常数级外部查询即可完成推理。
- 揭示了知识密度决定推理效率的相变现象，适用于大模型测试时增强研究。
测试时增强（如检索增强生成RAG或工具使用）依赖于模型参数化知识与外部信息的协同作用，但其理论基础尚不清晰。具体而言，回答查询所需的预训练知识量在少次增强步骤下是否足够，仍是未解之谜。为此，本文将多步推理建模为知识图谱上的s-t连通性问题：将模型预训练知识表示为部分且可能含噪的子图，将增强视为向一个预言机查询真实边以扩展知识。我们刻画了在给定部分先验知识条件下，模型生成准确答案所需的确切增强步骤数。关键发现表明存在相变现象：若知识图谱中n个顶点被分割成小连通分量，则通过增强寻找路径效率低下，需Ω(√n)次查询；一旦正确知识密度超过阈值、形成巨型连通组件，即可用期望常数次查询找到路径。
原文摘要 · Abstract (English)
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 $Ω(\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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。