Token LabSearch

Agent batch makespan: coordinating inference, caches and tools

A systems tutorial on finishing a batch of multi-turn agents sooner: separate admission from tool capacity, preserve reusable state and understand when advancing long chains helps—or hurts.

Sources & version details
In this article

A batch can be slow even when each call looks fast

Imagine a nightly evaluation of 500 coding agents. An agent asks a model for its next action, waits for a sandbox command, reads the result and asks again. The release gate opens only when every trajectory terminates. At the end, most GPUs may be idle while one agent alternates between a slow command and another inference call. A faster token decoder cannot eliminate a command dependency or a queue in a different service.

A trajectory is the complete sequence of model and environment stages for one task. Makespan is the wall-clock interval from the batch’s start to its last termination, including failed terminal outcomes. It is different from average task completion time, time to first token (TTFT), time per output token (TPOT), and the final-5% completion interval. This tutorial targets finite offline batches—evaluations, synthetic data and rollout collection. An interactive assistant instead needs explicit user-latency and fairness constraints; do not silently substitute a batch objective.

The learning goal is to identify the actual bottleneck, design independent capacity controls, calculate cache residency, read the paper’s ablations correctly and implement a local scheduling experiment. Prerequisites are queues, concurrency limits and causal dependencies: a queued task is not necessarily running; an agent waiting for a tool still owns context; and its next inference turn cannot begin before the required observation exists. Knowing these distinctions is more useful here than memorizing scheduler names.

The critical path and the resource lower bound

Let be task k’s termination time relative to batch start. Makespan is max ; mean completion is their arithmetic mean. With fixed stage durations, every serial trajectory supplies a lower bound on makespan. A homogeneous pool of tool slots supplies another: total tool service time divided by . Take the maximum of these bounds, not their sum, because different trajectories can overlap. Finite inference capacity and release times can make the real schedule slower still. Here N is the number of tasks; and are the inference and environment service durations of turn n in task k, measured in seconds. counts simultaneous environment executions.

For three identical tasks, each with inference 1 s → tool 2 s → inference 1 s, a single admission slot yields 12 s. Admit all three while preserving one tool slot: first inference stages overlap during seconds 0–1, tools run during 1–3, 3–5 and 5–7, and final inference stages finish at 4, 6 and 8 s. Makespan becomes 8 s without accelerating any operation. Mean completion is 6 s, versus 8 s under serial admission. This is an original deterministic example with unconstrained inference parallelism, not a measured GPU result.

The resource bound is 6 s and the longest individual path is 4 s, so the generic bound is 6 s. The actual 8 s reflects the initial release delay and the last inference stage. That gap is why a utilization dashboard alone cannot certify an optimal schedule. A realistic server also has batching effects: increasing concurrency can lengthen individual calls while decreasing total batch duration.

Three trajectories; C_S = 3, C_E = 1. Idle gaps are queue waits; colors show fixed service, not measured GPU speed.
Three trajectories; C_S = 3, C_E = 1. Idle gaps are queue waits; colors show fixed service, not measured GPU speed. Open full-size diagram

A reference architecture with two independent gates

An admission controller owns active-trajectory slots. A slot remains occupied while its task waits for inference or a tool. A separate dispatcher owns running-environment slots. A pending tool job holds its trajectory slot but not an execution slot. The inference gateway routes each turn to a model worker; the worker owns its prefix cache and hybrid recurrent state. A durable trajectory record contains the request ID, model version, tool result and terminal status. This is a teaching reference design, not a diagram of a vendor’s private infrastructure.

A trajectory label is an affinity hint, never an authorization credential. Before dispatch, validate tenant, tool capability, arguments, deadline and cancellation state. Returning a tool result releases only the next dependent turn; it does not create permission for a new action. Keep cache keys separated by authorized sharing scope and model/tokenizer configuration. Cross-tenant reuse requires a separate security decision; a matching label is insufficient.

