Constraint satisfaction problems encompass a wide variety of combinatorial optimization problems including coloring, sudoku, but also SAT. AnyCSP is a neural framework that learns search heuristics for constraint satisfaction problems using a message-passing graph neural network.

This topic investigates replacing its message-passing architecture with a graph transformer while retaining its general representation of variables, possible values, and constraints. The project would explore how attention can exploit this structure and enable communication beyond local neighborhoods within AnyCSP’s iterative search process. The resulting architecture would be compared with the original AnyCSP and potentially ConsFormer on solution quality, runtime, memory consumption, and generalization to larger or structurally different instances.

Starting literature:

• AnyCSP: One Model, Any CSP (IJCAI 2023)
• GraphGPS (NeurIPS 2022)
• ConsFormer: Self-Supervised Transformers as Iterative Solution Improvers for Constraint Satisfaction (ICML 2025)