What, so it only takes 20 minutes every {TTL_expiry} seconds? How does that help? The cache becomes a pastiche of what the service should have had in the first place - a "GET /starting_tree" handler.

I think you have gravely misunderstood me. It's not necessary for the client to expire their entire cache all at once - this would be incredibly foolish.

If you make a GET request against a REST interface then you should cache the results of that request and note the datetime you made it.

If you need to make a subsequent request against the same resource then you can first make a HEAD request to get only the headers. By comparing timestamps you can see whether or not the resource has changed since you last accessed it.

If the REST interface is appropriately designed then the "last changed" value will propagate upwards from the leaves of the tree towards the API root. So caching the results of requests can save you from making an immense number of requests.

It will still be hideously slow on the first run due to overheads.

Yes, the first run will be slow. But subsequent runs (which presumably are very large in number) will be much quicker.

The first run will be intolerably slow. Caching will not be sufficient.