Structural Chain-of-Thought: Reasoning with Executable Computational Graphs

Petr Senatorov; Karim Vafin; Elena Tutubalina; Oleg Somov

cs.AIOct 10, 2026

Structural Chain-of-Thought: Reasoning with Executable Computational Graphs

Authors: Petr Senatorov, Karim Vafin, Elena Tutubalina, Oleg Somov

Organizations: MIPT · AIRI

Abstract

Chain-of-thought prompting enables reasoning in large language models but produces explanations that are difficult to verify, expensive to generate, and not always faithful. We introduce a Structural Chain-of-Thought framework where models generate executable computational graphs instead of free-form reasoning. The final answer is obtained by deterministically executing the graph. The model is trained using graph-based reinforcement learning that rewards structural validity, answer correctness, and node overlap with reference graphs. Experiments across five benchmarks and four model families show that our method consistently improves accuracy over supervised graph training and can reduce generation length by up to 5-6x compared with standard GRPO and chain-of-thought supervised training. Our faithfulness experiments reveal that models trained with our approach tend to rely on deriving their answers from the generated graphs rather than producing post-hoc rationalizations as usually in chain-of-thought reasoning.

Figures & tables

Figure 1: Comparison between free-form reasoning and computational graph representations for solving a natural-language arithmetic problem.

Dataset	Train	Test	# Inputs	# Ops
GSM8k+	5,634	1,409	2–4	3–7
iGSM	2,634	658	9–23	5–18
MATH	7,959	1,992	3–5	3–8
Entailment	1,313	340	3–25	1–17
ProofWriter	5,000	2,000	1–5	0–7

Table 1: Datasets used in our experiments. We report train/test sizes and the ranges of input nodes (representing quantities mentioned in the problem, not all of which necessarily appear in the resulting computational graph) and operations (represented by operational nodes in the corresponding computational graphs).

Dataset	Method	Gemma2-2B	LLama3.2-3B	Falcon3-3B	Qwen3-4B	Average
GSM8k+	ICL with FS	0.12 $\pm$ 0.0	0.11 $\pm$ 0.0	0.29 $\pm$ 0.0	0.18 $\pm$ 0.0	0.17 $\pm$ 0.07
	Tree-of-Thoughts	0.00 $\pm$ 0.00	0.01 $\pm$ 0.00	0.02 $\pm$ 0.00	0.12 $\pm$ 0.00	0.04 $\pm$ 0.05
	Answer-only SFT	0.00 $\pm$ 0.00	0.00 $\pm$ 0.00	0.00 $\pm$ 0.00	0.00 $\pm$ 0.00	0.00 $\pm$ 0.00
	CoT + Answer SFT	0.08 $\pm$ 0.00	0.24 $\pm$ 0.00	0.26 $\pm$ 0.00	0.37 $\pm$ 0.01	0.24 $\pm$ 0.10
	Graph SFT	0.24 $\pm$ 0.01	0.31 $\pm$ 0.00	0.33 $\pm$ 0.00	0.43 $\pm$ 0.00	0.33 $\pm$ 0.07
	Default GRPO	0.00 $\pm$ 0.00	0.03 $\pm$ 0.00	0.04 $\pm$ 0.00	0.24 $\pm$ 0.01	0.08 $\pm$ 0.09

Table 2: Performance with standard deviations across datasets and training methods. Best results are shown in bold and second-best in italic.

Dataset	Qwen3-4B	Pythia-1.4B	Llama-3.2-3B-Instruct	Gemma-2-2B	Falcon3-3B-Instruct
MATH	45.9	14.9	51.2	26.3	70.8
GSM8K	28.2	1.3	34.9	21.2	78.1
GSM8K+	0.0	0.0	0.0	0.0	0.0
iGSM	0.0	0.0	0.0	0.0	1.3
Entailment	9.6	0.0	0.0	0.0	0.3
ProofWriter	0.3	0.0	0.0	0.0	31.1

Table 3: CoDeC contamination scores (%) computed for each benchmark dataset. The score is the fraction of samples with a negative in-context delta

\Delta(x)<0

; lower values indicate less contamination.

Figure 2: Accuracy/Overall AllCorrect (top) and generation length (bottom, log scale), averaged over the four models; error bars give the spread across models. Graph-Based GRPO leads on four of five datasets at among the lowest token cost; MATH is the exception. Tree-of-Thoughts and Answer-only SFT are omitted for scale and because the latter emits no reasoning. Full results: Tables 2 and 8 .

Figure 3: Qwen3-4B accuracy (Overall AllCorrect on ProofWriter) stratified by normalized gold graph length. Graph GRPO stays above Graph SFT in all bins and remains more robust on longer graphs.

