Back to series
· 13 min read

PagedAttention and KV Cache Management


I. Why Is KV Cache Needed?

During autoregressive generation in large language models, every time the model generates a new token, it must use the context information that has already been generated.

The Transformer's attention computation requires Query, Key, and Value:

Attention(Q,K,V)=Softmax\left(\frac{QK^T}{\sqrt{d_k}}\right)V

Where:

  • Query (Q): the query vector of the current token.
  • Key (K): the key vector of historical tokens.
  • Value (V): the value vector of historical tokens.
  • d_k: the dimension of the key vector.

If the Key and Value of the entire historical sequence are recomputed every time a new token is generated, a large amount of redundant computation will occur.

KV Cache is designed to solve this problem.

1. Computation Without KV Cache

Assume the model needs to generate three tokens:

Input: A B C

Generation 1:
Compute A, B, C → generate D

Generation 2:
Recompute A, B, C, D → generate E

Generation 3:
Recompute A, B, C, D, E → generate F

As the sequence grows, historical tokens are repeatedly recomputed.

2. Computation With KV Cache

With KV Cache, the model saves the Key and Value of historical tokens.

Input: A B C

Prefill:
Compute A, B, C
Save K, V cache

Decode 1:
Compute only K, V for D
Read historical cache
Generate E

Decode 2:
Compute only K, V for E
Read historical cache
Generate F

The KV of historical tokens does not need to be recomputed.

Note: the Decode stage still needs to read the historical KV Cache for attention; it only avoids recomputing the K and V of historical tokens.

3. Where KV Cache Is Located in the Transformer

For a model with multiple Transformer layers, each layer needs to maintain its own Key and Value.

Assume the model has 32 layers:

  • Layer 1 maintains its own K, V.
  • Layer 2 maintains its own K, V.
  • And so on up to layer 32.

Therefore, KV Cache is cache data organized by dimensions such as Layer, Head, and Token.

II. Data Structure of KV Cache

To understand PagedAttention, you first need to understand the storage structure of KV Cache.

1. Basic Dimensions of KV Cache

A typical KV Cache can be abstracted as:

KVCache \in \mathbb{R}^{L\times 2\times B\times S\times H_{kv}\times D_h}

Where:

Parameter Meaning
L Number of Transformer layers
2 The two parts: Key and Value
B Request batch size
S Cache sequence length
H_{kv} Number of KV heads
D_h Dimension of each head

In actual implementations, the physical layout of KV Cache is affected by the Attention Backend, parallelization strategy, and hardware implementation, and does not necessarily strictly follow the above dimension order.

2. KV Cache Storage Illustration

Assume the model has 2 layers, and each layer stores Key and Value:

Transformer
│
├── Layer 0
│   ├── Key Cache
│   └── Value Cache
│
└── Layer 1
    ├── Key Cache
    └── Value Cache

Each token generates its own Key and Value at the corresponding layer.

As the generation length increases, KV Cache continues to grow.

3. Differences Between KV Cache and Model Weights

Comparison Dimension Model Weights KV Cache
Content stored Parameters obtained from model training Key, Value of historical tokens
Whether it changes with requests Usually unchanged Changes dynamically with request execution
Whether it is related to context length Not directly related Highly related
Whether it increases with concurrency Usually does not increase linearly with the number of requests Usually increases with concurrency
Lifecycle Usually exists with the model instance Usually changes with the lifecycle of a request or cache reuse
GPU memory purpose Store model parameters Store historical context computation results

Model weights determine the model's computational capability, while the KV Cache stores the historical information already computed during inference.

III. Why Does the KV Cache Consume So Much GPU Memory?

The GPU memory footprint of the KV Cache is directly related to the model architecture, context length, number of concurrent requests, and data precision.

1. KV Cache Memory Formula

The theoretical footprint of the KV Cache for a single request can be expressed as:

M_{KV}= 2\times L\times S\times H_{kv}\times D_h\times P

Where:

  • L: number of model layers.
  • S: number of cached tokens.
  • H_{kv}: number of KV heads.
  • D_h: head dimension.
  • P: number of bytes per element.
  • 2: represents Key and Value respectively.

If there are multiple requests:

M_{KV,total}= 2\times L\times B\times S\times H_{kv}\times D_h\times P

This assumes all requests have the same cache length. In practice, request lengths often differ, so memory must be calculated per request or estimated from the block allocation.

