Probing for Long-Horizon Deductive Reasoning Capabilities in Language Models with Prolog

Hadeel Al-Negheimish; Jasna Ilieva; Yoon Kim

cs.CLOct 8, 2026

Probing for Long-Horizon Deductive Reasoning Capabilities in Language Models with Prolog

Authors: Hadeel Al-Negheimish, Jasna Ilieva, Yoon Kim

Organizations: King Saud University · Massachusetts Institute of Technology

Abstract

Current frontier LLMs can theoretically process long contexts with 1M tokens or more. But to what extent can they go beyond simple retrieval and perform deeper reasoning over such long contexts? We empirically investigate long-horizon reasoning capabilities of LLMs, focusing on deductive logic expressed in Prolog. We construct ProloNg, a synthetic testbed to probe Prolog Long Reasoning, which systematically varies the complexity (reasoning depth) of problems, where the hardest case has a reasoning depth of 22 and 62k context length. We study 8 reasoning models across 5 families of frontier LLMs, and find that performance degrades substantially as reasoning depth grows, with the majority of models approaching chance beyond depth 10.

Figures & tables

Figure 1: Example problem of depth-4, with an excerpt from the Qwen-3-30B-Thinking model 2 2 2 Full example in Appendix H (left). The symbolic derivation involves backward chaining through four rules until all subgoals are satisfied (right). See Appendix B for an instantiation of this program as a policy compliance problem.

Figure 2: Model accuracy deteriorates with longer depths, with most models sharply declining after depth 10. Random chance is 0.5, since the dataset is balanced.

Figure 3: Proportion of extracted answers per model at each reasoning depth. Many models develop a pronounced conservative bias, predicting that a query is unprovable (red bars), even though the dataset is balanced.

	Original		Shared context
Depth	Acc	# tokens	Acc	# tokens
0	0.9913	133.0	0.8550	2604
2	0.9913	196.5	0.8325	2604
4	0.9775	350.5	0.7725	2604
6	0.8950	690.0	0.7650	2604
8	0.8425	1328.5	0.7474	2604

Table 1: Accuracy and median token usage across reasoning depths for the original and shared-context settings.

Appendix figures & tables9 assets

Supplementary material from the paper’s appendix.

Appendix

Model name	Weights	Model size	Release date	Context size
Claude-Opus-4.7		Not disclosed	Apr. 16, 2026	$1M$ tokens
GPT-5.5		Not disclosed	Apr. 23, 2026	$1M$ tokens
GPT-5.4-mini		Not disclosed	Mar. 17, 2026	$400k$ tokens
DeepSeek-V4-Pro		$1.6T$ ( $49B$ activated)	Apr. 24, 2026	$1M$ tokens
Kimi-K2.6		$1T$ ( $32B$ activated)	Apr. 20, 2026	$256k$ tokens
Qwen3.6-27B		$27B$	Apr. 21, 2026	$262k$ native; up to $\sim 1M$ extended

Appendix

Table 2: Comparison of frontier models used in this analysis based on publicly available data.

Figure 4: Boxplots for input tokens per Depth for DeepSeek-V4-Pro

Panel of Figure 5 — Figure 5: Dependency graph of the program example in Figure 2 .

depth	rules	facts	preds	unique shapes	tokens (deepseek)
0	0.0	2.0	1.0	2	133
2	3.0	9.0	7.0	77	197
4	9.0	26.0	21.0	100	351
6	23.0	66.0	56.5	100	690
8	51.0	138.0	118.5	100	1329
10	95.0	268.0	228.5	100	2543

Appendix

Table 3: Median ProloNg data statistics by depth.

depth	n_examples	time (s)	trace_len
0	100	0.03	3.0
2	100	0.03	21.0
4	100	0.03	63.0
6	100	0.03	169.5
8	100	0.04	355.5
10	100	0.05	685.5

Appendix

Table 4: Median time and trace length by depth for provable queries.

