Not necessarily "on the device"—they can be part of the browser. Or—for phones at least—part of the carrier profile. In either of those cases, rather than one centralized authority, there's an explicit chain of trust: you trust the browser maker, who trusts set X; or you trust your ISP, who trusts set Y.
That's more in the mindset of how the original X.509 design was supposed to work: you trust your company/university, who installs set Z on their workstations. Except, in this case, you're much more free to switch who you trust.
Of course, in the "carrier profile" case, a lot of the smaller ISPs might delegate their cert-verification to some company set up specifically to be an, ahem, Authority for Certificates.
But those companies would be "CAs" in a very different sense than the one we have today: they wouldn't issue certs; they'd instead generate pin lists and run OCSP portals, i.e., verify certs—including certs that are not their own. They'd essentially provide "TLS stack plugins" for devices that subscribed to them, instructing those devices on what makes for a valid or invalid cert. (Or you could build the infrastructure the other way around, and make a "TLS thin client" library that talks to its CA every time it wants to know if a cert is valid. Given that OCSP already exists, it wouldn't be that much more traffic.)
This would also mean that the TLS "technology" could evolve much more quickly, since TLS extensions wouldn't have to get 100% traction with TLS client software before they'd be useful. Instead, the extension would merely need to be taken into consideration by one CA when that CA generated its pin-lists and OCSP databases (or, dynamically by webapp-like software, in the TLS-thin-client case.)