Elamur Research⌕
☰
home / papers / 2026 / Logic Haystacks: Probing LLMs' Long-Context Logical Reasoning (Without Easily Identifiable Unrelated Padding)

Logic Haystacks: Probing LLMs' Long-Context Logical Reasoning (Without Easily Identifiable Unrelated Padding)

Paper · 2026 · Damien Sileo

Summary

Long-context benchmarks for LLMs often hide a small task inside unrelated filler text, such as Paul Graham essays. Models can spot and ignore that filler, and it may also accidentally interfere with the task. This paper introduces Logic Haystacks, a benchmark where every distractor resembles the relevant evidence but is formally guaranteed not to affect the answer.

The author uses the Unigram-FOL grammar to generate simplified English sentences paired with first-order logic forms. A "satisfiable merging" procedure, checked with the Vampire theorem prover, repeatedly joins smaller premises and removes sentences that cause contradictions. This builds consistent premises of up to 4096 sentences.

The task is to name the premise lines that contradict a given hypothesis. A counterfactual check removes each candidate line in turn and confirms that every gold evidence line is actually needed, so each item has exactly one correct answer.

Models score far worse with these realistic distractors than with essay padding, and their effective context drops sharply around 128 sentences. The results suggest standard padding-based tests overstate usable context length.

Key points

  • Scale and generation cost: premises reach 2048 sentences (about 25k GPT-4 tokens). Producing the data required 12 days of computation with 52 threads on an Intel Xeon Gold 5320 machine. The vocabulary of names and predicates was tripled from 26 to 78 so that symbols repeat often without causing too many semantic clashes.
  • Data split and scoring: there are 600 validation and 2790 test examples. Each test variant contains 200 contradiction items with 1, 2, or 3 necessary and sufficient evidence lines. Answers are scored with Jaccard similarity against the gold evidence.
  • Models tested: the Llama 3.1 family (8B, 70B, 405B), Llama-3.3-70B, Gemini 1.5 Flash, and GPT-4o-mini. Gemini Flash is clearly strongest under realistic distractors, a gap that Paul Graham padding hides.
  • Difficulty with more evidence: with two required evidence lines, no model exceeds 20% retrieval at 1024 sentences. Embedding the hypothesis inside the premise makes the task hard even with easy padding.
  • Model size: larger Llama models perform better, but scaling alone does not give robust results. The datasets are publicly released on Hugging Face.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

 Institutions

🔬Institut national de recherche en sciences et technologies du numériqueLe Chesnay-Rocquencourt · France84 works · 25,414 citations🔬Centre National de la Recherche ScientifiqueParis · France168 works · 62,369 citations🎓Centrale Lille InstitutVilleneuve-d'Ascq · France3 works · 403 citations🔬Centre de Recherche en Informatique, Signal et Automatique de LilleVilleneuve-d'Ascq · France3 works · 403 citations🎓Université de LilleLille · France3 works · 403 citations

 Fields, topics and concepts

📚 Shelves 5The field of science this work belongs to (OpenAlex fields).Computer Science · 16,667 worksArtificial Intelligence · 16,194 worksArts and Humanities · 16,039 worksLanguage and Linguistics · 15,891 worksComputer Vision and Pattern Recognition · 2,869 works

🧭 Topics 3Research subjects and languages the work is about.Language models & pretraining · 3,320 worksReasoning · 1,426 worksInterpretability · 130 works

Cite

Cite as Damien Sileo. 2026. Logic Haystacks: Probing LLMs' Long-Context Logical Reasoning (Without Easily Identifiable Unrelated Padding). Proceedings of the 19th Conference of the European Chapter of the Association for Computational Linguistics (Volume 2: Short Papers).

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.18653/v1/2026.eacl-short.3

