acceptodds
Under review as a conference paper at ICLR 2027

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

Abstract

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 speedup and improves average success rate by 15.53 percentage points over existing graph compression methods.

Primary area:
foundation or frontier models, including LLMs
Keywords:
Graph Reasoning, Large Language Models, Certificate Complexity, Graph Compression, Toolchain Optimization

Reviews

Among:
Shape:
1234this paper, Top 4%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.33 over 3 reviews, above 96% of the others.
Reviewer_TnZdOpenReview ↗
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
AuthorsOpenReview ↗

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.

MethodID success (%)OOD success (%)PlanningExecutionTotal
Retrieval-based Planner84.830.000.277.087.35
Learning-based Planner43.9228.540.105.625.72
CAGR92.1782.272.924.537.45

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.

AuthorsOpenReview ↗

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.

Reviewer_HESbOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper studies when graph compression reduces the total cost of tool-based LLM graph reasoning. It proposes CAGR, which combines a library of answer-preserving compression tools, an LLM constructor trained through MCTS and advantage-weighted policy improvement, and a learned gate that selects when to stop compression and execute the task. The authors introduce GraphLarge and report improved success rates and execution times over several graph-reasoning baselines, together with component ablations and evaluations on additional benchmarks.

Critical strengths

S1. This paper introduce Certificate graphs as executable representations that preserve task answers, and show that both their achievable sizes and construction costs vary substantially across graph instances.

S2. CAGR combines combines learned compression strategies with adaptive execution to determine how to construct Certificate graphs and when to stop compression.

Critical weaknesses

W1. The computational cost of constructing GraphLarge is not quantified. Reporting the time and resources required for graph sampling and reference-answer generation would help assess the practicality of reproducing the benchmark at billion-edge scale.

W2. The constructor’s optimization objective is only indirectly aligned with execution efficiency. Equation 6 rewards final compression and earlier reductions but does not account for the measured cost of individual tools. Consequently, toolchains with similar compression statistics may incur substantially different execution costs.

Questions for authors

Q1. What are the wall-clock time and computational resources required to construct GraphLarge, particularly for graph sampling and reference-answer generation?

Q2. Can you characterize the achievable limits of answer-preserving compression, either through theoretical bounds or comparisons with optimal reductions on tractable instances? How close do the learned toolchains come to these limits?

Q3 . How well does the reward in Equation 6 correlate with measured execution time? Have you compared it with a runtime-aware reward under the same search and training budget?

3 comments
AuthorsOpenReview ↗

Response to Reviewer HESb

We thank the reviewer for the constructive feedback. We address the concerns in order.

W1&Q1. GraphLarge construction and reproduction cost

GraphLarge was designed to account for and effectively control computational costs. We use compact CSR storage, and each sampled graph supports ten requests, sharing graph construction costs across queries. Following the protocol in Appendix D, we measured the offline graph and request generation and reference-solving costs at the GraphLarge scale reported in the paper:

Table R1. Measured GraphLarge construction time.

DomainGraph and request generationReference solving
Web14.06 h29.48 h
Transportation0.96 h2.46 h
Social5.57 h18.95 h
Citation5.09 h11.11 h

Peak memory across the recorded reference-solving jobs was 29.10 GiB, measured by sampled process-tree RSS. Appendix H provides a concrete example: two Shortest Path queries share a graph with 29.44 million nodes and 1.054 billion edges, requiring 5.63 GB of packed storage (Table 22).

W2&Q3. Compression reward and execution efficiency

We appreciate the reviewer’s insightful question, which directly relates to a challenge we encountered in our early experiments. We are very glad to share our findings and the reasoning behind our design.

a. Runtime rewards vary with execution conditions. During development, we found that LLM training, graph loading, and graph execution competed for resources when run in parallel. With four workers, graph scans slowed by 3–5×, and identical tool choices received different rewards. As a result, the runtime feedback used to train the LLM could differ substantially from execution time during inference.

b. We therefore decouple compression learning from time-based stopping. CCO trains the LLM to achieve large reductions early in the chain, while the Gate learns from measured prefix costs when further compression is worthwhile. On Transportation, Eq. 6 reward has a mean within-request Spearman correlation of +0.803 with negative total execution time, supporting its use for toolchain learning. Table 3 supports this design: removing the order term leaves final compression at 0.73 but increases time from 7.45 to 14.15 s; removing the Gate increases time to 10.04 s.

c. We compare both rewards under the same conditions. We retrained on Transportation under identical conditions, changing only the reward to log⁡(TDirect/Tchain)\log(T_{\mathrm{Direct}}/T_{\mathrm{chain}}). Full-chain time includes compression, execution, and recovery; invalid or incorrect toolchains retain the same penalties. CCO reduces execution time by 20.93%, with nearly identical task success.

Table R2. Reward comparison on the 300 Transportation test requests.

