acceptodds
Under review as a conference paper at ICLR 2027

Cache Complete Cone Prefill for Local-Attention Decoders

Abstract

Prefill processes a prompt before generation begins and contributes directly to the time to first token. We propose *Cache Complete Cone Prefill* (C3P), a training- and calibration-free accelerator for local-attention decoders that retains pretrained weights and the native decoding interface. C3P traces dependencies backward from the requested logits and the cached state read by later decoding, then executes only the resulting *cone*. We prove that it reproduces both exactly in real arithmetic and is minimal among schedules that only delete original operations. We derive closed-form expressions for how many token positions each layer must process, explaining how prompt length, attention window size, and model depth determine the available savings. On an A100, C3P reduces BF16 Mistral-7B prefill latency by up to 10.6% over a FlashAttention-2 baseline that already uses final-layer slicing. On synthetic FP32 local decoders, it achieves up to speedup and 80.30% lower peak allocated memory over final-layer slicing. We further ask what information must be retained to preserve the prompt logits and future outputs when the decoding state is encoded differently. For a single attention layer with fixed keys, we determine the minimum information that must be retained from cached values to reproduce future outputs exactly, and how this requirement depends on the number of decoding steps. For purely local decoder stacks, we establish conditions under which the prompt logits and the logits of a sufficiently long continuation together uniquely determine the input vectors at every prompt position in the cone, so re-encoding cannot discard the information in those inputs. In sum, C3P combines training-free, plug-and-play prefill acceleration with rigorous guarantees on exactness and computational minimality.

Primary area:
infrastructure, software libraries, hardware, systems, etc.
Keywords:
efficient inference, prefill acceleration, local attention, KV cache, long-context inference, autoregressive decoders

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_cAGXOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
3
Presentation
3
Soundness
1
Read review
Paper summary

This paper introduces Cache Complete Cone Prefill (C3P), a prefill schedule for causal decoders with local or otherwise statically known receptive fields. C3P treats the requested prompt logits and the continuation state as targets in a static computation graph, traces their backward dependency closure, and evaluates only that closure. The schedule distinguishes positions that require a full transformer-block output from positions that require only key/value or other state production. The paper proves equality with dense prefill in real arithmetic and inclusion-minimality within the explicitly restricted class of deletion-only schedules that preserve the original operators and state representation. It also derives closed-form layerwise row and MAC counts for sliding-window attention.

Critical strengths

This paper proposes C3P: a training-free, calibration-free method that accelerates long-context prefill without modifying the model or the decoding interface, by tracing a dependency cone—planned top-down and executed bottom-up. The paper proves that this schedule is the unique minimal choice among deletion-only approaches, derives closed-form solutions for the numbers of full-output rows and K/V rows under local attention.

Critical weaknesses
  1. The gains on real large models are modest (1.045×–1.119× on Mistral-7B) and depend heavily on the window-to-depth ratio; moreover, all experiments are conducted at batch size 1, leaving the net benefit unclear under realistic serving workloads with continuous batching and prefix caching.

  2. Theorem 1 only guarantees exactness in real arithmetic; under BF16, the rounding trajectories of C3P and dense prefill differ, so outputs are no longer bitwise identical.

Questions for authors
  1. Modern serving systems rely heavily on prefix caching. Under realistic high-concurrency workloads, does C3P still retain net gains?
  2. The method targets the last-position logits only. If a workload requires the full prompt logits, does the cone degenerate entirely?
Reviewer_Er53OpenReview ↗
Rating
3
Confidence
4
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This work presents cache complete cone prefill (C3P), which is an inference optimization insight for LLMs with long context and sliding windows. C3P builds on the idea that in models where attention is only over the last N tokens in S total tokens, prefill for the last layer only needs to start from position S-N, and in the layer before that S-2N, and so on. Therefore, the full causal prefill stage is not needed here. C3P is implemented for a Mistral-7B model and tested on an A100, providing a 9-15% TTFT improvement.

Critical strengths

I'd like to thank the authors for submitting their work. I like the elegance of the idea behind C3PO; at its core it is quite clean and technically sound. Also, I find the experimental results sound and convincing.

Critical weaknesses

I believe sections 2 and 5 are over-complicating an otherwise simple and elegant idea. I do not follow why such dense theoretical work is necessary for the message of this paper. I would highly suggest that the authors shorten or remove those sections. A major flaw in the motivation of this paper is that recent LLM architectures usually rely on global layers, that severely reduces the benefits C3PO can get, and also utilize sparse attention instead of sliding window, which makes C3PO impossible. Despite this, I do believe C3PO's core concept is a useful idea to publish.

Questions for authors

If I have misunderstood the goal behind sections 2 (formalizing the cache cone) and 5 (proving skipping the work does not make the result incorrect), I would appreciate the authors correcting me.

Reviewer_U7D2OpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
1
Read review
Paper summary

The paper introduces a new training- and calibration-free prefill acceleration technique, cache complete cone Prefill (C3P) for AR decoders that utilize local attention, causal convolutions, or hybrid local-global layers. While traditional prefill processes every prompt token through every layer densely, C3P works backward from the requested final logits and the continuation state to define a dependency graph, namely the cache-complete cone. By evaluating only the nodes within this cone using original operators and weights, C3P guarantees exact mathematical equivalence to dense prefill while minimizing redundant computations.

