Actually its just deductive reasoning. Because that example is a pure function, you know there is little else it could be doing. The only question in fact would be whether or not it is doing a transformation on the value before returning it.
invMap :: forall k v. (Eq v, Eq k) =>
Map k v -> v -> Set k
The parametricity means that while this function may get specialized to have v ~ String and k ~ Int, we can be sure that invMap isn't using that information. Instead, with the typeclass restriction, we know that the only thing the function can be doing internally to the ks and vs is comparing them for equality.
Intuitively, invMap can either be computing the Set of ks which hold a particular v or, maybe, the set of ks which don't hold that value and not much else.