Algorytm przeszukiwania atomowej przestrzeni stanów czyni postęp tylko w jeden sposób: poprzez rozszerzenie węzła w celu odwiedzenia następców. Algorytm CSP ma wybór. Może generować następniki, wybierając nowe przypisanie zmiennej, lub może wykonać określony rodzaj wnioskowania zwany propagacją ograniczeń: używając ograniczeń do zmniejszenia liczby dopuszczalnych wartości dla zmiennej, co z kolei może zredukować dopuszczalne wartości dla innej zmiennej, i tak dalej. Chodzi o to, aby pozostawić mniej wyborów do rozważenia przy następnym wyborze przypisania zmiennej. Propagacja ograniczeń może być spleciona z wyszukiwaniem lub może być wykonana jako etap przetwarzania wstępnego przed rozpoczęciem wyszukiwania. Czasami to wstępne przetwarzanie może rozwiązać cały problem, więc w ogóle nie jest wymagane wyszukiwanie. Kluczową ideą jest lokalna spójność. Jeśli potraktujemy każdą zmienną jako węzeł w grafie, a każde ograniczenie binarne jako krawędź, to proces wymuszania spójności lokalnej w każdej części grafu powoduje eliminację niespójnych wartości w całym grafie. Istnieją różne rodzaje spójności lokalnej, które z kolei omówimy teraz.