Additionally, the paper introduces formal proofs demonstrating that C3P achieves exactness in real arithmetic and is inclusion-minimal among deletion-only schedules. They also derive closed-form expressions for required full-output and K/V row counts based on prompt length, attention window size, and model depth. C3P is evaluated experimentally using synthetic FP32 decoders and BF16 Mistral-7B, equipped with FlashAttention-2 as well as hybrid architectures (Gemma-3-4B, LFM2-2.6B), C3P achieves measurable prefill speedups (e.g., 1.045×–1.119× over final-layer slicing on Mistral-7B at 16K~32K tokens) and memory reductions without altering the native decoding interface.

Critical strengths

The paper introduces a fresh perspective by framing prefill acceleration through the lens of program slicing and backward dependency graph closure (Cone(Ω)=Ω∪AncG(Ω)Cone(\Omega) = \Omega \cup Anc_G(\Omega)). Rather than relying on heuristic token pruning or approximate caching, it rigorously defines minimal execution cones to eliminate redundant compute while preserving exact model outputs. It introduces various formal theorems and proofs, which elevate the contribution from a potential empirical engineering hack to a principled algorithmic framework.

The experiments provide a solid bridge between theory and practice. The evaluation covers a comprehensive synthetic grid across varying depths and window sizes, validates correctness against strict error tolerances, and demonstrates practical utility by integrating with optimized kernels such as FlashAttention-2 on Mistral-7B and testing hybrid local-global/convolutional architectures (i.e. Gemma-3-4B, LFM2-2.6B).

Critical weaknesses

C3P’s efficiency relies entirely on strict local-attention windows or bounded causal receptive fields. However, I have major concerns regarding its limited operational scope and incompatibility with cutting-edge dominating LLM paradigms. That is, the dominant architecture of modern frontier LLMs including leading models from ecosystems such as DeepSeek, Qwen, Moonshot's Kimi, Mixtral, and the Llama family, heavily relies on global attention mechanisms, Multi-head Latent Attention (MLA), and ultra-long context windows (128K+ tokens) paired with massive Mixture-of-Experts (MoE) routing. On these architectures, local window constraints are absent or quickly degenerate, causing C3P's backward-tracing dependency cones to expand and match dense prefill almost immediately. Consequently, it would have strengthened the work if the paper had addressed how exclusively focusing on row-slicing attention and FFN blocks performs compared to full global attention in hybrid architectures such as the recent gpt-oss-120b/20b models, which combine alternating local sliding-window attention layers with full attention and directly align with C3P's mathematical formulation.

Note that modern high-throughput inference runtimes such as vLLM or SGLang and optimized hardware kernels like FlashAttention-2/3 or FlashMask rely on predictable, highly parallelized, uniform memory access patterns and tensor shapes. Because C3P introduces irregular, layer-wise row slicing (qlq_l and plp_l vary dynamically per layer), I find it difficult to assess its practical utility. Specifically, the paper lacks a detailed systems-level or full practical analysis of how this dynamic scheduling overhead, irregular padding, and fragmented memory allocation interact with tensor parallelism (TP) and pipeline parallelism (PP) in a real serving cluster environment.

On optimized baselines like FlashAttention-2 with Mistral-7B, C3P yields modest speedups (e.g., 1.045× to 1.119×, saving ~55 to 269 ms). Given the significant engineering complexity required to inject dynamic backward-tracing dependency schedulers into existing attention runtimes, it remains unclear whether these marginal latency reductions justify the implementation overhead outside of synthetic or highly constrained edge cases.

Questions for authors
  1. While C3P's mathematical formulation targets hybrid and local-attention models, do you have any idea of how does such dynamic row-slicing interact with some recent architectures that mix alternating local/global layers with sparse Mixture-of-Experts (MoE) routing in practice? More specifically, does skipping token positions at intermediate layers cause routing fragmentation or dispatch overhead that offsets the theoretical MAC savings or not?

  2. Question about Section 4 & Appendix C.2: The empirical evaluation is restricted to single-device, batch-size-one execution on an A100 GPU (e.g., Table 2 and the Mistral-7B latency benchmarks in Section 4.3). In realistic production serving environments though utilizing Tensor Parallelism (TP) or Pipeline Parallelism (PP) across multiple nodes would make more sense, how does C3P's irregular, layer-wise dynamic row slicing (qlq_l and plp_l varying per layer) impact all-reduce communication barriers, collective synchronization, and workload balancing across devices in practice?

  3. Question about Section 2.2 and Section 2.4: Given that C3P yields relatively modest E2E improvements over highly optimized FlashAttention-2 baselines, saving only ~55 ms at 16K tokens and ~269 ms at 32.5K tokens (Figure 3 and Table 8), how does the runtime overhead of the backward-tracing dependency graph planning (detailed in Section 2.2 and Table 1) scale with model depth and prompt length? At what thresholds do the dynamic scheduling and graph construction costs begin to outweigh the raw computational MAC reductions? Any particular reason why such ablation study was never conducted?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.