🤖 machine learning

Requests of a Feather Must Flock Together: Batch Size vs. Prefix Homogeneity in LLM Inference

This paper introduces Feather, a reinforcement learning-based prefix-aware scheduler that optimizes the trade-off between batch size and prefix homogeneity using a lightweight Chunked Hash Tree, achieving 2–10× higher LLM inference throughput by reducing KV cache access overhead compared to existing state-of-the-art schedulers.

Original authors: Saksham Rathi, Preeti, Mythili Vutukuru

Published 2026-05-08

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Saksham Rathi, Preeti, Mythili Vutukuru

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are running a very busy, high-speed library where a single librarian (the GPU) is trying to answer thousands of questions from different people (requests) at the same time.

In the world of Large Language Models (LLMs), the librarian has to read a massive book of "context" (the Key-Value cache) for every single word they generate. The paper argues that the current way of organizing these questions is inefficient because it focuses too much on how many questions the librarian answers at once, rather than how similar those questions are.

Here is the story of their solution, Feather, broken down into simple concepts:

1. The Problem: The "Crowded Bus" vs. The "Family Group"

Currently, most systems try to pack as many people as possible onto a bus (a "batch") to make the trip efficient. They use a "First Come, First Served" rule.

The Issue: If you put 500 strangers on a bus, they all want to go to 500 different places. The driver has to stop at 500 different stops, constantly switching directions. This is chaotic and slow.
The Discovery: The authors found that if you take a smaller group of 100 people who all live on the same street (share a "prefix"), the driver can drive straight down that street without stopping. Even though the bus isn't full, the trip is much faster because the driver doesn't have to keep turning the wheel.

The Key Insight: It is better to have a smaller group of people going to the same place than a huge group of people going to different places. This is called Prefix Homogeneity.

2. The Old Way: The "Tree Climber"

Existing systems (like SGLang) try to find these groups by looking at a giant, complex family tree (a Radix Tree) to see who shares the same ancestors.

The Problem: Climbing this tree to find matches takes a lot of time and energy on the computer's "brain" (the CPU). In fact, the time spent climbing the tree was sometimes almost as long as the time the librarian spent actually answering the questions! It was like spending 10 minutes organizing the passengers just to drive for 10 minutes.

3. The Solution: "Feather"

The authors built a new scheduler called Feather that fixes both problems.

Part A: The "Chunked Hash Tree" (CHT) – The Smart Checklist

Instead of climbing the giant family tree, Feather uses a clever shortcut.

The Analogy: Imagine instead of checking every single letter of a person's name, you just check the first few "chunks" of their address.
How it works: Feather breaks the long text into small blocks (chunks) and gives each block a unique "fingerprint" (a hash). It keeps a simple list of which fingerprints are currently being used.
The Benefit: It can instantly see, "Oh, this new request has the same fingerprints as the group already on the bus." It does this so fast that the "CPU brain" barely breaks a sweat. It's like using a barcode scanner instead of reading a whole book to check a ticket.

Part B: The "Reinforcement Learning" (RL) – The Smart Dispatcher

Feather doesn't just find similar groups; it learns when to stop adding people to the bus.

The Dilemma: If you keep adding people to the bus, you might eventually have to add someone who lives on a different street. If you add them, the whole group becomes messy, and the speed drops.
The Learning: Feather acts like a smart dispatcher who has learned through trial and error: "If I add one more person, we might lose our speed. Let's send this bus now while it's still fast, and wait for the next group."
The Result: It dynamically decides the perfect moment to launch the batch, balancing between having a full bus and keeping everyone on the same street.

4. The Results: Speeding Up the Library

When the authors tested Feather:

Speed: It made the system 2 to 10 times faster than the current best methods when people were asking similar questions.
Safety: If the questions were all totally different (no shared streets), Feather didn't get confused; it just performed just as well as the old methods.
Efficiency: It reduced the "traffic jams" in the computer's memory, meaning the librarian didn't have to run back and forth as much to fetch the book pages.

Summary

Feather is a new way of organizing AI requests. Instead of stuffing as many requests as possible into a single batch, it groups similar requests together (like a family going to the same destination) and uses a super-fast, low-energy method to find those groups. It learns exactly when to stop adding people to the group to keep the trip smooth and fast.

The paper claims this approach significantly speeds up AI response times without needing expensive new hardware, simply by organizing the "traffic" smarter.

Technical Summary: Requests of a Feather Must Flock Together

Problem Statement

Large Language Model (LLM) inference is fundamentally memory-bound during the auto-regressive decode phase. Each generated token requires attending to the Key-Value (KV) cache of all previous tokens, necessitating a full sweep of the KV cache in GPU memory for every step. While prior work has focused on maximizing batch size to improve GPU utilization, this paper identifies a critical, overlooked trade-off: prefix homogeneity.

In real-world workloads (e.g., few-shot prompting, system prompts, RAG), requests often share significant prefixes. Existing inference engines (like vLLM and SGLang) utilize radix trees or hash structures to detect these shared prefixes and reuse KV caches, primarily to reduce memory footprint. However, current schedulers prioritize maximizing batch size or minimizing memory evictions without considering the impact of prefix heterogeneity on memory access patterns.

