At the very least, it always tells Truecaller who is calling you (your phone doesn't have a copy of the database - it is being looked up).
And at least as of a few years ago, Truecaller would upload a copy of your phonebook to their servers. That's how they bootstrapped their database - from user's addressbooks. I only ever used it on a burner with an empty phone book, and occasionally get Truecaller pearls like "Annoying John - do not answer" as the caller's name.