@inproceedings{sileo2026logic,
  title = {{Logic Haystacks: Probing LLMs' Long-Context Logical Reasoning (Without Easily Identifiable Unrelated Padding)}},
  author = {Damien Sileo},
  booktitle = {Proceedings of the 19th Conference of the European Chapter of the Association for Computational Linguistics (Volume 2: Short Papers)},
  year = {2026},
  doi = {10.18653/v1/2026.eacl-short.3},
  url = {https://doi.org/10.18653/v1/2026.eacl-short.3}
}

References

23 references, 10 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. Yushi Bai, Shangqing Tu, Jiajie Zhang, Hao Peng, Xiaozhi Wang, Xin Lv, Shulin Cao, Jiazheng Xu, Mosh Levy, Alon Jacoby, and Yoav Goldberg. 2024. Same task, more tokens: the impact of input length on the reasoning performance of large language models. arXiv preprint arXiv:2402.14848.
  2. Damien Sileo. 2024. Scaling synthetic logical reasoning datasets with context-sensitive declarative grammars. In Proceedings of the 2024 Conference on Empirical Methods in Natural Language Processing, pages 5275–5283, Miami, Florida, USA. Association for Computational Linguistics. find
  3. Patrick Lewis, Ethan Perez, Aleksandra Piktus, Fabio Petroni, Vladimir Karpukhin, Naman Goyal, Heinrich Küttler, Mike Lewis, Wen-tau Yih, Tim Rocktäschel, et al. 2020. Retrieval-augmented generation for knowledge-intensive nlp tasks. Advances in Neural Information Processing Systems, 33:9459–9474.
  4. Damien Sileo. 2025. Attention overflow: Language model input blur during long-context missing items identification. In Proceedings of the 14th International Joint Conference on Natural Language Processing and the 4th Conference of the Asia-Pacific Chapter of the Association for Computational Linguis… find
  5. Mo Li, Songyang Zhang, Yunxin Liu, and Kai Chen. 2024. Needlebench: Can llms do retrieval and reasoning in 1 million context window? arXiv preprint arXiv:2407.11963. — [arXiv:2407.11963](https://arxiv.org/abs/2407.11963) find
  6. Zhan Ling, Kang Liu, Kai Yan, Yifan Yang, Weijian Lin, Ting-Han Fan, Lingfeng Shen, Zhengyin Du, and Jiecao Chen. 2025. Longreason: A synthetic long-context reasoning benchmark via context expansion. find
  7. Damien Sileo and Antoine Lernould. 2023. MindGames: Targeting theory of mind in large language models with dynamic epistemic modal logic. In Findings of the Association for Computational Linguistics: EMNLP 2023, pages 4570–4577, Singapore. Association for Computational Linguistics. find
  8. Nelson F Liu, Kevin Lin, John Hewitt, Ashwin Paranjape, Michele Bevilacqua, Fabio Petroni, and Percy Liang. 2024. Lost in the middle: How language models use long contexts. Transactions of the Association for Computational Linguistics, 12:157–173.
  9. Amirkeivan Mohtashami and Martin Jaggi. 2024. Random-access infinite context length for transformers. Advances in Neural Information Processing Systems, 36. find
  10. Damien Sileo and Marie-francine Moens. 2023. Probing neural language models for understanding of words of estimative probability. In Proceedings of the 12th Joint Conference on Lexical and Computational Semantics (*SEM 2023), pages 469–476, Toronto, Canada. Association for Computational Linguistics. find
  11. Rémi Monasson, Riccardo Zecchina, Scott Kirkpatrick, Bart Selman, and Lidror Troyansky. 1999. Determining computational complexity from characteristic ‘phase transitions’. Nature, 400(6740):133–137. find
  12. Zayne Sprague, Xi Ye, Kaj Bostrom, Swarat Chaudhuri, and Greg Durrett. 2023. Musr: Testing the limits of chain-of-thought with multistep soft reasoning. arXiv preprint arXiv:2310.16049. find
  13. Terufumi Morishita, Gaku Morio, Atsuki Yamaguchi, and Yasuhiro Sogawa. 2023. Learning deductive reasoning from synthetic corpus based on formal logic. In International Conference on Machine Learning, pages 25254–25274. PMLR. find
  14. Yi Tay, Mostafa Dehghani, Samira Abnar, Yikang Shen, Dara Bahri, Philip Pham, Jinfeng Rao, Liu Yang, Sebastian Ruder, and Donald Metzler. 2021. Long range arena : A benchmark for efficient transformers. In International Conference on Learning Representations.
  15. Giles Reger, Martin Suda, Andrei Voronkov, Laura Kovács, Ahmed Bhayat, Bernhard Gleiss, Marton Hajdu, Petra Hozzova, JR Evgeny Kotelnikov, Michael Rawson, et al. 2022. Vampire 4.7-smt system description. find
  16. Jidong Tian, Yitian Li, Wenqing Chen, Liqiang Xiao, Hao He, and Yaohui Jin. 2021. Diagnosing the first-order logical reasoning ability through LogicNLI. In Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing, pages 3738–3747, Online and Punta Cana, Dominican Republ…
  17. Kyle Richardson, Hai Hu, Lawrence Moss, and Ashish Sabharwal. 2020. Probing natural language inference models through semantic fragments. Proceedings of the AAAI Conference on Artificial Intelligence, 34:8713–8721.
  18. Cunxiang Wang, Ruoxi Ning, Boqi Pan, Tonghui Wu, Qipeng Guo, Cheng Deng, Guangsheng Bao, Qian Wang, and Yue Zhang. 2024a. Novelqa: A benchmark for long-range novel question answering. arXiv preprint arXiv:2403.12766.
  19. Kyle Richardson and Ashish Sabharwal. 2022. Pushing the limits of rule reasoning in transformers through natural language satisfiability. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 11209–11219. find
  20. Lei Wang, Shan Dong, Yuhui Xu, Hanze Dong, Yalu Wang, Amrita Saha, Ee-Peng Lim, Caiming Xiong, and Doyen Sahoo. 2024b. Mathhay: An automated benchmark for long-context mathematical reasoning in llms. arXiv preprint arXiv:2410.04698. — [arXiv:2410.04698](https://arxiv.org/abs/2410.04698) find
  21. Nipun Sadvilkar and Mark Neumann. 2020. PySBD: Pragmatic sentence boundary disambiguation. In Proceedings of Second Workshop for NLP Open Source Software (NLP-OSS), pages 110–114, Online. Association for Computational Linguistics.
  22. Jason Weston, Antoine Bordes, Sumit Chopra, and Tomás Mikolov. 2016. Towards ai-complete question answering: A set of prerequisite toy tasks. In 4th International Conference on Learning Representations, ICLR 2016, San Juan, Puerto Rico, May 2-4, 2016, Conference Track Proceedings.
  23. Yukun Zhu, Ryan Kiros, Rich Zemel, Ruslan Salakhutdinov, Raquel Urtasun, Antonio Torralba, and Sanja Fidler. 2015. Aligning books and movies: Towards story-like visual explanations by watching movies and reading books. In The IEEE International Conference on Computer Vision (ICCV).

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/sileo-2026-logic-haystacks-probing-llms-long/