When to Compress: Efficient LLM Reasoning on Graphs with One Billion Edges

Large Language Models (LLMs) can handle natural-language requests involving graph reasoning tasks by invoking appropriate tools. On large-scale graphs, however, tool execution can involve substantial computation unrelated to the requested answer. Graph compression can reduce this computation, but how it is performed affects both answer correctness and execution efficiency. Even for the same task, the information needed to determine the answer can differ substantially in scope and size across graph instances. Moreover, constructing a smaller answer-preserving graph may cost more than the subsequent execution saves. This raises the question of when and how to compress a graph. We thus introduce a Certificate graph, an executable graph representation that preserves the original task answer, and propose CAGR, a Certificate-Aware Graph Reasoning framework that learns how to obtain such representations and determines when further compression is worthwhile. CAGR learns compression strategies through Certificate Compression Optimization (CCO), which combines toolchain search with LLM policy improvement, while a lightweight Compression Gate weighs further compression costs against subsequent execution savings to determine when to execute. We also introduce GraphLarge, which extends existing LLM graph reasoning benchmarks to the billion-edge scale and covers 28 domain-task settings across four real-world domains. Results show that CAGR achieves a 5.78$\times$ speedup and improves average success rate by 15.53 percentage points over existing graph compression methods.