Training rewardSuccess (%)Execution time (s/case)
CCO reward88.004.08
Runtime reward87.675.16

Q2. Achievable compression and execution limits

We consider two objectives: maximizing compression and minimizing total execution time. Both depend heavily on the task and graph instance. We therefore study Shortest Path as an example.

a. Maximum achievable compression. We define maximum compression by the Certificate subgraph with the smallest ∣V∣+∣E∣|V|+|E|. We compare CAGR with this minimum Certificate subgraph on the Web Shortest Path validation set.

Table R3. Comparison with minimum Certificate subgraphs.

MethodAverage compression (%)Average total time (s)
CAGR51.6610.01
Minimum Certificate Subgraph99.9971.04

Finding and constructing the minimum Certificate subgraph adds computational cost. In our comparison, CAGR reduces total time by 85.91% despite achieving less compression.

b. Minimum total execution time. Finding the fastest compression strategy is difficult. Even the related problem of choosing distance-preserving shortcuts to minimize average shortest-path hop count is NP-hard [1]. Certificate tools provide valid operations, but their best combination, order, and stopping point depend on the instance.

For the two cases in Appendix H, the paper’s search protocol allows millions of candidate tool sequences. Guided by domain knowledge, we searched 1,200 promising sequences for each case.

Table R4. Comparison with the best tool sequences found.

CasePaper-selected depth replay (s)Best cost found (s)
A18.635 ± 0.17717.977 ± 0.167
B63.393 ± 1.16759.075 ± 0.193

The paper-selected strategies are only 3.66% and 7.31% above the best costs found. Table 18 also compares CAGR with Best Measured Prefix, which selects the fastest prefix after measuring every prefix of each generated chain. CAGR takes 7.45 s versus 6.76 s, a gap of 0.69 s per case, while reducing time by 25.80% over Full Chain and 40.30% over Static Prefix.

[1] Bauer et al., The Shortcut Problem—Complexity and Algorithms, JGAA 2012.

Thank you for your detailed response. The response addressed my concerns, and I will maintain my score.

Thank you for your thoughtful follow-up and constructive feedback. Your comments have helped us improve the paper’s technical clarity and presentation. We will incorporate the clarifications and additional results into the next version of the manuscript.

Reviewer_NDuzOpenReview ↗
Rating
4
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper investigates the computational efficiency of LLM tool use on massive graphs (up to 1.15 billion edges). While graph compression/reduction can decrease the workload of subsequent graph solvers, compression itself incurs non-trivial computation that may outweigh the execution savings.

Critical strengths

S1. The paper targets a critical, often-ignored bottleneck in agentic and tool-augmented graph reasoning: preprocessing and graph reduction can be computationally more expensive than solving the original problem directly. Framing this trade-off through instance-dependent Certificate graphs is intuitive, theoretically grounded, and practically significant.

S2. Evaluating LLM toolchain execution on graphs with over one billion edges across 28 tasks is impressive. Most existing LLM-graph benchmarks remain constrained to thousands or millions of edges; pushing this boundary provides a valuable evaluation ground for large-scale systems.

S3. The combination of single-call complete plan generation (avoiding multi-turn LLM inference latency) with an external, fast learned gate avoids high agentic overhead while maintaining runtime execution adaptivity. The inclusion of backward answer-recovery mappings ensures correctness guarantees for complex reductions (e.g., flow shortcuts, quotient graphs).

S4. The authors provide extensive comparisons against competitive baselines (GCoder, Graph-TI, GraphChain, GraphCogent), RL training ablations (GRPO, DPO), detailed feature ablations, and full mathematical preservation contracts for 77 compression primitives in the appendix.

Critical weaknesses

W1. While GraphLarge sources real-world topologies (WDC, Overture, Friendster, MAG240M), non-structural attributes such as edge weights and flow capacities are synthetically sampled uniformly from {1,…,50}. Real-world network flows, road congestion, and citation weights follow power-law or highly skewed distributions, which drastically alter bottleneck structures and the pruning effectiveness of contraction/filtering tools.

W2. CCO executes 128 MCTS evaluations per instance across 3 iterative rounds on billion-edge graphs. Running hundreds of graph algorithm iterations on billion-edge subgraphs during training requires immense CPU/memory resources. The paper provides inference latency but does not report the total computational budget (CPU/GPU core-hours) required to run the MCTS search and training pipeline.

W3. In Table 18, a Per-task Static Chain with the Gate already achieves an execution time of 10.73s (compared to 39.34s for Direct and 7.45s for CAGR). This indicates that the majority of performance gains stem from the pre-compiled C++/CSR tool library and the MLP gate, rather than fine-grained reasoning by the LLM. It remains slightly unclear how much the LLM's natural language comprehension contributes compared to a standard semantic parser paired with rule-based heuristics.

Questions for authors

D1. What is the runtime of GraphChain if it is provided with the exact same 77 pre-compiled Certificate compression tools as discrete tool calls (rather than dynamically writing reduction code)?

