During the prefilling phase for an input sequence $\mathbf{x}$, we generate a sequence of prefixes and their corresponding Key-Value (KV) cache states. This mapping is defined as:

$\begin{matrix} x_0 (\mathbf{x}_{<1}) & \Rightarrow & \mathrm{cache}_{<1} x_0 x_1 (\mathbf{x}_{<2}) & \Rightarrow & \mathrm{cache}_{<2} & ... & x_0 x_1 ... x_{m-1} (\mathbf{x}_{<m}) & \Rightarrow & \mathrm{cache}_{<m} \end{matrix}$

where $\mathrm{cache}_{<i}$ denotes the KV cache state for the prefix $\mathbf{x}_{<i}$. All these mappings can be stored in the prefix cache for efficient reuse.