acceptodds
Under review as a conference paper at ICLR 2027

GraphFinder: From Problem Recognition to Ontology-Grounded and Executable Graph Formalization

Abstract

Many real-world optimization problems appear as unstructured natural-language descriptions that do not mention graphs explicitly, and it is often unclear whether they can be formalized as classical graph problems and solved by established graph algorithms. This paper asks whether LLMs can reliably transform such descriptions into executable, ontology-compatible graph formalizations. We propose GraphFinder, which first determines whether a useful graph abstraction exists from a natural language optimization problem, then selects and instantiates a classical formulation from a curated graph problem ontology and returns an executable solver. The system uses typed slot filling to constrain formalization, treats verbal LLM verification only as advisory, and uses program execution plus machine-checkable output conditions as its acceptance gate. We explicitly distinguish executable success from semantic faithfulness and add a 100-instance equivalence tier with independent reference solvers. On the 520-problem GraphAbstraction-Bench we build, 55-way identification reaches 0.880-0.925 top-1 accuracy, while free-form executable end-to-end success is only 0.30-0.37. Ontology grounding with execution raises executable end-to-end success to 0.84 on the paired 50-problem subset and 0.715 on all 200 implicit optimization problems. On the 100-instance equivalence tier with concrete numeric data and independent reference solvers, reference-correct end-to-end success is 0.80 with predicted classes and 0.72 with oracle classes.

Primary area:
optimization
Keywords:
graph formalization, large language models, combinatorial optimization, graph algorithms, executable formalization

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_yWb4OpenReview ↗
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
  1. The paper decomposes the task into graphizability detection, problem-class identification, semantic grounding, and code execution, making different failure modes relatively easy to analyze.
  2. The ontology-grounded formulation and execution gate provide a useful framework for evaluating whether an LLM-generated graph formalization is runnable.
  3. 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
  1. 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.

  2. 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.

  3. 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

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):

ExperimentV4.1-FlashOriginal (deepseek-chat)
Identification, 200 GA-Implicit0.885 top-1 / 1.000 top-50.880 / 0.970
Grounded E2E (seed-42, n = 50)0.680.715–0.84 (multiseed mean 0.747)
Equivalence tier, predicted routeident 1.000 / exec 0.81 / 0.720.90 / 0.87 / 0.80

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:

NodesEdgesIdent.Exec.Obj. match
501131.000.830.83
2004641.001.001.00
5001,1651.000.000.00

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.

Reviewer_yWb4OpenReview ↗

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:

ModelIdent. top-1E2E (seed-42 / 200)Tier ref.-correct
deepseek-chat (orig.)0.8800.84 / 0.7150.80
GLM-4.5-Air0.9450.680 / --
DeepSeek-V4.1-Flash0.8850.680 / -0.72
DeepSeek-V4-Pro0.8450.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):

NodesIdent.Shortest pathMax flowMin-cost flow
1,0006/62/22/20/2 (1 repair: 1/2)
5,0006/62/22/20/2 (1 repair: 1/2)
10,0006/62/22/20/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.

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

This paper introduces GraphFinder, a framework for converting natural-language optimization problems into ontology-grounded graph formulations and executable solvers. The pipeline includes graphability filtering, graph-problem identification over a 55-class ontology, typed slot filling, and execution-based verification. The authors also introduce GraphAbstraction-Bench and report a notable gap between graph-problem identification and end-to-end formalization: identification reaches 0.88–0.925 top-1 accuracy, while free-form executable E2E is only 0.30–0.37.

I find the problem interesting and the benchmark potentially useful. However, I have several concerns about the evaluation and the strength of the methodological contribution.

Critical strengths
  1. The paper studies an interesting and relatively underexplored problem: discovering a graph abstraction from natural-language optimization problems rather than assuming that the graph is already given.
  2. The separation of identification, formalization, and execution is conceptually useful.
  3. The benchmark evaluates more than classification and includes negative/adversarial examples and a 100-instance reference-equivalence tier.