2. Memory Estimation Example

Assume a model with the following parameters:

Parameter Value
Number of Transformer layers 32
Number of KV heads 8
Head dimension 128
Data precision FP16
Context length per request 8192
Number of concurrent requests 16

FP16 uses 2 bytes per element.

Single request:

M_{KV}= 2\times32\times8192\times8\times128\times2
=1,073,741,824\ Bytes

This is approximately 1 GiB.

16 requests:

M_{KV,total}=16\times1GiB=16GiB

In other words, the KV Cache alone can occupy about 16 GiB of GPU memory.

This does not yet include model weights, activations, the CUDA workspace, or runtime overhead.

3. Impact of GQA and MQA on the KV Cache

KV Cache size is also affected by the attention architecture.

Attention structure Number of KV heads Memory characteristics
MHA Same as the number of query heads Larger KV Cache
GQA Fewer than the number of query heads Smaller KV Cache
MQA Usually 1 Smaller KV Cache

For example, a model with 32 query heads:

  • MHA: 32 KV heads.
  • GQA: 8 KV heads.
  • MQA: 1 KV head.

With all other parameters identical:

M_{GQA}=\frac{8}{32}M_{MHA}
M_{MQA}=\frac{1}{32}M_{MHA}

Therefore, GQA and MQA not only reduce the GPU memory requirements of the KV Cache but also lower the pressure of reading KV data during the decode phase.

IV. Problems with Traditional KV Cache Management

Traditional contiguous KV Cache management typically requires each request's cache to be stored in a contiguous region of GPU memory.

This approach is simple to implement but has obvious problems in high-concurrency inference scenarios.

1. Wasted Memory from Pre-allocation

Suppose three requests each have a maximum context length of 4096 tokens:

Request Maximum Reserved Tokens Actual Used Tokens
A 4096 512
B 4096 2048
C 4096 3000

If space is preallocated according to the maximum context length, each request would need to occupy 4096 tokens of cache space.

But actual usage is only 512, 2048, and 3000, respectively.

This creates a large amount of unused cache space.

2. GPU Memory Fragmentation Problem

Suppose there are multiple free regions of different sizes in GPU memory:

GPU memory space:

[Request A][Free][Request B][Free][Request C][Free]

Although the total free space may be sufficient, there may not be a contiguous space large enough to satisfy the allocation requirements of a new request.

This is the external GPU memory fragmentation problem.

Two types of waste need to be distinguished:

  • Internal fragmentation: The allocated space is larger than the actual usage, and the remaining part cannot be used by other requests.
  • External fragmentation: Free space is scattered, making it difficult to satisfy larger contiguous allocation requests.

3. Uncertain Request Length

The output length of a large model usually cannot be accurately determined in advance.

For example:

  • Request A ends after generating 20 tokens.
  • Request B ends after generating 200 tokens.
  • Request C ends after generating 2000 tokens.

If preallocated according to the maximum length, there will be obvious waste.

If allocated according to the current length, the cache space will need to be expanded frequently.

Traditional contiguous allocation methods struggle to simultaneously balance dynamic expansion, GPU memory utilization, and concurrency capacity.

4. Main Problems of Traditional Management Methods

Problem Cause Impact
Internal fragmentation Preallocated space is too large GPU memory utilization decreases
External fragmentation Contiguous memory allocation restrictions Allocation is difficult
Difficulty in dynamic expansion Request lengths keep changing Requires reallocation or copying
Isolation between requests Caches are usually allocated independently Difficult to share the same prefix
Limited concurrency A single request occupies too much space The number of runnable requests decreases

V. Core Idea of PagedAttention

PagedAttention is one of the core technologies proposed by vLLM.

It draws on the virtual memory paging mechanism of operating systems and divides the KV Cache into fixed-size Blocks.

Each request no longer needs to occupy an entire contiguous GPU memory region; instead, a Block Table records the mapping between logical positions and physical Blocks.

1. From Contiguous Storage to Paged Storage

Traditional approach:

Request A:
[Block 0][Block 1][Block 2][Block 3]

Request B:
[Block 4][Block 5][Block 6][Block 7]

Each request usually requires a contiguous cache region.

PagedAttention:

Request A:
Logical Block 0 → Physical Block 3
Logical Block 1 → Physical Block 8
Logical Block 2 → Physical Block 1

Request B:
Logical Block 0 → Physical Block 5
Logical Block 1 → Physical Block 2
Logical Block 2 → Physical Block 9

