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

arXiv:2605.06046 · cs.LG · Submitted 2026-05-07 · Read on arXiv

Listen

Transcript

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: I'm Tom, and with me are Jane, Lu, senior AI researcher at Tsinghua, Meng, lead engineer at a mysterious AI startup and Lalam, the in-house Large Language Model.

Jane: Today's paper: "Requests of a Feather Must Flock Together".

Tom: The gist: smaller, prefix-homogeneous batches can achieve higher decode throughput than larger, heterogeneous batches due to better spatial and temporal locality during KV cache accesses.

Jane: First, who's behind it and why it matters.

Title and authors: Tom: So, to recap, we're looking at this paper called "Requests of a Feather Must Flock Together: Batch Size vs. Prefix Homogeneity in LLM Inference." The authors are Saksham Rathi, Preeti Indian Institute of Technology Bombay Mumbai, and Mythili Vutukuru from IIT Bombay >

Jane: They’re essentially investigating how batching multiple requests for text generation affects the speed, and they focus on this idea that when requests share a common prefix, smaller batches can actually outperform larger ones that have different prefixes >

Tom: That's the main finding of the paper. It challenges the idea that just making a batch bigger is always better for decode throughput because it focuses on how much those requests overlap in what they're asking for >

Lu: It seems they’ve pointed out a gap in current scheduling strategies, noting that existing methods often focus only on maximizing batch size during the decode phase rather than considering this prefix sharing aspect >

Meng: That makes sense from an engineering viewpoint. If we just keep adding requests hoping the batch gets bigger, we might end up fetching a lot of redundant data because those requests are all asking for totally different starting points >

Lalam: And what they found is that the performance gains increase with how long that shared prefix is across all the requests in a batch, which really supports their argument >

The paper's summary: Tom: So, summarizing what they found in "Requests of a Feather Must Flock Together: Batch Size vs. Prefix Homogeneity in LLM Inference," they show that for prefix-sharing workloads, smaller batches with high homogeneity can achieve higher decode throughput >

Jane: They found that when a prefix is shared by all requests, there is significant spatial and temporal locality in the memory accesses of the KV cache located in the GPU DRAM >

Tom: This locality leads to two things: higher memory bandwidth utilization and a reduced total amount of data fetched from DRAM >

Lu: The paper also found that prefix homogeneity has an even stronger impact on performance than just maximizing batch size during decode phase, which is what they observed through controlled experiments >

Meng: So, the key takeaway here is that you can get better speed by being smart about how you group the requests so they share as much of their initial input as possible >

Lalam: And interestingly, even when there isn't much prefix sharing at all, the adaptive batching policy they developed can still match the performance of existing schedulers like vLLM's FCFS scheduler >

The paper's improvements: Tom: Now let's look at what they proposed to fix these issues. They introduced a new approach called Feather, which is a prefix-aware scheduler built using reinforcement learning to learn the best trade-off between batch size and prefix homogeneity >

Jane: It seems they designed this system with two main parts: a Chunked Hash Tree, or CHT, for really fast prefix detection and an RL-based policy to decide when to add another request to a batch >

Lu: The CHT is this lightweight data structure that uses a min-heap ordered by per-request missing count—that’s how it finds the best candidate in O of log W time >

Meng: That sounds efficient. It replaces what they call DFS-based approaches, which they say have huge CPU overhead for long sequences, with something much faster >

Lalam: And the RL policy is what lets it adapt dynamically; it learns to stop adding requests at the point that maximizes throughput based on those observed batch characteristics >

Conclusion: Tom: So, to wrap up this discussion on "Requests of a Feather Must Flock Together: Batch Size vs. Prefix Homogeneity in LLM Inference," the main message is that we should look beyond just making batches huge and start paying attention to how requests share prefixes >

Jane: They showed that for prefix-shared workloads, smaller, homogeneous batches are actually better because of the way they reuse data in memory >

Tom: The results show up as a two to ten times higher end-to-end throughput compared to existing schedulers on some benchmarks when they leverage this locality properly >

Lu: The implication is that we need schedulers that actively manage prefix sharing, not just batch size constraints, which opens up new avenues for how we organize inference pipelines >

Meng: And from a practical standpoint, the overhead of their prefix detection is very low—they report it can be reduced by up to one thousand times compared to older DFS methods >

Lalam: It's neat that this paper also highlights how adaptive batch size management, driven by reinforcement learning, can handle situations where there isn't much prefix sharing either, matching other schedulers in those cases >

