Silniejsze formy propagacji można zdefiniować pojęciem -konsystencja. CSP jest k-spójny, jeśli dla dowolnego zestawu k-1 zmiennych i dla dowolnego spójnego przypisania do tych zmiennych, spójną wartość można zawsze przypisać dowolnej th zmiennej. 1-konsystencja mówi, że przy danym zbiorze pustym możemy uczynić spójnym dowolny zbiór jednej zmiennej: to właśnie nazwaliśmy spójnością węzłów. Konsystencja 2 jest taka sama jak konsystencja łuku. W przypadku wykresów z ograniczeniami binarnymi 3-spójność jest taka sama jak spójność ścieżki.
CSP jest silnie k-spójny, jeśli jest (k-1)-spójny, a także (k-2)-spójny …, aż do 1-spójny. Załóżmy teraz, że mamy CSP z n węzłami i uczynimy go silnie n-spójnym (tj. silnie k-spójnym dla k = n). Możemy wtedy rozwiązać problem w następujący sposób: Najpierw wybieramy stałą wartość dla X1. Mamy wtedy gwarancję, że będziemy mogli wybrać wartość dla X2, ponieważ wykres jest 2-spójny, dla X3, ponieważ jest 3-spójny i tak dalej. Dla każdej zmiennej Xi wystarczy przeszukać wartości d w dziedzinie, aby znaleźć wartość zgodną z Xi…Xi-1 . Całkowity czas działania to tylko O(n2d).
Oczywiście nie ma darmowego obiadu: spełnianie ograniczeń jest ogólnie NP-zupełne, a każdy algorytm ustalania n-spójności musi w najgorszym przypadku zająć czas wykładniczy w n. Co gorsza, n-spójność wymaga również przestrzeni, która jest wykładnicza w n. W praktyce określenie odpowiedniego poziomu sprawdzania spójności jest w większości nauką empiryczną. Obliczanie ze spójności 2 jest powszechne, a ze spójności 3 rzadziej.