{"id":"d4ed79e6-c3de-489e-8aba-4c1fb9e954bd","arxiv_id":"2608.06769","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"GraphVerse is a new visual graph reasoning benchmark with structure-preserving image edits and a process-sensitive score, and it shows current multimodal LLMs lag far behind humans, especially on paired-image and NP-hard tasks.","lead":"The paper introduces GraphVerse, a benchmark of 11,000 visual graph-reasoning questions that tests whether multimodal AI models can read, understand, and reason over diagrams of graphs, including pairs of images. It also proposes four image-editing strategies and a process-scoring method to catch models that guess the right answer without reasoning.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The LLM-judge premise behind VGR-Score is validated only on five of eleven tasks: the human-agreement and judge-swap studies (App. D) omit TSP, MCP, MVC, and MIS, exactly where VGR-S exceeds accuracy by 30–40 points and where step verification requires checking NP-hard optimality.","rationale":"The reader's CONDITIONAL verdict identifies the LLM-judge premise as the weakest assumption; I agree with that area, but the paper deserves credit for testing it (App. D), and the concern is more precisely scoped than 'agreement with the judge's language style.' Two observations sharpen the case. First, the headline result — frontier MLLMs trail human baselines by about 35% and score near zero on paired-image MCS — is computed from Acc, an exact-match metric against programmatic gold solutions, so it survives any judge critique. What the judge governs is the benchmark's second contribution, process-sensitive VGR-Score, and the diagnostic reading that 'models achieve near-zero accuracy but much higher VGR-S, so reasoning is partially correct.' Second, the judge's verification burden is task-dependent: for Diameter/SD/Cycle the judge checks a path or cycle against an edge list, a pattern-matching operation within LLM competence; for TSP/MCP/MVC/MIS it must certify optimality, which for n≤15 still requires exhaustive or structural reasoning whose reliability is unknown and plausibly biased toward leniency. The exclusion of these exact tasks from D.1/D.2 is the empirical gap. The proposed test — human agreement on the excluded tasks plus a programmatic-verifier cross-check — directly settles whether VGR-S on those tasks is a reasoning-quality measure or a leniency artifact. I also considered two rival concerns: unreplicated single-run training comparisons (Table 3: RL vs RL w/o GIE gap of roughly 2–3 Acc points on a 1,060-sample test set; MathVista transfer +1.51%) and patch-perturbation prompts instructing models to 'assume the affected panels are restored.' Both are real weaknesses, but they weaken auxiliary claims (GIE effectiveness, transferability) rather than the paper's load-bearing structure: benchmark construction, programmatic ground truth, and the Acc-based human gap. The judge gap is more central because it conditions the metric that the paper presents as a headline contribution. Hence the verdict is UNCHANGED, with the condition being the additional validation on the excluded NP-hard optimization task family.","tokens_in":35127,"tokens_out":11950,"duration_ms":99783,"concrete_test":"Extend the Appendix D protocol to the excluded tasks. (1) Run the human-agreement study on TSP, MCP, MVC, and MIS with at least 50 samples per task, two annotators, and responses from Gemini-3-Pro, GPT-5.2, and one weak open model; accept the judge only if the mean absolute human-minus-judge VGR-S deviation stays within ±0.3 and step-level agreement (Cohen's kappa) is at least 0.7. (2) Cross-check judge step scores with a programmatic verifier: parse each model's claimed clique, vertex cover, independent set, or TSP tour, verify optimality with an exact solver for n≤15, recompute VGR-S, and require the programmatic and LLM-judge scores to agree within ±2 points on these tasks.","verdict_should_be":"UNCHANGED","load_bearing_attack":"GraphVerse's central process-sensitive contribution, VGR-Score (Sec. 4.4, Algorithm 5), asks GPT-5.1 to extract a response's reasoning steps and score each as consistent with verbalized graph evidence (adjacency plus edit metadata). The headline Acc findings — MLLMs about 35% below human baselines, near-zero paired-image accuracy — are programmatically verifiable and do not depend on the judge. But the metric's stated value, and the Sec. 5.2 claim that 'VGR-S exceeds accuracy by 30–40%, implying partially correct reasoning on hard tasks,' rest entirely on judge reliability. The paper's robustness evidence is genuine but narrow. App. D.1's human-agreement study covers only Diameter, SD, Cycle, Coloring, and GED; D.2's judge swap covers only these five tasks on Gemini-3-Pro. Excluded are TSP, MCP, MVC, and MIS — precisely the four optimization tasks where (a) the judge must verify NP-hard optimality claims (maximum clique / independent set, minimum vertex cover, optimal TSP tour) from a verbalized adjacency list on graphs of up to 15 nodes, a computational check language models perform unreliably, and (b) VGR-S diverges most from accuracy (e.g., DeepSeek-V4-Pro TSP: 3.9 Acc vs 34.2 VGR-S; Qwen2.5-72B MCP: 12.0 Acc vs 23.8 VGR-S). With only 25 samples per task and no step-level inter-annotator agreement reported, the process-sensitivity claim for the hardest tasks is unverified. The judgment required here is not agreement with the judge's language style; it is certification of optimality, a different and harder competence than checking graph-traversal statements.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces GraphVerse, a benchmark for visual graph reasoning in multimodal large language models, comprising 11,000 samples (with a 1,060-sample testmini) across nine single-image tasks and two paired-image tasks grounded in real-world graph sources. The benchmark contributes four graph-centric image editing (GIE) strategies that modify graph images while preserving semantic structure, and VGR-Score, a process-sensitive metric computed by an LLM judge that scores extracted reasoning steps against programmatically verbalized graph evidence. Experiments on 19 MLLMs and three text-only description-to-LLM baselines report large gaps between current MLLMs and human annotators, substantially higher VGR-Score than accuracy on many NP-hard tasks, improvements from PoT prompting and from SFT/RL training with GIE-augmented data, and transfer gains on MathVista.","tokens_in":35495,"tokens_out":4404,"duration_ms":37449,"significance":"If the central claims hold, GraphVerse would be a valuable addition to MLLM evaluation: the ground-truth answers come from standard graph solvers, the GIE strategies are well-motivated and target distinct reasoning faculties, and the ablation design includes a no-GIE training control and an independent MathVista transfer check. The programmatic verbalization of graph evidence is a genuinely useful design choice because it removes the need for a vision-capable judge. The main contribution at risk is VGR-Score as a diagnostic of partial reasoning: its human-agreement and judge-robustness evidence covers only five of the eleven tasks, and the largest VGR-Score/accuracy divergences occur precisely in the excluded NP-hard tasks. The accuracy-based findings, including the large MLLM-human gaps and the paired-image difficulty, are programmatically verifiable and do not depend on the judge. The paper ships code and detailed prompts, which strengthens reproducibility.","major_comments":[{"comment":"The central diagnostic claim that VGR-Score reveals 'partially correct reasoning despite incorrect final answers' (Sec. 5.2) is load-bearing for the paper, but the VGR-Score validation covers only five tasks: Diameter, SD, Cycle, Coloring, and GED. The excluded tasks TSP, MCP, MVC, MIS, and MCS are exactly those where the judge must certify NP-hard optimality or subgraph isomorphism from a verbalized adjacency list, and where Table 1 shows the largest VGR-S minus Acc gaps (e.g., DeepSeek-V4-Pro TSP: 3.9 Acc vs. 34.2 VGR-S; Gemini-3-Pro MCS: 6.0 Acc vs. 34.3 VGR-S). Without human-agreement or judge-swap evidence on these tasks, and with only 25 samples per task, the claim that VGR-S exceeds accuracy by 30-40% and thereby implies partially correct reasoning is unverified for precisely the tasks on which the metric's added value rests. I recommend either extending the Appendix D studies to TSP, MCP, MVC, MIS, and MCS, or explicitly restricting the process-sensitivity claims to the five validated tasks.","section":"Sec. 4.4 / Algorithm 5; Appendix D.1-D.2; Sec. 5.2"},{"comment":"All experimental comparisons are based on a single run, and the testmini uses only 25 samples per task-GIE cell (Table 6). Several headline improvements are therefore within the range of ordinary sampling noise: for example, Table 3 reports an RL paired-image improvement of 16.1 absolute points on Qwen3-VL-8B, which corresponds to about four samples, and Table 4 reports overall MathVista gains of 0.31 and 1.10 points. Without confidence intervals, bootstrap estimates, or multiple seeds, claims such as 'RL brings a 13.6% gain over SFT' and 'What transfers from GraphVerse is not graph knowledge, but reasoning itself' are not statistically supported. I request error bars or a statistical test for the main comparative claims, or a softening of the quantitative language.","section":"Sec. 5.1 / Table 6; Sec. 5.3 / Table 3"},{"comment":"The claim that 'post-training with GIE-augmented data yields larger gains than a matched no-GIE training set' is not consistently supported across settings. In Table 3, for Qwen3-VL-8B, RL with GIE achieves 16.1 on Paired Image while RL w/o GIE achieves 17.5; for Qwen3-VL-2B, RL with GIE achieves 1.8 on Paired Image while RL w/o GIE achieves 2.2. The aggregate averages favor GIE, but the paired-image subcategory shows a negative or null effect of GIE. Because GIE effectiveness is a central contribution, the paper should either explain this per-setting inconsistency, report the comparison with error bars, or qualify the aggregate claim.","section":"Sec. 5.3 / Table 3; Sec. E.3 / Table 13"}],"minor_comments":[{"comment":"The human-agreement study uses two annotators and reports only the mean difference between LLM-judge and manual scores; no inter-annotator agreement (e.g., Cohen's kappa) is provided, making it hard to interpret whether the 'strong agreement' is between the judge and humans or merely between the two humans.","section":"Appendix D.1 / Table 9"},{"comment":"The human reference baselines in Table 1 appear to come from two PhD annotators, but no per-task variance or inter-annotator reliability is reported for the NP-hard tasks, despite those tasks having the largest model-human gaps.","section":"Appendix E.6"},{"comment":"The row 'MLLM Description=>LLMs' is difficult to interpret in Table 1 because the number of models differs from the main MLLM list and the procedure is only fully described in Appendix E.3; a one-sentence pointer in the main text would help.","section":"Sec. 5.1 / Table 1"},{"comment":"There is a typo in the Figure 12 prompt: 'patch-fliped' should be 'patch-flipped'.","section":"Appendix G / Figure 12"},{"comment":"The task labels 'Poly' and 'NPH' are not defined in a table or glossary; the reader must infer them from the text in Sec. 4.2. A short definition or table footnote would improve accessibility.","section":"Sec. 4.2 / Table 7"}],"recommendation":"major_revision","confidential_remarks":"The benchmark itself is well constructed and the programmatic verification is a clear strength. The main risk is that the paper's most distinctive metric, VGR-Score, is validated on only a subset of tasks, which leaves the headline 'partially correct reasoning' conclusions unsupported. I would be comfortable with acceptance after the validation gap is closed or the claims are narrowed. The single-run statistical weakness is also worth addressing in revision."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nRead GraphVerse. Bottom line: it is a genuinely useful benchmark, and the headline finding survives scrutiny. The process-score story is softer than the paper's tone suggests.\n\nWhat is actually new: the first visual graph reasoning benchmark with paired-image tasks, four graph-centric image editing operations that are real structural interventions rather than caption perturbations, and a process-sensitive metric built on deterministic verbalization of graph evidence. The construction is careful — ground truth comes from standard graph solvers, the evidence given to the judge is programmatic, and the accuracy numbers from 19 models clearly show MLLMs far below human level on visual graph reasoning, with near-zero MCS accuracy and a 35% average gap. That result does not depend on the LLM judge and will be cited.\n\nThe paper also earns credit for the GIE training ablation and the MathVista transfer control. Those are the right experiments to run, and they support the claim that the editing operations add something beyond simple text transcription.\n\nThe soft spots are real but localized. The VGR-Score judge is validated on only five of eleven tasks — Diameter, Shortest Distance, Cycle, Coloring, GED — and those are exactly the tasks where the judge is checking graph-traversal statements rather than certifying NP-hard optimality. TSP, MCP, MVC, and MIS, where VGR-S diverges most from accuracy and where the judge must verify optimality from a verbalized adjacency list on up to 15 nodes, are absent from the human-agreement and judge-swap studies. With only 25 samples per task and no step-level inter-annotator agreement, the claim that VGR-S \"implies partially correct reasoning on hard tasks\" is under-supported. The accuracy gap is solid; the process interpretation for hard tasks is not yet.\n\nThere is no circularity problem: GIE effectiveness is checked against a no-GIE control and independent transfer, and the self-citations are not load-bearing. The main fixable weakness is the missing judge validation on the optimization-heavy tasks. I would also want repeated runs before trusting the small GIE gains, but that is a minor point.\n\nRecommendation: send it to peer review. A serious referee should push the authors to extend Appendix D to TSP, MCP, MVC, and MIS, and to report step-level agreement. The benchmark itself is worth having even if the process metric needs another round of evidence.\n\nFor my own use: I would bring it to reading group and cite the accuracy findings, not the process metric as it stands.","headline":"A solid, genuinely useful VGR benchmark with programmatic ground truth; the headline accuracy findings are robust, but the process-score story leans on an LLM judge that is validated only on the five easiest tasks, and that soft spot needs referee attention.","tokens_in":36074,"tokens_out":1869,"would_cite":true,"duration_ms":19185,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"GraphVerse measures MLLMs' visual graph reasoning and finds them roughly 35% behind humans.","keywords":["visual graph reasoning","multimodal large language models","benchmark","graph-centric image editing","process-sensitive evaluation","cross-image reasoning","graph computational problems"],"falsifier":"Take a fixed set of model responses, ask two independent human annotators to split them into key reasoning steps and score them under the same rubric, and compare with the LLM judge's extracted steps and VGR-Score; if step-level agreement is low, or if the judge gives a high process score to a fluent but fabricated chain that reaches the right answer through a wrong graph, the metric is measuring judge behavior rather than visual-graph reasoning.","tokens_in":34921,"feed_emoji":"📊","tokens_out":8987,"duration_ms":73641,"temperature":0.7,"pith_summary":"GraphVerse is a benchmark for visual graph reasoning in multimodal large language models, built from real-world graphs rendered as images and paired with programmatically verified graph problems. The paper's central claim is that prior visual graph reasoning benchmarks collapse into perception-then-text reasoning, so they never test whether a model can reason from the visual evidence itself; GraphVerse counters this with four Graph-centric Image Editing (GIE) strategies that alter graph images without changing their underlying topology, forcing models to recover and reason over the edited visual structure. It also introduces VGR-Score, which scores individual reasoning steps against programmatic graph evidence rather than only the final answer. On 11,000 samples tested with 19 MLLMs, the paper reports that even the strongest models trail human baselines by about 35% on average, with near-zero accuracy on paired-image maximum common subgraph, and that vision-based reasoning errors are the dominant failure mode. If the benchmark's measurements are right, current MLLMs are far from robust visual-structural reasoning, and training on GIE-augmented data improves both in-domain performance and transfer to broader multimodal reasoning.","feed_headline":"MLLMs trail humans by 35% on visual graph reasoning","feed_subtitle":"New benchmark edits graph images and scores reasoning steps, exposing vision-based errors as the main bottleneck.","key_machinery":"The load-bearing mechanism is the suite of Graph-centric Image Editing (GIE) strategies, each targeting a different cognitive demand: Image-Graph Patch Perturbation randomly flips or swaps non-empty image patches to break visual continuity; Cross-Graph Composition splits one graph into two panels and gives explicit cross-links to merge; Graph Attentional Focusing picks a target connected subgraph as the largest monochromatic component among distractor colors; and Spatially-Conditioned Recoloring recolors nodes relative to an anchor and cardinal direction. The second mechanism is VGR-Score, a process-sensitive metric built on a scoring LLM that extracts key reasoning steps from the model response and checks each against graph evidence verbalized programmatically from the ground-truth adjacency matrix and edit metadata; the final score is $\\lambda R_{\\text{step}} + (1-\\lambda) \\mathbf{1}[\\hat{y} \\in A^*]$ with $\\lambda = 0.7$. Together these ensure that the evidence needed to verify reasoning never has to be re-read from the image by the judge, and that partial credit is assigned to individual reasoning steps rather than the final answer alone.","core_discovery":"The paper aims to establish that visual graph reasoning is a distinct, scalable, and diagnosis-rich evaluation substrate, and that GraphVerse is a valid instrument for it. Its central design move is to keep the rendered graph image itself as the active evidence: the four GIE strategies damage, split, highlight, or recolor the visualization while preserving the semantic graph, so a correct answer requires the model to re-read and update its structural understanding from the image. The paper then reports three headline findings: current frontier MLLMs are far below human performance, with the best models losing about 35% on average and scoring below 10% on paired-image Maximum Common Subgraph; paired-image reasoning is much harder than single-image reasoning across every model family; and step-level scoring shows that vision-based reasoning errors, not perception or text errors, dominate the failures. The paper also claims that the supervision induced by GraphVerse transfers: reinforcement learning on GIE-augmented data improves accuracy on MathVista, suggesting the trained ability is general visual reasoning rather than graph knowledge.","pith_inferences":["A natural reading is that the GIE strategies are not only evaluation tools but also a data-augmentation recipe that forces a model to update its internal graph representation after an image-level change; this could be tested by measuring whether GraphVerse-trained models become more robust to arbitrary visual corruption of relational diagrams beyond graphs.","Because VGR-Score verifies reasoning against programmatically verbalized graph evidence rather than against the rendered image, it may reward a model that states the correct graph in language while under-penalizing internally consistent-but-wrong perception; a sharper metric would additionally score the model's stated node and edge reading against the actual image content.","The paper leaves more-than-two-image and temporal graph reasoning to future work, but the large paired-image drop suggests this is a challenging frontier; extending GIE to temporal edits, such as edge insertions and deletions over time, is a natural next step.","Since task difficulty is controlled by graph size and editing type, GraphVerse's difficulty scaling is cheap and programmatic; a practical extension would be a curriculum that increases both topological and visual complexity, making visual graph reasoning a scalable training signal for general multimodal models."],"forward_implications":["Even the strongest current MLLMs remain far from human-level visual graph reasoning: on average they trail human baselines by about 35%, and on paired-image Maximum Common Subgraph most models score below 10% accuracy.","The dominant failure mode is vision-based reasoning, not perception: across representative models, visual reasoning errors account for roughly half of all incorrect responses, and this share grows as perception improves.","Paired-image visual graph reasoning is substantially harder than single-image reasoning, with frontier models losing more than half their accuracy, suggesting cross-image structural alignment is a distinct unmet capability.","Final-answer accuracy can misrepresent reasoning quality: VGR-Score often exceeds accuracy by 30–40% on hard tasks, showing partially correct reasoning, and can fall below accuracy for strong models, revealing unstable reasoning processes.","If GraphVerse's measurements hold, GIE-augmented training data is a useful supervision source: reinforcement learning with such data improves in-domain accuracy and transfers to MathVista, with larger gains than training without GIE."],"supporting_citations":[{"why":"Supplies the real-world graph sources, random-walk-with-restart subgraph sampling, and the text-based graph computation benchmark against which GraphVerse positions its visual setting.","marker":"Tang et al., 2025"},{"why":"Supplies the process-sensitive LLM-judge scoring convention and the $\\lambda = 0.7$ weighting that VGR-Score adapts for visual graph reasoning.","marker":"Zhang et al., 2024"},{"why":"A prior visual graph benchmark whose perception-plus-text-reasoning design GraphVerse is explicitly built to overcome; it defines the baseline deficiency.","marker":"Zhu et al., 2025b"},{"why":"An earlier visual graph benchmark (GITA) that reduces visual graph tasks to transcription plus text reasoning, motivating the GIE edits.","marker":"Wei et al., 2024"},{"why":"Earlier work on graph-theory problems in visual context that provides the task vocabulary GraphVerse extends with edits and paired images.","marker":"Li et al., 2024"},{"why":"A prior visual graph arena using answer-only evaluation and single-canvas multi-graph content, against which GraphVerse's paired-image setting is contrasted.","marker":"Babaiee et al., 2025"},{"why":"CLEVR supplies the compositional visual-reasoning paradigm that the Cross-Graph Composition strategy instantiates for graph images.","marker":"Johnson et al., 2017"},{"why":"MathVista is the out-of-domain benchmark used to test whether GraphVerse-trained visual reasoning transfers beyond graphs.","marker":"Lu et al., 2023"}],"fun_headline_variants":["MLLMs lag 35% behind humans on visual graph reasoning","GraphVerse shows MLLM mistakes are visual, not textual","Paired-image graph reasoning is MLLMs' hardest test","New benchmark edits graph images to test MLLM visual reasoning"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The benchmark's scores depend on the scoring model being able to break a free-form answer into its key reasoning steps and compare each step against the true graph facts, so if that step extraction or comparison is unreliable, the reported reasoning-error rates are not trustworthy.","fun_headline_variants_meta":{"raw":{"variants":["MLLMs lag 35% behind humans on visual graph reasoning","GraphVerse shows MLLM mistakes are visual, not textual","Paired-image graph reasoning is MLLMs' hardest test","New benchmark edits graph images to test MLLM visual reasoning"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001285,"raw_usage":{"total_tokens":5275,"prompt_tokens":998,"completion_tokens":4277,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":614,"completion_tokens_details":{"reasoning_tokens":4205}},"tokens_in":614,"tokens_out":4277,"duration_ms":27469,"temperature":1.0,"reasoning_tokens":4205,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T14:29:57.174907+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a fixed set of model responses, ask two independent human annotators to split them into key reasoning steps and score them under the same rubric, and compare with the LLM judge's extracted steps and VGR-Score; if step-level agreement is low, or if the judge gives a high process score to a fluent but fabricated chain that reaches the right answer through a wrong graph, the metric is measuring judge behavior rather than visual-graph reasoning.","supporting_citations":[],"review_version":2}