Physical Blocks can be distributed in different locations in GPU memory.

Logically contiguous tokens do not need to be stored in physically contiguous GPU memory regions.

2. Core Components of PagedAttention

Component Function
KV Cache Block Stores K and V data for a fixed number of tokens
Block Table Records the mapping between logical Blocks and physical Blocks
Block Manager Manages Block allocation, release, and references
Free Block Pool Holds currently available physical Blocks
Attention Kernel Reads KV Cache according to the Block mapping and computes Attention
Scheduler Schedules execution based on request status and resource conditions

3. Overall Structure of the Paging Mechanism

flowchart TD
    A["Request Token Sequence"] --> B["Logical Token Position"]
    B --> C["Compute Logical Block Index"]
    C --> D["Query Block Table"]
    D --> E["Get Physical Block Index"]
    E --> F["Compute Offset Within Block"]
    F --> G["Locate KV Cache"]
    G --> H["Read Key and Value"]
    H --> I["Perform Attention Computation"]
    I --> J["Generate Model Output"]

    K["Block Manager"] --> L["Free Block Pool"]
    L --> M["Allocate Physical Block"]
    M --> D
    N["Request State Change"] --> O["Update Block Table"]
    O --> D

    style A fill:#E0F0FE,stroke:#93BCE8,color:#1E4976
    style B fill:#F5F8F4,stroke:#B5CBBB,color:#40594A
    style C fill:#F5F8F4,stroke:#B5CBBB,color:#40594A
    style D fill:#EAE8FA,stroke:#A49BD5,color:#51477D
    style E fill:#EAF3EC,stroke:#83A995,color:#315D49
    style F fill:#F5F8F4,stroke:#B5CBBB,color:#40594A
    style G fill:#EAF3EC,stroke:#83A995,color:#315D49
    style H fill:#E0F0FE,stroke:#93BCE8,color:#1E4976
    style I fill:#EAF3EC,stroke:#83A995,color:#315D49
    style J fill:#DCEFE5,stroke:#4F8B70,color:#24563F
    style K fill:#EAE8FA,stroke:#A49BD5,color:#51477D
    style L fill:#F5F8F4,stroke:#B5CBBB,color:#40594A
    style M fill:#EAF3EC,stroke:#83A995,color:#315D49
    style N fill:#F7F4E8,stroke:#C7B77A,color:#675A2D
    style O fill:#F5F8F4,stroke:#B5CBBB,color:#40594A

6. Organization of KV Cache Blocks

To understand PagedAttention, the most important thing is to understand how Blocks are organized.

1. Basic Definition of a Block

A Block is a KV Cache storage unit with a fixed capacity.

Assume:

  • Each Block holds 16 Tokens.
  • Each Token stores a Key and a Value at each layer.
  • Every Transformer Layer has corresponding cached data.

When a request has 35 Tokens, it requires:

N_{\text{blocks}}= \left\lceil\frac{35}{16}\right\rceil =3

The logical organization of the three Blocks:

Logical Block Token Range Used Count
Block 0 0–15 16
Block 1 16–31 16
Block 2 32–34 3

The last Block still has 13 Tokens of remaining capacity.

This part is unused space inside the Block.

2. Calculating the Offset Within a Block

Assume the Block Size is 16 and the logical position of the Token is 35.

Logical Block index:

BlockIndex=\left\lfloor\frac{35}{16}\right\rfloor=2

Offset within the Block:

Offset=35\bmod16=3

Therefore:

  • The logical Block index is 2.
  • The offset within the Block is 3.

Then query the Block Table for the corresponding physical Block index to ultimately locate the KV Cache data.

General formulas:

LogicalBlockIndex= \left\lfloor\frac{Position}{BlockSize}\right\rfloor
BlockOffset=Position\bmod BlockSize
PhysicalBlock= BlockTable[LogicalBlockIndex]

3. Structure of the Block Table

Assume request A uses three logical Blocks:

Logical Block Physical Block
0 3
1 8
2 1

The Block Table can be represented as:

block_table = {
    "request_A": [3, 8, 1]
}

This means that logical Blocks 0, 1, and 2 of request A correspond to physical Blocks 3, 8, and 1, respectively.

Note that this is only a simplified Python representation to help understand the mapping relationship. Inside real vLLM, efficient data structures and GPU-accessible index information are used; it does not simply rely on a Python dictionary to perform every Token's GPU memory access.