Setting	Mean	Max
Full model	43.88 $\pm$ 0.99	45.07
– Style reward	42.54 $\pm$ 0.89	43.79
– Correctness reward	42.75 $\pm$ 0.65	43.44
– Overlap reward	44.00 $\pm$ 1.12	45.49
– Default scheduler	44.00 $\pm$ 0.86	45.21
1 rollout	43.88	45.07

Table 4: Ablation study of reward components, scheduling, and the number of rollouts for Qwen3-4B on GSM8k+. Mean accuracy is reported over seeds, with the best result in bold.

$\Delta$ internal – external (pp, lower better)
Method	GSM8K+	iGSM	MATH	PW
ICL	12.1 3	21.1 18	25.2 30	14.3 5
Graph SFT	28.4 9	1.0 0	1.7 1	11.8 5
Graph GRPO	31.9 9	0.2 0	0.4 0	3.5 1
$F_{\mathrm{strong}}$ (%, higher better)
ICL	0.0 0	2.1 1	1.7 1	28.8 25

Table 5: Faithfulness, averaged over the four models; subscripts give the spread across models, rounded to the nearest point.

\Delta

is the absolute gap between internal (graph execution) and external (emitted answer) accuracy;

F_{\mathrm{strong}}

requires answer–graph consistency both before and after intervention. Bold = best per column. Entailment has no external answer; therefore, neither internal–external accuracy nor answer-based faithfulness metrics are applicable. Per-model values, and

F_{\mathrm{ID}}

F_{\mathrm{OOD}}

, are in Table 10 .

Appendix figures & tables6 assets

Supplementary material from the paper’s appendix.

Appendix

	Score (%)		Wilson 95% CI (%)		Mann–Whitney $U$			Fisher’s exact
Model	Model / Pythia		Model / Pythia		$U$	$p$	Cliff’s $\delta$	OR	$p$
MATH
Qwen3-4B	45.9 /	14.9	43.7–48.1 /	13.4–16.6	1 403 460	$<10^{-6}$	0.276	4.831	$<10^{-6}$
Llama-3.2-3B-Instruct	51.2 /	14.8	50.1–52.3 /	14.1–15.6	15 448 768.5	$<10^{-6}$	0.498	6.016	$<10^{-6}$
Gemma-2-2B	26.3 /	14.8	25.3–27.3 /	14.1–15.6	17 161 310	$<10^{-6}$	0.443	2.045	$<10^{-6}$
Falcon3-3B-Instruct	70.8 /	14.8	69.8–71.8 /	14.1–15.6	10 488 688.5	$<10^{-6}$	0.660	13.901	$<10^{-6}$

Appendix

Table 6: Two-sample comparison of the per-sample CoDeC deltas between each target model and Pythia-1.4B (reference). Values are reported as target / reference. The Mann–Whitney

U

test is one-sided (

H_{1}

: target deltas stochastically smaller) and Fisher’s exact test is one-sided (

H_{1}

: higher odds of a negative delta in the target); Cliff’s

\delta

is the effect size for the rank test.

Model	Dataset	Orig. / Redef.		Orig. / Redef.		$U$	$p$	Cliff’s $\delta$	OR	$p$
		Score (%)		Wilson 95% CI (%)		Mann–Whitney $U$			Fisher’s exact
Qwen3-4B	GSM8K	28.2 /	0.0	25.9–30.6 /	0.0–0.3	25 530.0	$<10^{-6}$	0.974	$\infty$	$<10^{-6}$
Llama-3.2-3B-Instruct	GSM8K	34.9 /	0.0	32.5–37.4 /	0.0–0.3	0.0	$<10^{-6}$	1.000	$\infty$	$<10^{-6}$
Gemma-2-2B	GSM8K	21.2 /	0.0	19.2–23.4 /	0.0–0.3	0.0	$<10^{-6}$	1.000	$\infty$	$<10^{-6}$
Falcon3-3B-Instruct	GSM8K	78.1 /	0.0	75.9–80.2 /	0.0–0.3	0.0	$<10^{-6}$	1.000	$\infty$	$<10^{-6}$

Appendix

Table 7: Two-sample comparison of the original GSM8K versus its redefined-operator version (GSM8K+) on the same model. Values are reported as original / redefined. The Mann–Whitney

U

test is one-sided (

H_{1}

: original deltas stochastically smaller) and Fisher’s exact test is one-sided (

H_{1}

: higher odds of a negative delta in the original); Cliff’s

\delta

is the effect size for the rank test.

