Naukowcy z arXiv zaprezentowali DiBS – metodę łączącą diffusion models z tradycyjnym solverem symbolicznym do rozwiązywania problemów spełniania ograniczeń, konkretnie Sudoku. Kluczowa innowacja polega na tym, że model dyfuzyjny nie rozwiązuje problemu samodzielnie, lecz pełni rolę przewodnika – podpowiada solver'owi, którą gałąź drzewa przeszukiwania rozwijać w pierwszej kolejności. Taki hybrydowy podход łączy zalety obu światów: bezwzględną poprawność solwerów symbolicznych z intuicją nauczonych modeli głębokich.
Istniejące podejścia mają komplementarne wady. Solwery oparte na deep learning'u są szybkie, ale mogą dać błędne odpowiedzi lub nie znaleźć rozwiązania. Tradycyjne solwery symboliczne zawsze znajdują prawidłowe rozwiązanie, ale czasem utknęły w długotrwałym przeszukiwaniu – szczególnie na tak zwanych instancjach tail, gdzie zwykłe heurystyki zawodzą. DiBS rozwiązuje ten problem, ucząc model, jak oceniać jakość kandydackich wartości w bieżącym częściowym przypisaniu.
Testy na benchmark'u Royle 17-clue Sudoku (znane trudne instancje) pokazały, że DiBS znacznie zmniejsza liczbę węzłów przeszukiwania i cofnięć (backtrack'ów) w porównaniu z silnymi heurystykami, szczególnie w percentylach long-tail. Naukowcy dostarczyli również teoretyczne wyjaśnienie, dlaczego ta metoda działa. Kod jest dostępny publicznie, co otwiera możliwości zastosowania podejścia do innych problemów kombinatorycznych.