These tests on the other hand detect circulating tumor DNA (ctDNA), among other things. It is well known that tumors shed DNA and other material more than normal cells, even at early cancer stage. (Of course, later stage and more aggressive tumors are more indeed likely to shed more.) The detection limit for some of these tests is in the range of single digit copies of DNA fragment per mL of plasma.
Furthermore, the goal isn’t necessarily to detect every cancer as small as it could possibly be. Even if you don’t do a great job at finding all cancers at stage I, you may still save lives by detecting cancers at an earlier stage than they otherwise would have been found. Finding something at stage II instead of III or stage III instead of IV may well mean the difference of a shot for curative resection / radiation. (Whether these tests would be remotely cost-effective at attempting this at population scale... I leave as an exercise to the reader & healthcare system.)
Grail had a paper with some scant info on their test performance in multiple cancer types across all cancer stages. https://www.annalsofoncology.org/article/S0923-7534(21)02046...