depth	n_examples	time (s)	trace_len
0	100	0.03	2.0
2	100	0.03	14.0
4	100	0.03	32.0
6	100	0.03	80.0
8	100	0.04	177.5
10	100	0.05	353.0

Appendix

Table 5: Median time and trace length by depth for unprovable queries.

Figure 6: Accuracy per target provability. The deterioration in performance is sharper for provable queries as complexity increases, which aligns with the models’ conservative bias.

Figure 7: Mean number of output tokens per model. Only Qwen-3.5 continues to grow monotonically, with the rest remaining significantly below the token budget.

Model	Original	Disentangled
Qwen3.5-4B	$-0.668$	$-0.861$
Qwen3.5-27B	$0.127$	$0.744$
Qwen3.6-27B	$0.226$	$0.189$
DeepSeek-V4-Pro	$0.315$	$-0.083$

Appendix

Table 6: Per-model random intercept estimates (BLUPs) from the GLMM, comparing the matched (k=4) original and disentangled settings.

Explore similar work

Can RL Teach Long-Horizon Reasoning to LLMs? Expressiveness Is Key
May 7, 2026Tianle Wang, Zhaoyang Wang, Guangchen Lan +4Logical Reasoning RL for Language Model Reasoning
Purdue University · UNC Chapel Hill · Georgia Tech +1
PrologMCP: A Standardized Prolog Tool Interface for LLM Agents
Jun 12, 2026Agnieszka Mensfelt, Adarsh Prabhakaran, Adrian Haret +2Logic Programming Symbolic Reasoning
Department of Computer Science, Royal Holloway, University of London, UK
Recursive Models for Long-Horizon Reasoning
Mar 2, 2026Chenxiao Yang, Nathan Srebro, Zhiyuan LiLong-Context Modeling Language Modeling
Toyota Technological Institute at Chicago

May 7, 2026, cs.AIJ/K move · Enter open · S save

Can RL Teach Long-Horizon Reasoning to LLMs? Expressiveness Is Key

Tianle Wang, Zhaoyang Wang, Guangchen Lan, Xinpeng Wei+3

Purdue University · UNC Chapel Hill · Georgia Tech+1

Logical Reasoning RL for Language Model Reasoning Language Model Scaling Laws LLM Reasoning

Open paper AskPDF arXiv

Reinforcement learning (RL) has been applied to improve large language model (LLM) reasoning, yet the systematic study of how training scales with task difficulty has been hampered by the lack of controlled, scalable environments. Observed LLM shortcomings in long-horizon reasoning have raised the prospect that they are fundamental to the autoregressive transformer architecture. To address this, we introduce ScaleLogic, a synthetic logical reasoning framework that offers independent control over two axes of difficulty: the depth of the required proof planning (i.e., the horizon) and the expressiveness of the underlying logic. Our proposed framework supports a wide range of logics: from simple implication-only logic ("if-then") towards more expressive first-order reasoning with conjunction ("and"), disjunction ("or"), negation ("not"), and universal quantification ("for all"). Using this framework, we show that the RL training compute

T

follows a power law with respect to reasoning depth

D

(

T \propto D^γ

R^{2} > 0.99

), and that the scaling exponent

γ

increases monotonically with logical expressiveness, from

1.04

2.60

. On downstream mathematics and general reasoning benchmarks, more expressive training settings yield both larger performance gains (up to

+10.66

points) and more compute-efficient transfer compared to less expressive settings, demonstrating that what a model is trained on, not just how much it is trained, shapes downstream transfer. We further show that the power-law relationship holds across multiple RL methods, and curriculum-based training substantially improves scaling efficiency. More broadly, our results demonstrate that LLM shortcomings in long-horizon reasoning are not fundamental to the underlying architecture, and can be addressed by improved training methodology and data.

Abstract

Explore similar work

Can RL Teach Long-Horizon Reasoning to LLMs? Expressiveness Is Key

PrologMCP: A Standardized Prolog Tool Interface for LLM Agents

Recursive Models for Long-Horizon Reasoning