The authors demonstrate that heterogeneous batches (containing requests with different prefixes) disrupt spatial and temporal locality in GPU DRAM accesses, leading to poor bandwidth utilization and reduced throughput. Conversely, prefix-homogeneous batches (where all requests share a common prefix) allow for efficient hardware prefetching and cache reuse. The paper argues that existing schedulers fail to recognize that a moderately small, homogeneous batch can outperform a larger, heterogeneous one. Furthermore, the mechanisms used to detect prefix sharing (e.g., radix tree traversals) incur prohibitive CPU overhead, often comparable to or exceeding GPU execution time.

Methodology

The paper introduces Feather, a prefix-aware scheduler designed to optimize the trade-off between batch size and prefix homogeneity. Feather integrates two primary components:

1. Chunked Hash Tree (CHT)

To address the high CPU overhead of traditional radix-tree traversals, Feather employs a lightweight data structure called the Chunked Hash Tree.

Mechanism: Instead of token-by-token comparisons, requests are represented as vectors of cumulative hashes over fixed-size token chunks.
Efficiency: CHT maintains a "working set" of hashes for the active batch and a min-heap of waiting requests ordered by their "missing count" (the number of chunks not yet covered by the active batch).
Complexity: This allows the scheduler to identify the best candidate request to add to a batch in $O(\log W)$ time (where $W$ is the number of waiting requests), a significant improvement over the $O(W \times T)$ or $O(E)$ complexity of depth-first radix tree traversals.
Operations: CHT supports efficient insertion, finding the best request, adding a request to the active batch, and removing completed requests, utilizing lazy heap updates and incremental tip maintenance to minimize overhead.

2. Reinforcement Learning (RL) Batching Policy

Feather uses an RL-based policy to determine the optimal stopping point for batch formation.

The Trade-off: Adding more requests increases GPU utilization (larger batch size) but may dilute prefix homogeneity (reducing memory locality).
State & Action: The scheduler observes the current batch size, the loss in shared prefix depth ( $\Delta$ ), and the number of waiting requests sharing the new prefix depth ( $w$ ). It decides whether to Add another request or Stop and dispatch the batch.
Policies: The authors evaluate three policies: a static heuristic, a Contextual Bandit (UCB), and Q-Learning. The goal is to maximize the reward, defined as decode throughput.
Adaptability: The RL policy learns to form batches that are "just right"—large enough to utilize the GPU but homogeneous enough to maximize memory locality. It dynamically adapts to workload intensity and prefix sharing patterns.

Key Contributions

Identification of a Critical Trade-off: The paper establishes that prefix homogeneity is a stronger determinant of decode throughput than batch size alone. It demonstrates that even a single divergent request in a batch can disrupt locality and reduce throughput by nearly 2x.
Quantification of CPU Overhead: The authors reveal that state-of-the-art prefix detection mechanisms (like radix tree traversals in SGLang) incur CPU overheads that can reach 50–90% of total latency, effectively negating the benefits of prefix reuse.
Feather Scheduler: The design and implementation of Feather, which integrates the CHT data structure with an RL-based batching policy. Feather is integrated into both vLLM and SGLang.
Hardware Agnosticism: Unlike prefix-aware attention kernels that require specific hardware tuning, Feather operates at the scheduling layer, making it compatible with existing attention kernels and hardware configurations.

Results

The evaluation was conducted on NVIDIA RTX 6000 Ada and A100 GPUs using models like Llama 3 8B, Qwen, and LongChat 13B across diverse workloads (L-Eval, LongBench).

Throughput Gains: Feather achieves 2–10× higher end-to-end throughput compared to existing schedulers (vLLM's FCFS, SGLang's LPM/DFS-W) in workloads with shared prefixes ranging from 1K to 10K tokens.
Prefix Sensitivity: In experiments with 800 requests split into 8 prefix groups, processing them in 8 homogeneous batches of 100 requests yielded nearly 2× higher throughput than processing them in larger, heterogeneous batches.
Overhead Reduction: Feather's CHT reduces prefix detection overhead by up to 1000× compared to DFS-based approaches for long sequences. The scheduling overhead remains below 1% of GPU execution time, whereas baseline approaches can exceed GPU execution time.
Robustness: Feather performs on par with the status quo (FCFS) when workloads lack prefix sharing, ensuring no performance degradation in non-shared scenarios.
Comparison with Kernels: Feather outperforms or matches specialized prefix-aware attention kernels (like PAT) despite not modifying the kernel itself, proving that scheduling-level optimizations can be as effective as kernel-level ones.

Significance

The paper claims that maximizing batch size is no longer sufficient for efficient LLM serving. The primary bottleneck in modern decode phases is memory bandwidth, which is heavily influenced by access locality. By shifting the focus from "maximizing batch size" to "optimizing prefix homogeneity," Feather unlocks significant performance gains without requiring hardware-specific kernel modifications.

The work highlights that the cost of finding shared prefixes (CPU overhead) has been a hidden bottleneck in current systems. Feather's lightweight CHT and adaptive RL policy demonstrate that it is possible to dynamically balance compute utilization and memory locality, leading to substantial improvements in both throughput and latency for real-world LLM inference workloads. The authors plan to open-source Feather by contributing it to the vLLM and SGLang repositories.