Use a bounded pending queue and admission backpressure. On timeout, record an explicit uncertain or failed outcome. If a side effect might already have happened, inspect its operation ID or state before retrying; releasing a semaphore is not rollback. Cancellation must stop queued work and propagate to running calls where supported. Repeated retries need a separate budget and backoff. Store the checkpoint before making the next stage ready. These reliability rules are proposed engineering requirements, not claims tested by the paper.

Original reference design: inference and environment execution use separate capacity controls. Solid arrows carry requests/results; dashed arrows record state. Authorization precedes tool execution; timeout and cancellation terminate or reconcile the trajectory.
Original reference design: inference and environment execution use separate capacity controls. Solid arrows carry requests/results; dashed arrows record state. Authorization precedes tool execution; timeout and cancellation terminate or reconcile the trajectory. Open full-size diagram

Hybrid cache capacity: two pools can bottleneck one another

For an ordinary attention model, saved keys and values grow with cached token length. A hybrid model can additionally retain a recurrent summary for a trajectory. Reusing a prefix may require both kinds of state. A large empty KV pool is useless if the recurrent-state pool cannot retain the same trajectories. The paper therefore selects a workload-informed allocation at deployment; it does not resize these pools dynamically during the batch.

Let M be memory available after weights and runtime reservations, the estimated KV bytes per resident trajectory and the recurrent bytes per trajectory. If , estimated residency is the smaller of the two pool capacities. Balancing them gives and continuous capacity . Round down for an integer reference. This is an approximation: page granularity, fragmentation, shared prefixes, intermediate states and a distribution of sequence lengths matter.

An original example reserves 12 GiB for caches, with GiB and GiB. A 6/6 GiB partition supports only min(6,24)=6 trajectories. A 9.6/2.4 GiB partition balances both at 9.6, yielding an integer reference of 9. The extra capacity is not proof that is best: long outliers may evict state, and tool capacity may already be saturated. Profile representative trajectories and leave headroom; do not size production solely from a mean.

Routing and scheduling preserve opportunities, not guarantees

Worker affinity avoids repeatedly rebuilding a growing prefix, but strict affinity can overload one replica while another is idle. The paper’s load-bounded consistent hashing starts from a trajectory’s home worker and permits spillover when the home worker exceeds a load threshold. It uses observed in-flight requests rather than predicting future token counts. A spill may intentionally sacrifice reuse to avoid a longer queue; cache-hit rate is therefore an intermediate metric, not the final objective.

Inside a worker, routing-prefix scheduling uses recent trajectory labels to narrow priority-related prefix lookups. A remembered label is not evidence that the underlying GPU state is still resident. Conversely, dropping a label does not delete the cache. This distinction matters operationally: telemetry must separately count routing affinity, actual prefix reuse, uncached prefill tokens, queue delay and terminal completion. Otherwise a high affinity percentage can conceal expensive recomputation.

For a pure attention deployment, recurrent-state partitioning is irrelevant, but the routing trade-off remains. For shared-cache systems, network transfer cost enters the choice; this paper’s worker-local reuse model does not establish an optimum for cross-worker cache migration. For heterogeneous workers, request count alone is a weak load estimate. Consider service demand and capacity before adopting a homogeneous-worker routing rule.

Advancing observed long chains without knowing the future

After capacity separation, tool ordering determines which trajectories reveal their next stages. CAAS groups job arrivals into bands of width B seconds. Within the oldest band it prefers greater completed inference depth, then a bucketed shorter observed mean inference duration, then FIFO sequence. The completed-turn count includes the turn that generated the pending tool job. Priorities are fixed on enqueue. The scheduler does not inspect future trace lengths. In the priority tuple, is arrival time in seconds, is completed inference depth, the barred tau is the observed mean inference duration in seconds, and is the monotonically increasing enqueue sequence. B and ΔI are positive durations, so all tuple entries are dimensionless.

