Keep the keys and values of prompts already run in a radix tree of tokens, so a new prompt that starts the same way skips that part of prefill; evict the least recently used leaves nobody is using.
This interactive visualization needs JavaScript.