GraphDecisionBench: Benchmarking System One Models on Graph Tasks

AI summary

Overview

Research area: Evaluation and benchmarking of large language models (LLMs) on graph understanding and graph-based decision-making, with a specific focus on "System One" models that select an answer directly from supplied options rather than generating extended reasoning.

Technical level: Intermediate — the abstract assumes familiarity with LLM evaluation design, graph structured tasks, and the distinction between choice-based (System One) and reasoning-based model interfaces, but the framing is conceptual rather than mathematically deep.

Scope: The paper introduces a model-independent benchmark for diagnosing how choice-based graph models behave across structural tasks, input formats, and proposal conditions, and reports an illustrative evaluation centered on the model Jev.

What This Paper Is About

Language models are increasingly used for graph problems such as interpreting connectivity and making decisions over structured data, and a newer class of "System One" models like Jev works by picking directly from a set of offered options instead of reasoning step by step. It is not clear how capable these choice-based models actually are on graph tasks, or whether their apparent successes reflect real structural understanding. The paper's goal is to build a benchmark that separates these questions and makes the behavior of such models diagnosable and comparable.

Key Contributions

1. A model-independent benchmark for graph decision-making (GraphDecide). The title names the work GraphDecisionBench while the abstract introduces the benchmark as GraphDecide; it is described as independent of any particular model, so it can be applied to different systems rather than being tied to one architecture.

2. Structural task profiles combined with matched graph-text input contrasts. The benchmark pairs tasks designed around structural properties with controlled comparisons between graph-form and text-form inputs, allowing the effect of input representation to be observed rather than assumed.

3. Heuristic-proposal controls. By including heuristic proposals as a control condition, the benchmark can distinguish genuine model capability from the difficulty or ease of the candidate options the model is handed.

4. Task contracts, candidate interfaces, and scoring rules that support cross-model comparison. These components are designed so that native option-selecting models and language-model adapters can be evaluated on the same footing, with the evaluation spanning fourteen model-interface configurations.

Main Findings

• Adjacency recognition is not structural correctness: Accurate recognition of adjacency does not guarantee broader structural correctness, meaning a model can get local graph relationships right while still failing on the wider structure.
• Combined graph-text input is not automatically better: Feeding a model both the graph and a text description does not consistently improve prediction, so multimodal-style input is not a reliable performance boost on these tasks.
• Feasibility is not quality: Producing a feasible construction does not establish that the solution is high quality, separating "can build something valid" from "can build something good."
• The benchmark surfaces these distinctions through Jev: Jev's results are presented as the illustration of the benchmark's central distinctions, and the evaluation places Jev and related choice-based models alongside language-model baselines.

Note: the abstract does not report scores, accuracy figures, or comparative rankings, so no numeric performance conclusions can be drawn from it.

Methodology in Plain English

The researchers built a benchmark rather than a single model. It defines a set of graph-related tasks with explicit "contracts" specifying what a correct answer looks like, then runs models against those tasks under controlled variations. Two variations matter most: whether the graph is presented as a graph, as text, or as both; and whether the model is given a heuristic-generated candidate proposal or must work without one. Allowing candidate options to be supplied is what makes the setup suitable for System One models, which select rather than generate. The same task definitions, candidate formats, and scoring rules are applied across native option-selecting models and language-model adapters, so results can be compared even though the underlying interfaces differ. The study covers fourteen model-interface configurations and uses Jev as the running example for interpreting what the benchmark reveals.

Why This Matters

Impact on research: The work reframes graph evaluation away from a single headline accuracy number and toward diagnostic distinctions — local versus global structure, input modality effects, and proposal quality versus model skill. That gives researchers a vocabulary and a controlled setup for asking why a model succeeds or fails, not just whether it does. The repository of code and aggregate results, as mentioned in the abstract, supports reuse.

Real-world applications (implied by the benchmark's framing, not stated as results in the abstract):

• Evaluating AI assistants used in domains where structured relationships matter, such as network or logistics analysis.
• Screening models for decision-support tools where the model chooses among pre-generated options rather than proposing them freely.
• Assessing whether adding a textual description alongside structured data actually helps a deployed system.
• Distinguishing model capability from candidate-option quality when judging whether a system is ready for use.

Industry relevance: Organizations deploying choice-based model interfaces need to know whether good-looking outputs come from genuine structural understanding or from easy candidate sets. A benchmark with heuristic-proposal controls and interface-agnostic scoring gives a way to make that judgment before deployment.

Future Directions

• Extending the benchmark beyond the fourteen configurations evaluated here, to a wider range of choice-based models and language-model adapters.
• Investigating why joint graph-text input fails to consistently improve prediction — identifying which task types, if any, benefit from the combined representation.
• Developing models or training approaches that close the gap between adjacency-level accuracy and broader structural correctness.
• Separating proposal generation from proposal selection more sharply, so that solution quality can be attributed to the model rather than to the heuristics that produced the candidates.

Target Audience

Researchers and practitioners working on LLM evaluation, graph learning, and structured decision-making; engineers building or selecting choice-based model interfaces for production systems; and benchmark designers interested in matched-input contrasts and proposal controls as evaluation techniques. Readers looking for concrete performance leaderboards will not find them in the abstract, which reports methodology and qualitative distinctions rather than scores.

Authors’ abstract

Large language models (LLMs) are increasingly explored for graph understanding and decision-making, while System One models such as Jev select directly from supplied options. However, the capabilities of System One models on graph-related tasks remain unclear. We introduce GraphDecide, a model-independent benchmark that combines structural task profiles, matched graph-text input contrasts and heuristic-proposal controls to diagnose graph decision performance. We evaluate Jev and related choice-based models alongside language-model baselines, covering fourteen model-interface configurations. Jev's results illustrate the benchmark's central distinctions: accurate adjacency recognition does not guarantee broader structural correctness, joint graph-text input does not consistently improve prediction, and feasible construction does not establish high solution quality. Its task contracts, candidate interfaces and scoring rules support comparison across native selectors and language-model adapters. Code and aggregate results are available at https://github.com/VictorYXL/JevGraphBench.