Probing for Long-Horizon Deductive Reasoning Capabilities in Language Models with Prolog
On the map: LLM reasoning → Test-time compute and efficient thinking also fits: Reasoning benchmarks and evaluation
Abstract (arXiv)
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.
Key facts. No citing papers in the map yet (data through 14 Oct 2026). Placed in Test-time compute and efficient thinking, one of 17 directions in LLM reasoning. Builds on 7 of its 11 references that are in the map. First posted on arXiv 8 Oct 2026.
Builds on
7 of 11 references.
References · 7
- 2024RULER: What's the Real Context Size of Your Long-Context Language Models?cited by 1,346
- 2024LongBench v2: Towards Deeper Understanding and Reasoning on Realistic Long-context Multitaskscited by 379
- 2022Language Models Are Greedy Reasoners: A Systematic Formal Analysis of Chain-of-Thoughtcited by 337
- 2020ProofWriter: Generating Implications, Proofs, and Abductive Statements over Natural Languagecited by 324
- 2020Transformers as Soft Reasoners over Languagecited by 270
- 2025ZebraLogic: On the Scaling Limits of LLMs for Logical Reasoningcited by 201
- 2024HELMET: How to Evaluate Long-Context Language Models Effectively and Thoroughlycited by 125
Built on by
Not cited yet.
Similar, not cited
Close in wording, no citation either way
- 2024Disentangling Logic: The Role of Context in Large Language Model Reasoning Capabilities
- 2026How Much Thinking is Enough? Quantifying and Understanding Redundancy in LLM Reasoning
- 2024The Role of Deductive and Inductive Reasoning in Large Language Models
- 2025JustLogic: A Comprehensive Benchmark for Evaluating Deductive Reasoning in Large Language Models
- 2026Empirical Evidence of Complexity-Induced Limits in Large Language Models on Finite Discrete State-Space Problems with Explicit Validity Constraints
- 2025LongReason: A Synthetic Long-Context Reasoning Benchmark via Context Expansion
- 2023Large Language Models are In-Context Semantic Reasoners rather than Symbolic Reasoners
- 2025The Illusion of Procedural Reasoning: Measuring Long-Horizon FSM Execution in LLMs