We’re excited to announce that Paulius Skaisgiris, Max Heisinger, Mykyta Ielanskyi, Erich Kobler, Thomas Pammer, and Veronika Semmelrock won the Outstanding Paper award for their Paper “From Natural Language to Exact Cover: A Neuro-Symbolic Approach to Zebra Puzzles” at the ICLR 2026 workshop for Logical Reasoning of Large Language Models!

The paper explores a neuro-symbolic approach to logical reasoning that combines the semantic capabilities of large language models with the reliability of formal symbolic methods. It proposes a framework in which natural language inputs are transformed into structured representations that can be solved through deterministic reasoning procedures. By integrating neural and symbolic components, the paper aims to bridge the gap between flexible language understanding and formally grounded inference. Empirical results demonstrate the potential of hybrid reasoning systems to improve performance on complex logical tasks beyond purely neural approaches.

The International Conference on Learning Representations (ICLR) is one of the world’s leading conferences in deep learning. It brings together researchers, engineers, entrepreneurs, and students from academia and industry to share advances in representation learning and related areas of machine learning. The conference is internationally recognized for presenting influential research across AI, statistics, and data science, with applications ranging from computer vision and speech recognition to robotics, computational biology, gaming, and natural language processing.

Congratulations to Paulius Skaisgiris, Max Heisinger, Mykyta Ielanskyi, Erich Kobler, Thomas Pammer, and Veronika Semmelrock on this excellent achievement!

Abstract

Chain-of-Thought (CoT) generation has substantially improved the performance of Large Language Models (LLMs) on complex reasoning tasks, including code generation, data analysis, and exam-style question answering. Despite these advances, purely neural LLMs continue to struggle with elementary logical reasoning problems and lack the determinism, soundness, and reliability characteristic of symbolic reasoning systems. Conversely, classical symbolic methods such as SAT solving and Exact Cover guarantee correctness and completeness but require problems to be expressed in highly specialized formal encodings, limiting their applicability to natural language inputs. In this work, we present a tightly integrated neuro-symbolic framework that bridges this gap by combining neural semantic parsing with deterministic constraint solving. Our approach leverages the relational extraction capabilities of modern LLMs to parse Zebra-style logic puzzles written in free-form text and translate the extracted constraints into structured tool calls. These function calls assemble a formally specified Exact Cover instance, which is subsequently solved by a symbolic solver to ensure logically consistent solutions. We conduct a comprehensive empirical evaluation across multiple parameter scales, post-training paradigms, and LLM families. The results on larger puzzles demonstrate that our hybrid approach consistently outperforms strong plain neural baselines, including CoT prompting, as well as recent neuro-symbolic methods.

About the Authors

Paulius Skaisgiris is a first-year PhD student at TU Wien Informatics, supervised by Mantas Šimkus. His research focuses on bridging symbolic and sub-symbolic AI methods to develop safe and responsible AI systems, with a particular emphasis on formal trustworthy specifications for aligned reinforcement learning. Prior to his PhD, he earned a BSc in Data Science and Artificial Intelligence from Maastricht University and an MSc in Logic from the University of Amsterdam.

Max Heisinger received his BSc, MSc, and PhD in Computer Science at the Johannes Kepler University Linz. He stayed for two years as a PostDoc at the Institute for Symbolic AI, improving prenexing techniques for solving quantified Boolean formulas and co-writing the fastest non-commutative Gröbner basis computation tool. He founded OptiKonf as a Spin-Out to apply his passion for logical solutions in industry, where he is building a novel platform for applied Symbolic AI, starting with smarter product configurators. Together with Simone Heisinger, he was awarded funding from the aws PreSeed - DeepTech to continue developing the technical foundations of OptiKonf. His research interests include SAT, QBF, and SMT solving, systems programming, programming languages, and machine learning.

Mykyta Ielanskyi is a PhD student at the Johannes Kepler University Linz at the Institute of Machine Learning. His research focuses on uncertainty quantification, post-training and decoding of large language models, and AI applications in the life sciences. His recent work has advanced uncertainty quantification algorithms and their empirical validation in LLMs, with publications in top-tier conferences. His broader interests include neurosymbolic systems and global optimization. His anticipated PhD thesis is titled “On Empirical Aspects of Bayesian Deep Learning in the Age of Scale”.

Erich Kobler received his BSc and MSc in Information and Computer Engineering, as well as his PhD in Computer Science (sub auspiciis Praesidentis) from the Graz University of Technology. After a PostDoc position at Graz University of Technology and a role as a senior lecturer at the Johannes Kepler University Linz, he co-led the Imaging Lab at the Department of Neuroradiology at the University Hospital Bonn. In 2024, he returned to the Johannes Kepler University Linz as an Assistant Professor for Machine/Deep Learning in Medical Imaging. In recognition of his PhD research on combining variational methods and deep learning, he received the Award of Excellence in 2021. His research interests include machine learning, medical imaging, inverse problems, and AI in medicine.

Thomas Pammer is a PhD student at the Johannes Kepler University Linz at the Institute for Application-oriented Knowledge Processing, supervised by Johannes Fürnkranz. His research interests lie in interpretable rule learning, with a particular focus on sparse Boolean rule networks. Within the BilAI Project, he actively contributes to collaborative research by integrating his exact optimization ideas and expanding his knowledge in subsymbolic AI methods. He earned his BSc in Statistics and Data Science and an MSc in Economics and Business Analytics with a strong focus on analytical methods.

Veronika Semmelrock is a doctoral researcher in the Cluster of Excellence Bilateral AI at the University of Klagenfurt, supervised by Gerhard Friedrich. Her research combines symbolic and subsymbolic AI methods to develop algorithms that solve combinatorial and optimization problems correctly and efficiently, with a particular focus on code evolution. She completed her Master’s degree in Artificial Intelligence and Cybersecurity at the University of Klagenfurt.

Curious about our other news? Subscribe to our news feed, calendar, or newsletter, or follow us on social media.