  We reformulate the Cavity Approximation (CA), a class of algorithms recently
introduced for improving the Bethe approximation estimates of marginals in
graphical models. In our new formulation, which allows for the treatment of
multivalued variables, a further generalization to factor graphs with arbitrary
order of interaction factors is explicitly carried out, and a message passing
algorithm that implements the first order correction to the Bethe approximation
is described. Furthermore we investigate an implementation of the CA for
pairwise interactions. In all cases considered we could confirm that CA[k] with
increasing $k$ provides a sequence of approximations of markedly increasing
precision. Furthermore in some cases we could also confirm the general
expectation that the approximation of order $k$, whose computational complexity
is $O(N^{k+1})$ has an error that scales as $1/N^{k+1}$ with the size of the
system. We discuss the relation between this approach and some recent
developments in the field.
