# MaxSAT-Based Feedback for Guiding Vision-Language Models in Sudoku

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Placed in Reasoning benchmarks and evaluation, one of 17 directions in LLM reasoning.
- Builds on 14 of its 32 references that are in the map.
- First posted on arXiv 14 Jul 2026.

## Placed in

- LLM reasoning / [Reasoning benchmarks and evaluation](https://mlsanity.com/lr/reasoning-benchmarks-and-evaluation/)
- Multimodal LLMs / vision-language models / [VLM benchmarks and visual reasoning](https://mlsanity.com/mllm/vlm-benchmarks-and-visual-reasoning/)

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

- [Qwen3 Technical Report](https://mlsanity.com/paper/2505.09388/) (2025)
- [PAL: Program-aided Language Models](https://mlsanity.com/paper/2211.10435/) (2022)
- [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)
- [ZebraLogic: On the Scaling Limits of LLMs for Logical Reasoning](https://mlsanity.com/paper/2502.01100/) (2025)
- [Molmo2: Open Weights and Data for Vision-Language Models with Video Understanding and Grounding](https://mlsanity.com/paper/2601.10611/) (2026)
- [SatLM: Satisfiability-Aided Language Models Using Declarative Prompting](https://mlsanity.com/paper/2305.09656/) (2023)
- [Large Language Models Can Solve Real-World Planning Rigorously with Formal Verification Tools](https://mlsanity.com/paper/2404.11891/) (2024)
- [Planning Anything with Rigor: General-Purpose Zero-Shot Planning with LLM-based Formalized Programming](https://mlsanity.com/paper/2410.12112/) (2024)
- [ConstraintLLM: A Neuro-Symbolic Framework for Industrial-Level Constraint Programming](https://mlsanity.com/paper/2510.05774/) (2025)
- [Counterexample Guided Program Repair Using Zero-Shot Learning and MaxSAT-based Fault Localization](https://mlsanity.com/paper/2502.07786/) (2024)
- [MuSLR: Multimodal Symbolic Logical Reasoning](https://mlsanity.com/paper/2509.25851/) (2025)
- [PyVeritas: On Verifying Python via LLM-Based Transpilation and Bounded Model Checking for C](https://mlsanity.com/paper/2508.08171/) (2025)
- [Preference Elicitation for Step-Wise Explanations in Logic Puzzles](https://mlsanity.com/paper/2511.10436/) (2025)

## Built on by (most cited first, 1 of 1)

- [Recursive Vision Language Models for General Symbolic Reasoning](https://mlsanity.com/paper/2608.01534/) (2026)

## Abstract (arXiv)

Vision--Language Models (VLMs) have recently demonstrated promising performance on structured visual reasoning tasks, including grid-based puzzles. However, despite strong perceptual capabilities, these models lack explicit mechanisms for enforcing logical consistency and frequently generate assignments that violate underlying constraints. In this paper, we propose a neuro-symbolic approach that integrates formal constraint reasoning into the VLM solving process via a Maximum Satisfiability (MaxSAT) oracle. Rather than computing solutions directly, the symbolic component acts as a consistency validator and refinement engine. Candidate placements generated by the VLM are encoded as soft clauses in a partial MaxSAT formulation, while Sudoku constraints remain hard clauses. When inconsistencies arise, the MaxSAT solver identifies a largest mutually consistent subset of assignments, which is then translated into structured textual and visual feedback to guide subsequent refinements. We evaluate our approach on a Sudoku dataset across multiple open-source and closed-access VLMs. Results show that MaxSAT-based feedback improves logical consistency and increases the number of solved instances, particularly in full-board refinement mode. These findings demonstrate that symbolic optimisation can enhance the reliability of vision-language reasoning.