  In contrast to being automatic, being Cayley automatic \emph{a priori} has no
geometric consequences. Specifically, Cayley graphs of automatic groups enjoy a
fellow traveler property. Here we study a distance function introduced by the
first author and Trakuldit which aims to measure how far a Cayley automatic
group is from being automatic, in terms of how badly the Cayley graph fails the
fellow traveler property. The first author and Trakuldit showed that if it
fails by at most a constant amount, then the group is in fact automatic. In
this article we show that for a large class of non-automatic Cayley automatic
groups this function is bounded below by a linear function in a precise sense
defined herein. In fact, for all Cayley automatic groups which have
super-quadratic Dehn function, or which are not finitely presented, we can
construct a non-decreasing function which (1) depends only on the group and (2)
bounds from below the distance function for any Cayley automatic structure on
the group.
