From Natural Language to Exact Cover: A Neuro-Symbolic Approach to Zebra Puzzles (arXiv 2611.03641)

Forum topic · 小凯 · 2026-11-03

Summary

This paper presents a neuro-symbolic framework combining LLM-based semantic parsing with deterministic exact cover solving for Zebra-style logic puzzles. While chain-of-thought (CoT) prompting has improved LLM reasoning, purely neural models still lack the determinism, soundness, and reliability of symbolic systems; conversely, symbolic methods like SAT solving and exact cover guarantee correctness but require specialized formal encodings. The proposed approach uses an LLM to translate natural-language puzzle descriptions into structured tool calls that build an exact cover instance, then a symbolic solver computes solutions. Leveraging the unique-solution property of Zebra puzzles, invalid, under-constrained, or over-constrained encodings are iteratively fed back and corrected. Systematic evaluation across multiple parameter scales, post-training paradigms, and LLM families shows the hybrid method consistently outperforms strong purely neural baselines (including CoT prompting) and recent neuro-symbolic approaches.

Paper Overview

Field: Machine Learning Authors: Paulius Skaisgiris, Thomas Pammer, Veronika Semmelrock, Mykyta Ielanskyi, Maximilian Heisinger, Erich Kobler Published: 2026-11-02 arXiv: 2611.03641

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 synergistic neuro-symbolic framework that bridges this gap by combining neural semantic parsing with deterministic exact cover reasoning.

Approach

Given a natural-language description of a Zebra-style logic puzzle, the LLM translates entities and constraints into structured tool calls that construct an exact cover instance. A symbolic solver then computes the solution. Using the unique-solution property of Zebra puzzles, invalid, under-constrained, or over-constrained encodings are identified and iteratively corrected via feedback to the LLM.

Results

The authors conduct systematic empirical evaluations across multiple parameter scales, post-training paradigms, and LLM families. The hybrid neuro-symbolic method consistently outperforms strong purely neural baselines—including CoT prompting—as well as recent neuro-symbolic approaches.

--- *Auto-collected on 2026-11-04*