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

Hadeel Al-Negheimish; Jasna Ilieva; Yoon Kim

doi:10.18653/2026.findings-emnlp.1888

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

Hadeel Al-Negheimish, Jasna Ilieva, Yoon Kim

Correct Metadata for

Use this form to create a GitHub issue with structured data describing the correction. You will need a GitHub account. Once you create that issue, the correction will be reviewed by a staff member.

⚠️ Mobile Users: Submitting this form to create a new issue will only work with github.com, not the GitHub Mobile app.

Important: The Anthology treat PDFs as authoritative. Please use this form only to correct data that is out of line with the PDF. See our corrections guidelines if you need to change the PDF.

Title Adjust the title. Retain tags such as <fixed-case>.

Authors Adjust author names and order to match the PDF.

Abstract Correct abstract if needed. Retain XML formatting tags such as <tex-math>. You may use ... for bold, ... for italic, ... for underline, <sc>...</sc> for small-caps, <tt>...<tt> for typewriter text, <url>...</url> for URLs, <a href=...> for hyperlinks, and <par/> for paragraph breaks.

Verification against PDF Ensure that the new title/authors match the snapshot below. (If there is no snapshot or it is too small, consult the PDF.)

Authors concatenated from the text boxes above:

ALL author names match the snapshot above—including middle initials, hyphens, and accents.

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.

Anthology ID:: 2026.findings-emnlp.1888
Volume:: Findings of the Association for Computational Linguistics: EMNLP 2026
Month:: October
Year:: 2026
Address:: Budapest, Hungary
Editors:: Hung-Yi Lee, Sunipa Dev, Jessy Li, Desmond Elliott
Venue:: Findings
SIG:: SIGDAT
Publisher:: Association for Computational Linguistics
Note:
Pages:: 40248–40259
Language:
URL:: https://aclanthology.org/2026.findings-emnlp.1888/
DOI:: 10.18653/2026.findings-emnlp.1888
Bibkey:
Cite (ACL):: Hadeel Al-Negheimish, Jasna Ilieva, and Yoon Kim. 2026. Probing for Long-Horizon Deductive Reasoning Capabilities in Language Models with Prolog. In Findings of the Association for Computational Linguistics: EMNLP 2026, pages 40248–40259, Budapest, Hungary. Association for Computational Linguistics.
Cite (Informal):: Probing for Long-Horizon Deductive Reasoning Capabilities in Language Models with Prolog (Al-Negheimish et al., Findings 2026)
Copy Citation:
PDF:: https://aclanthology.org/2026.findings-emnlp.1888.pdf

PDF Cite Search Fix data

Export citation

BibTeX
MODS XML
Endnote
Preformatted

@inproceedings{al-negheimish-etal-2026-probing,
    title = "Probing for Long-Horizon Deductive Reasoning Capabilities in Language Models with {P}rolog",
    author = "Al-Negheimish, Hadeel  and
      Ilieva, Jasna  and
      Kim, Yoon",
    editor = "Lee, Hung-Yi  and
      Dev, Sunipa  and
      Li, Jessy  and
      Elliott, Desmond",
    booktitle = "Findings of the {A}ssociation for {C}omputational {L}inguistics: {EMNLP} 2026",
    month = oct,
    year = "2026",
    address = "Budapest, Hungary",
    publisher = "Association for Computational Linguistics",
    url = "https://aclanthology.org/2026.findings-emnlp.1888/",
    doi = "10.18653/2026.findings-emnlp.1888",
    pages = "40248--40259",
    ISBN = "979-8-89176-462-0",
    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."
}

Download as File

