# APAC — Adaptive Paged Attention Controller for LLM Serving

A runtime control plane that sits above paged KV memory and continuously adjusts allocation, retention, offload, and routing policy according to observed request patterns.

## Key Findings (Latest Results)

### 1. LRU Eviction is Near-Optimal for Single-Pool Prefix Sharing
Running Bélády (hindsight-optimal) eviction against LRU under memory pressure:
- **Oracle gap: 0%** across throughput, TTFT, and cache hit rate
- Implication: APAC's value cannot come from better eviction alone

### 2. Multi-Pool Routing Offers Dramatic Latency Improvements
Comparing routing policies under memory pressure (2 pools, 128 blocks each, 500 requests):

| Policy | Throughput | p99 TTFT | Cache Hits |
|--------|-----------|----------|------------|
| **Oracle** | **89.7 rps** | **76 ms** | 11,468 |
| Round-robin | 87.5 rps | 964 ms | 61,226 |
| Random | 85.0 rps | 1097 ms | 67,687 |
| Least-loaded | 88.1 rps | 1173 ms | 38,525 |

**Key result: Oracle routing reduces p99 TTFT by 92%** (964ms → 76ms)

The oracle routes each request to the pool with the best prefix cache coverage for that request's prefix. This maximizes cache reuse per-pool and dramatically reduces queueing delays.

### 3. Class-Based Routing Can Be Catastrophic
Routing all shared-prefix requests to a single "hot" pool:
- **p99 TTFT: 2278ms** (vs 964ms for round-robin)
- Throughput drops 2% from overload on the hot pool

Implication: Intelligent routing requires per-request prefix analysis, not coarse class-based heuristics.

## Project Structure

```
apac/
├── schemas/           # Event schemas (trace format, controller decisions)
├── collectors/        # Live trace collectors (vLLM KV events, metrics)
├── simulator/         # Discrete-event simulator for KV cache policies
│   ├── core/          # DES engine, block pool, scheduler
│   ├── workloads/     # Workload generators (BurstGPT, ShareGPT, synthetic)
│   └── replay/        # Trace replay engine
├── controller/        # APAC controller (policy engine, forecasters, routing)
├── oracle/            # Hindsight-optimal oracle for gap analysis
├── visualiser/        # Block heatmaps, timeline plots, residency histograms
├── experiments/       # Experiment configs and scripts
└── tests/             # Unit and integration tests
```

## Quick Start

```bash
pip install -e .
# Run oracle gap analysis on BurstGPT traces
python -m apac.experiments.oracle_gap --workload burstgpt --block-size 16 --num-blocks 2048
```

## Key Concepts

- **Trace Collector**: Subscribes to vLLM KV events via ZMQ and reconstructs block-level state
- **Simulator**: Replays request traces through a paged block allocator with configurable policies
- **Oracle**: Computes Belady-optimal (hindsight) decisions for routing, retention, and offload
- **Controller**: Online APAC that makes decisions based on observable signals only

## Datasets Used

- [BurstGPT](https://huggingface.co/datasets/lzzmm/BurstGPT) — 5.29M rows, Azure OpenAI production traces
- [WildChat-1M](https://huggingface.co/datasets/allenai/WildChat-1M) — 1M timestamped conversations
- [ShareGPT52K](https://huggingface.co/datasets/RyokoAI/ShareGPT52K) — Length distribution reference

## References

- PagedAttention (vLLM): [arxiv:2309.06180](https://arxiv.org/abs/2309.06180)
- BurstGPT: [arxiv:2401.17644](https://arxiv.org/abs/2401.17644)
- Splitwise: [arxiv:2311.18677](https://arxiv.org/abs/2311.18677)
- Ada-KV: [arxiv:2407.11550](https://arxiv.org/abs/2407.11550)
- LMCache: [arxiv:2510.09665](https://arxiv.org/abs/2510.09665)
- SGLang RadixAttention: [arxiv:2312.07104](https://arxiv.org/abs/2312.07104)