Admittedly this is more an algorithms question than a Rust question.
To implement mini-kanren in scheme, all we really need is unification (of arbitrary terms) + backtracking.
In prolog, the default strategy seems to be Warren Abstract Machine - Wikipedia
There are a few implementations of wam in rust, including @mthom 's GitHub - mthom/scryer-prolog: A modern Prolog implementation written mostly in Rust.
Question: what is the advantage of warren-abstract-machine over unification+backtracking ?