Solving Zebra Puzzles Using Constraint-Guided Multi-Agent Systems

2024-07-04 · Shmuel Berman, Kathleen McKeown, Baishakhi Ray

Prior research has enhanced the ability of Large Language Models (LLMs) to solve logic puzzles using techniques such as chain-of-thought prompting or introducing a symbolic representation. These frameworks are still usually insufficient to solve complicated logical problems, such as Zebra puzzles, due to the inherent complexity of translating natural language clues into logical statements. We introduce a multi-agent system, ZPS, that integrates LLMs with an off the shelf theorem prover. This system tackles the complex puzzle-solving task by breaking down the problem into smaller, manageable parts, generating SMT (Satisfiability Modulo Theories) code to solve them with a theorem prover, and using feedback between the agents to repeatedly improve their answers. We also introduce an automated grid puzzle grader to assess the correctness of our puzzle solutions and show that the automated grader is reliable by evaluating it in a user-study. Our approach shows improvement in all three LLMs we tested, with GPT-4 showing 166% improvement in the number of fully correct solutions.

📄 PDF Abstract BibTeX arXiv:2407.03956

Code (0)

등록된 구현이 없습니다.

Methods 이 논문이 사용한 방법론

Attention 설명 없음

Linear Layer A Linear Layer is a projection $\mathbf{XW + b}$.

Multi-Head Attention 설명 없음

Softmax The Softmax output function transforms a previous layer's output into a vector of probabilities. It is commonly used for multiclass classification. Given an input vector $x$…

Residual Connection 설명 없음

BPE Byte Pair Encoding, or BPE, is a subword segmentation algorithm that encodes rare and unknown words as sequences of subword units. The intuition is that various word…

Layer Normalization Unlike batch normalization, Layer Normalization directly estimates the normalization statistics from the summed inputs…

Label Smoothing Label Smoothing is a regularization technique that introduces noise for the labels. This accounts for the fact that datasets may have mistakes in them, so maximizing the…

ZebraLogic: On the Scaling Limits of LLMs for Logical Reasoning

2025-02-03 · Bill Yuchen Lin, Ronan Le Bras, Kyle Richardson, Ashish Sabharwal 외

We investigate the logical reasoning capabilities of large language models (LLMs) and their scalability in complex non-monotonic reasoning. To this end, we introduce ZebraLogic, a comprehensive evaluation framework for a…

Logical Reasoning

Logic.py: Bridging the Gap between LLMs and Constraint Solvers

2025-02-17 · Pascal Kesseli, Peter O'Hearn, Ricardo Silveira Cabral

We present a novel approach to formalise and solve search-based problems using large language models, which significantly improves upon previous state-of-the-art results. We demonstrate the efficacy of this approach on t…

Language Modeling Language Modelling

Zebra-CoT: A Dataset for Interleaved Vision Language Reasoning

2025-07-22 · Ang Li, Charles Wang, Deqing Fu, Kaiyu Yue 외 arxiv

Humans often use visual aids, for example diagrams or sketches, when solving complex problems. Training multimodal models to do the same, known as Visual Chain of Thought (Visual CoT), is challenging due to: (1) poor off…

Reinforcement Learning Multimodal Reasoning Visual Reasoning

Crossing Cuts Polygonal Puzzles: Models and Solvers

2021-06-19 · CVPR 2021 1 · Peleg Harel, Ohad Ben-Shahar

Jigsaw puzzle solving, the problem of constructing a coherent whole from a set of non-overlapping unordered fragments, is fundamental to numerous applications, and yet most of the literature has focused thus far on l…

MultiZebraLogic: A Multilingual Logical Reasoning Benchmark

2025-11-05 · Sofie Helene Bruun, Dan Saattrup Smart arxiv

We create high-quality datasets for LLM evaluation of logical reasoning skills across nine different languages, which have been manually checked by fluent speakers. The datasets consist of so-called zebra puzzles, and we…