# Do LLMs Dream of Discrete Algorithms?

arXiv: https://arxiv.org/abs/2506.23408 · HTML: https://mlsanity.com/paper/2506.23408/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 14 of its 54 references that are in the map.
- First posted on arXiv 29 Jun 2025.

## Builds on (most cited first, 14 of 14)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Retrieval-Augmented Generation for Knowledge-Intensive NLP Tasks](https://mlsanity.com/paper/2005.11401/) (2020)
- [A Survey on Hallucination in Large Language Models: Principles, Taxonomy, Challenges, and Open Questions](https://mlsanity.com/paper/2311.05232/) (2023)
- [The Rise and Potential of Large Language Model Based Agents: A Survey](https://mlsanity.com/paper/2309.07864/) (2023)
- [The AI Scientist: Towards Fully Automated Open-Ended Scientific Discovery](https://mlsanity.com/paper/2408.06292/) (2024)
- [A Survey on Knowledge Graphs: Representation, Acquisition and Applications](https://mlsanity.com/paper/2002.00388/) (2020)
- [Logic-LM: Empowering Large Language Models with Symbolic Solvers for Faithful Logical Reasoning](https://mlsanity.com/paper/2305.12295/) (2023)
- [The Illusion of Thinking: Understanding the Strengths and Limitations of Reasoning Models via the Lens of Problem Complexity](https://mlsanity.com/paper/2506.06941/) (2025)
- [On the Self-Verification Limitations of Large Language Models on Reasoning and Planning Tasks](https://mlsanity.com/paper/2402.08115/) (2024)
- [From Human Memory to AI Memory: A Survey on Memory Mechanisms in the Era of LLMs](https://mlsanity.com/paper/2504.15965/) (2025)
- [Graph-enhanced Large Language Models in Asynchronous Plan Reasoning](https://mlsanity.com/paper/2402.02805/) (2024)
- [CoT is Not True Reasoning, It Is Just a Tight Constraint to Imitate: A Theory Perspective](https://mlsanity.com/paper/2506.02878/) (2025)
- [Effort and Size Estimation in Software Projects with Large Language Model-based Intelligent Interfaces](https://mlsanity.com/paper/2402.07158/) (2024)
- [Log2NS: Enhancing Deep Learning Based Analysis of Logs With Formal to Prevent Survivorship Bias](https://mlsanity.com/paper/2105.14149/) (2021)

## Abstract (arXiv)

Large Language Models (LLMs) have rapidly transformed the landscape of artificial intelligence, enabling natural language interfaces and dynamic orchestration of software components. However, their reliance on probabilistic inference limits their effectiveness in domains requiring strict logical reasoning, discrete decision-making, and robust interpretability. This paper investigates these limitations and proposes a neurosymbolic approach that augments LLMs with logic-based reasoning modules, particularly leveraging Prolog predicates and composable toolsets. By integrating first-order logic and explicit rule systems, our framework enables LLMs to decompose complex queries into verifiable sub-tasks, orchestrate reliable solutions, and mitigate common failure modes such as hallucination and incorrect step decomposition. We demonstrate the practical benefits of this hybrid architecture through experiments on the DABStep benchmark, showing improved precision, coverage, and system documentation in multi-step reasoning tasks. Our results indicate that combining LLMs with modular logic reasoning restores engineering rigor, enhances system reliability, and offers a scalable path toward trustworthy, interpretable AI agents across complex domains.