<?xml version="1.0" encoding="UTF-8"?>
<modsCollection xmlns="http://www.loc.gov/mods/v3">
<mods ID="al-negheimish-etal-2026-probing">
    <titleInfo>
        <title>Probing for Long-Horizon Deductive Reasoning Capabilities in Language Models with Prolog</title>
    </titleInfo>
    <name type="personal">
        <namePart type="given">Hadeel</namePart>
        <namePart type="family">Al-Negheimish</namePart>
        <role>
            <roleTerm authority="marcrelator" type="text">author</roleTerm>
        </role>
    </name>
    <name type="personal">
        <namePart type="given">Jasna</namePart>
        <namePart type="family">Ilieva</namePart>
        <role>
            <roleTerm authority="marcrelator" type="text">author</roleTerm>
        </role>
    </name>
    <name type="personal">
        <namePart type="given">Yoon</namePart>
        <namePart type="family">Kim</namePart>
        <role>
            <roleTerm authority="marcrelator" type="text">author</roleTerm>
        </role>
    </name>
    <originInfo>
        <dateIssued>2026-10</dateIssued>
    </originInfo>
    <typeOfResource>text</typeOfResource>
    <relatedItem type="host">
        <titleInfo>
            <title>Findings of the Association for Computational Linguistics: EMNLP 2026</title>
        </titleInfo>
        <name type="personal">
            <namePart type="given">Hung-Yi</namePart>
            <namePart type="family">Lee</namePart>
            <role>
                <roleTerm authority="marcrelator" type="text">editor</roleTerm>
            </role>
        </name>
        <name type="personal">
            <namePart type="given">Sunipa</namePart>
            <namePart type="family">Dev</namePart>
            <role>
                <roleTerm authority="marcrelator" type="text">editor</roleTerm>
            </role>
        </name>
        <name type="personal">
            <namePart type="given">Jessy</namePart>
            <namePart type="family">Li</namePart>
            <role>
                <roleTerm authority="marcrelator" type="text">editor</roleTerm>
            </role>
        </name>
        <name type="personal">
            <namePart type="given">Desmond</namePart>
            <namePart type="family">Elliott</namePart>
            <role>
                <roleTerm authority="marcrelator" type="text">editor</roleTerm>
            </role>
        </name>
        <originInfo>
            <publisher>Association for Computational Linguistics</publisher>
            <place>
                <placeTerm type="text">Budapest, Hungary</placeTerm>
            </place>
        </originInfo>
        <genre authority="marcgt">conference publication</genre>
        <identifier type="isbn">979-8-89176-462-0</identifier>
    </relatedItem>
    <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.</abstract>
    <identifier type="citekey">al-negheimish-etal-2026-probing</identifier>
    <identifier type="doi">10.18653/2026.findings-emnlp.1888</identifier>
    <location>
        <url>https://aclanthology.org/2026.findings-emnlp.1888/</url>
    </location>
    <part>
        <date>2026-10</date>
        <extent unit="page">
            <start>40248</start>
            <end>40259</end>
        </extent>
    </part>
</mods>
</modsCollection>

Download as File

%0 Conference Proceedings
%T Probing for Long-Horizon Deductive Reasoning Capabilities in Language Models with Prolog
%A Al-Negheimish, Hadeel
%A Ilieva, Jasna
%A Kim, Yoon
%Y Lee, Hung-Yi
%Y Dev, Sunipa
%Y Li, Jessy
%Y Elliott, Desmond
%S Findings of the Association for Computational Linguistics: EMNLP 2026
%D 2026
%8 October
%I Association for Computational Linguistics
%C Budapest, Hungary
%@ 979-8-89176-462-0
%F al-negheimish-etal-2026-probing
%X 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.
%R 10.18653/2026.findings-emnlp.1888
%U https://aclanthology.org/2026.findings-emnlp.1888/
%U https://doi.org/10.18653/2026.findings-emnlp.1888
%P 40248-40259

Download as File

Markdown (Informal)

[Probing for Long-Horizon Deductive Reasoning Capabilities in Language Models with Prolog](https://aclanthology.org/2026.findings-emnlp.1888/) (Al-Negheimish et al., Findings 2026)

Probing for Long-Horizon Deductive Reasoning Capabilities in Language Models with Prolog (Al-Negheimish et al., Findings 2026)

ACL

Hadeel Al-Negheimish, Jasna Ilieva, and Yoon Kim. 2026. Probing for Long-Horizon Deductive Reasoning Capabilities in Language Models with Prolog. In Findings of the Association for Computational Linguistics: EMNLP 2026, pages 40248–40259, Budapest, Hungary. Association for Computational Linguistics.