Would you mind providing a counterexample to illustrate what incorrect output it's producing?

> A lexicographical compare is linear in the size.

Indeed, lt2() also has a loop that iterates a linear number of times as you mention. It is consistent with this.

> the derived cmp2 is correct and has a run time twice that of cmp3. which matches the stl definitions of lexicographical_compare, see below.

Perhaps you might be confused about what lexicographical_compare does? It does not "compare" in the 3-way sense. It only performs a "less-than" comparison. The name is rather misleading.

2. the c++ behaviour in 2.4.2 is puzzling and most likely bug, worth reporting to and discussing with STL implementors.

I'm not sure what to report to anyone, as I don't find it puzzling; it is entirely consistent with everything I'm aware of and have tried to explain in the paper. It is also not specific to any particular implementation; I believe you will see this behavior on any correct implementation you try it on. It might be helpful if you try to produce a counterexample using what you believe would be a correct & efficient implementation to validate or invalidate this.