Unified Multi-Dimensional Benchmark for Complex Graph Reasoning in Large Language Models

A five-stage semi-automatic framework for constructing complex graph reasoning benchmarks and evaluating large language models across text-based, code-based, and augmented reasoning settings.

---

Overview

Graph reasoning provides a promising testbed for evaluating the reasoning ability of large language models (LLMs). Graph instances can be programmatically generated, structurally controlled, and naturally scaled to long-input settings. However, existing graph reasoning benchmarks suffer from limited coverage of data complexity, reliance on manual construction, and a lack of unified evaluation across text-based and code-based reasoning modes.

This benchmark addresses these limitations with a five-stage semi-automatic pipeline that expands benchmark coverage along five dimensions:

An LLM-based data generator automatically produces task descriptions, graph data, reference solutions, graph-loading scripts, question forms, and evaluation scripts, while retaining human validation at key quality-control stages.

---

Repository Structure

.
├── data_generation/
│   ├── seed_tasks.json                        # Atomic graph algorithm task definitions
│   ├── prompts.py                             # All LLM prompt templates (Stages 1–5)
│   ├── utils.py                               # Shared helpers and LLM call routing
│   ├── s1_graph_generation_code.py            # Stage 1: composite task generation
│   ├── s2_problem_solving_code_generation.py  # Stage 2: solver code + labelling
│   ├── s3_task_descriptions_and_questions.py  # Stage 3: descriptions + questions
│   ├── s4_evaluation_script_generation.py     # Stage 4: eval script generation
│   └── s5_quality_validation.py              # Stage 5: quality scoring + filtering
│
├── evaluation/
│   ├── llm_api.py                             # Unified LLM call interface
│   ├── run_textual.py                         # Textual reasoning evaluation pipeline
│   ├── run_coding.py                          # Coding reasoning evaluation pipeline
│   └── aggregate.py                           # Results aggregation + leaderboard
│
├── edgelists/                                 # Per-task graph data (JSON, multiple sizes)
├── solutions/                                 # Ground-truth solver scripts
├── inject_test_case_scripts/                  # Per-task description template fillers
├── eval_textual_reasoning_scripts/            # Per-task textual response evaluators
├── eval_coding_reasoning_scripts/             # Per-task coding response evaluators
├── composite_tasks.json                       # Final benchmark task manifest
├── PIPELINE.md                                # Detailed pipeline documentation
└── README.md

---

Five-Stage Data Generation Pipeline

The benchmark is constructed through five sequential stages. Each stage takes the previous stage's manifest as input and adds new artifacts.

seed_tasks.json
      │
      ▼
┌─────────────┐    ┌──────────────────┐    ┌──────────────────────────┐
│   Stage 1   │ -> │     Stage 2      │ -> │         Stage 3          │
│  Composite  │    │ Solution Code &  │    │ Descriptions, Questions, │
│    Task     │    │  Test-Case       │    │   & Injector Scripts     │
│  Generation │    │  Labelling       │    │                          │
└─────────────┘    └──────────────────┘    └──────────────────────────┘
                                                       │
                                                       ▼
                                         ┌─────────────────────────┐
                                         │        Stage 4          │
                                         │  Evaluation Script      │
                                         │     Generation          │
                                         └─────────────────────────┘
                                                       │
                                                       ▼
                                         ┌─────────────────────────┐
                                         │        Stage 5          │
                                         │  Quality Validation     │
                                         │    & Filtering          │
                                         └─────────────────────────┘

Stage 1 — Composite Task Generation

Combines 1–4 seed tasks from seed_tasks.json into composite graph algorithm tasks using one of seven composition strategies (e.g., sequential, constrained, hierarchical, nested). LLM-generated Python code produces graph instances at four sizes: 10, 100, 1,000, and 10,000 nodes.

Stage 2 — Problem-Solving Code Generation

For each composite task, an LLM generates a ground-truth Python solve() function. The script validates the solver via syntax checking and execution against all graph sizes, retrying up to 3 times with error-directed debug prompts.

Stage 3 — Task Description and Question Generation

Generates four description templates per task (D1–D4) varying by framing style (real-world narrative vs. formal graph theory) and data delivery method (inline vs. file reference), plus two question templates for textual (R1) and coding (R2) reasoning modes. A per-task injector script fills description placeholders with actual graph data at runtime.

Stage 4 — Evaluation Script Generation

Creates two task-specific evaluation scripts per task — one for textual responses (extracting answers from <answer></answer> tags) and one for coding responses (extracting and executing the generated solve() function). Both apply type-aware comparison rules (exact match, float tolerance, Jaccard similarity, etc.).

Stage 5 — Quality Validation and Filtering

An LLM scores each task on five quality dimensions (1–5 scale): Clarity, Difficulty Accuracy, Graph Suitability, Naturalness, and Answer Uniqueness. Tasks scoring 1 on any dimension, or 2 on two or more dimensions, are rejected.

---

Evaluation Framework

Once the benchmark is built, LLMs are evaluated across two reasoning tracks and multiple scenarios.

Textual Reasoning (R1)

The model receives a problem description with inline graph data and must return an answer wrapped in <answer></answer> tags.

Coding Reasoning (R2)

The model receives a description and a code stub and must complete the solve() function. The generated function is then executed against the ground-truth test cases.

Results Aggregation

evaluation/aggregate.py reads per-task result files and computes accuracy and score metrics broken down by node size, composition size (k), difficulty, scenario, and reasoning mode. It produces per-model summaries and a cross-model leaderboard.

---

Quickstart

Installation

pip install anthropic openai python-dotenv networkx

Environment Variables

Create a .env file with API keys for the providers you intend to use:

DEEPSEEK_API_KEY=sk-...
ANTHROPIC_API_KEY=sk-ant-...
OPENAI_API_KEY=sk-...
GOOGLE_API_KEY=AI...
# Add keys for any other providers as needed

Running the Full Data Generation Pipeline

# Run stages sequentially
python -m data_generation.s1_graph_generation_code --target-per-k 100
python -m data_generation.s2_problem_solving_code_generation --skip-existing
python -m data_generation.s3_task_descriptions_and_questions --skip-existing
python -m data_generation.s4_evaluation_script_generation --skip-existing
python -m data_generation.s5_quality_validation --skip-existing

Running Evaluation

# Evaluate a model
python -m evaluation.run_textual --model <model-name> --skip-existing
python -m evaluation.run_coding  --model <model-name> --skip-existing

# Aggregate results across all evaluated models
python -m evaluation.aggregate --results-root results

---

Documentation

For a full description of every pipeline stage, CLI arguments, input/output schemas, and directory layout, see PIPELINE.md.

---

Citation

If you use this benchmark in your research, please cite the associated paper (details to be added upon publication).

---

License

Please refer to the repository for license information.