Critical weaknesses
  1. Executability is a weak proxy for correct formalization. The main execution gate only checks whether the program runs and produces the required JSON output. It does not verify semantic equivalence to the original problem. More importantly, the paper's own E7 analysis finds that 36/40 execution-success cases are judged semantically incorrect. This makes the interpretation of the main executable E2E results unclear. I think the reference-equivalence evaluation should play a much more central role.
  2. The verbal-verifier experiment appears to evaluate the wrong target. The verbal verifier is designed to check semantic properties such as constraint preservation and extra freedom, but its usefulness is evaluated by whether PASS/FAIL predicts execution success. Since semantically incorrect programs can still execute successfully, this does not establish that verbal verification is uninformative. A more appropriate test would examine whether verifier judgments predict reference correctness on the equivalence tier.
  3. The claimed identification–formalization gap is not fully isolated. The paper compares 0.88–0.925 accuracy from a dedicated 55-way classification setting with 0.30–0.37 free-form E2E performance. However, in the free-form setting, correct class identification itself drops to only 41.5%. Thus, part of the gap may come from the different prompting/setup rather than formalization difficulty alone. An oracle-class comparison between free-form and grounded formalization would provide cleaner evidence.
  4. Two reported aggregates need correction. Table 6 gives 6/23 correct ontology-targeted predictions and 37/37 correct abstentions, implying 43/60 overall correct outcomes, rather than the reported 29/60. Appendix B.2 reports McNemar discordance of 35:0 for grounded-plus-execution versus free-form-plus-verbal, but Table 10 gives 42/50 versus 15/50 successes, so the difference between discordant counts must be 27. Please regenerate these totals and paired tests from the underlying records and confirm whether the conclusions change.
  5. The methodological novelty is somewhat limited. The system combines an ontology, retrieval/LLM identification, typed slots, code generation, and execution checks. I find the task definition and benchmark contribution stronger than the algorithmic novelty. PEE is also weaker than the LLM identifier and even trails BM25+ at top-1 retrieval.
Questions for authors
  1. On the 100 reference instances, how do free-form and typed-grounded formalization compare when given the same class, original description, generation budget, and correctness checks? Does verbal-verifier PASS/FAIL predict reference correctness on this tier?
  2. Can you regenerate the Table 6 overall score (6/23 and 37/37 imply 43/60, not 29/60) and the Appendix B.2 McNemar discordance (35:0 is inconsistent with 42/50 versus 15/50) from the underlying records? Do any conclusions change?
  3. Why do predicted classes outperform oracle classes in Table 7, and which classes, instance sizes, reference algorithms, and feasibility checks does the reference tier cover?
3 comments

Thanks. Both aggregate inconsistencies were real errors and have now been corrected. We also ran the two experiments you proposed.

W1 (executability proxy; E6 central). Agreed. The experiments introduction now declares the reference-equivalence tier the central semantic evaluation, with reference-correct E2E as the primary quality measure; tier numbers now lead the abstract and conclusion (0.80 predicted / 0.76 oracle; false acceptance 0.080 / 0.062). The 36/40 E7 figure is a benchmark property (GA-Implicit lacks concrete instance data, so programs emit demonstrative instances), not evidence the gate is uninformative — it is why the tier exists. Sec. 3.7 formalizes the strengthened gate: instance-binding checks, per-family feasibility certificates, second-solver cross-checks.

