In this paper we present a cycle-cutset driven stochastic local search algorithm which approximates the optimum of sums of unary and binary potentials, called Stochastic Tree Local Search or ST LS. We study empirically two pure variants of ST LS against the state-of-the art GLS + scheme and against a hybrid.