I mean: I see how one can test an implementation against a specification of an interface. What are "tests written against the implementation"?

One of the usual techniques is to examine the code as written and find all the decision points, which will lead to discovering all the possible paths of execution through the code. Tests can then be written to "exercise" each of these possible paths to ensure that every line of code behaves as expected.

It is arguable how often this is useful and, of course, refactoring is likely to render some of these tests obsolete.