4. Physical Layout of Blocks

The physical cache layout of PagedAttention is usually organized along dimensions such as model layer, KV type, Block, Head, and Head Dimension.

Conceptually, it can be understood as:

KV Cache
│
├── Layer 0
│   ├── Key
│   │   ├── Physical Block 0
│   │   ├── Physical Block 1
│   │   └── Physical Block N
│   │
│   └── Value
│       ├── Physical Block 0
│       ├── Physical Block 1
│       └── Physical Block N
│
├── Layer 1
│   ├── Key
│   └── Value
│
└── Layer N
    ├── Key
    └── Value

The specific physical tensor layout depends on the Attention Backend and model configuration being used.

VII. Execution Principles of PagedAttention

PagedAttention does not simply store the KV Cache in blocks; it also needs to solve how to efficiently access these scattered cached data.

1. Cache Access in Traditional Attention

Suppose a request has 64 historical Tokens.

The traditional contiguous storage approach can directly access a contiguous segment of KV Cache:

Token 0 → Token 1 → Token 2 → ... → Token 63

The access logic is relatively simple.

However, contiguous memory allocation brings problems with dynamic expansion and GPU memory fragmentation.

2. Cache Access in PagedAttention

Suppose the Block Size is 16:

Logical Tokens:

0-15    → Logical Block 0
16-31   → Logical Block 1
32-47   → Logical Block 2
48-63   → Logical Block 3

The physical Blocks may be distributed as:

Logical Block 0 → Physical Block 5
Logical Block 1 → Physical Block 2
Logical Block 2 → Physical Block 9
Logical Block 3 → Physical Block 1

The Attention Kernel needs to find the corresponding physical cache according to the Block Table.

3. Attention Access Process

flowchart TD
    A["Current Query"] --> B["Read logical Token position"]
    B --> C["Calculate logical Block number"]
    C --> D["Query Block Table"]
    D --> E["Obtain physical Block address"]
    E --> F["Calculate offset within Block"]
    F --> G["Read historical Key"]
    F --> H["Read historical Value"]
    G --> I["Calculate QK similarity"]
    H --> J["Participate in weighted sum"]
    I --> K["Softmax"]
    K --> L["Attention output"]
    J --> L

    style A fill:#E0F0FE,stroke:#93BCE8,color:#1E4976
    style B fill:#F5F8F4,stroke:#B5CBBB,color:#40594A
    style C fill:#F5F8F4,stroke:#B5CBBB,color:#40594A
    style D fill:#EAE8FA,stroke:#A49BD5,color:#51477D
    style E fill:#EAF3EC,stroke:#83A995,color:#315D49
    style F fill:#F5F8F4,stroke:#B5CBBB,color:#40594A
    style G fill:#E0F0FE,stroke:#93BCE8,color:#1E4976
    style H fill:#E0F0FE,stroke:#93BCE8,color:#1E4976
    style I fill:#EAF3EC,stroke:#83A995,color:#315D49
    style J fill:#EAF3EC,stroke:#83A995,color:#315D49
    style K fill:#EAE8FA,stroke:#A49BD5,color:#51477D
    style L fill:#DCEFE5,stroke:#4F8B70,color:#24563F

4. What Does PagedAttention Change?

PagedAttention does not change the core mathematical computation of Attention.

What it changes is:

  • The storage organization of KV Cache.
  • The mapping from logical Tokens to physical Blocks.
  • The way the Attention Kernel accesses historical KV.
  • The management of cache allocation and release.

Therefore, the value of PagedAttention is mainly reflected in GPU memory management and high-concurrency inference efficiency.

8. Block Manager: Cache Allocation and Release

Block Manager is a key component in KV Cache management.

It is responsible for maintaining the usage status of physical Blocks and dynamically allocating and releasing cache according to the request lifecycle.

1. Responsibilities of Block Manager

Responsibility Specific Role
Block initialization Create a pool of available physical Blocks
Block allocation Allocate cache space for new requests
Block mapping Establish the relationship between logical Blocks and physical Blocks
Block expansion Request additional Blocks when a request grows
Block release Reclaim cache when a request completes
Reference counting Manage Blocks shared by multiple requests
Cache reuse Support reuse scenarios such as prefix caching

2. Free Block Pool

Suppose the system initializes 10 physical Blocks:

Free Block Pool:

