To be precise, a small number of very small Prolog programs can be run backwards.

There are essentially no significant Prolog programs that are reversible with acceptable efficiency.

To be even more precise, Prolog programs only ever run forward because the order of evaluation is fixed as top-down, left-to-right. These notions of "forward" and "backward" are very unhelpful and should be given up. Beginners find the order of evaluation hard enough to understand, let's not confuse them even more.

Also, the notion is woefully incomplete. Let's say we consider this "forward":

    ?- list_length([a, b, c], Length).
    Length = 3.

Then you would say that this is "backward":

    ?- list_length(List, 3).
    List = [_A, _B, _C].

Fine, but what's this then? "Inward"?

    ?- list_length([a, b, c], 3).
    true.

And then presumably this is "outward":

    ?- list_length(List, Length).
    List = [], Length = 0 ;
    ...
    List = [a, b, c], Length = 3 .

None of these cases change the order of evaluation. They are all evaluated top-down, left-to-right. The sooner beginning Prolog programmers understand this, the better. The sooner we stop lying to people to market Prolog, the better.

What's going on in the second example? Did Prolog generate a list term stuffed with gensym variables, which satisifies the list_length being 3?

It generated a list stuffed with distinct logical variables. Any list of length 3 is unifiable with this list. Or in other words, this is the unique (up to variable renaming) most general list of length 3.

Whether this is a "yes" to your question depends on what your mental model of "gensym variables" is. They are variables, not symbols (which Prolog would call atoms).

I was largely joking. Even though the capability is there, it is not computationally practical nor possible to accomplish such a feat for any sufficiently complex programme.

In the most extreme case, attempting to run a complex Prolog programme backwards will result in an increase in entropy levels in the universe to such an extent that it will cause an instant cold (or hot) death of our universe, and life as we know it will perish momentarily (another tongue in cheek joke).

the bidirectional (relational) aspect of prolog is what got me into this. I love symmetries so it was a natural appeal even before I learned about logic programming (Sean Parent made a google talk about similar ideas implemented in cpp). That said it's very limited. But I wonder how far it could go. (the kanren guys might have more clues)