Continuous batching for on-device LLM inference on Android

TL;DR

Naive serial inference on Android collapses under concurrent requests. Continuous batching — iteration-level scheduling with per-sequence KV cache slot management — lets a single llama.cpp instance serve multiple in-flight requests without throughput cliffs. This post walks through the queue architecture, batch assembly logic, and slot allocator you need to build it correctly in Kotlin.

The problem nobody warns you about

Most teams treat the inference engine like a function call: one request in, wait for completion, next request in. That works at one user. At five concurrent users on the same device — think a local Android server powering multiple app features simultaneously — you hit a throughput cliff so steep it looks like a wall.

The culprit is prefill starvation. While a long generation decodes token-by-token, every new request sits idle. GPU/NPU compute is underutilized, KV cache memory sits half-empty, and your p50 latency balloons proportionally to queue depth.

The server-side world solved this years ago with continuous batching (also called iteration-level scheduling). The on-device world is only catching up now.

Static batching vs continuous batching

Property	Static Batching	Continuous Batching
Scheduling unit	Full request	Single decode iteration
New request joins	After current batch completes	Next available iteration
KV cache allocation	Fixed at batch start	Dynamic per sequence slot
GPU utilization	Spiky, often <50%	Sustained, typically 70–90%
p50 latency under load	Grows linearly with queue	Near-flat to moderate concurrency
Implementation complexity	Low	Moderate

With static batching, a 5-request queue behind a 500-token generation means request 5 waits for ~2,500 decode steps before its prefill even begins. With continuous batching, that same request joins the batch at the next iteration boundary.

The architecture: three moving parts

You need three components working together.

1. The request queue

data class InferenceRequest(
    val id: String,
    val prompt: String,
    val maxTokens: Int,
    val responseChannel: Channel<String>
)

class RequestScheduler(private val maxConcurrent: Int = 4) {
    private val pending = ArrayDeque<InferenceRequest>()
    private val active = mutableMapOf<String, SequenceSlot>()

    fun enqueue(request: InferenceRequest) {
        pending.addLast(request)
        tryPromote()
    }

    private fun tryPromote() {
        while (active.size < maxConcurrent && pending.isNotEmpty()) {
            val req = pending.removeFirst()
            val slot = SlotAllocator.acquire() ?: return // KV cache full
            active[req.id] = SequenceSlot(req, slot)
        }
    }
}

maxConcurrent isn’t arbitrary. It’s bounded by your KV cache capacity. Exceed it and you either evict sequences (destroying their generation) or OOM. Size it at initialization from available VRAM/shared memory.

2. Per-sequence KV cache slot manager

llama.cpp exposes llama_kv_cache_seq_rm and llama_kv_cache_seq_cp for sequence-level control. Wrap these in a slot allocator:

class SlotAllocator(private val totalSlots: Int) {
    private val free = ArrayDeque((0 until totalSlots).toList())
    private val inUse = mutableSetOf<Int>()

    @Synchronized
    fun acquire(): Int? = free.removeFirstOrNull()?.also { inUse.add(it) }

    @Synchronized
    fun release(slot: Int) {
        inUse.remove(slot)
        free.addLast(slot)
        // Signal scheduler via coroutine channel
    }
}

Each active sequence owns exactly one slot. When a generation completes or is cancelled, release() fires and the scheduler immediately promotes the next pending request into that slot. No idle cycles.

3. Dynamic batch assembly

At each decode step, the batch is re-assembled from all active sequences:

suspend fun runBatchStep(active: Map<String, SequenceSlot>) {
    val batch = llama_batch_init(active.size, 0, 1)
    active.values.forEachIndexed { i, seq ->
        llama_batch_add(batch, seq.nextToken, seq.position, intArrayOf(seq.slot), i == active.size - 1)
    }
    llama_decode(ctx, batch)
    
    active.values.forEach { seq ->
        val logits = llama_get_logits_ith(ctx, seq.batchIndex)
        val token = sample(logits, seq.samplingParams)
        seq.emit(token)
        if (token == eosToken || seq.length >= seq.request.maxTokens) {
            seq.complete()
        }
    }
    llama_batch_free(batch)
}

The loop runs continuously as long as any sequence is active. New requests slot in; completed sequences drain out. The engine never idles waiting for a single long generation to finish.

What this buys you

In my experience building production systems, the gains from iteration-level scheduling are most visible at moderate concurrency (3–6 simultaneous requests). Below that, batch management overhead can slightly inflate single-request latency. Above ~8 concurrent sequences on a mobile GPU, you hit memory pressure before CPU scheduling becomes the bottleneck. Tune maxConcurrent empirically against your target device tier.

What actually matters

Size your slot allocator at startup, not at runtime. Calculate maximum concurrent sequences from available KV cache memory before accepting any requests. Fail fast rather than evict mid-generation.
Decouple your queue from your batch loop using coroutines. The RequestScheduler and the decode loop should communicate through channels, not shared mutable state. This keeps cancellation and backpressure composable.
Benchmark p50, not just throughput. Continuous batching trades marginal single-request latency for better tail behavior under load. Measure at the 50th and 95th percentile under realistic concurrent load — that’s where you see the real gains.