Guessing the Secret in RLWE Search-to-Decision
The &quot;guesses&quot; are part of the enumeration of all possible values of $s\bmod \mathfrak{q}_iR^\vee$. The reduction has two parts essentially:

A way of telling if the guess was correct (the $\mathsf{WDLWE}_{q, \Psi}^i$ oracle)
A small space of values to try (as values $s\bmod \mathfrak{q}_i R^\vee$ are within $R_q^\vee/\mathfrak{q}_iR_q^\vee$, which from context in the paper appears to have size $N(\mathfrak{q}_i) = q = \mathsf{poly}(n)$).

You then enumerate all possible guesses, and return the one which verifies to be correct.
This is a deterministic process (although you're free to choose the particular order to enumerate things in).