SemanticTokens Edits not performant in large documents

In the Razor and Roslyn LSP we have struggled with writing performant SemanticTokens experiences. The problems seem to boil down as follows (doing my best to include things that only exist as a consequence of the shape of LSP as opposed to Roslyn and Razor decisions).

1. There is no mechanism other than workspace/semanticTokens/refresh by which the client may avoid "polling". workspace/semanticTokens/refresh is a "big hammer" in that it means all documents will (eventually) need to repaint. This means that a client must either poll every Xms (inefficient) or operate on TYPECHAR (either this will re-request for every visible editor (and possibly not-visible editors unless an "isDirty" system is implimented) or it will only send a request for the document that was edited, at which point something such as adding/removing a static modifier may not result in re-coloration of another window which was expected).
2. The algorithms to calculate the difference between the previous token array and the new token array are supra-linear with regards to document length and number of changes. This means that as document size increases we're either using an increasing amount of memory (possible Out-Of-Memory Exception), or CPU (just plain slower) depending on your implementation. We have tried strategies to a mitigate this ("chunking" to reduce the supra-linear growth), but we still found the requirement to calculate the diff caused us performance issues.
3. An edit request requires that the SyntaxTree for the entire document be walked. For particularly large documents and/or complicated SyntaxTrees this can be VERY expensive (10's of seconds have been seen in real-world Razor scenarios). This may be reduced by using the range request rather than the edit request (and only requesting the range that can be viewed), however then not only is the size of the reply in the "no change" scenario (very likely if we still have polling) much larger, but on each reply the client must "re-paint" (however sophisticated/expensive that may be). Combine that with the fact that some clients are "polling" and there's a lot of wasted network and CPU.

One idea is we could include a textDocument/semanticTokens/refresh API similar to the one for workspace which specifies the document(s) to invalidate, and possibly range(s) within that document. This helps clients avoid either polling or sending too many requests using the workspace API, but it does not alone improve the performance of the individual calls (either on the server side for calculation or the client side for re-paint).

I can go into greater depth about our scenario and its troubles if that's helpful.

CC @allisonchou and @gundermanc.

Start by reviewing the semantic-tokens protocol behavior described here, especially workspace/semanticTokens/refresh and the edit, range, and refresh request shapes. Determine whether the proposed document- or range-scoped invalidation addresses the stated client and server costs, and define the protocol changes and compatibility expectations before implementation.