Dataset	Method	Gemma2-2B	LLama3.2-3B	Falcon3-3B	Qwen3-4B
GSM8k+	ICL with FS	105 $\pm$ 46	188 $\pm$ 173	86 $\pm$ 40	880 $\pm$ 312
	Tree-of-Thoughts	2476 $\pm$ 396	4442 $\pm$ 594	4868 $\pm$ 775	6907 $\pm$ 1031
	Answer-only SFT	8 $\pm$ 2	4 $\pm$ 10	12 $\pm$ 86	3 $\pm$ 1
	CoT + Answer SFT	869 $\pm$ 213	112 $\pm$ 92	251 $\pm$ 149	216 $\pm$ 130
	Graph SFT	348 $\pm$ 4	267 $\pm$ 2	401 $\pm$ 7	428 $\pm$ 27
	Default GRPO	216 $\pm$ 4	364 $\pm$ 28	504 $\pm$ 35	669 $\pm$ 89

Appendix

Table 8: Token consumption comparison per generation across datasets and training methods. Standard deviations are shown in smaller font for readability.

Dataset	Model	Not valid graphs	Not initialized nodes	Unused nodes	Incorrect ops/formulas
GSM8k+	Falcon3-3B	2 $\pm$ 0	2 $\pm$ 0	18 $\pm$ 2	78 $\pm$ 2
	Gemma2-2B	7 $\pm$ 1	2 $\pm$ 0	20 $\pm$ 2	72 $\pm$ 1
	LLama3.2-3B	4 $\pm$ 1	1 $\pm$ 0	19 $\pm$ 3	75 $\pm$ 2
	Qwen3-4B	2 $\pm$ 0	1 $\pm$ 0	9 $\pm$ 1	87 $\pm$ 1
iGSM	Falcon3-3B	1 $\pm$ 0	2 $\pm$ 1	13 $\pm$ 4	85 $\pm$ 3
	Gemma2-2B	94 $\pm$ 3	2 $\pm$ 2	2 $\pm$ 1	2 $\pm$ 2

Appendix

Table 9: Distribution of error categories (%) for Graph-Based GRPO across datasets and models (mean and standard deviation over 3 seeds). Incorrectly initialized constant nodes are counted under Incorrect ops/formulas .

Figure 4: Pass@ $k$ on iGSM across three random seeds. Shaded regions indicate 95% confidence intervals over seeds. Graph GRPO consistently outperforms SFT and exhibits more stable performance as the number of sampled graphs increases.

Panel of Figure 5 — Figure 5: Example of prompt used for generating structured computational graphs with answer.

LLM Reasoning with Graphs

Large language model reasoning with graphs uses structured relationships to support multi-step inference, evidence retrieval, and planning.

See all 196 papers

LCoT-GV: Graph Attention Networks for Verifying Long Reasoning Chains in Large Language Models
Aug 31, 2026Bérénice Jaulmes, Mehwish AlamLLM Reasoning with Graphs LLM Reasoning
1T´el´ecom Paris, Institut Polytechnique de Paris, France · 2BNP Paribas, IT Group, France
Correct Prediction, Wrong Steps? Consensus Reasoning Knowledge Graph for Robust Chain-of-Thought Synthesis
Apr 15, 2026Zipeng Ling, Shuliang Liu, Seonil Son +4Logical Reasoning Self-Consistency Decoding
The Hong Kong University of Science and Technology (Guangzhou) · University of Alberta · Alberta Machine Intelligence Institute +3
Visual Graph Scaffolds for Structural Reasoning in Large Language Models
Jun 1, 2026Runlin Lei, Xiaokui Xiao, Zhewei WeiLLM Reasoning with Graphs LLM Prompting
Renmin University of China · National University of Singapore

Aug 31, 2026J/K move · Enter open · S save

LCoT-GV: Graph Attention Networks for Verifying Long Reasoning Chains in Large Language Models

Bérénice Jaulmes, Mehwish Alam

1T´el´ecom Paris, Institut Polytechnique de Paris, France · 2BNP Paribas, IT Group, France

LLM Reasoning with Graphs LLM Reasoning Large Reasoning Models

Open paper AskPDF arXiv

Large Reasoning Models produce Long Chains-of-Thought (LCoTs) which involve breaking down the problem into smaller reasoning steps before reaching the conclusion. However, these steps often contain contradictions, unsupported inferences, or irrelevant steps, even when the final answer is correct. We propose Long Chain-of-Thought Graph Verifier (LCoT-GV), a graph-based framework that represents LCoTs as reasoning graphs. Each node in the graph represents a reasoning step and the edges encode semantic and logical relations. A Graph Attention Network is then trained to predict chain-of-thought correctness from the reasoning graph. We construct a new graph-oriented verification dataset from multiple reasoning benchmarks for question answering in various domains. The results show that our method is competitive with the most similar approaches.

Abstract

LLM Reasoning with Graphs

Explore similar work

LCoT-GV: Graph Attention Networks for Verifying Long Reasoning Chains in Large Language Models

Correct Prediction, Wrong Steps? Consensus Reasoning Knowledge Graph for Robust Chain-of-Thought Synthesis

Visual Graph Scaffolds for Structural Reasoning in Large Language Models