Ze względu na potencjalnie ogromny i czasami nieograniczony rozmiar niejawnej sieci Bayesa, która odpowiada typowemu OUPM, pełne jej rozwinięcie i wykonanie dokładnego wnioskowania jest dość niepraktyczne. Zamiast tego musimy wziąć pod uwagę przybliżone algorytmy wnioskowania, takie jak MCMC. Z grubsza mówiąc, algorytm MCMC dla OUPM bada przestrzeń możliwych światów zdefiniowanych przez zbiory obiektów i relacje między nimi, jak pokazano na rysunku 18.1 (góra). Ruch pomiędzy sąsiednimi stanami w tej przestrzeni może nie tylko zmieniać relacje i funkcje, ale także dodawać lub odejmować obiekty oraz zmieniać interpretacje stałych symboli. Chociaż każdy możliwy świat może być ogromny, obliczenia prawdopodobieństwa wymagane dla każdego kroku – czy to w próbkach Gibbsa, czy w Metropolis-Hastings – są całkowicie lokalne i w większości przypadków zajmują stały czas. Dzieje się tak, ponieważ stosunek prawdopodobieństwa między sąsiednimi światami zależy od podgrafu o stałej wielkości wokół zmiennych, których wartości są zmieniane. Co więcej, zapytanie logiczne może być oceniane przyrostowo w każdym odwiedzanym świecie, zwykle w stałym czasie na świat, zamiast przeliczania od zera. Należy zwrócić szczególną uwagę na fakt, że typowy OUPM może mieć możliwe światy o nieskończonej wielkości. Jako przykład rozważmy model śledzenia wielocelowego na rysunku :
funkcja X(a; t), oznaczająca stan samolotu a w czasie t, odpowiada nieskończonej sekwencji zmiennych dla nieograniczonej liczby samolotów na każdym kroku. Z tego powodu MCMC dla OUPMs próbkuje nie całkowicie określone światy możliwe, ale światy częściowe, z których każdy odpowiada rozłącznemu zbiorowi kompletnych światów. Częściowy świat to minimalna samonośna instancja6 podzbioru odpowiednich zmiennych – to znaczy przodków zmiennych dowodowych i zapytań. Na przykład zmienne X(a,t) dla wartości t większych niż czas ostatniej obserwacji (lub czas zapytania, w zależności od tego, który jest większy) są nieistotne, więc algorytm może rozważyć tylko skończony przedrostek ciągu nieskończonego.