GraphCert provides a bootstrapped supervision pipeline for agentic graph reasoning during post‑training. The central module, the Bootstrapped Graph Quizzer, generates graph‑grounded QA pairs under generation controls and annotates supporting evidence. The annotated evidence undergoes execution certification and semantic curation; accepted items are canonicalized into certified evidence rubrics. During subsequent GRPO training, these rubrics reward both answer correctness and evidence alignment.
Experiments on five graph‑reasoning tasks in GRBENCH show that GraphCert consistently outperforms much larger LLM agents and other post‑training baselines in both accuracy and evidence matching. Transfer studies reveal that the learned policy generalizes across heterogeneous graph domains, indicating that the model acquires reusable graph‑reasoning skills rather than domain‑specific heuristics.
These results establish executable self‑certification as an effective self‑training approach for compact graph reasoning agents. The code will be released publicly.
Review