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

arXiv:2510.16609v3 Announce Type: replace-cross 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 proper