{"ID":6620651,"CreatedAt":"2026-07-15T01:01:48.440468303Z","UpdatedAt":"2026-07-15T03:28:55.185153975Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2607.12711","arxiv_id":"2607.12711","title":"MaxSAT-Based Feedback for Guiding Vision-Language Models in Sudoku","abstract":"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.","short_abstract":"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 un...","url_abs":"https://arxiv.org/abs/2607.12711","url_pdf":"https://arxiv.org/pdf/2607.12711v1","authors":"[\"Pedro Orvalho\",\"Guillem Alenyà\",\"Felip Manyà\"]","published":"2026-07-14T12:39:05Z","proceeding":"cs.AI","tasks":"[\"cs.AI\",\"cs.LO\"]","methods":"[\"Language Model\"]","has_code":false}