Suppose B=30 s and the duration bucket is 1 s. Job A arrives at 61 s after 4 turns averaging 2.2 s: its key begins (2,−4,3). Job B arrives at 59 s after 1 turn averaging 1 s: (1,−1,1). B wins because its arrival band is older. Job C arrives at 62 s after 7 turns averaging 3.1 s: (2,−7,4), so C precedes A within band 2. Depth matters only after the arrival-band comparison.

Depth is a heuristic for possible long remaining work, not a critical-path oracle. A task that has already completed many turns may actually be almost done; another at turn one may have a huge future. Small B approaches arrival order; large B gives depth more influence. Earlier bands limit repeated overtaking, but this is not a guarantee of tenant fairness, deadlines or bounded waiting under stalled operations. Use separate quotas and aging/SLO rules when those are requirements.

What the published numbers do—and do not—show

The November 12 v1 technical report evaluates Ling-3.0-Flash and Ling-3.1-Flash using H20 deployments and multiple agent workloads. Its headline 10.4%–65.0% makespan reduction belongs to combined configurations, not to CAAS alone. In the live MCP-Atlas comparison, the authors average three runs of 500 tasks. The table below reproduces selected numerical facts with attribution; it is not a Token Lab benchmark.

For Ling-3.0, 466.1 → 168.2 min is a 63.9% reduction from inference optimizations plus separated admission. Switching only the environment policy in that optimized setup gives 168.2 → 163.0 min, a further 3.1%. Relative to the original baseline, the combined reduction is 65.0%. Adding 63.9% and 3.1% is wrong because the denominators differ. Live runs include retries and terminal failures. That does not establish behavior under an injected retry storm or adversarial multi-tenant load.

Replay holds stage sequences and environment durations fixed but performs actual inference. It measures execution efficiency, not whether generated actions remain semantically correct. Live experiments complement replay but include stochastic differences in trajectories. The reported final-5% interval can increase against the narrow-admission baseline even while makespan drops: different tasks remain in the tail. Compare absolute batch completion as well as cohort composition; do not optimize the tail interval in isolation.

Authors’ live MCP-Atlas results · minutes · three 500-task runs
ModelBaselineOpt-FCFSOpt-CAAS
Ling-3.0466.1168.2163.0
Ling-3.1333.5140.5128.5

arXiv:2611.16661v1 · Table 3https://arxiv.org/html/2611.16661v1#S5.T3

Where this belongs in a production system

First decide which service owns the objective. For a nightly evaluator, minimize time to a complete valid report at a fixed hardware and API budget. For RL, also account for policy-version freshness: a faster collection batch is not automatically a better learning update if trajectories are stale or selected unfairly. For user-facing agents, constrain p95 response latency and tenant service before optimizing batch throughput. Never drop failures from the denominator to make completion look better.

Separate CPU-limited shell execution, rate-limited external APIs and exclusive simulators into resource classes; one homogeneous is only a teaching model. Multi-tool operations may hold several resources, creating deadlocks unless acquisition order or reservations are explicit. A general DAG may have multiple outstanding actions, whereas the paper’s chain abstraction has at most one outstanding environment stage per trajectory. Extending the heuristic to a DAG needs dependency tracking, join semantics and resource-specific queues.

Open problems include online capacity adaptation, robust load estimation for heterogeneous workers, cache transfer economics, fairness across tenants and retry-amplification control. A useful deployment sequence is an instrumented baseline, a reversible configuration change, then a guarded rollout with the original scheduler available. Do not let a learned or heuristic scheduling score bypass permissions, deadlines or cancellation. The validation plan and executable teaching model follow only after these mechanisms and boundaries are clear.

Practice and validation

Run Python 3.11+ with no packages, API keys or network. The first case verifies the 12 s versus 8 s calculation. The seeded 50-trajectory case compares FCFS and the published CAAS priority rule on identical synthetic traces. The implementation has unlimited parallel inference with fixed delays, homogeneous non-preemptive tool slots and one outstanding tool stage per trajectory. It does not implement GPU batching, cache eviction, routing, real tools, failure recovery or the authors’ system.