Saksham Rathi, Preeti Indian Institute of Technology Bombay, Mythili Vutukuru Indian Institute of Technology Bombay

Indian Institute of Technology Bombay

cs.LG

Submitted: 2026-05-07

Updated: 2026-10-10

Comments: 22 pages, 36 figures

Code: https://github.com/metallama/llama3

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 83/100

The gist: The gist: smaller, prefix-homogeneous batches can achieve higher decode throughput than larger, heterogeneous batches due to better spatial and temporal locality during KV cache accesses.

Key concepts

Prefix Homogeneity: This refers to a situation where all requests within a single batch share the same initial sequence of tokens (a common prefix). When this occurs, the GPU's memory accesses for the key-value cache become highly localized in time and space, which significantly speeds up decoding.
KV Cache Locality: The Key-Value (KV) cache stores previously computed attention results in fast GPU memory. Prefix homogeneity ensures that when processing a batch, the system repeatedly accesses the same parts of this cache concurrently. This reuse reduces slow fetches from main DRAM, leading to faster overall generation.
Feather Scheduler: Feather is an intelligent scheduling system that uses reinforcement learning to decide the best batch size and prefix sharing strategy at runtime. It employs a Chunked Hash Tree for fast prefix detection, allowing it to create batches that are as homogeneous as possible without incurring high CPU overhead.
Chunked Hash Tree (CHT): The CHT is a lightweight data structure designed to quickly find which requests in the current batch share the longest common prefix. It organizes information based on how many prefix chunks each request is missing, allowing the system to identify the best candidates for forming a homogeneous group very fast.

Terminology

KV cache — 4× in this paper · explained in 3 episodes
Decode — 2× in this paper · explained in 2 episodes
Homogeneity — 2× in this paper · explained in 2 episodes
Reinforcement Learning — 1× in this paper · explained in 4 episodes
Reinforcement Learning (RL) — 1× in this paper · explained in 25 episodes

Summary

The gist: smaller, prefix-homogeneous batches can achieve higher decode throughput than larger, heterogeneous batches due to better spatial and temporal locality during KV cache accesses.

Motivation

The work addresses the memory-bound nature of auto-regressive token generation in large language models by investigating the trade-off between batch size and prefix homogeneity. This is because when a prefix is shared by all requests, there is significant spatial and temporal locality in the memory accesses of the KV cache located in the GPU DRAM, which leads to both higher memory bandwidth utilization and reduced total amount of data fetched from DRAM.

Key Findings on Homogeneity

The experiments validated three hypotheses underpinning the design of Feather. First, when all requests in a batch share a common prefix, their attention operations traverse the same KV cache regions concurrently. Second, in prefix-homogeneous batches, decode throughput increases smoothly with the length of the shared prefix. Third, while prefix heterogeneity causes a drop in throughput, the amount of heterogeneity has a marginal impact on the loss of locality.

Feather Architecture

Feather is introduced as a prefix-aware scheduler that uses reinforcement learning (RL) to learn the optimal tradeoff between batch size and prefix homogeneity. It is built on two components:

Chunked Hash Tree (CHT): This lightweight data structure enables fast prefix detection. CHT maintains a minheap ordered by per-request missing count—the number of prefix chunks not yet covered by the batch—enabling identification of the best candidate in O (log W) time.
RL-based batching policy: This policy decides when to stop adding requests to a batch based on observing batch characteristics and evaluating the impact of adding another request.

Performance and Overhead Analysis

Feather achieves 2–10× higher end-to-end throughput as compared to existing schedulers. This gain is achieved by reducing the total number of KV cache accesses, surpassing the performance of prefix-aware attention kernels that have the same goal. Furthermore, Feather reduces prefix-detection overhead by up to 1000× compared to DFS-based approaches for long sequences.

Conclusion

In summary, this paper makes the following contributions: (i) We demonstrate the tradeoff between batch size and prefix homogeneity in the decode phase performance of LLM inference, and identify previously overlooked CPU overheads in prefix-aware scheduling. (ii) We design the Chunked Hash Tree (CHT) data structure for low-overhead prefix detection, and develop a reinforcement learning-based policy for adaptive batch construction. (iii) We build Feather, a prefix-aware scheduler integrated into vLLM and SGLang, and demonstrate improvements in throughput and latency on diverse workloads.

Why the name Feather?

