# TimeBill: Time-Budgeted Inference for Large Language Models

arXiv: https://arxiv.org/abs/2512.21859 · HTML: https://mlsanity.com/paper/2512.21859/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 35 references that are in the map.
- First posted on arXiv 26 Dec 2025.

## Builds on (most cited first, 20 of 20)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [PaLM: Scaling Language Modeling with Pathways](https://mlsanity.com/paper/2204.02311/) (2022)
- [DistilBERT, a distilled version of BERT: smaller, faster, cheaper and lighter](https://mlsanity.com/paper/1910.01108/) (2019)
- [Efficient Streaming Language Models with Attention Sinks](https://mlsanity.com/paper/2309.17453/) (2023)
- [GLU Variants Improve Transformer](https://mlsanity.com/paper/2002.05202/) (2020)
- [Root Mean Square Layer Normalization](https://mlsanity.com/paper/1910.07467/) (2019)
- [AWQ: Activation-aware Weight Quantization for LLM Compression and Acceleration](https://mlsanity.com/paper/2306.00978/) (2023)
- [Chatbot Arena: An Open Platform for Evaluating LLMs by Human Preference](https://mlsanity.com/paper/2403.04132/) (2024)
- [SparseGPT: Massive Language Models Can Be Accurately Pruned in One-Shot](https://mlsanity.com/paper/2301.00774/) (2023)
- [SnapKV: LLM Knows What You are Looking for Before Generation](https://mlsanity.com/paper/2404.14469/) (2024)
- [KIVI: A Tuning-Free Asymmetric 2bit Quantization for KV Cache](https://mlsanity.com/paper/2402.02750/) (2024)
- [DistServe: Disaggregating Prefill and Decoding for Goodput-optimized Large Language Model Serving](https://mlsanity.com/paper/2401.09670/) (2024)
- [KVQuant: Towards 10 Million Context Length LLM Inference with KV Cache Quantization](https://mlsanity.com/paper/2401.18079/) (2024)
- [DuoAttention: Efficient Long-Context LLM Inference with Retrieval and Streaming Heads](https://mlsanity.com/paper/2410.10819/) (2024)
- [Response Length Perception and Sequence Scheduling: An LLM-Empowered LLM Inference Pipeline](https://mlsanity.com/paper/2305.13144/) (2023)
- [A Simple and Effective L2 Norm-Based Strategy for KV Cache Compression](https://mlsanity.com/paper/2406.11430/) (2024)
- [S3: Increasing GPU Utilization during Generative Inference for Higher Throughput](https://mlsanity.com/paper/2306.06000/) (2023)
- [BestServe: Serving Strategies with Optimal Goodput in Collocation and Disaggregation Architectures](https://mlsanity.com/paper/2506.05871/) (2025)

## Built on by (most cited first, 4 of 4)

- [Timely Machine: Awareness of Time Makes Test-Time Scaling Agentic](https://mlsanity.com/paper/2601.16486/) (2026)
- [RouteBalance: Fused Model Routing and Load Balancing for Heterogeneous LLM Serving](https://mlsanity.com/paper/2606.17949/) (2026)
- [Predict-then-Diffuse: Adaptive Response Length for Compute-Budgeted Inference in Diffusion LLMs](https://mlsanity.com/paper/2605.04215/) (2026)
- [Unifying Data, Memory, and Compute Efficiency in LLM training: A Survey](https://mlsanity.com/paper/2606.10706/) (2026)

## Abstract (arXiv)

Large Language Models (LLMs) are increasingly deployed in time-critical systems, such as robotics, autonomous driving, embodied intelligence, and industrial automation, where generating accurate responses within a given time budget is crucial for decision-making, control, or safety-critical tasks. However, the auto-regressive generation process of LLMs makes it challenging to model and estimate the end-to-end execution time. Furthermore, existing efficient inference methods based on a fixed key-value (KV) cache eviction ratio struggle to adapt to varying tasks with diverse time budgets, where an improper eviction ratio may lead to incomplete inference or a drop in response performance. In this paper, we propose TimeBill, a novel time-budgeted inference framework for LLMs that balances the inference efficiency and response performance. To be more specific, we propose a fine-grained response length predictor (RLP) and an execution time estimator (ETE) to accurately predict the end-to-end execution time of LLMs. Following this, we develop a time-budgeted efficient inference approach that adaptively adjusts the KV cache eviction ratio based on execution time prediction and the given time budget. Finally, through extensive experiments, we demonstrate the advantages of TimeBill in improving task completion rate and maintaining response performance under various overrun strategies.