agent-batch-scheduler.py
python3 agent-batch-scheduler.py

Expected output (seed 17): the simple case is 12.0/8.0 s under both policies; mixed FCFS is 427.0 s and CAAS is 411.0 s. Final-5% intervals are 28.0/2.0 s; mean completion is 221.30/220.58 s. These are synthetic simulator outputs, not predictions for your deployment. With only three tasks, the discrete 95% quantile is the final task, so its tail interval is zero and uninformative.

Python · agent-batch-scheduler.py
"""Token Lab synthetic scheduling lab. Python 3.11+, standard library only.
No model, API, tools, GPU or external environment is called.
Inference stages have fixed durations and unlimited parallel capacity.
This is an independently written teaching model, not the paper's evaluator.
"""
from dataclasses import dataclass
from heapq import heappush, heappop
from math import ceil, floor, isfinite

@dataclass(frozen=True)
class Trace:
    inference: tuple[float, ...]
    environment: tuple[float, ...]
    def __post_init__(self):
        assert len(self.inference) == len(self.environment) + 1
        assert all(isfinite(x) and x > 0 for x in self.inference + self.environment)


def run(traces, samples=4, environments=1, policy="fcfs", band=30.0, bucket=1.0):
    assert samples > 0 and environments > 0 and band > 0 and bucket > 0
    assert policy in {"fcfs", "caas"}
    events, pending, completed, spans = [], [], {}, []
    active = busy = next_task = serial = 0
    observed = [0.0] * len(traces)
    max_busy = 0
    def schedule(end, kind, task, turn):
        nonlocal serial
        serial += 1
        heappush(events, (end, serial, kind, task, turn))
    def admit(now):
        nonlocal active, next_task
        while active < samples and next_task < len(traces):
            task = next_task
            next_task += 1
            active += 1
            schedule(now + traces[task].inference[0], "inference", task, 0)
    admit(0.0)
    while events:
        now = events[0][0]
        # Process simultaneous completions before choosing the next environment job.
        while events and events[0][0] == now:
            _, _, kind, task, turn = heappop(events)
            trace = traces[task]
            if kind == "environment":
                busy -= 1
                schedule(now + trace.inference[turn + 1], "inference", task, turn + 1)
            else:
                observed[task] += trace.inference[turn]
                if turn == len(trace.environment):
                    completed[task] = now
                    active -= 1
                else:
                    serial += 1
                    key = (serial,) if policy == "fcfs" else (
                        floor(now / band), -(turn + 1),
                        ceil(observed[task] / (turn + 1) / bucket), serial)
                    heappush(pending, (key, task, turn, now))
        admit(now)
        while pending and busy < environments:
            _, task, turn, arrival = heappop(pending)
            end = now + traces[task].environment[turn]
            spans.append((task, turn, arrival, now, end))
            busy += 1
            max_busy = max(max_busy, busy)
            schedule(end, "environment", task, turn)
    assert len(completed) == len(traces) and not pending and busy == active == 0
    ordered = sorted(completed.values())
    t95 = ordered[ceil(.95 * len(ordered)) - 1] if ordered else 0
    end = ordered[-1] if ordered else 0
    return {"makespan": end, "tail5": end - t95,
            "mean_completion": sum(ordered) / len(ordered) if ordered else 0,
            "completed": completed, "spans": spans, "max_busy": max_busy}


def checks():
    short = Trace((1., 1.), (2.,))
    assert run([short], samples=1)["makespan"] == 4
    assert run([short] * 3, samples=1)["makespan"] == 12
    assert run([short] * 3, samples=3)["makespan"] == 8
    for policy in ["fcfs", "caas"]:
        r = run([short] * 3, samples=3, environments=2, policy=policy)
        assert r["max_busy"] <= 2 and r["makespan"] == 6
        assert sum(e-s for _, _, _, s, e in r["spans"]) == 6
    # Earlier arrival bands outrank later bands regardless of observed depth.
    assert (0, -1, 5, 1) < (1, -100, 1, 2)
    try:
        Trace((1.,), (2.,))
    except AssertionError:
        pass
    else:
        raise AssertionError("invalid dependency chain accepted")
    return short