[0][1][2][3][4][5][6][7][8][9]

Request A needs two Blocks:

Request A:
[0][1]

The free pool becomes:

Free Block Pool:

[2][3][4][5][6][7][8][9]

Request B needs three Blocks:

Request B:
[2][3][4]

When Request A completes, Block 0 and Block 1 can return to the free pool.

3. Block Allocation Process

flowchart TD
    A["New request arrives"] --> B["Calculate the number of Blocks needed"]
    B --> C["Query Free Block Pool"]
    C --> D{"Are there enough free Blocks"}
    D -->|"Yes"| E["Allocate physical Blocks"]
    D -->|"No"| F["Check reclaimable cache"]
    F --> G{"Do reclaimable resources exist"}
    G -->|"Yes"| H["Free or reclaim Blocks"]
    G -->|"No"| I["Wait or apply preemption policy"]
    H --> C
    I --> J["Wait for resources to become available"]
    J --> C
    E --> K["Update Block Table"]
    K --> L["Request continues execution"]

    style A fill:#E0F0FE,stroke:#93BCE8,color:#1E4976
    style B fill:#F5F8F4,stroke:#B5CBBB,color:#40594A
    style C fill:#EAE8FA,stroke:#A49BD5,color:#51477D
    style D fill:#F7F4E8,stroke:#C7B77A,color:#675A2D
    style E fill:#EAF3EC,stroke:#83A995,color:#315D49
    style F fill:#F5F8F4,stroke:#B5CBBB,color:#40594A
    style G fill:#F7F4E8,stroke:#C7B77A,color:#675A2D
    style H fill:#EAF3EC,stroke:#83A995,color:#315D49
    style I fill:#F7EAE7,stroke:#C98D7C,color:#754438
    style J fill:#F5F8F4,stroke:#B5CBBB,color:#40594A
    style K fill:#EAE8FA,stroke:#A49BD5,color:#51477D
    style L fill:#DCEFE5,stroke:#4F8B70,color:#24563F

4. Block Release Mechanism

After a request finishes, the Block Manager checks the Blocks occupied by that request.

If a Block is no longer referenced by any other request, it can be released and put back into the free pool.

If a Block is being shared by multiple requests, it cannot be released directly; instead, its reference count must be decremented until no request is using it any more.

This mechanism is an important foundation that allows Prefix Caching to reuse caches safely.

IX. Prefix Caching: Prefix Cache Sharing

The paged structure of PagedAttention provides the basis for KV Cache sharing.

Prefix Caching allows different requests to reuse the KV Cache produced by an identical prefix, thereby reducing redundant Prefill computation.

1. Why is prefix caching needed?

In real-world workloads, many requests use a fixed system prompt.

For example:

Request A:
You are a professional Java assistant.
Please explain JVM garbage collection.

Request B:
You are a professional Java assistant.
Please explain the Java class loading mechanism.

Request C:
You are a professional Java assistant.
Please explain how the thread pool works.

All three requests contain the same system prompt.

If this shared prefix were recomputed every time, GPU compute resources would be wasted.

2. The reuse process of prefix caching

Assume the shared prefix has already been computed and the corresponding KV Cache Blocks still exist.

Subsequent requests can reuse these Blocks by matching the cached information.

flowchart TD
    A["Request A"] --> C["Shared Token Prefix"]
    B["Request B"] --> C
    D["Request C"] --> C
    C --> E["Execute Prefix Prefill"]
    E --> F["Generate KV Cache Block"]
    F --> G["Build Cache Index"]
    G --> H["Reuse by Request A"]
    G --> I["Reuse by Request B"]
    G --> J["Reuse by Request C"]
    H --> K["Compute A's Unique Content"]
    I --> L["Compute B's Unique Content"]
    J --> M["Compute C's Unique Content"]

    style A fill:#E0F0FE,stroke:#93BCE8,color:#1E4976
    style B fill:#E0F0FE,stroke:#93BCE8,color:#1E4976
    style D fill:#E0F0FE,stroke:#93BCE8,color:#1E4976
    style C fill:#EAE8FA,stroke:#A49BD5,color:#51477D
    style E fill:#EAF3EC,stroke:#83A995,color:#315D49
    style F fill:#EAF3EC,stroke:#83A995,color:#315D49
    style G fill:#EAE8FA,stroke:#A49BD5,color:#51477D
    style H fill:#F5F8F4,stroke:#B5CBBB,color:#40594A
    style I fill:#F5F8F4,stroke:#B5CBBB,color:#40594A
    style J fill:#F5F8F4,stroke:#B5CBBB,color:#40594A
    style K fill:#DCEFE5,stroke:#4F8B70,color:#24563F
    style L fill:#DCEFE5,stroke:#4F8B70,color:#24563F
    style M fill:#DCEFE5,stroke:#4F8B70,color:#24563F

