GraphInstruct

A progressive-complexity benchmark for diagnosing capability gaps in LLM graph generation.

---

✨ Why GraphInstruct?

LLMs are increasingly used as on-demand graph synthesizers, yet existing graph-LLM benchmarks stratify along graph type, task domain, or classical algorithm—axes that average over the structural-complexity dimension that actually governs failure. GraphInstruct closes this diagnostic gap:

• 800 hand-authored instructions stratified into 6 progressively-constrained complexity levels (L0 format → L5 multi-step graph editing)
• 5 evaluation dimensions (D1 structural · D2 textual · D3 embedding · D4 instruction-match · D5 efficiency), all deterministic, zero LLM-as-judge
• 45-cell capability survey over 12 LLMs and 4 prompting strategies (180 K outputs) reveals where in the complexity spectrum each model breaks
• Verification-Guided Iterative Generation (VGIG) + Constraint-Aware Adaptive Prompting (CAAP) surpass the per-level prompt-engineering oracle by +0.035 to +0.050 across three target models

---

🚀 Quickstart (5 minutes)

# Windows users only: avoid OMP runtime conflict + GBK encoding crashes
export KMP_DUPLICATE_LIB_OK=TRUE
export PYTHONIOENCODING=utf-8

# 1. Enter the repository root
cd <repository-root>
pip install -e .

# 2. Verify with 549 unit tests (~30 s)
python -m unittest discover -v -s tests

# 3. Open the interactive notebook (5-min hands-on tour)
jupyter notebook examples/01_quickstart.ipynb

For a deeper dive, see docs/INSTALL.md and docs/REPRODUCE.md.

---

📁 What's in this repository?

Directory	What	Used for
data/instructions/	800 instructions in 6 JSON files (L0–L5)	The benchmark itself
data/reference_pools/	4,163 reference graphs (3,115 synthetic L3 + 1,048 real-world L4)	D1 / D3 distributional metrics
graphinstruct/	Python package: parser, validators, D1–D5 metrics, scoring, VGIG/CAAP	Importable evaluation pipeline
tests/	549 unit tests across 19 files	Verifying correctness
scripts/	7 production CLI tools (baseline runner, ablations, visualization)	Reproducing paper tables
results/	Per-cell quality scores, leaderboard CSVs	Direct evidence for paper Tables 1, 2, 3
figures/	All 21 paper figures as PNG/JPEG	Inspect results without running code
examples/	2 Jupyter notebooks (quickstart + evaluate-your-model)	Onboarding new users
docs/	INSTALL · REPRODUCE · DATA_README · DATA_LICENSE · DATASHEET	Detailed documentation

---

🔬 Reproduce the paper

Three reproduction tiers depending on the depth of verification you want:

Tier	What you reproduce	Compute	API cost	Time
A	Data integrity + parser + D1/D4/D5 metric correctness + D5 robustness ablation	CPU only	$0	~5 min
B	Quality / Combined / S_final scores from cached generations	CPU + GPU (D3)	$0	~45 min
C	Full 45-cell capability survey from scratch	API	~$600	~7 days

Full recipe: docs/REPRODUCE.md.

# Tier A: D5 exponential-scale robustness ablation (paper App. C, Tab. 3)
# Should print Spearman rho in [0.966, 1.000] across the 3x3 (s_T, s_A) grid
python scripts/d5_robustness.py

Note: run_baseline.py auto-selects max_tokens per model to match the paper (gpt-3.5-turbo=4096, all others=16384). No flag needed — see docs/REPRODUCE.md for details.

---

🔎 Extended analyses

Beyond the main reproduction pipeline above, this repository ships an extended-analyses companion that drills into individual design choices:

• SUPP_ANALYSES.md — additional robustness and sensitivity studies (CV-style Oracle baseline, cost-adjusted method comparison, reference-pair dedup, parse-failure rates, leave-one-out regression robustness, weight-vector ablations).
• scripts/analyses/ — standalone CPU-only scripts that regenerate every number in the companion (e.g. python scripts/analyses/b17_loo_ols.py). Outputs land in scripts/analyses/results/ as JSON.

These analyses are independent of the main paper tables; the headline leaderboards below are unaffected.

---

📊 Headline results (top 5 of 45 baseline cells)

Rank	Model	Strategy	Quality	TPV	Q/kTPV
1	Sonnet-4.6	few-CoT	0.9018	2,846	0.317
2	Sonnet-4.6	few-shot	0.8836	2,415	0.366
3	Qwen3.5-397B-A17B	few-CoT	0.8788	4,082	0.215
4	Sonnet-4.6	zero-CoT	0.8780	969	0.906
5	Qwen3.5-122B-A10B	few-CoT	0.8714	4,779	0.182

The full 45-cell leaderboard, Pareto frontier, and D5 robustness ablation are in results/leaderboards/ as CSV files that map directly to paper Tables 1, 2, and 3.

---

🔧 Use GraphInstruct on your own model

from pathlib import Path
from graphinstruct.data_loader import load_all_levels
from graphinstruct.evaluate import evaluate

# 1. Load the 800-instruction benchmark
instructions = load_all_levels(data_dir=Path("data/instructions"))

# 2. Run YOUR model on each instruction
my_outputs = []
for level, insts in instructions.items():
    for inst in insts:
        graph_str = my_llm.generate(inst.instruction)   # <-- your LLM here
        my_outputs.append({"id": inst.id, "level": level, "output": graph_str})

# 3. Score it: D1 + D4 + D5 (no GPU needed); add D2/D3 with [full] install
report = evaluate(instructions, my_outputs, dimensions=("D1", "D4", "D5"))
print(f"Total Quality: {report.total_score:.4f}")
print(f"Per-level: {report.per_level_scores}")

See examples/02_eval_your_model.ipynb for a runnable end-to-end example.

---

📚 Documentation

Document	Topic
INSTALL.md	Detailed install for Linux / macOS / Windows; optional dependencies
REPRODUCE.md	Three-tier reproduction recipe; paper-number-to-command mapping
DATA_README.md	Instruction file schema, reference-pool format
DATA_LICENSE.md	Per-source attribution for L4 real-world subset
DATASHEET.md	Datasheet for Datasets (Gebru et al., 2021)

---

🎓 Citation

If you use GraphInstruct, please cite:

@misc{graphinstruct2026,
  title        = {{GraphInstruct}: A Progressive Benchmark for Diagnosing
                  Capability Gaps in {LLM} Graph Generation},
  author       = {{The GraphInstruct Authors}},
  year         = {2026}
}

If you use the L4 real-world reference subset, please also cite the upstream sources listed in docs/DATA_LICENSE.md.

---

📜 License

Component	License
Code (graphinstruct/, tests/, scripts/)	MIT
Synthetic data (data/instructions/, L3 pool)	CC-BY-4.0
L4 real-world reference subset	Upstream license; see DATA_LICENSE.md

---

🤝 Contributing & Contact

For questions about reproduction or usage, please open a GitHub issue.