if __name__ == "__main__":
    short = checks()
    print("checks=passed")
    for policy in ["fcfs", "caas"]:
        for capacity in [1, 3]:
            r = run([short] * 3, samples=capacity, policy=policy)
            print(f"{policy} C_S={capacity} C_E=1 makespan={r['makespan']:.1f}s")
    # A broader synthetic comparison, with identical traces for both policies.
    import random
    rng = random.Random(17)
    traces = []
    for _ in range(50):
        turns = rng.choice([1, 2, 8, 16])
        traces.append(Trace(tuple(float(rng.randint(1, 4)) for _ in range(turns+1)),
                            tuple(float(rng.randint(1, 6)) for _ in range(turns))))
    for policy in ["fcfs", "caas"]:
        r = run(traces, samples=20, environments=3, policy=policy)
        print(f"{policy} mixed makespan={r['makespan']:.1f}s tail5={r['tail5']:.1f}s "
              f"mean={r['mean_completion']:.2f}s")

For a fair comparison, keep the same traces, submission order, , and random seed; change only the queue policy. Then vary admission separately. Sweep arrival-band width and tool capacity, include equal-depth and highly skewed chains, and report regressions as well as improvements. Add injected timeouts with a fixed terminal policy; count every admitted task. Model bounded inference capacity before drawing GPU conclusions. A single favorable seed establishes neither statistical significance nor universal superiority.

Original interview exercises—not company interview questions

Why can TPOT become worse while the batch finishes sooner?

Hint

Distinguish per-call competition from overlap across tasks.

Answer and analysis

Higher admitted concurrency may slow each active decode while keeping more independent stages in flight. The appropriate objective is constrained makespan, with a separate latency SLO if needed. Report both rather than declaring either universally better.

Does the 65% headline measure CAAS alone?

Hint

Choose the baseline that differs in exactly one intervention.

Answer and analysis

No. For live Ling-3.0 MCP-Atlas, compare 168.2 with 163.0 min for the incremental policy effect: about 3.1%. Comparing 466.1 with 163.0 measures the combined configuration. These comparisons have different denominators.

What happens if all trajectory labels are retained but the cache is evicted?

Hint

A routing hint is not storage state.

Answer and analysis

Affinity still directs calls, but prefill recomputation rises. Measure actual cached tokens and uncached work. Recover by rebuilding authorized context; never assume a label makes stale or cross-tenant data valid.

A tool times out after submitting a payment. Should the scheduler immediately retry?

Hint

Separate resource accounting from external side effects.

Answer and analysis

No automatic blind retry. Record uncertainty, reconcile the operation ID with the payment system and apply an idempotency contract. Semaphore release does not undo the payment. A scheduling speedup cannot justify duplicate business actions.

Scoring: 1—names the metric; 2—distinguishes queues, admission and execution; 3—derives the numerical example and runs the code; 4—designs controlled comparisons and explains a regression; 5—adds failure semantics, tenant constraints and a justified production rollout. Mastery requires all five abilities, not reading time alone.

Predict, test and keep evidence

Before revealing an answer, predict one result. After the exercise, record the discrepancy and a transfer test. Saved locally across language editions.

Open notebook / export / clear →

The mathematical review scope is recorded per lesson. It does not establish empirical paper reproduction; report suspected errors in your notes. Review scope

References and further learning

Primary paper by Wei Feng et al., Ling Team, Ant Group. Version v1 is CC BY 4.0; formulas, method descriptions and the selected data table are attributed adaptations. Diagrams, numerical examples and simulator are original Token Lab teaching material. No implementation repository for the paper was verified in this review; the local simulator must not be presented as the authors’ code.

Continue: agent architecture, cache mechanics and RAG