Research map / Large language models / Reasoning and chain of thought

TimeBill: Time-Budgeted Inference for Large Language Models

AAAI 2026 · Large language models › Reasoning and chain of thought · approach: Efficient LLM serving

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes TimeBill, a time-budgeted inference framework that predicts LLM end-to-end execution time with a fine-grained bucketed response length predictor and a FLOPs-guided profiled time estimator, then adapts the KV cache eviction ratio to meet a deadline.

Problem

LLM inference in hard real-time systems has uncertain end-to-end execution time because response length is unknown until generation finishes, and fixed KV cache eviction ratios either miss time budgets or degrade response quality.

Approach

Combine a small-LM (Qwen2.5-0.5B) 512-bucket response length classifier distilled from the target LLM with a workload-guided execution time model (quadratic prefill, linear decoding fitted by profiling), and solve in closed form for the minimal KV eviction ratio that fits the remaining time budget.

Key results

• The 512-bucket RLP achieves MAE 42.71 and R^2 0.723, versus 105.72 MAE and 0.152 R^2 for ProxyModel and 108.96 MAE and -0.004 R^2 for S3.
• Execution time estimator reports MAPE of 1.22% for prefill and 1.69% for decoding steps on the target LLM.
• Across time budgets of 5-10 s, TimeBill reaches the highest average score among tested approaches while keeping a completion rate similar to fixed alpha=95%.

Surprising findings

• Regression-based response length prediction performs poorly compared with bucketed classification, indicating exact length prediction is hard.
• Increasing the pessimistic factor k beyond about 5 lowers the average score because the eviction ratio becomes too large.

Limitations

• Predictor and time model are tied to a specific target LLM and hardware, requiring offline profiling and retraining per deployment.
• Evaluation uses a single target model (Qwen2.5-7B-Instruct) on one GPU type (NVIDIA A40).
• Relies on a conservative pessimistic factor k=5 whose choice materially affects accuracy-completion trade-offs.

Experimental setup

Datasets: Arena-Human-Preference-100k LongBench

Benchmarks: LongBench

Metrics: F1 ROUGE-L Levenshtein distance task completion rate MAE RMSE R2 MAPE

Baselines: Vanilla inference SnapKV with fixed eviction ratio (25%, 50%, 75%, 95%) AWQ ProxyModel S3

Builds on: SnapKV ProxyModel S3 AWQ

Closest papers by meaning

• An Architecture Search Framework for Inference-Time Techniques (ICML 2025 · similarity 0.89)
• AgentTTS: Large Language Model Agent for Test-time Compute-optimal Scaling Strategy in Complex Tasks (NeurIPS 2025 · similarity 0.89)
• TokenPowerBench: Benchmarking the Power Consumption of LLM Inference (AAAI 2026 · similarity 0.88)
• Fast Inference for Augmented Large Language Models (NeurIPS 2025 · similarity 0.88)
• EE-LLM: Large-Scale Training and Inference of Early-Exit Large Language Models with 3D Parallelism (ICML 2024 · similarity 0.88)
• SCBench: A KV Cache-Centric Analysis of Long-Context Methods (ICLR 2025 · similarity 0.88)