- Rating
- 3
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
The paper proposes CAGR, which uses an LLM to compose answer-preserving graph compression tools and a learned gate to decide when to stop compression and execute a graph algorithm. Experiments on GraphLarge and existing benchmarks report improved task success and reduced execution time.
Critical strengths
GraphLarge offers a useful testbed for large-scale graph reasoning, covering 28 domain-task settings across four real-world graph sources and reaching billion-edge scale. It enables evaluation under computational constraints that smaller benchmarks do not adequately capture.
The empirical evaluation is substantial, spanning multiple benchmarks and controlled ablations. Measuring total runtime, including compression overhead, provides credible evidence of the system’s practical efficiency benefits.
Critical weaknesses
The role of the LLM is insufficiently justified. These are well-defined graph problems with established solvers, and the conditions for safe compression can be checked and applied algorithmically. Once the request is mapped to a graph problem, it is unclear what substantive capability the LLM contributes beyond invoking existing procedures. Compression may itself cost more than direct solving, and the simple cost-prediction gate does not establish why managing this tradeoff requires an LLM-based agent.
The framework is heavily specialized through its tool library. It relies on 77 compression tools and 45 execution tools, including 44 task-specific compression tools. Much of its problem-solving capability is therefore supplied through manually engineered algorithms and correctness rules. The paper does not adequately justify this large LLM-facing toolset or establish how the approach extends beyond its supported problem families. Adding new tasks may require substantial additional tool construction and validation, limiting the framework’s generality.
Questions for authors
What is the main value of using an LLM here? With graph computation and correctness largely handled by the tools, does the model mainly learn to navigate the tool library rather than reason about graph structure? Could a non-LLM selector or planner achieve comparable benefits? Beyond the current benchmark, what distinctive LLM capability or broader research direction does this framework aim to develop?
What guided the design and granularity of the tool library, particularly the decision to encode so much task-specific knowledge in individual tools? Could the LLM instead help compose general graph primitives or construct reusable tools, reducing the need to manually support each problem family? How do you view the tradeoff between this possibility and the correctness guarantees provided by the current specialized library?
4 comments
Response to Reviewer TnZd, Part II
Q1. The value and broader purpose of using an LLM.
1. What does the LLM contribute once the graph problem is identified?
The LLM selects and orders compression tools for each graph instance. Identifying the task determines what to solve, but leaves open how to reduce the graph efficiently. Our response to W1 explains this role and provides the controlled comparison in Table 18.
2. Does the LLM use graph structure or merely select tools?
The LLM uses graph information to select and arrange tools. We provide a compact summary of each graph, including its size, density, degree statistics, and directionality, together with the request and tool descriptions (Appendix C.2). Fig. 9 shows different compression sequences across instances of the same task. Appendix H further shows why query information matters: on the same graph, compression benefits one query but increases the cost of another.
3. Could a non-LLM planner provide comparable benefits?
With the same inputs, tool library, and Gate, CAGR exceeds the better non-LLM result by 7.34 percentage points on ID tasks and 53.73 points on OOD tasks (Table R1 in our response to W1). Both alternatives plan faster but complete fewer requests successfully.
4. What broader capability does CAGR aim to develop?
Large-graph reasoning faces two practical challenges: understanding varied user requests and solving them efficiently.
a. User requests are diverse. They vary in wording, scenarios, and task parameters. LLMs can interpret these requests and select suitable graph tools across tasks.
b. Graph computation can be expensive. On large graphs, even basic structural queries can involve substantial computation. Selecting the correct solver is therefore only part of the problem. Applying compression also takes time, and using more compression tools can increase the total cost.
Our goal is to use the LLM’s understanding, planning, and generalization abilities to solve large-graph tasks correctly and efficiently.
Q2. Tool-library design and alternatives to manual specialization.
1. What guided the design and granularity of the tool library?
We define tools according to the conditions needed to preserve task answers. A graph operation can require different rules for different tasks. For example, merging parallel edges keeps the minimum weight for Shortest Path but sums capacities for Maximum Flow. These rules need separate definitions because using the wrong rule changes the answer. As explained in our response to W2.2, Appendix E provides the tool definitions and correctness requirements, and Table 17 groups the compression tools by their preservation mechanisms.
2. Could the LLM compose general graph primitives or construct reusable tools?
CAGR already uses the LLM to combine reusable graph operations. The library includes 33 task-general compression tools, and CCO trains the LLM Constructor to select and order tools for each request. Automatically constructing new tools is a direction worth further exploration. As detailed in Appendix E, new tools can be added through the same interface and reused across tasks once their applicability, answer preservation, and recovery rules are verified. In future work, we will study the efficiency and benefits of using LLMs to fully automate the creation of new tools.
3. How does CAGR balance greater automation with correctness guarantees?
CAGR automates toolchain planning while using tools with established correctness conditions. Generating new tools could support more tasks, but an incorrect compression step can remove information needed for the answer. Verifying a new tool for every request also adds computation costs.
We therefore establish preservation and recovery rules before using a tool, allowing this work to be shared across many requests. The same approach can support automatically generated tools: validate them before adding them to the library, then reuse them across compatible tasks.
I appreciate the substantial effort behind this work. I will raise my score.
My remaining concern is more conceptual. The LLM does not actually observe or reason over the billion-edge graph itself. Instead, it receives a compact graph summary and selects from a carefully engineered tool library. The actual graph computation, correctness guarantees, and compression stopping decisions are handled by specialized algorithms and the gate.
This makes me wonder what role the LLM fundamentally plays in solving the core problem. The task seems closer to cost-aware tool planning and algorithm selection, where a dedicated optimizer or learned cost model might be equally natural, or potentially more efficient. I understand the value of LLMs for interpreting natural-language requests and generalizing to new tool descriptions, but I am still not fully convinced that the graph compression problem itself particularly calls for an LLM.
This is more a question about the motivation and broader research significance of the approach than about its empirical effectiveness. I acknowledge the strong experimental results and the considerable work that went into this paper, even though I still have this conceptual reservation.
We sincerely thank you for your feedback and are glad to share our further thoughts.
Our work starts from three practical challenges in graph reasoning: (1) users’ intents can vary and may be implicit; (2) obtaining detailed structural information from a large graph can be expensive; and (3) compression may not be worthwhile because of its own cost, or even feasible when the task depends on global information. The LLM was our first choice because it can understand varied requests and use tool descriptions to plan across tasks. Our goal is to use these abilities while making graph reasoning more efficient.
A dedicated optimizer may perform better in a specific setting. Our motivation is to let users express graph reasoning goals in natural language without having to specify the algorithms and compression steps themselves. On large graphs, turning these requests into an efficient computation is a substantial challenge. CAGR studies how to connect the LLM’s request understanding and tool planning with reliable and efficient graph execution.
Actually, recently emerging System One models such as Jev offer an interesting direction [1]. They use natural-language state information to score predefined choices without generating a full textual response. Toolchain planning could be expressed as a sequence of such choices, with our tool contracts and Gate retained. This could reduce planning overhead while preserving semantic understanding. Whether it also preserves toolchain quality and transfer to unseen tasks would be valuable to investigate.
We appreciate this discussion. It points to a concrete extension of our work: learning more efficient planners that retain the flexibility needed for varied graph reasoning requests. If this exploration yields useful findings, we will include them in the next version of this manuscript.
[1] TypeSafe AI, Introducing System One Models & Jev, September 2026.
Response to Reviewer TnZd, Part I
We thank the reviewer for the constructive feedback. We address the Weaknesses and Questions separately. For the reviewer’s comments, we label the paragraphs W1–W2 and Q1–Q2 and summarize their individual concerns in numbered headings. For our responses, we use lowercase letters (a, b, etc.) where further explanation is needed.
W1. Unclear contribution of the LLM.
The LLM learns which compression tools to use and in what order for each request. Knowing the task does not determine the best toolchain: applying more compression tools can increase total execution time. CCO trains the LLM Constructor to choose and arrange tools using the request and graph information, while the Gate decides when to stop compression and run the solver.
With the execution tool, Gate, and backend fixed, CAGR reduces execution time by 30.57% compared with one fixed compression chain per task (Table 18).
We also compare two non-LLM planners trained on ID search results, using the same inputs, full tool library, and Gate as CAGR at evaluation. Retrieval selects an executor through text similarity and reuses a retrieved compression chain. The MLP scores tools step by step to build new chains. Both use the same rule-based parser to extract and bind request arguments.
Table R1. Non-LLM planners under the paper’s ID/OOD protocols, with CAGR results from the paper. Times are in s/ID case.
CAGR exceeds the better non-LLM result by 7.34 percentage points on ID tasks and 53.73 points on OOD tasks. The non-LLM planners spend less time planning, but complete fewer requests successfully.
W2. Heavy specialization and limited generality of the tool library.
1. Performance gains mainly come from the tools.
CAGR’s performance comes from both the tools and its ability to select, arrange, and use them effectively. Table 6 gives GCoder and Graph-TI the same complete tool library and graph backend. They achieve 79.00% and 75.42% success at 11.71 and 12.90 s, compared with 92.17% at 7.45 s for CAGR.
We further compare how these tools are used:
a. Fixed chains. Table 18 uses the same execution tool, Gate, and backend. CAGR reduces execution time by 30.57% compared with using one fixed compression chain per task.
b. Retrieval-based and learning-based planners. Table R1 uses the same tool library and Gate. These planners achieve 84.83% and 43.92% ID success, and 0.00% and 28.54% OOD success, compared with 92.17% and 82.27% for CAGR.
The tools do provide the graph algorithms and correctness guarantees. CAGR excels at learning how to select and combine them for each request, improving both task success and execution efficiency.
2. The large tool library is not clearly explained.
We have detailed the tool library and explained why and how we organize the tools in Appendix E:
a. Execution tools. Different graph settings require different solver choices. For example, weighted and unweighted Shortest Path use different algorithms, and tools must support the graph’s directionality. The library provides these choices for the supported tasks.
b. Compression tools. We provide both task-general and task-specific tools. Task-specific rules preserve the requested answer; for example, merging parallel edges for Shortest Path must retain the minimum weight. Table 17 reports tool counts by category and summarizes their preservation and recovery rules. Appendices E.3 and E.4 further provide proofs for representative task-general and task-specific tools.
3. Supporting new tasks may require substantial work.
a. Existing tools support new tasks. CAGR provides task-general compression tools that can be reused across tasks when their conditions apply. We also evaluate its ability to use new tools: thirteen compression tools and twelve execution tools are excluded from training and introduced through their descriptions at evaluation. CAGR achieves 82.27% success on unseen GraphLarge tasks without additional training (Table 4).
b. The library supports adding new tools. We have provided the tool specifications and correctness requirements in Appendices E.1 and E.2 to guide tool development and validation. Once added, these tools can be reused across compatible tasks and instances.