- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper presents GraphFinder, a pipeline for identifying graph problems implicit in natural-language descriptions, mapping them to ontology-grounded graph formulations, and generating executable solvers. The system combines graphizability filtering, ontology selection, typed slot filling, and execution-based verification. The experiments show that recognizing the underlying graph-problem class is substantially easier than producing a semantically faithful formalization. However, I have significant concerns about the practical significance, model selection, scalability evaluation, and presentation quality.
Critical strengths
- The paper decomposes the task into graphizability detection, problem-class identification, semantic grounding, and code execution, making different failure modes relatively easy to analyze.
- The ontology-grounded formulation and execution gate provide a useful framework for evaluating whether an LLM-generated graph formalization is runnable.
- The paper appropriately distinguishes execution success from semantic correctness and includes a stricter reference-equivalence evaluation rather than treating successful execution as sufficient evidence.
Critical weaknesses
-
Lack of novelty and unclear practical significance. The central benchmark studies whether LLMs can recognize latent graph problems in natural language and solve them. However, it is unclear why this problem has sufficiently broad or important real-world relevance, or which users or applications would specifically benefit from this capability. The paper does not establish a compelling use case beyond the benchmark itself.
-
The evaluated models are outdated. The model comparison is limited and includes relatively old systems, such as Qwen2.5 from 2024. Given the rapid development of LLMs, the reported results may not reflect the capabilities of current frontier or recent open-weight models. This weakens the conclusions about the general difficulty of the task.
-
No meaningful evaluation of graph scale. The paper does not report the number of nodes and edges in its graph instances, nor does it evaluate substantially larger graphs. Current LLMs can support context windows exceeding one million tokens, so it would be important to test whether the proposed approach can handle graphs with tens of thousands of nodes or similarly large structured inputs. Without such experiments, the scalability claims are difficult to assess. In addition, some figures and tables are difficult to read and could be presented more clearly.
Questions for authors
same as weakness
3 comments
Official Comment by Reviewer yWb4
Thank you for the detailed response and additional experiments. However, I still have two concerns.
First, evaluating only one additional model, DeepSeek-V4.1-Flash, provides limited evidence that the findings generalize across current frontier models.
Second, experiments with at most 500 nodes do not sufficiently establish scalability for networks containing thousands or tens of thousands of nodes. The reported truncation may reflect an overly restrictive output-token budget, compounded by embedding the full edge list in the generated program. Without demonstrating that the output budget was adequate or evaluating external data loading, this failure does not establish an inherent scalability limit.
I appreciate the authors’ efforts, but these concerns remain insufficiently addressed. I will therefore maintain my current score.
We thank the reviewer. Both concerns prompted new experiments, reported below and incorporated into the revision.
1. Model generalization. We added DeepSeek-V4-Pro, the current flagship on our API access (thinking disabled for comparability; identical prompts and criteria). Full replication: identification on 200 GA-Implicit 0.845 top-1 / 0.970 top-5; equivalence tier predicted route 1.000 identification (alias-normalized) / 0.95 execution / 0.86 reference-correct - the best tier result of any model; grounded E2E on the seed-42 subset 0.64. The evidence now spans four strong models across 2024-2026:
| Model | Ident. top-1 | E2E (seed-42 / 200) | Tier ref.-correct |
|---|---|---|---|
| deepseek-chat (orig.) | 0.880 | 0.84 / 0.715 | 0.80 |
| GLM-4.5-Air | 0.945 | 0.680 / - | - |
| DeepSeek-V4.1-Flash | 0.885 | 0.680 / - | 0.72 |
| DeepSeek-V4-Pro | 0.845 | 0.640 / - | 0.86 |
The pattern is stable across all four: identification 0.845-0.945, grounded E2E 0.64-0.715, tier 0.72-0.86, with formalization fidelity - not identification - the persistent bottleneck; the newest flagship improves the tier but does not close the gap. We state openly that both current models come from one provider, since that is where our API access lies.
2. Scalability. The reviewer's hypothesis about the 500-node failure is correct, and we now demonstrate it, then go further with the external-data-loading protocol they suggested.
(a) Budget diagnostic: rerunning the same inline 500-node protocol with a 16k completion budget (vs. 8k in E10) yields 4/6 reference-correct (shortest path 2/2, max flow 2/2) with programs of ~19k characters, versus 0/6 before. The E10 failure was a budget artifact, not a capability limit; the revision now says exactly this and makes no inherent-scalability claim for the inline protocol.
(b) Data-by-reference at 1k-10k nodes: instance data is written to instance.json next to the solver; the description states the problem and the file schema only; the generated program loads the file at runtime. Exact NetworkX references; 3 classes x {1000, 5000, 10000} nodes x 2 instances (up to ~30k edges):
| Nodes | Ident. | Shortest path | Max flow | Min-cost flow |
|---|---|---|---|---|
| 1,000 | 6/6 | 2/2 | 2/2 | 0/2 (1 repair: 1/2) |
| 5,000 | 6/6 | 2/2 | 2/2 | 0/2 (1 repair: 1/2) |
| 10,000 | 6/6 | 2/2 | 2/2 | 0/2 (1 repair: 1/2) |
Identification is perfect at every scale, generated programs stay constant-size (~1k characters) regardless of graph size, and shortest path and max flow are reference-correct end-to-end at 10k nodes. Minimum-cost flow fails on all six instances with a single scale-independent bug (a networkx demand-API misuse), of which half are fixed by one bounded repair round with the traceback as feedback (the paper's protocol); overall 15/18 after repair. The residual bottleneck is class-level code-generation quality, not scale. We do not claim beyond 10k nodes and report this boundary explicitly.
Both experiments are in the revised Appendix E8/E10 with per-problem records. We hope this addresses the two concerns; we are grateful for the push, which materially sharpened the scalability claims.
We thank the reviewer for the assessment. During the discussion period we ran two new experiment groups addressing the model-recency and graph-scale concerns; the revision includes both, with a revision log.
W1 (practical significance). The revision adds an explicit users paragraph to the Introduction: (1) operations analysts and engineers who hold a domain description (a delivery network, a crew roster, a pipe system) and need to know whether an established graph algorithm applies before investing in custom optimization — our results show where human review belongs (identification is largely solved at 0.88+; faithful formalization is the bottleneck); (2) builders of optimization assistants (the OptiMUS/ORLM line), for whom a trustworthy admission-and-formalization front end determines whether downstream solvers can be trusted; (3) settings where the most valuable decision is the negative one — that no useful graph abstraction exists, where a forced formulation would be silently wrong; our negative and adversarial tiers and the abstention mechanism (0/60 trap falls) target exactly this. Unlike graph-LLM benchmarks that reason on already-given graphs, our benchmark evaluates the earlier abstraction decision that all of those systems presuppose.
W2 (outdated models). A fair concern — our main model is API-served and changes silently over time; the revision discloses this and designates per-problem records as the authoritative artifact. We reran the main experiments with the current DeepSeek-V4.1-Flash (thinking disabled for like-for-like comparability; prompts, temperatures, and acceptance criteria unchanged):
The main conclusions persist on a current model: identification is strong, reference-correct end-to-end success remains the bottleneck, and grounding + execution gating remains the best configuration (new paragraph in Appendix E8; Model-scope limitation updated). A thinking-enabled variant with a larger budget scored 0.775 top-1 — lower, with frequent format non-compliance after long reasoning. We agree broader coverage of current open-weight frontier models is valuable and will extend E8 in the camera-ready.
W3 (graph scale). Three additions. (1) The equivalence tier's scale is now explicit (Appendix E6): 10 classes × 10 instances, 5–12 nodes (mean 7.7), 2–23 edges — deliberately small so exact references (Dijkstra, preflow-push, network simplex, exhaustive search) and class-specific feasibility checks are computable. (2) New scale stress test (Appendix E10): shortest-path / max-flow / min-cost-flow instances at 50/200/500 nodes with exact NetworkX references, full pipeline unchanged:
Identification is scale-robust (perfect even at 500 nodes with 18.5k-character inputs); with an adequate generation budget the pipeline solves 200-node instances exactly; the 500-node failure mode is completion-token truncation when generated programs inline the full edge list — an honest boundary that motivates the schema-vs-data separation already in our design: the formalization binds what the data is, and at scale the data should reach the generated solver by reference rather than inlined in prompt and program. We make no tens-of-thousands-of-nodes claim; the revision states this explicitly. (3) Presentation: figure captions and reading order clarified in the revision; fonts enlarged and the densest tables split in the camera-ready.