[Misc]: Prefix caching in the BlockManagerV2

[cadedaniel]

Recently, we refactored the block manager subsystem to improve testability by separating concerns of each layer. See #3492 for more information.

The following features are missing to support prefix caching:

• Eviction policies based on last access time
• Eviction policies based on length of prefix (necessary for correctness as our prefix caching attention only supports contiguous prefixes)
• Tracking the computed bit in prefix caching
• E2E correctness test comparing greedy generation equality with prefix caching vs. without prefix caching (see this test for inspiration, which compares greedy generation equality between v1 and v2 block managers)
• Performance profiling of v2 + prefix caching

For design, #3492 has more details (also feel free to reach out to me). One key is to understand how prefix caching promotion works in the new design:

[cadedaniel]

cc @robertgshaw2-neuralmagic

[rkooo567]

QQ: So the new block manager will be used just for spec decoding until these features will be available?

[cadedaniel]

prefix caching w/v2 block manager is blocked on these features, non-prefix caching usage is blocked by #3666 and #3665

[robertgshaw2-neuralmagic]

@SageMoore taking a look