With the rapidly improving reasoning abilities of Large Language Models (LLMs), there is also a rising demand to use them in a wide variety of domains. This brings about the need to carefully evaluate the limits of the capabilities of these models with various tests and benchmarks. Graph structures are ubiquitous in real-world data, and are often used to represent and analyze relationship patterns within data. Many benchmarks have already been proposed in the graph literature to test the reasoning ability of LLMs to follow and execute graph algorithms. However, due to the limited context length of LLMs, these benchmarks consist of very small graphs. In real-world data, the size of graphs can be significantly larger, and in many cases, not fully accessible. In this paper, we examine a class of problems that arises with very large graphs having limited accessibility. We propose a large graph benchmark dataset, EstGraph, and introduce four distinct tasks designed to estimate large graph properties. We evaluate the reasoning abilities of LLMs on these tasks using a wide variety of graph datasets. In addition, we provide task-specific prompt constructions based on random walk sampling of large graphs (up to millions of nodes) that effectively convey sufficient information to LLMs within the limits of context length.

Graph-based retrieval is effective for knowledge graph question answering (KGQA), but retrieving the correct reasoning path remains challenging in multi-hop settings because the retrieval objective changes as reasoning progresses. Existing methods often address this issue with repeated LLM-based planning, which improves adaptivity but increases inference cost. We present a training-free residual-guided retrieval framework that updates the retrieval signal according to the current reasoning path in embedding space. The method performs multi-hop graph retrieval without repeated hop-wise LLM calls and invokes the LLM only once for final answer generation. Experiments on WebQSP and CWQ show that our method achieves superior Hit rates with only a single LLM call. Additional comparisons with supervised graph-based KGQA methods show that the proposed method remains effective without task-specific training data. These results suggest that residual-guided retrieval is an efficient alternative for multi-hop graph-based question answering.