Feather is named after the structural pattern of prefix-homogeneous batches in our system: a shared prefix forms a central shaft, from which individual requests branch out as they diverge, much like the barbs of a Feather. The metaphor captures both the visual structure of our batches and the functional benefit of keeping prefix sharing requests together for better performance.

Final Performance Gains

Feather consistently improves end-to-end throughput across diverse workloads while keeping scheduling overhead low. Its advantage grows with model size, as larger models spend more time in attention, amplifying the benefits of temporal and spatial KV-cache locality that Feather exploits. At 100 prefix groups, Feather achieves up to 22× higher throughput than vLLM (FCFS). This demonstrates that forming prefix-homogeneous batches not only improves scheduling efficiency but also significantly reduces KV cache evictions through more effective immediate cache reuse. The RL policy dynamically adapts the batch size in response to both prefix homogeneity (i.e., the number of requests sharing the same prefix group) and the current workload intensity.

Workloads without Prefix Sharing

Even in the absence of prefix sharing, Feather, powered by its adaptive RL-based policy—matches the performance of vLLM’s FCFS scheduler. In contrast, SGLang policies achieve lower TBT, which can be attributed to their smaller batch sizes.

Complexity of Existing Methods

Existing approaches introduce significant CPU overhead when detecting prefix sharing, which is sometimes even comparable to the GPU execution time.

Improvements for AI systems

Improved batching strategy for decode phase inference: The Feather scheduler can achieve 2–10× higher end-to-end throughput as compared to existing schedulers by learning the optimal tradeoff between batch size and prefix homogeneity through a reinforcement learning policy. This allows the system to dynamically stop batch formation at the point that maximizes throughput, leveraging the insight that moderately small prefix-homogeneous batches can outperform larger heterogeneous batches.
Enhanced prefix detection efficiency: Replacing expensive tree traversals with a lightweight data structure, CHT, reduces CPU overhead by avoiding radix-tree traversals and instead using a min-heap ordered by per-request missing count, achieving an O (log W) time selection cost compared to the prohibitive overhead of existing prefix-aware schedulers.
Optimized KV cache access patterns: By constructing batches that maximize shared prefixes, the system exploits spatial and temporal locality in the memory accesses of the KV cache located in the GPU DRAM, which leads to both higher memory bandwidth utilization and reduced total amount of data fetched from DRAM, directly improving performance beyond what is achievable by prefix-aware attention kernels alone.
Adaptive batch size management: The RL policy enables the scheduler to dynamically adapt the batch size in response to both prefix homogeneity (i.e., the number of requests sharing the same prefix group) and the current workload intensity, ensuring that smaller, homogeneous batches outperform larger heterogeneous ones during decode iterations where locality benefits are most pronounced.
Reduced scheduling latency: The CHT structure minimizes overhead, as it avoids token-by-token comparisons during insertion and instead relies on maintaining a working set and a min-heap, resulting in an operation cost of O (log W) selection cost, which is significantly faster than DFS traversal for long sequences.

Abstract

Auto-regressive token generation in large language models is memory-bound because it requires "attending to" key and value tensors (KV cache) of all previous tokens. Prior work aims to improve the efficiency of this decode process by batching multiple requests together, and maximizing batch size subject to GPU memory constraints. The key observation of our work is that with prefix-sharing workloads, smaller, prefix-homogeneous batches - where all requests share a common prefix - can achieve higher decode throughput than larger, heterogeneous batches, due to better spatial and temporal locality during KV cache accesses. However, prefix-aware schedulers in state-of-the-art inference engines maximize prefix reuse within a batch only to reduce KV cache memory footprint, but do not stop batch formation at smaller homogeneous batches that could have performed better. Further, we show that shared prefix detection in existing schedulers relies on radix-tree traversals, incurring substantial CPU overhead that is often comparable to GPU execution time. This paper presents Feather, a prefix-aware scheduler that uses reinforcement learning (RL) to learn the optimal tradeoff between batch size and prefix homogeneity. We also introduce Chunked Hash Tree (CHT), a lightweight data structure that enables fast prefix detection and efficient request selection for the RL scheduler, avoiding expensive tree traversals. We integrate Feather into vLLM and SGLang, and our evaluation shows that Feather achieves 2-10X higher end-to-end throughput as compared to existing schedulers, while doing no worse than the status quo when the workload does not have enough prefix sharing. Feather achieves these gains by reducing the total number of KV cache accesses, surpassing the performance of prefix-aware attention kernels that have the same goal.