D2. What was the total wall-clock time and compute footprint (CPU hours, GPU hours, peak RAM) required to execute CCO across the 3 iterations of MCTS search and AWPI updates on GraphLarge?

D3. How sensitive are the Certificate compression ratios and the Compression Gate's decisions to the distribution of edge weights/capacities (e.g., uniform vs. Pareto/power-law distributions)?

D4. When evaluating on unseen tasks (OOD in Table 4), was the Compression Gate retrained on OOD prefix costs, or was the zero-shot/frozen Gate used directly? If transferred directly, how does the Gate predict k_d for unseen execution tools?

2 comments
AuthorsOpenReview ↗

Response to Reviewer NDuz

We thank the reviewer for the constructive feedback. We address the concerns in order.

W1&D3. Sensitivity to edge weights and capacities

CAGR’s structural compression tools use graph connections and query nodes to determine which nodes and edges to remove. Changing edge weights does not alter these structural conditions. We tested uniform, Pareto, and power-law edge weights on 60 Web Shortest Path validation requests, keeping graph topology and query nodes fixed.

Table R1. Results under different edge-weight distributions.

Edge-weight distributionCAGR time (s)
Uniform10.01
Pareto10.57
Power law9.87

All three distributions achieve 93.33% success and 51.66% compression. The Gate also selects the same stopping depth for each request. Execution time varies because edge weights can change the order and number of nodes visited by the solver.

We thank the reviewer for highlighting this issue and will consider more edge-weight and capacity distributions in future extensions of GraphLarge.

W2&D2. Computational cost of CCO training

CCO reduces CPU and GPU costs through three mechanisms:

a. Prefix reuse. MCTS reuses prefix graphs and execution records within each case. New branches compute only the remaining operations (Appendix B.1).

b. Shared graph storage. Requests on the same graph share its read-only CSR representation, avoiding repeated storage of the original graph.

c. Overlapping generation and execution. LLM requests are batched, and independent searches run asynchronously, allowing LLM generation and CPU graph execution to overlap.

Under the paper’s experimental settings, the three CCO rounds took 63.28 hours.

Table R2. Costs of three-round CCO training.

StageWall time (h)CPU core-hoursGPU-hoursPeak RAM (GiB)
MCTS search62.41689.82486.43208.14
AWPI updates0.877.486.9742.77
Complete CCO pipeline63.28697.30493.39208.14

W3. Contribution of the LLM beyond the tool library and Gate

a. The LLM understands varied natural-language requests. Graph reasoning requests vary in wording, scenarios, and task parameters. The LLM identifies the requested task and arguments, then uses graph information and tool descriptions to plan the computation.

b. LLM-based CAGR outperforms fixed-chain planning and other tool-based LLM baselines using the same tools. With the executor, Gate, and backend fixed, CAGR reduces time by 30.57% over a fixed chain per task (Table 18). With equal tool access, CAGR achieves 92.17% success versus 79.00% for GCoder and 75.42% for Graph-TI (Table 6), and outperforms GraphChain by 7.53 percentage points with a 5.38× speedup on Transportation (Table R4).

c. CAGR also outperforms non-LLM planners in success rate and generalization to unseen tasks. Both planners learn from ID search results and use 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 R3. Non-LLM planners under the paper’s ID/OOD protocols, with CAGR results from the paper. Times are in s/ID case.

MethodID success (%)OOD success (%)PlanningExecutionTotal
Retrieval-based Planner84.830.000.277.087.35
Learning-based Planner43.9228.540.105.625.72
CAGR92.1782.272.924.537.45

D1. GraphChain with the same compression tools

Due to the rebuttal time limit, we retrained GraphChain on Transportation using its original training protocol and the same Certificate Compression Tools as CAGR.

Table R4. Transportation ID results: 300 requests, five runs; CAGR from the paper.

MethodSuccess (%)Time (s)
GraphChain79.8021.27
CAGR87.333.95

CAGR achieves 7.53 percentage points higher success and a 5.38× speedup. GraphChain rewards information reduction and fewer tool calls, but does not explicitly weigh further compression costs against subsequent execution savings. It can therefore spend time on compression that brings little benefit. CAGR addresses this through learned toolchain planning and adaptive stopping.

D4. Frozen Gate transfer to unseen tasks and tools

The Gate is trained on ID prefix costs and applied to OOD tasks without retraining. OOD costs are not used for training or model selection. The tool-complexity feature is calculated from the tool description, not predicted by the Gate. Equation 22 defines:

κd(T)=log⁡(1+fT(nd,md,ξq)),\kappa_d(T)=\log\left(1+f_T(n_d,m_d,\xi_q)\right),

where fTf_T is the tool’s complexity expression, evaluated using the current graph size and query parameters. Unseen tools therefore use the same feature format without requiring measured OOD runtimes.

Thanks for the detailed responses and I will keep my score.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.