W2 (verifier tested on the wrong target). Fair point — the original calibration only supports gating executability. We ran your proposed test (verifier on the tier's slot-fill formalizations, joined with reference correctness):

VerdictnP(exec ∣ verdict)P(ref. correct ∣ verdict)
PASS510.7840.725
FAIL490.9590.878

Verdicts are anti-correlated with correctness (FAIL 0.878 vs PASS 0.725; the same inversion holds for execution) — a stronger negative result, now in Appendix E2. Caveat: verdicts from fresh same-prompt formalizations (current API), joined with stored outcomes. The verifier remains an optional repair signal only.

W3 (gap not isolated). We ran your oracle-class comparison on the 100-instance tier — same class, descriptions, budget, and checks (same-session reruns):

Route (oracle class)ExecutionReference-correct
Free-form0.880.64
Grounded (typed slots)0.820.75

Even given the class, free-form reaches only 0.64, concentrated in flow (1/20 vs 14/20 grounded): runnable formalizations that silently violate capacity/conservation structure. This isolates formalization fidelity from identification and triangulates with E3 (flow constraint coverage 0.341) and E6 false acceptance. Free-form naming also remains far lower in deployment (0.31–0.415 vs 0.880 dedicated).

W4/Q2 (two aggregate errors). Both confirmed and fixed. (1) Table 6: the two denominators were swapped — correct values are ontology-targeted 6/37 (0.162) and correct abstention 23/23; overall 29/60 and trap-fall 0/60 were already correct; the correction strengthens the conclusion (traps more misleading than printed, abstention perfect). (2) Appendix B.2: the "35:0" came from a stale v1 file (FF+verbal 7/50) while the tables report v2 (15/50); correct discordance is 28:1 (χ² = 23.3, p = 1.4 × 10⁻⁶), and 26:0 is confirmed (χ² = 24.0, p = 9.4 × 10⁻⁷). Your arithmetic (net difference 27) is confirmed. (3) Audit addendum: the factorial FF+execution cell (0.36) had no per-problem records; we replaced it with the same-protocol rerun 0.26 (interaction +0.56), and Table 2's FF row now uses the record-backed rerun (0.310 / 0.275), noting the earlier aggregate (0.415 / 0.370). Every conclusion survives with equal or larger margins; per-problem records are now authoritative.

W5 (novelty). Agreed; task + benchmark + findings are primary, and the system contribution is the decomposition and its failure signals (now stated explicitly). PEE honestly trails BM25+ at top-1 (0.310 vs 0.430) but leads P@5 (0.755 vs 0.735) and family P@1 (0.715 vs 0.615); its role is a controlled structure probe (E9) and a practical shortlist, not SOTA retrieval.

Q1. Answered by the W2/W3 experiments: same class, budget, checks — free-form 0.64 vs grounded 0.75 reference-correct (deficit in flow, 1/20); verifier PASS/FAIL does not predict reference correctness (0.725 vs 0.878, anti-correlated).

Q3 (predicted vs. oracle). An annotation artifact, now fixed: ten instances labeled minimum_vertex_cover vs ontology key vertex_cover — the predicted route was scored incorrect by exact string match although all ten solutions are reference-correct (alias-normalized identification 1.000); the oracle route failed template lookup on all ten. Rerunning them with the correct key gives oracle reference-correct 0.760 (exec 0.810, obj match 0.780); a same-era full rerun gives 0.75, confirming it. The residual 0.80 vs 0.76 is within noise. Tier composition (now in Appendix E6): 10 classes × 10 instances, 5–12 nodes, 2–23 edges; exact references (Dijkstra, preflow-push, network simplex, exhaustive search) with class-specific feasibility checks. New scale stress test (Appendix E10): identification stays 1.0 up to 500 nodes; execution and objective match are perfect at 200 nodes; the 500-node failure is completion-token truncation from inlining ~1,165 edges.

Thank you for acknowledging the issues and conducting the additional experiments. Prioritizing reference-equivalence evaluation and adding the oracle-class comparison are meaningful improvements. The distinction between execution success and semantic correctness is now much clearer.

Before updating my assessment, I would appreciate clarification on three points:

Verifier–outcome alignment. You mention that verifier judgments come from fresh formalizations and are joined with stored outcomes. Were each verifier judgment and its reference-correctness label computed on the exact same generated formulation/code, rather than merely the same problem? If the outputs differ, the reported association would not establish whether the verifier predicts semantic correctness. Please clarify this pairing and, if necessary, evaluate both on the same outputs.

Consistency of corrected results. The response identifies several issues involving denominators, experiment versions, missing per-instance records, and label aliases. Please provide a consolidated table of the final corrected results, identifying which values replace the original results and which come from new runs. Please also confirm that the revised tables and paired statistical tests use consistent per-instance records.

Uncertainty in the new comparisons. For the oracle-class reference-correctness comparison of 0.64 versus 0.75, please report the paired outcome counts and an appropriate uncertainty estimate or paired test. Likewise, please support or qualify the statement that the remaining 0.80 versus 0.76 difference is within noise.

These clarifications would help determine whether the revised evaluation adequately resolves my original concerns. I retain my rating pending clarification.

We thank the reviewer and answer the three clarifications; the first prompted a new, fully aligned experiment reported below.

1. Verifier-outcome alignment. Correct: the previous analysis joined verdicts on freshly regenerated formalizations with outcomes from the stored run - same problems, not same artifacts. We agree this weakens the claim and reran it fully aligned. For each of the 100 instances: generate one slot-fill formalization; the verifier judges it; the solver is generated from that same formalization and executed; reference correctness (objective match + solution check) is computed on that output.

VerdictnP(ref. correct)P(exec)
PASS550.5820.618
FAIL450.7110.822

Paired counts: PASS and correct 32, PASS and incorrect 23, FAIL and correct 32, FAIL and incorrect 13. The verdict remains non-informative-to-inverted: P(ref. correct given PASS) = 0.582 is below both the marginal rate (0.64) and P(ref. correct given FAIL) = 0.711; execution shows the same inversion (0.618 vs 0.822). The design choice - verifier as optional repair signal, never an acceptance gate - is supported under full alignment, and the revision replaces the cross-artifact table with this one.

2. Consolidated corrected results. Overall (29/60), trap-fall (0/60), and the 26:0 McNemar (chi2 = 24.0, p = 9.4e-7) were confirmed unchanged; the corrections are:

ResultOriginalCorrectedBasis
Ontology-targeted top-10.261 (6/23)0.162 (6/37)records; denominators swapped
Correct abstention37/3723/23same records
McNemar vs FF+verbal35:028:1 (chi2 = 23.3, p = 1.4e-6)v2 records (35:0 from stale v1)
Factorial FF+exec cell; interaction0.36; +0.440.26; +0.56protocol-identical rerun (no records before)
FF+execution (n = 200)0.415 / 0.3700.310 / 0.275record-backed rerun
E6 oracle exec / obj / ref / false-acc.77/.74/.72/.065.81/.78/.76/.062alias-fix rerun; same-era rerun (0.75) confirms

Headline ranges propagated accordingly (FF E2E 0.26-0.37; oracle reference-correct 0.76). We confirm every revised table and paired test is computed from the per-problem records in the supplement; the one previously aggregate-only number (FF+exec cell) is now rerun-backed, and this erratum table appears in the revision.

3. Uncertainty in the new comparisons. Oracle-class comparison (same-session reruns, n = 100): free-form 64 vs grounded 75 reference-correct; discordant 20:9 in grounded's favor, chi2 = 3.45, p = 0.063 - not significant at 0.05 overall. The advantage is concentrated in the flow family (1/20 vs 14/20; discordant 13:0, chi2 = 11.1, p = 0.0009); touring slightly favors free-form (8 vs 6, discordant 4:6, n.s.). Grounding buys constraint fidelity where capacity and conservation structure lives; outside flow the routes are statistically indistinguishable, and the revision now says so. For predicted vs corrected-oracle (0.80 vs 0.76): discordant 12:8, chi2 = 0.45, p = 0.50 (13:8, p = 0.38 vs the same-era oracle rerun), so "within noise" is supported and is now stated with these statistics.

All three items are in the revision. We are grateful for the scrutiny that materially improved the correctness of the reported results.

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

The paper investigates the problem of transforming natural-language descriptions of optimization problems into executable, ontology-grounded graph formalizations using LLMs. The key empirical insight is the identification-formalization gap: LLMs excel at identifying the abstract graph problem category (88.0%–92.5% 55-way classification accuracy), but struggle to generate unconstrained, executable, and semantically faithful code directly from natural language (30%–37% free-form end-to-end success).

Critical strengths

S1. The paper clearly articulates and empirically proves a significant phenomenon: recognizing the class of a graph problem is vastly easier for LLMs than instantiating a faithful, executable formalization. Decoupling identification from formalization is a very sensible formulation.

S2. The paper provides compelling empirical evidence (Tables 10 & 12) showing that verbal LLM self-verification is largely uninformative as a hard gate (conditional execution success rates for LLM PASS vs FAIL are virtually identical at ~90% vs ~89%). Replacing verbal critique with a programmatic execution gate is well-motivated and convincingly validated.

S3. The construction of GraphAbstraction-Bench (520 problems covering explicit, implicit, negative, and adversarial cases) and the inclusion of a 100-instance reference-equivalence tier with ground-truth numeric solvers provides a benchmark for evaluating graph formalization quality.

S4.The authors include thorough structural controls (permutation tests, lexical overlap baselines, structural signature Hamming distance correlation) and multi-model replications (GLM-4.5-Air, Qwen2.5-7B, smaller models), demonstrating strong empirical rigour.

Critical weaknesses

W1. The Graphizability Filter uses a simple 4-feature logistic regression with handcrafted heuristics (e.g., relation density, transitivity proxy). PEE is a standard fine-tuned dual encoder (Sentence-BERT derivative). Furthermore, Table 4 shows that direct LLM zero/few-shot identification (88.0%–92.5% top-1) significantly outperforms PEE (31.0% top-1), rendering PEE mostly a prompt-token compression tool rather than a superior accuracy driver. Typed slot filling is a standard application of JSON-schema constrained decoding.

W2. Table 3 shows that while grounded formalization improves objective fidelity (0.980 vs. 0.939) and eliminates unstated extra freedom (0.980 vs. 0.847), its constraint coverage drops drastically (0.565 for grounded vs. 0.913 for free-form). Rigid ontology templates force LLMs to drop complex or domain-specific side constraints that do not fit the fixed schema.

W3. In Table 5, applying the hard threshold (≥0.5) for the graphizability filter reduces downstream executable E2E performance from 0.715 to 0.525 by rejecting 44 valid graphable implicit problems. The filter appears overly conservative, penalizing sparse or non-transitive graph problems.

Questions for authors

D1. Given that 90% of execution successes on GA-Implicit generate arbitrary mock data due to missing numeric inputs (Table 18), how do you propose refining the acceptance gate so that execution checks verify semantic instance fidelity rather than syntax/runnable completion?

D2. Grounded formalization achieves only 0.565 constraint coverage (Table 3). How can the typed slot-filling templates be extended to capture side constraints (e.g., time windows, piecewise costs) without breaking ontology compatibility?

E3. Since direct LLM zero-shot classification achieves 88.0% top-1 accuracy compared to PEE's 31.0%, in what operational settings would a user choose PEE over direct LLM identification, beyond prompt token saving?

3 comments

We thank the reviewer for a careful reading. Several raised issues are results we report ourselves as findings or limitations; we treat them as measured design boundaries. New analyses run during the discussion period are reported inline and included in the uploaded revision (revision log maps every change).

W1 (component novelty). We agree each module is a standard building block in isolation; the revision states this explicitly (Introduction). The contribution is the decomposition — admission / identification / typed formalization / execution-based acceptance, each with a restricted output space and a machine-checkable failure signal — plus the findings it enables (identification–formalization gap; grounding × execution interaction +0.56; verbal-verification miscalibration) and GraphAbstraction-Bench. Filter: deliberately simple and auditable; its role is admission control (91.0% accuracy, 0.988 precision), with abstention driven by the semantic compatibility check (37/37 correct abstentions, 0/60 trap falls). PEE: we agree and state (Sec. 5.4) that direct LLM identification is stronger at top-1; PEE is a structural shortlist, and the claim is that contrastive training injects topology (P@1 0.310 vs 0.170 frozen backbone; structure correlation ρ = 0.355 vs 0.146 frozen / 0.164 bag-of-words; permutation p < 0.0002). Typed slot filling vs JSON-schema decoding: templates are a semantic schema of typed graph roles; the LLM chooses bindings, not a formalism — this restores identification discipline (naming 0.31–0.415 free-form → 0.880 grounded).

W2 (constraint coverage 0.565). Agreed, and reported as a central cost. New per-family breakdown (Appendix E3): constraint coverage Flow 0.341, Touring 0.475, Path 0.639, Matching 0.688, Covering 0.708; objective fidelity ≥ 0.917 everywhere. The two deficit families are exactly where E6 concentrates false acceptance — template undercount and gate under-checking share a cause and a location. Also, free-form's higher coverage (0.913) co-occurs with unstated extra freedom (0.847) and naming ≤ 0.415, hence E2E 0.26–0.37 vs 0.715 grounded: coverage alone is not the right metric. Unrepresentable mandatory constraints trigger abstention (37/37 correct), not silent dropping.

W3 (filter conservativeness). Agreed; we ran the promised attribution on all 200 problems (new Appendix E5 tables). (a) Per-family rejection: covering 20/49, flow 11/32, path 9/41, touring 4/42, matching 0/36; classes rejected in every instance are sparse-structure ones (shortest path, max flow, widest path, vertex cover, max independent set, ...). (b) Per-feature (36 rejected): relation density 0.177 vs 0.473 accepted; pairwise-constraint fraction 0.019 vs 0.353; counterfactually restoring relation density alone flips 26/36 above the threshold (vs 20/17/5 for the other features) — the dominant driver, confirming your diagnosis quantitatively. (c) Admission-set sweep (ROC-AUC 0.970): precision 1.000 at t = 0.5 with recall 0.756; ambiguous forwarding is the recommended default (183/200 accepted, E2E 0.650 vs 0.715 no-filter). Disclosed: only 25/44 rejections recur under re-extraction (LLM extraction is non-deterministic over time), which further motivates blending the logistic features with a calibrated LLM-scored graphizability judgment.

D1 (acceptance gate). The 90% figure is a benchmark property (GA-Implicit descriptions lack numeric data, so programs build demonstrative instances), reported as a first-class finding (E7); E6 exists because of it. The revision formalizes the strengthened gate (Sec. 3.7): instance-binding check, per-family feasibility certificates, second-solver cross-check; E6 already instantiates the latter two (reference-correct 0.80/0.76, false acceptance 0.080/0.062).

D2 (side constraints). Sec. 3.6 adds three compatibility-preserving mechanisms: typed auxiliary-constraint slots (abstain on unsupported types), compositional templates G₁ ⊕ G₂, and post-hoc executable checks recorded in the Semantic Anchor Table so nothing is silently dropped.

Question (when is PEE preferred?). Beyond token savings: (1) growing ontologies — prompts scale linearly in ∣O∣ (227.2k tokens per 200 queries at 55 classes) while retrieval is constant-cost; (2) deterministic, model-independent index for auditing (identification is capacity-dependent: Qwen2.5-7B 0.565); (3) weak/local models — a top-20 shortlist keeps family coverage (P@5 = 0.920) and runs on CPU in ≈ 1.3 s; (4) cost at scale — k = 20 hybrid 0.865 vs 0.880 top-1 at ~38% of the prompt.

Thank you for your detailed response and the new experiments added in the revision. I appreciate your honesty in analyzing these limitations. However, while the new data makes the analysis more solid, it also confirms several weaknesses in the proposed method that are still not solved:

  1. In terms of filter instability and bias (W3), your new results confirm that the relation density feature hurts sparse graph problems (like shortest path and max flow), rejecting them in every instance. More importantly, you mentioned that only 25/44 rejections happen again under re-extraction because the LLM feature extraction is not deterministic. This is a big issue. In W1, you said the logistic regression filter is good because it is simple and auditable. However, if the input features extracted by the LLM are unstable, the whole filter becomes unreliable. Also, just lowering the threshold does not fix the bias against sparse graphs.

  2. There is no experimental results for the new template mechanisms (W2 & D2). The new results show very low constraint coverage in Flow (0.341) and Touring (0.475). To solve this, you added three methods in Sec. 3.6 (auxiliary slots, G1⊕G2, and post-hoc checks). These ideas make sense, but there are no experiments showing they actually work on the benchmark. Saying that the system will correctly abstain when facing complex side constraints just shows that the fixed templates are still too rigid for real-world problems.

  3. PEE is still not very useful at the current scale (W1 & E3). I understand PEE can save tokens if the ontology grows very large in the future. But in this paper, there are only 55 classes (~1.1k tokens per query). With modern LLMs (which support long context and prompt caching), this token cost is very small. Since the k=20 hybrid still has lower accuracy (0.865) than direct LLM classification (0.880–0.925), PEE actually hurts the performance in your current setup.

In sum, the new revision adds very good error analysis. However, as a method paper, the system still suffers from an unstable and biased filter, rigid templates with low constraint coverage, and an unnecessary retrieval module. Therefore, I have decided to keep my score.

We thank the reviewer. Since the last exchange we ran two experiments targeting the remaining criticisms: a measured replacement for the feature-based filter, and an A/B test of the auxiliary-constraint slot mechanism. Both are below and are incorporated in the uploaded revision.

1. Filter instability and bias. We agree, and our own disclosure quantified it: across extraction runs months apart, three-way admission decisions agree on 84% of 200 problems (kappa = 0.53), flips concentrate in the marginal band (of the 44 hard-rejected, 19 re-extract as accept, 14 as forward). First, the filter is not part of the strongest configuration: the headline route (GND (LLM) + execution, E2E 0.715) runs without it; the filter is optional admission control for abstention-critical deployments (23/23 correct abstentions, 0/60 trap falls, at the cost of E2E 0.660). Second, we now measured the promised replacement - a direct LLM graphizability verdict (one call, no feature extraction): admission accuracy 0.970, precision 1.000 (zero false admits), recall 0.967, versus 0.910 / 0.988 / 0.911 for the feature filter; it accepts 32/32 instances of the eight sparse-structure classes that relation density rejected in every instance; and two full runs on the 200 implicit problems give identical verdicts (200/200, kappa = 1.0; caveat: same-day retest, whereas the feature pipeline's 84% was across months). The unstable component is the LLM feature-extraction intermediary, which the direct judgment removes. The revision adopts this judgment as the default admission module, keeping the logistic scorer as a transparent, fully local fallback.

2. Template mechanisms without experiments. We agree that abstention is not a coverage fix, so we ran the A/B on the 21 flow and touring problems of the E3 judged set (the two deficit families), same session, same judge. Arm A = the original template; Arm B adds one mechanism only, the typed AUXILIARY_CONSTRAINTS open list:

Arm (21 problems)ConstraintEntityObjectiveNo-extra-freedom
A: template only0.4880.7141.0000.976
B: + aux slots0.7620.8690.9880.929

Constraint coverage rises from 0.488 to 0.762 (flow 0.432 to 0.614; touring 0.550 to 0.925), entity coverage rises, objective fidelity is essentially unchanged, and no-extra-freedom pays a small disclosed cost (0.976 to 0.929): the open list occasionally adds mild extra freedom, averaging 1.9 auxiliary constraints per problem. Caveats: judge-based metric, deficit families only, single mechanism (G1+G2 and post-hoc checks remain future work) - the gain is measured, not argued (reported in Appendix E3 of the revision).

3. PEE at the current scale. A factual clarification: PEE is not in the deployed path. The strongest configuration uses direct LLM identification (Table 2: GND (LLM) + execution = 0.715); the PEE route (0.235) is an ablation, and the paper already states direct identification is stronger. Direct identification also stays best across all four strong models we replicated (top-1 0.845-0.945, Appendix E8). So PEE does not hurt the current setup - it is simply not used where accuracy matters. We agree the token savings at 55 classes are marginal with caching; the revision marks PEE optional and relocates it to the analysis sections (E4/E9).

Summary. We agree the reference system has measured limits. The two experiments address them with numbers rather than promises: an LLM admission judgment that is stable, unbiased on sparse classes, and more accurate than the feature filter, and an auxiliary-slot mechanism that raises judged constraint coverage by +0.274 on the deficit families. We respect the reviewer's decision and thank them for analyses that measurably improved the paper.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.