Decomposition-Invariant Entitlement: Fair Scheduling for Agentic LLM Programs

Agentic applications turn one user task into a dynamic directed acyclic graph (DAG) of LLM calls whose decomposition is chosen by the model or runtime. Using critical-path progress as the service charge that controls inter-program scheduling makes a program's service share depend on its DAG decomposition: for fixed additive work, it undercharges the program by the ratio of total to longest-path service, exactly $k$ for $k$ balanced branches. We define accounting and allocation decomposition invariance. Program-VTC enforces both properties by adding the service of every LLM call to one weighted virtual counter per program. In vLLM, it keeps normalized service within $0.5\%$ of parity across sequential, balanced, nested, and flat decompositions on Qwen3.8-27B and Nemotron-3.5-30B-A3B; critical-path accounting falls as low as $0.017$. Program-VTC remains near parity across service metrics, fan-out, I/O mix, prefix sharing, arrivals, departures, and tool waits. Its median throughput is $0.2\%$ below stock vLLM. Across coding, research, and verifier-guided search, Program-VTC points within $5\%$ of ATLAS's achieved share complete within $5.2\%$, while competitor throughput differs by at most $2.0\%$. Critical path can prioritize urgency; resource entitlement remains independent of the number of calls a program creates.