Probing for Long-Horizon Deductive Reasoning Capabilities in Language Models with Prolog
Open accessAbstract
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.
AI snapshot
Written from the paper’s full text.
TL;DR
The paper introduces PROLONG, a synthetic Prolog benchmark for long-horizon deductive reasoning with proof depths up to 22 and contexts up to a median of 62k tokens. Across 8 frontier reasoning models, accuracy collapses toward chance beyond depth 10, driven by a conservative bias toward predicting “unprovable” and by unfaithful reasoning traces.
Key findings
- Performance degrades monotonically with reasoning depth: most models approach the 0.5 chance baseline beyond depth 10, while GPT-5.5 is the outlier, maintaining high accuracy until depth 16 and degrading to 67% accuracy at depth-20.
- Many models develop a “conservative bias,” increasingly predicting queries are unprovable as depth grows; Claude-Opus-4.7, DeepSeek-V4-Pro, and Kimi-K2.6 show this most strongly beyond depth 10.
- Reasoning traces are often unfaithful: for GPT-5.5 true negatives, only 34 of 84 (40.5%) correctly cited the planted missing fact; for DeepSeek-V4-Pro, only 11% of 91 true negatives correctly mentioned the missing fact, and 97 of 100 provable queries were falsely claimed unsupported.
- In a disentangled shared-context setting, both context length and proof depth independently degrade performance: context length β = -0.54 and proof depth β = -0.36, both p < 0.001.
Methods
- PROLONG is generated from simple definite Prolog programs represented as DAGs, with no loops or recursion, predicate arity at most two, and one rule per predicate; each program has a provable and an unprovable query.
- The benchmark contains 2,400 samples: 100 programs per depth, each with two queries, at depths 0–22 skipping odd depths; median input tokens grow from 133 at depth 0 to 62k at depth 22.
- The authors evaluate 8 frontier reasoning models and fit generalized linear mixed models with model identity as a random intercept and context length and proof depth as fixed effects; a disentangled dataset of 600 samples fixes context length across depths 0, 2, 4, 6, 8, and 10.
Limitations
- The paper states that generated programs exclude recursion, reasoning loops, and negation; closed-source models provide only reasoning summaries, not full traces; API costs are substantial; and output token budgets of 64k for most models and 82k for Qwen models may limit accuracy at longer depths.
- The text also makes evident that the benchmark is synthetic, binary, balanced, and restricted to simple linear proof chains with no backtracking or unsuccessful branches, so findings may not generalize to more complex logical reasoning.
Model-written summary. Check it against the paper before relying on it.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
9 of 16 cited sources checked · 6 supported · 0 flagged · accuracy not yet measured
- Premisecitation
Previous deductive reasoning benchmarks such as RuleTaker, ProofWriter, and ProntoQA studied proof depths up to five steps or hops.
“Early work on deductive reasoning benchmarks such as RuleTaker (Clark et al., 2020) and ProofWriter (Tafjord et al., 2021) established the basic setup of query answering over sets of rules and facts, with ProofWriter reaching a maximum proof depth of five steps.ProntoQA (Saparov and He, 2023) introduces proof-structure controls and formal error attribution, also evaluated up to five hops.”
Quote in the paperSubstantial claim2 of 3 sources checked - Premisecitation
Using Prolog instead of natural language in evaluations avoids ambiguity and content effects that can impact performance, as models may draw on prior knowledge rather than the stated context.
“we opt to use Prolog instead of natural language in our evaluations, in order to avoid ambiguity and content effects that can impact performance, as models may draw on prior knowledge rather than the stated context (Lampinen et al., 2024).”
Quote in the paperSubstantial claim1 of 1 sources checked- cites Lampinen et al., 2024 source
The Results and Discussion (pages unavailable) show that models’ reasoning performance is affected by whether problem content aligns with real-world expectations, supporting the concern about prior knowledge overriding a stated premise. The paper does not evaluate Prolog or establish that using it instead of natural language avoids ambiguity or content effects. (LLM, conf=0.85)
Experimental — accuracy not yet measured
- Premisecitation
LongBench-v2, RULER, and HELMET evaluate retrieval and QA over extended contexts, treating reasoning and retrieval as independent axes in most tasks.
“On the long-context processing side, LongBench-v2 (Bai et al., 2025), RULER (Hsieh et al., 2024), and HELMET (Yen et al., 2025) evaluate retrieval and QA over extended contexts, treating reasoning and retrieval as independent axes in most tasks.”
Quote in the paperSubstantial claim1 of 3 sources checked- cites Bai et al., 2025
Couldn’t be matched to a paper in Crossref, so it can’t be checked.
- cites Hsieh et al., 2024
The Introduction (pp. 1–2) and Section 3 (p. 3) show that RULER evaluates retrieval and question answering at varying, extended context lengths. They describe separate task categories, but do not establish that reasoning and retrieval are treated as independent axes in most tasks. This verdict concerns RULER, not the other two benchmarks named in the sentence. (LLM, conf=0.84)
Experimental — accuracy not yet measured - cites Yen et al., 2025
Couldn’t be matched to a paper in Crossref, so it can’t be checked.
- Findingreasoning
The dataset contains 2400 samples at varying levels of complexity.
“This results in a dataset of 2400 samples at varying levels of complexity, ranging from 133 median input tokens 4 at depth 0 to 62k tokens at depth 22.”
Quote in the paperNot a substantial claim - Findingown data
Accuracy degrades monotonically as depth increases.
“However, accuracy degrades monotonically as depth increases, with the rate and onset of decline varying considerably across models.”
Quote in the paperSubstantial claim
- Findingown data
Claude-Opus-4.7 is the second-best performer.
“Claude-Opus-4.7 is the second-best performer, remaining competitive with GPT-5.5 through depth 12 before deteriorating sharply between depths 14 and 16, ultimately settling near chance at depth 22.”
Quote in the paperNot a substantial claim - Findingown data
The best-performing frontier model, GPT-5.5, degrades to 67% accuracy at depth-20.
“even the best-performing frontier model, GPT-5.5, degrades to 67% accuracy at depth-20”
Quote in the paperSubstantial claim - Findingreasoning
PROLONG's context length scales with the number of rules and facts as depth grows, reaching a median of 62k tokens.
“Crucially, this is also a long-horizon and long-context reasoning benchmark: context length scales as the number of rules and facts in the program grows with depth, reaching a median of 62k tokens.”
Quote in the paperSubstantial claim - Findingown data
Claude-Opus-4.7 settles near chance at depth 22.
“Claude-Opus-4.7 is the second-best performer, remaining competitive with GPT-5.5 through depth 12 before deteriorating sharply between depths 14 and 16, ultimately settling near chance at depth 22.”
Quote in the paperSubstantial claim - Findingown data
The PROLONG benchmark contains 100 programs per depth, each with a provable and unprovable query, yielding 200 samples per depth.
“We generate a set of 100 programs per depth, each with a provable and unprovable query, resulting in 200 samples per depth.”
Quote in the paperSubstantial claim - Findingown data
GPT-5.5 maintains high accuracy until depth 16, before declining at depths 20-22.
“GPT-5.5 is the clear outlier, maintaining high accuracy until depth 16, before declining at depths 20 -22.”
Quote in the paperSubstantial claim - Findingown data
Claude-Opus-4.7 deteriorates sharply between depths 14 and 16.
“Claude-Opus-4.7 is the second-best performer, remaining competitive with GPT-5.5 through depth 12 before deteriorating sharply between depths 14 and 16, ultimately settling near chance at depth 22.”
Quote in the paperNot a substantial claim - Findingown data
GPT-5.5 exhibits a milder version of the same conservative tendency.
“GPT-5.5 exhibits a milder version of the same tendency.”
Quote in the paperNot a substantial claim - Findingown data
Claude-Opus-4.7 remains competitive with GPT-5.5 through depth 12.
“Claude-Opus-4.7 is the second-best performer, remaining competitive with GPT-5.5 through depth 12 before deteriorating sharply between depths 14 and 16, ultimately settling near chance at depth 22.”
Quote in the paperNot a substantial claim - Findingown data
Beyond depth 10, several models approach the chance baseline of 0.5 for this binary task.
“Beyond depth 10, several models approach the chance baseline of 0.5 for this binary task.”
Quote in the paperSubstantial claim - Findingown data
Qwen3.5 models' main failure mode is running out of tokens before reaching an answer.
“Qwen3.5 models' main failure mode is different: they run out of tokens before reaching an answer, even at depth-10 where the median input size is only 2.5k tokens (grey bars).”
Quote in the paperSubstantial claim - Findingown data
The remaining models follow broadly similar trajectories of steeper decline.
“The remaining models follow broadly similar trajectories of steeper decline.”
Quote in the paperNot a substantial claim - Findingown data
By depth 16-18, the proportion of negative predictions in Claude-Opus-4.7, DeepSeek-V4-Pro, and Kimi-K2.6 dominates overwhelmingly.
“By depth 16 -18, the proportion of negative predictions in these models dominates overwhelmingly.”
Quote in the paperSubstantial claim - Findingown data
Claude-Opus-4.7, DeepSeek-V4-Pro, and Kimi-K2.6 develop a pronounced conservative bias beyond depth 10.
“Claude-Opus-4.7, DeepSeek-V4-Pro, and Kimi-K2.6 all develop a pronounced conservative bias beyond depth 10, increasingly predicting that queries are unprovable regardless of whether they actually are.”
Quote in the paperSubstantial claim - Findingown data
Performance of the evaluated models degrades substantially as reasoning depth grows.
“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.”
- Also stated in: § 1 Introduction · plain
“We perform a systematic evaluation and analysis of 8 frontier reasoning models, and find that even the best-performing frontier model, GPT-5.5, degrades to 67% accuracy at depth-20, with the majority of models failing to perform above chance beyond depth-10.”
Quote in the paperSubstantial claim - Also stated in: § 1 Introduction · plain
- Findingown data
All models begin near ceiling performance at shallow depths.
“All models begin near ceiling performance at shallow depths, indicating that they are aware of the Prolog syntax.”
Quote in the paperNot a substantial claim - Findingown data
The rate and onset of accuracy decline vary considerably across models.
“However, accuracy degrades monotonically as depth increases, with the rate and onset of decline varying considerably across models.”
Quote in the paperSubstantial claim - Findingown data
Claude-Opus-4.7, DeepSeek-V4-Pro, and Kimi-K2.6 increasingly predict queries are unprovable regardless of whether they actually are.
“Claude-Opus-4.7, DeepSeek-V4-Pro, and Kimi-K2.6 all develop a pronounced conservative bias beyond depth 10, increasingly predicting that queries are unprovable regardless of whether they actually are.”
Quote in the paperSubstantial claim - Findingown data
Many models exhibit a bias towards predicting unprovable that increases with the complexity of the program.
“There appears to be a clear pattern in how models fail: while the benchmark is balanced by construction, with an equal number of provable/unprovable queries at every depth, many models exhibit a bias towards one answer, unprovable (red bars), that increases with the complexity of the program.”
Quote in the paperSubstantial claim - Findingown data
Failure occurs in an even simpler setting than ZebraLogic: a smaller search space with a linear proof chain beyond depth 10.
“We show failure occurs in an even simpler setting: a smaller search space with a linear proof chain beyond depth 10.”
Quote in the paperSubstantial claim - Findingown data
In the full non-disentangled evaluation set across all eight models, context length showed a large, significant effect (β = -1.38, p < 0.001).
“Context length showed a large, significant effect (β = -1.38,p < 0.001)”
Quote in the paperSubstantial claim - Findingown data
In the matched models (k=4) original data, context length remains large and significant (β = -1.48, p < 0.001).
“context length remains large and significant (β = -1.48,p < 0.001)”
Quote in the paperSubstantial claim - Findingown data
Among the 84 True Negatives, 21 mentioned other facts as blockers even though they are provable.
“The other cases were: 14 only returned the final answer, without reasoning; 15 gave a vague and incomplete proof; and 21 mentioned other facts as blockers even though they are provable.”
Quote in the paperSubstantial claim- Rests on an assumption: Manual verification of 10% of the problems is sufficient to trust the LLM's failure reason extraction for all problems.
- Rests on an assumption: The reasoning summaries provided by closed-source models are sufficiently faithful to their internal reasoning to support conclusions about reasoning failures.
- Findingown data
Accuracy deterioration with depth is less drastic for unprovable queries than for provable queries.
“We can see that the deterioration is less drastic in unprovable queries.”
- Also stated in: § Final Answer: Since the query `p(o1, o2)`can be proven, the answer is 1. \boxed{1} · plain
“The deterioration in performance is sharper for provable queries as complexity increases”
Quote in the paperSubstantial claim - Also stated in: § Final Answer: Since the query `p(o1, o2)`can be proven, the answer is 1. \boxed{1} · plain
- Findingown data
Among the 84 True Negatives, 14 only returned the final answer without reasoning.
“The other cases were: 14 only returned the final answer, without reasoning; 15 gave a vague and incomplete proof; and 21 mentioned other facts as blockers even though they are provable.”
Quote in the paperNot a substantial claim- Rests on an assumption: Manual verification of 10% of the problems is sufficient to trust the LLM's failure reason extraction for all problems.
- Rests on an assumption: The reasoning summaries provided by closed-source models are sufficiently faithful to their internal reasoning to support conclusions about reasoning failures.
- Findingown data
In the full non-disentangled evaluation set across all eight models, proof depth's effect was much smaller (β = -0.18, p = 0.012).
“while proof depth's effect was much smaller (β = -0.18,p = 0.012)”
Quote in the paperSubstantial claim - Findingown data
Qwen3.5 models run out of tokens even at depth-10 where the median input size is only 2.5k tokens.
“Qwen3.5 models' main failure mode is different: they run out of tokens before reaching an answer, even at depth-10 where the median input size is only 2.5k tokens (grey bars).”
Quote in the paperSubstantial claim - Findingown data
The size of the context grows significantly with depth.
“The size of the context grows significantly with depth, Figure 4 shows boxplots of the input tokens as measured by DeepSeek-V4-Pro.”
Quote in the paperNot a substantial claim - Findingown data
Restricting to the same four models used in the disentangled experiment (n = 9,600) yields a smaller random-intercept variance (σ2 = 0.156, SD = 0.395).
“Restricting to the same four models used in the disentangled experiment (n = 9,600), to rule out model composition as a confound, yields a smaller random-intercept variance (σ 2 = 0.156, SD = 0.395)”
Quote in the paperSubstantial claim - Findingown data
Across 8 models, accuracy collapses toward chance beyond depth 10.
“Across 8 models, accuracy collapses toward chance beyond depth 10, driven largely by a conservative bias: models increasingly default to predicting a query is unprovable as depth grows, despite the problems remaining well within advertised context limits.”
Quote in the paperSubstantial claim - Findingown data
Qwen3.5 models are the only ones whose reasoning traces grow monotonically with increased depth.
“In appendix E, we report the length of the reasoning traces for each model, and the Qwen3.5 models are the only ones whose reasoning traces grow monotonically with increased depth; the rest plateau.”
Quote in the paperNot a substantial claim - Findingown data
In the matched models (k=4) original data, proof depth is no longer statistically significant (β = -0.15, p = 0.108).
“while proof depth is no longer statistically significant (β = -0.15,p = 0.108).”
Quote in the paperSubstantial claim - Findingown data
Model accuracy deteriorates with longer depths, with most models sharply declining after depth 10.
“Model accuracy deteriorates with longer depths, with most models sharply declining after depth 10.”
Quote in the paperSubstantial claim - Findingreasoning
Context length and proof depth are tightly correlated (r = 0.97) in the original benchmark.
“However, context length and proof depth are tightly correlated (r = 0.97), since, by definition, we require the context to only contain elements that would be used in the proof; the longer the proof, the longer the context.”
Quote in the paperSubstantial claim - Findingown data
In GPT-5.5's False Negatives, the model claims that a necessary fact is missing or has no rules to support it, even though it exists in the context.
“It claims that a necessary fact is missing or has no rules to support it, even though it exists in the context.”
Quote in the paperSubstantial claim- Rests on an assumption: Manual verification of 10% of the problems is sufficient to trust the LLM's failure reason extraction for all problems.
- Rests on an assumption: The reasoning summaries provided by closed-source models are sufficiently faithful to their internal reasoning to support conclusions about reasoning failures.
- Findingown data
The reasoning traces of models other than Qwen3.5 plateau.
“In appendix E, we report the length of the reasoning traces for each model, and the Qwen3.5 models are the only ones whose reasoning traces grow monotonically with increased depth; the rest plateau.”
Quote in the paperSubstantial claim - Findingown data
Among the 84 True Negatives, 15 gave a vague and incomplete proof.
“The other cases were: 14 only returned the final answer, without reasoning; 15 gave a vague and incomplete proof; and 21 mentioned other facts as blockers even though they are provable.”
Quote in the paperNot a substantial claim- Rests on an assumption: Manual verification of 10% of the problems is sufficient to trust the LLM's failure reason extraction for all problems.
- Rests on an assumption: The reasoning summaries provided by closed-source models are sufficiently faithful to their internal reasoning to support conclusions about reasoning failures.
- Findingown data
Many models develop a pronounced conservative bias, predicting that a query is unprovable, even though the dataset is balanced.
“Many models develop a pronounced conservative bias, predicting that a query is unprovable (red bars), even though the dataset is balanced.”
Quote in the paperSubstantial claim - Findingown data
In GPT-5.5's reasoning summary for False Negatives, the model starts the reasoning chain correctly but then loses its way.
“Analyzing the reasoning summary produced by GPT-5.5, we find that in the False Negatives, the model starts the reasoning chain correctly, but then”
Quote in the paperNot a substantial claim- Rests on an assumption: Manual verification of 10% of the problems is sufficient to trust the LLM's failure reason extraction for all problems.
- Rests on an assumption: The reasoning summaries provided by closed-source models are sufficiently faithful to their internal reasoning to support conclusions about reasoning failures.
- Findingown data
Qwen3.6-27B displays a notably irregular pattern: output length peaks around depths 8-10 before declining to a plateau of approximately 40k tokens at greater depths.
“Qwen3.6-27Bdisplays a notably irregular pattern: output length peaks around depths 8 -10 before declining to a plateau of approximately 40k tokens at greater depths (note that the maximum budget was 82k).”
Quote in the paperNot a substantial claim - Findingown data
In the regenerated dataset with fixed context length across depths, there is no correlation between depth and length (r = 0.0003).
“Since the context length is fixed across depths for each problem, there is no correlation between depth and length (r = 0.0003).”
Quote in the paperSubstantial claim - Findingown data
For the 91 true negatives in DeepSeek-V4-Pro, only 11% of their reasoning traces correctly mention the missing fact planted.
“As for the 91 true negatives, only 11% of their reasoning traces correctly mention the missing fact planted.”
Quote in the paperSubstantial claim - Findingown data
The growth of the reasoning trace varies across models.
“The growth of the reasoning trace varies across models, as shown in Figure 7.”
Quote in the paperNot a substantial claim - Findingown data
Of the 84 True Negatives, only 34 correctly cited the planted missing fact (40.5%), and the vast majority did not (59.5%).
“For the True Negatives, LLM analysis indicates that of the 84 True Negatives, only 34 correctly cited the planted missing fact (40.5%), and the vast majority did not (59.5%).”
Quote in the paperSubstantial claim- Rests on an assumption: Manual verification of 10% of the problems is sufficient to trust the LLM's failure reason extraction for all problems.
- Rests on an assumption: The reasoning summaries provided by closed-source models are sufficiently faithful to their internal reasoning to support conclusions about reasoning failures.
- Findingown data
Qwen3.5 stands apart from all other models in its tendency to allocate monotonically increasing reasoning tokens with depth, with output length continuing to grow even at the deepest levels.
“Qwen3.5 stands apart from all other models in its tendency to allocate monotonically increasing reasoning tokens with depth, with output length continuing to grow even at the deepest levels”
Quote in the paperNot a substantial claim - Findingown data
Kimi-K2.6 exhibits a non-monotonic profile, with output length peaking around depth 16 before declining.
“Kimi-K2.6 similarly exhibits a non-monotonic profile, with output length peaking around depth 16 before declining.”
Quote in the paperNot a substantial claim - Findingown data
In the full non-disentangled evaluation set across all eight models (n = 19,200), the random-intercept variance for model identity was σ2 = 0.607 (SD = 0.779).
“Fit on the full, non-disentangled evaluation set across all eight models (n = 19,200), the random-intercept variance for model identity was σ2 = 0.607 (SD = 0.779).”
Quote in the paperSubstantial claim - Interpretationown data
Even when logical inference is simple, frontier reasoning models struggle to maintain the required chain of substitutions and fact lookups as proof depth and context size scale.
“This reveals that even when logical inference is simple, frontier reasoning models struggle to maintain the required chain of substitutions and fact lookups as proof depth and context size scale.”
Quote in the paperSubstantial claim - Study design and conductown data
Labels are correct, verified with the SWI-Prolog interpreter.
“We verify that labels are correct with the SWI- Prolog interpreter, which only takes half a second even for the largest programs.”
Quote in the paperSubstantial claim - Interpretationown data
GPT-5.5 is the clear outlier among the evaluated models.
“GPT-5.5 is the clear outlier, maintaining high accuracy until depth 16, before declining at depths 20 -22.”
Quote in the paperNot a substantial claim - Interpretationreasoning
The framework allows systematic construction of random logic programs with controllable levels of complexity.
“This framework allows systematic construction of random logic programs with controllable levels of complexity.”
Quote in the paperSubstantial claim - Study design and conductreasoning
The benchmark dataset is balanced by construction, with an equal number of provable and unprovable queries at every depth.
“A single program (context) accompanies two samples in the data, one with a provable query and another unprovable, such that the dataset is balanced.”
- Also stated in: § 4.3 Models become more conservative · hedged
“There appears to be a clear pattern in how models fail: while the benchmark is balanced by construction, with an equal number of provable/unprovable queries at every depth, many models exhibit a bias towards one answer, unprovable (red bars), that increases with the complexity of the program.”
Quote in the paperSubstantial claim - Also stated in: § 4.3 Models become more conservative · hedged
- Interpretationown data
The near-ceiling performance at shallow depths indicates that models are aware of Prolog syntax.
“All models begin near ceiling performance at shallow depths, indicating that they are aware of the Prolog syntax.”
Quote in the paperNot a substantial claim - Interpretationreasoning
The conservative bias suggests models are effectively giving up, defaulting to no when the proof chain becomes too long to follow.
“This suggests that models are effectively giving up, defaulting to”
Quote in the paperSubstantial claim- Rests on an assumption: The generated Prolog programs are a valid probe of long-horizon deductive reasoning capabilities in language models.
- Interpretationreasoning
The pattern in Figure 6 aligns with the models' conservative bias.
“which aligns with the models' conservative bias.”
Quote in the paperNot a substantial claim - Interpretationown data
The collapse in accuracy is driven largely by a conservative bias: models increasingly default to predicting a query is unprovable as depth grows, despite the problems remaining well within advertised context limits.
“Across 8 models, accuracy collapses toward chance beyond depth 10, driven largely by a conservative bias: models increasingly default to predicting a query is unprovable as depth grows, despite the problems remaining well within advertised context limits.”
Quote in the paperSubstantial claim- Rests on an assumption: The problems remain well within the models' advertised context limits.
- Interpretationown data
Reasoning traces are often unfaithful to the actual derivation, citing missing facts or blockers that are not really there.
“Reasoning traces are often unfaithful to the actual derivation, citing missing facts or blockers that are not really there.”
Quote in the paperSubstantial claim- Rests on an assumption: Manual verification of 10% of the problems is sufficient to trust the LLM's failure reason extraction for all problems.
- Rests on an assumption: The reasoning summaries provided by closed-source models are sufficiently faithful to their internal reasoning to support conclusions about reasoning failures.
- Interpretationreasoning
The coefficient split from the initial GLMM is highly sensitive to estimation noise rather than reflecting the two factors' true independent contributions.
“Hence, the coefficient split is highly sensitive to estimation noise rather than reflecting the two factors' true independent contributions.”
Quote in the paperSubstantial claim - Interpretationown data
The pattern in the full non-disentangled evaluation set is consistent with the confounding described in Section 4.5.
“consistent with the confounding described in Section 4.5.”
Quote in the paperSubstantial claim - Interpretationown data
GPT-5.5, Claude-Opus-4.7, DeepSeek-V4-Pro, and GPT-5.4-mini allocate reasoning budget efficiently regardless of problem complexity.
“suggesting these models allocate reasoning budget efficiently regardless of problem complexity.”
Quote in the paperSubstantial claim - Interpretationreasoning
Random chance is 0.5.
“Random chance is 0.5, since the dataset is balanced.”
Quote in the paperSubstantial claim - Interpretationown data
Qwen3.5's pattern is consistent with the model expanding its thinking trace without necessarily improving its derivations.
“a pattern consistent with the model expanding its thinking trace without necessarily improving its derivations.”
Quote in the paperNot a substantial claim - Interpretationown data
Frontier models have not learned a robust, generalizable implementation of backward chaining inference even in simple, linear proofs.
“These results suggest frontier models have not learned a robust, generalizable implementation of backwardchaining inference even in simple, linear proofs.”
Quote in the paperSubstantial claim- Rests on an assumption: The generated Prolog programs (simple, linear, no recursion/negation) are a valid testbed for studying long-horizon deductive reasoning in language models.
- Rests on an assumption: The problems remain well within the models' advertised context limits.
- Interpretationown data
The reasoning is not faithful to the actual derivation of a query.
“This indicates that the reasoning is not faithful to the actual derivation of a query.”
Quote in the paperSubstantial claim- Rests on an assumption: Manual verification of 10% of the problems is sufficient to trust the LLM's failure reason extraction for all problems.
- Rests on an assumption: The reasoning summaries provided by closed-source models are sufficiently faithful to their internal reasoning to support conclusions about reasoning failures.
- Classified as probably not a substantial claim. 18
- May combine two claims. 14
Probably not a substantial claim: may not pass S3 (load-bearing).
PremisecitationZebraLogic identifies sharp accuracy decline in constraint-satisfaction once the search space exceeds 10^7 possibilities.
“ZebraLogic (Lin et al., 2025) identifies sharp accuracy decline in constraint-satisfaction once the search space exceeds 10 7 possibilities.”
Quote in the paperNot a substantial claim1 of 1 sources checked- cites Lin et al., 2025 source
Classified as probably not a substantial claim.
PremisecitationA model that has learned a robust implementation of the proof-tree tracing algorithm should, in principle, generalize beyond the shallow depths seen in previous benchmarks.
“This process is algorithmic; a model that has learned a robust implementation of this algorithm should, in principle, generalize beyond the shallow depths seen in previous benchmarks (Clark et al., 2020;Tafjord et al., 2021;Saparov and He, 2023).”
Quote in the paperSubstantial claim2 of 3 sources checked- cites Clark et al., 2020 source
Section 4.2 (p. 4) reports that a model trained on problems up to depth 3 generalized to depth-5 problems, supporting the point about reasoning beyond shallower training depths. But Section 2 (p. 2) says the authors impose no structure on the neural reasoning process; the paper does not establish that the model learned a proof-tree tracing algorithm. (LLM, conf=0.82)
Experimental — accuracy not yet measured - cites Tafjord et al., 2021 source
- cites Saparov and He, 2023
Couldn’t be matched to a paper in Crossref, so it can’t be checked.
May combine two claims.
PremisecitationThese previous benchmarks revealed that models at the time struggle as proof depth increases, but the depths studied remain shallow.
“These benchmarks revealed that models at the time struggle as proof depth increases, but the depths studied remain shallow.”
Quote in the paperSubstantial claim2 of 3 sources checkedProbably not a substantial claim: may not pass S3 (load-bearing), S4 (based).
Findingnone givenContext structural diversity is expectedly limited in depths 0 and 2.
“We create a canonical representation, shape, for the program to ensure context structural diversity, which is expectedly limited in depths 0 and 2.”
Quote in the paperNot a substantial claimClassified as probably not a substantial claim.
Findingown dataMedian input token count ranges from 133 at depth 0 to 62k tokens at depth 22.
“This results in a dataset of 2400 samples at varying levels of complexity, ranging from 133 median input tokens 4 at depth 0 to 62k tokens at depth 22.”
Quote in the paperSubstantial claimMay combine two claims.
Findingown dataThe majority of evaluated models approach chance or fail to perform above chance beyond depth 10.
“with the majority of models approaching chance beyond depth 10.”
- Also stated in: § 1 Introduction · plain
“with the majority of models failing to perform above chance beyond depth-10.”
Quote in the paperSubstantial claim- Also stated in: § 1 Introduction · plain
May combine two claims.
Findingown dataPROLONG is a synthetic benchmark of 2,400 Prolog logic programs that systematically varies reasoning depth, with the hardest case at depth 22.
“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.”
- Also stated in: § 1 Introduction · plain
“by constructing PROLONGfoot_1 , a benchmark of 2,400 logic programs in Prolog with reasoning depths up to 22.”
Quote in the paperSubstantial claim- Also stated in: § 1 Introduction · plain
Probably not a substantial claim: may not pass S4 (based).
Findingnone givenThe proof tree in PROLONG's Prolog-style problems can be represented as a simple chain.
“where the proof tree can be represented as a simple chain.”
Quote in the paperNot a substantial claimMay combine two claims.
Findingown dataModels' performance on the same depth is poorer given longer context, and for the same context length, models' performance declines with increased reasoning depth.
“Models' performance on the same depth is poorer given longer context, and for the same context length, models' performance declines with increased reasoning depth.”
Quote in the paperSubstantial claimProbably not a substantial claim: may not pass S3 (load-bearing). May combine two claims.
Findingown dataInput token counts are similar across models, with a slight increase in Claude-Opus-4.7.
“Note that they are similar across the board, with a slight increase in Claude-Opus-4.7.”
Quote in the paperNot a substantial claimMay combine two claims.
Findingown dataBy disentangling depth from context length in a shared-context setting, both factors independently and comparably degrade performance, despite being near-perfectly correlated in the original benchmark.
“By disentangling depth from context length in a shared-context setting, we show both factors independently and comparably degrade performance, despite being near-perfectly correlated in the original benchmark.”
Quote in the paperSubstantial claimMay combine two claims.
Findingown dataIn the fixed-context setting, both context length and proof depth have statistically significant and comparable negative impacts on performance (context-length: β = -0.54; proof-depth: β = -0.36; both p < 0.001).
“In this setting we find that both length and depth have statistically significant and comparable impact (context-length: β = -0.54;proof-depth: β = -0.36;both p < 0.001).”
Quote in the paperSubstantial claimProbably not a substantial claim: may not pass S4 (based).
Findingnone givenThe dataset is balanced.
“since the dataset is balanced”
Quote in the paperNot a substantial claimMay combine two claims.
Findingown dataIn a GLMM restricted to the four models evaluated in both settings, context length has a large negative effect (β = -1.48, p < 0.001) while proof depth appears negligible and not statistically significant (β = -0.15, p = 0.108).
“These initial results indicate that regression restricted to the four models evaluated in both settings attributes most of the effect to context length (β = -1.48,p < 0.001), while proof depth appears negligible and not statistically significant (β = -0.15,p = 0.108).”
Quote in the paperSubstantial claimProbably not a substantial claim: may not pass S3 (load-bearing).
Findingown dataOn the disentangled dataset (n = 2,400), the random-intercept variance is σ2 = 0.347 (SD = 0.589).
“On the disentangled dataset (n = 2,400), the random-intercept variance is σ2 = 0.347 (SD = 0.589)”
Quote in the paperNot a substantial claimMay combine two claims.
Findingown dataOn the disentangled dataset (n = 2,400), both fixed effects are significant and comparable in magnitude: context length β = -0.54, p < 0.001; proof depth β = -0.36, p < 0.001.
“both fixed effects are significant and comparable in magnitude (context length: β = -0.54,p < 0.001; proof depth: β = -0.36,p < 0.001).”
Quote in the paperSubstantial claimMay combine two claims.
InterpretationreasoningEvaluating these problems simultaneously stresses a model's ability to reason over extended chains and to locate and use relevant information within long contexts.
“Evaluating these problems simultaneously stresses a model's ability to reason over extended chains and to locate and use relevant information within long contexts.”
Quote in the paperSubstantial claimProbably not a substantial claim: may not pass S3 (load-bearing).
Premiseown dataContext sizes for the evaluated models range from 256k tokens to 1M.
“Context sizes for these models range from 256k tokens to 1M , full details are shown in Table 2 in the appendix.”
Quote in the paperNot a substantial claim0 of 1 sources checked- cites Table 2
Couldn’t be matched to a paper in Crossref, so it can’t be checked.
Probably not a substantial claim: may not pass S4 (based). May combine two claims.
Study design and conductnone givenIn PROLONG, every rule and fact in the program is necessary in the proof derivation, so the model cannot succeed by locating a few relevant pieces and ignoring the rest.
“PROLONG differs from these benchmarks in that every rule and fact in the program is necessary in the proof derivation, so the model cannot succeed by locating a few relevant pieces and ignoring the rest.”
Quote in the paperNot a substantial claimClassified as probably not a substantial claim. May combine two claims.
Study design and conductnone givenThe data generation algorithm guarantees by construction that at least one path in the DAG is as deep as length N, with other paths sampled uniformly up to that length.
“The algorithm by construction guarantees that at least one path in the DAG is as deep as length N , the other paths sampled uniformly up to that length.”
Quote in the paperSubstantial claimProbably not a substantial claim: may not pass S3 (load-bearing).
Study design and conductnone givenA canonical representation, shape, is created for the program to ensure context structural diversity.
“We create a canonical representation, shape, for the program to ensure context structural diversity, which is expectedly limited in depths 0 and 2.”
Quote in the paperNot a substantial claimProbably not a substantial claim: may not pass S3 (load-bearing).
Study design and conductnone givenThe context lengths are still well within the advertised context lengths of the evaluated models.
“We emphasize that the context lengths are still well within the advertised context lengths of these models.”
Quote in the paperNot a substantial claim0 of 1 sources checked- cites Table 2
Couldn’t be matched to a paper in Crossref, so it can’t be checked.
Classified as probably not a substantial claim.
Study design and conductreasoningThe framework's generated programs do not include recursion, reasoning loops, or negation.
“This framework is intended to study deductive reasoning at its simplest, so the class of generated programs does not include recursion, reasoning loops, or negation.”
Quote in the paperSubstantial claimProbably not a substantial claim: may not pass S3 (load-bearing), S4 (based). May combine two claims.
Study design and conductnone givenClosed-source models do not offer access to the actual reasoning tokens used to reach the final answer, only a summary, which limits analysis of their reasoning traces.
“Closed-source models do not offer access to the actual reasoning tokens used to reach the final answer, only a summary, which limits analysis of their reasoning traces.”
Quote in the paperNot a substantial claimProbably not a substantial claim: may not pass S3 (load-bearing).
Study design and conductown dataThe failure reason extraction by GPT-5.5 was manually verified for 10% of the problems.
“We used an LLM, GPT-5.5, to extract the failure reason and check whether it is valid, and verified these manually for 10% of the problems.”
Quote in the paperNot a substantial claimProbably not a substantial claim: may not pass S3 (load-bearing). May combine two claims.
Study design and conductnone givenThe maximum number of output tokens used in this study is 64k for most models, and 82k for Qwen models, as recommended in their docs.
“Finally, the maximum number of output tokens used in this study is 64k for most models, and 82k for Qwen models, as recommended in their docs.”
Quote in the paperNot a substantial claimClassified as probably not a substantial claim.
Study design and conductreasoningModel identity is included as a random intercept, (1 | model_id), rather than a fixed effect, to account for baseline differences in model capability without assuming a specific reference model.
“Model identity is included as a random intercept, (1 | model_id), rather than a fixed effect, to account for baseline differences in model capability without assuming a specific reference model.”
Quote in the paperSubstantial claim
The paper relies on this without support.
Performance on PROLONG's synthetic Prolog tasks is a valid measure of long-horizon deductive reasoning capabilities in LLMs.
“We empirically investigate long-horizon reasoning capabilities of LLMs, focusing on deductive logic expressed in Prolog.”
“We operationalize deductive reasoning as a query-answering problem over simple Prolog-style logic programs (Bratko, 2001), where the proof tree can be represented as a simple chain.”
The paper relies on this without support.
Logical inferences of the kind tested are important for real-world applications, such as policy compliance problems.
“In addition to domains such as mathematics, such logical inferences are important for real-world applications, for example in policy compliance problems.”
The paper relies on this without support.
The eight evaluated reasoning models across five families are representative of frontier LLMs for conclusions about frontier reasoning models generally.
“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.”
“We perform a systematic evaluation and analysis of 8 frontier reasoning models, and find that even the best-performing frontier model, GPT-5.5, degrades to 67% accuracy at depth-20, with the majority of models failing to perform above chance beyond depth-10.”
The paper relies on this without support.
The generated Prolog programs are a valid probe of long-horizon deductive reasoning capabilities in language models.
“The class of problems we consider in this framework is a smaller subset of definite Prolog logic programs, where the context can be represented as directed acyclic graphs (DAGs) (see Figure 5 of the appendix), with no loops or recursion in rule definitions.”
“This framework allows systematic construction of random logic programs with controllable levels of complexity.”
The paper relies on this without support.
The generated Prolog programs (simple, linear, no recursion/negation) are a valid testbed for studying long-horizon deductive reasoning in language models.
“This framework is intended to study deductive reasoning at its simplest, so the class of generated programs does not include recursion, reasoning loops, or negation.”
The paper relies on this without support.
The problems remain well within the models' advertised context limits.
“despite the problems remaining well within advertised context limits”
The paper relies on this without support.
Manual verification of 10% of the problems is sufficient to trust the LLM's failure reason extraction for all problems.
“We used an LLM, GPT-5.5, to extract the failure reason and check whether it is valid, and verified these manually for 10% of the problems.”
The paper relies on this without support.
The reasoning summaries provided by closed-source models are sufficiently faithful to their internal reasoning to support conclusions about reasoning failures.
“Closed-source models do not offer access to the actual reasoning tokens used to reach the final answer, only a summary, which limits analysis of their reasoning traces.”
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
Each contradiction between two passages listed here was confirmed by an independent check.
Generation algorithm appends a variable-containing fact
MinorAlgorithm 1 replaces the ground head's arguments with variables before appending that head as a fact at depth zero. This conflicts with the paper's description of facts as ground literals.
“2 U ← head.args 3 σ ← {Ui → xi | i ∈ [|U |]} 4 head ← LiteralWithVars(head, σ) 5 if N = 0 then 6 F.append(head)”
“a set of rules (implications) and facts (ground literals)”
Cites
Fitting Linear Mixed-Effects Models Using <b>lme4</b>
Bates, D., Mächler, M., Bolker, B., & Walker, S. (2015) · Journal of Statistical Software · doi:10.18637/jss.v067.i01 · Cited by 86,835 · cited 2× · see citing works
“To better understand which factor drives models’ failures, we fit a generalized linear mixed model (GLMM) (Bates et al., 2015) with a binomial family and logit link, including model identity as a random intercept and context length and proof depth as fixed effects; full details in Appendix F.”
Transformers as Soft Reasoners over Language
Clark, P., Tafjord, O., & Richardson, K. (2020) · Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence · doi:10.24963/ijcai.2020/537 · Cited by 176 · cited 2× · see citing works
“This process is algorithmic; a model that has learned a robust implementation of this algorithm should, in principle, generalize beyond the shallow depths seen in previous benchmarks (Clark et al., 2020; Tafjord et al., 2021; Saparov and He, 2023).”
ProofWriter: Generating implications, proofs, and abductive statements over natural language
Tafjord, O., Dalvi, B., & Clark, P. (2021) · Findings of the Association for Computational Linguistics: ACL-IJCNLP 2021 · doi:10.18653/v1/2021.findings-acl.317 · Cited by 122 · cited 2× · see citing works
“This process is algorithmic; a model that has learned a robust implementation of this algorithm should, in principle, generalize beyond the shallow depths seen in previous benchmarks (Clark et al., 2020; Tafjord et al., 2021; Saparov and He, 2023).”
Yang, A., Li, A., Yang, B., Zhang, B., Hui, B., Zheng, B., Yu, B., Gao, C., Huang, C., Lv, C., et al. (2025) · arXiv · doi:10.48550/arxiv.2505.09388 · Cited by 111 · see citing works
Language models, like humans, show content effects on reasoning tasks
Lampinen, A. K., Dasgupta, I., Chan, S. C. Y., Sheahan, H. R., Creswell, A., Kumaran, D., McClelland, J. L., & Hill, F. (2024) · PNAS Nexus · doi:10.1093/pnasnexus/pgae233 · Cited by 69 · cited 1× · see citing works
“Another notable difference from previous work is that we opt to use Prolog instead of natural language in our evaluations, in order to avoid ambiguity and content effects that can impact performance, as models may draw on prior knowledge rather than the stated context (Lampinen et al., 2024).”
OpenAI, :, Jaech, A., Kalai, A., Lerer, A., Richardson, A., El-Kishky, A., Low, A., Helyar, A., Madry, A., et al. (2024) · arXiv · Cited by 50 · see citing works
Language Models Are Greedy Reasoners: A Systematic Formal Analysis of Chain-of-Thought
Saparov, A., & He, H. (2022) · arXiv · doi:10.48550/arxiv.2210.01240 · Cited by 46 · cited 2× · see citing works
“This process is algorithmic; a model that has learned a robust implementation of this algorithm should, in principle, generalize beyond the shallow depths seen in previous benchmarks (Clark et al., 2020; Tafjord et al., 2021; Saparov and He, 2023).”
RULER: What's the Real Context Size of Your Long-Context Language Models?
Hsieh, C.-P., Sun, S., Kriman, S., Acharya, S., Rekesh, D., Jia, F., Zhang, Y., & Ginsburg, B. (2024) · arXiv · Cited by 13 · cited 1× · see citing works
“On the long-context processing side, LongBench-v2 (Bai et al., 2025), RULER (Hsieh et al., 2024), and HELMET (Yen et al., 2025) evaluate retrieval and QA over extended contexts, treating reasoning and retrieval as independent axes in most tasks.”
HELMET: How to Evaluate Long-Context Language Models Effectively and Thoroughly
Yen, H., Gao, T., Hou, M., Ding, K., Fleischer, D., Izsak, P., Wasserblat, M., & Chen, D. (2024) · arXiv · Cited by 2 · cited 1× · see citing works
“On the long-context processing side, LongBench-v2 (Bai et al., 2025), RULER (Hsieh et al., 2024), and HELMET (Yen et al., 2025) evaluate retrieval and QA over extended contexts, treating reasoning and retrieval as independent axes in most tasks.”
LongBench v2: Towards Deeper Understanding and Reasoning on Realistic Long-context Multitasks
Bai, Y., Tu, S., Zhang, J., Peng, H., Wang, X., Lv, X., Cao, S., Xu, J., Hou, L., Dong, Y., et al. (2024) · arXiv · doi:10.48550/arxiv.2412.15204 · Cited by 2 · cited 1× · see citing works
“On the long-context processing side, LongBench-v2 (Bai et al., 2025), RULER (Hsieh et al., 2024), and HELMET (Yen et al., 2025) evaluate retrieval and QA over extended contexts, treating reasoning and retrieval as independent axes in most tasks.”
ZebraLogic: On the Scaling Limits of LLMs for Logical Reasoning
Lin, B. Y., Bras, R. L., Richardson, K., Sabharwal, A., Poovendran, R., Clark, P., & Choi, Y. (2025) · arXiv · doi:10.48550/arxiv.2502.01100 · Cited by 1 · cited 1× · see citing works
“ZebraLogic (Lin et al., 2025) identifies sharp accuracy decline in constraint-satisfaction once the search space exceeds 10 7 possibilities.”
Flagged first, then by citations
Research works printed but not linked: 2
- Ivan Bratko. 2001. Prolog programming for artificial intelligence, 3rd ed. edition. International computer science series. Addison Wesley, Harlow, England.
- Daya Guo, Dejian Yang, Haowei Zhang, Junxiao Song, Peiyi Wang, Qihao Zhu, Runxin Xu, Ruoyu Zhang, Shirong Ma, Xiao Bi, Xiaokang Zhang, Xingkai Yu, Yu Wu, Z F Wu, Zhibin Gou, Zhihong Shao, Zhuoshu Li, Ziyi Gao, Aixin Liu, and 175 oth- ers. 2025. DeepSeek-R1 incentivizes reasoning in LLMs through reinforcement learning. Nature, 645(8081):633-638. · DOI · Paper page
- Authors
- Al-Negheimish, H., Ilieva, J., & Kim, Y.
- Affiliations
- King Saud University (SA)
- Massachusetts Institute of Technology (US)
- Venue
- arXiv
- Publisher
- arXiv
- Published
- 2026
- ISSN
- 2331-8422 (ISSN-L)
- arXiv
- 2610.11592
- OpenAlex
- W7221067410
- Semantic Scholar
- 1d15b6be58d6c611833757ac6ed1313df0db0e71
- Cited by
- 0
- References
- 11
- Type
- posted content
- Open access
- green
- arxiv.org
- Locations
- arXiv (Cornell University) (submittedVersion)
- arXiv (Cornell University) (cc-by)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Logic, Reasoning, and Knowledge
- Physical Sciences › Computer Science › Artificial Intelligence › Topic Modeling
- Physical Sciences › Computer Science › Artificial Intelligence › Natural Language Processing Techniques
- Keywords
- long-horizon reasoning, deductive reasoning, Prolog, large language models, long-context modeling, reasoning depth, LLM benchmarking
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Claims read by deepseek-v4.1-flash under definition version 3 (extract-v3) on 2026-10-19.
Classified by jev-1.13-20260917 (gold-guideline-v0.2) on 2026-10-19.
Cited sources are checked by gpt-6-sol.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