3. Basis for Prefix Cache Matching

Prefix Caching usually matches based on the content of the Token Block and the relevant computation context, rather than simply determining whether two pieces of text are similar.

Factors to consider:

  • Whether the Token sequences are identical.
  • Whether the models are the same.
  • Whether the relevant computation configurations are compatible.
  • Whether the multimodal input information is identical.
  • Whether the cached Block still exists.
  • Whether the cache meets the reuse conditions of the current request.

4. Why Is Reuse Usually Done by Full Block?

Paged cache is usually managed in units of Blocks.

For example, if Block Size is 16:

Common prefix:

Token 0–15: Full Block
Token 16–31: Full Block
Token 32–39: Unfilled Block

Full Blocks are easier to match and share in cache.

The last unfilled Block usually cannot be directly used as a shared prefix for any new request in the same way as a full Block. The exact reuse boundary depends on the cache granularity and matching strategy in the implementation.

5. Reference Counting and Copy-on-Write

When multiple requests share the same physical Block, the system needs to track reference relationships.

Assume:

Request A ──┐
            ├── Shared physical Block 5
Request B ──┘

If request A completes, it can only decrement the reference count of that Block, and the Block cannot be reclaimed directly.

If request B is still using that Block, the cache must continue to retain it.

When different content needs to be written after a shared prefix, the system also needs to avoid directly overwriting shared data. A common approach is Copy-on-Write, which allocates new Blocks when shared content needs to be modified.

10. Dynamic Expansion Mechanism of KV Cache

The generation length of large models is usually uncertain, so KV Cache must support dynamic growth.

1. Allocating Cache When a Request Begins

Assume Block Size is 16.

The Prompt has 30 Tokens:

N_{\text{blocks}}= \left\lceil\frac{30}{16}\right\rceil=2

At request start, two Blocks are required.

2. Expansion During the Decode Phase

As Tokens are generated:

Current Token Count Required Block Count
30 2
31 2
32 2
33 3
48 3
49 4

When the Token count exceeds the capacity of the current Block, a new Block needs to be requested.

3. Dynamic Expansion Flow

flowchart TD
    A["Request starts"] --> B["Allocate initial Block"]
    B --> C["Execute Prefill"]
    C --> D["Enter Decode"]
    D --> E["Generate new Token"]
    E --> F{"Does the current Block have remaining capacity?"}
    F -->|"Yes"| G["Write to current Block"]
    F -->|"No"| H["Request new Block"]
    H --> I{"Is allocation successful?"}
    I -->|"Success"| J["Update Block Table"]
    I -->|"Failure"| K["Trigger insufficient resource handling"]
    K --> L["Wait, preempt, or recompute"]
    L --> H
    J --> G
    G --> M{"Has the stop condition been reached?"}
    M -->|"No"| D
    M -->|"Yes"| N["Release request cache"]

    style A fill:#E0F0FE,stroke:#93BCE8,color:#1E4976
    style B fill:#EAF3EC,stroke:#83A995,color:#315D49
    style C fill:#E0F0FE,stroke:#93BCE8,color:#1E4976
    style D fill:#E0F0FE,stroke:#93BCE8,color:#1E4976
    style E fill:#F5F8F4,stroke:#B5CBBB,color:#40594A
    style F fill:#F7F4E8,stroke:#C7B77A,color:#675A2D
    style G fill:#EAF3EC,stroke:#83A995,color:#315D49
    style H fill:#F5F8F4,stroke:#B5CBBB,color:#40594A
    style I fill:#F7F4E8,stroke:#C7B77A,color:#675A2D
    style J fill:#EAE8FA,stroke:#A49BD5,color:#51477D
    style K fill:#F7EAE7,stroke:#C98D7C,color:#754438
    style L fill:#F5F8F4,stroke:#B5CBBB,color:#40594A
    style M fill:#F7F4E8,stroke:#C7B77A,color:#675A2D
    style N fill:#DCEFE5,stroke:#4F8B70,color:#24563F