TimeBill: Time-Budgeted Inference for Large Language Models
Qi Fan, An Zou, Yehan Ma
2025-12-29
Summary
This paper introduces TimeBill, a new system designed to make large language models (LLMs) respond faster and more reliably when speed is critical, like in robots or self-driving cars.
What's the problem?
LLMs are great at generating text, but they do it one word at a time, making it hard to predict how long it will take to get a complete answer. Current methods for speeding them up often use a fixed strategy for removing information from memory (the 'KV cache'), which doesn't work well when different tasks need different amounts of time. Sometimes they finish too early with an incomplete answer, and other times they take too long and miss deadlines.
What's the solution?
TimeBill tackles this by predicting both how long an answer will be and how long it will take the LLM to generate it. It then cleverly adjusts how much information is removed from the LLM’s memory during the process, aiming to balance speed and accuracy. This adjustment happens automatically based on the predicted time and the time limit given.
Why it matters?
This research is important because it allows us to use LLMs in real-world applications where timing is crucial. If a robot needs to react quickly to avoid an obstacle, or a self-driving car needs to make a fast decision, having an LLM that can provide a reliable answer within a specific timeframe is essential for safety and effective operation.
Abstract
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.