QUILL: An Algorithm–Architecture Co-Design for Cache-Local Deformable Attention
Hyunwoo Oh, Hanning Chen, Sanggeon Yun, Yang Ni, Wenjun Huang, Tamoghno Das, Suyeon Jang, and Mohsen Imani · 2025
Read QUILL: An Algorithm–Architecture Co-Design for Cache-Local Deformable Attention by Hyunwoo Oh, Hanning Chen, Sanggeon Yun, Yang Ni, Wenjun Huang, Tamoghno Das, Suyeon Jang, and Mohsen Imani (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-13679.txt.
Introduction
Hyunwoo Oh and 7 co-authors present QUILL, an accelerator design that makes deformable attention hardware-friendly. Deformable transformers lead object detection accuracy, but their scattered memory access and low arithmetic density waste standard chips. QUILL reorders the work so data arrive in cache-friendly, single-pass order.
Queries are sorted by spatial closeness, and a look-ahead prefetches the needed regions into a spare buffer while compute proceeds. A fused engine runs interpolation, softmax, gathering, and projection in one pass without spilling data. Built as register-transfer hardware, it beat a flagship graphics card on throughput and energy by large multiples and stayed within a point of full-precision accuracy under mixed precision.
Catalog record
| CREATOR | Hyunwoo Oh, Hanning Chen, Sanggeon Yun, Yang Ni, Wenjun Huang, Tamoghno Das, Suyeon Jang, and Mohsen Imani |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 28 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2511-13679
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
QUILL: An Algorithm–Architecture Co-Design for Cache-Local Deformable Attention Hyunwoo Oh, Hanning Chen, Sanggeon Yun, Yang Ni, Wenjun Huang, Tamoghno Das, Suyeon Jang, and Mohsen Imani Abstract Deformable transformers deliver state-of-the-art detection but map poorly to hardware due to irregular memory access and low arithmetic intensity. We introduce QUILL , a schedule-aware accelerator that turns deformable attention into cache-friendly, single-pass work. At its core, Distance-based Out-of-Order Querying (DOOQ) orders queries by spatial proximity; the look-ahead drives a region prefetch into an alternate buffer—forming a schedule-aware prefetch loop that overlaps memory and compute. A fused MSDeformAttn engine executes interpolation, Softmax, aggregation, and the final projection ( W m ′′ W_{m}^{\prime\prime} ) in one pass without spilling intermediates, while small tensors are kept on-chip and surrounding dense layers run on integrated GEMMs. Implemented as RTL and evaluated end-to-end, QUILL achieves up to 7.29 × \times higher throughput and 47.3 × \times better energy efficiency than an RTX 4090, and exceeds prior accelerators by 3.26–9.82 × \times in throughput and 2.01–6.07 × \times in energy efficiency. With mixed-precision quantization, accuracy tracks FP32 within ≤ \leq 0.9 AP across Deformable and Sparse DETR variants. By converting sparsity into locality—and locality into utilization—QUILL delivers consistent, end-to-end speedups. I Introduction Detection transformers (DETR) [ 1 ] have attracted widespread attention for their end-to-end object detection capabilities, often outperforming CNN-based detectors in simplicity and adaptability [ 2 ] . As a result, DETR-based models have seen rapid adoption in tasks such as 2D recognition and multimodal AI systems [ 1 , 2 , 3 , 4 , 5 , 6 ] . However, original DETR variants still suffer from high computational cost and slow convergence, mainly due to dense attention mechanisms that obscure gradient flow from input features [ 7 ] . Deformable DETR [ 7 ] addresses these issues with multi-scale deformable attention (MSDeformAttn), sampling only a handful of spatial locations per query. Inspired by deformable convolutions [ 8 ] , this design significantly reduces FLOPs and accelerates training. Consequently, as shown in Fig. 1 , MSDeformAttn underpins state-of-the-art detector modules [ 9 , 10 , 11 , 12 , 13 , 14 , 15 ] and has been adopted in emerging tasks such as video restoration [ 16 ] and large vision–language models [ 17 ] . Fig. 1 : Landscape of SOTA object detection models. Fig. 2 : FLOPs vs. latency on RTX 4090 comparing the backbone to the deformable transformer block. Fig. 3 : GPU performance breakdowns of Deformable DETR and query-pruned models on RTX 4090 . ( a ) Latency across internal blocks. ( b ) Roofline view of bottlenecks and mitigation levers. Despite MSDeformAttn’s algorithmic efficiency, practical deployments on GPUs expose notable latency and throughput drawbacks [ 18 , 19 , 20 ] , limiting adoption in real systems [ 21 ] . Our profiling on an RTX 4090 highlights four observations: 1. Fewer FLOPs, higher latency (Fig. 2 ). Although the backbone accounts for most FLOPs, the deformable transformer block dominates run time . MSDeformAttn’s mathematically sparse pattern fragments memory access , triggering frequent stalls. 2. Pruning reduces FLOPs but not latency proportionally (Fig. 3 (a)). Query pruning [ 22 ] lowers FLOPs roughly with the keeping ratio \rho [ 13 ] , but latency gains remain modest (e.g., even at \rho{=}0.1 ) due to scattered sampling overheads. 3. Decoder cost remains substantial even with 98.5% fewer queries (Fig. 3 (a), top). The decoder uses a tiny set of queries (e.g., 300; a 98.5% reduction vs. the encoder’s 20,097), yet it still accounts for \sim 33% of runtime , indicating an order-of-magnitude higher per-query cost . Modern Deformable DETR variants exacerbate this by increasing N_{d} (e.g., N_{d}{=}900 [ 10 , 15 ] ). 4. Three fundamental bottlenecks (Fig. 3 (b)). A roofline view identifies cache misses ( 1 ), low arithmetic intensity ( 2 ), frequent bank conflicts ( 3 ) [ 19 ] as dominant causes of low PE utilization on current platforms. These results reveal a mismatch between MSDeformAttn’s sparse behavior and modern GPU architectures, motivating an algorithm–architecture co-design that preserves model outputs while reorganizing execution for locality and utilization. Most transformer accelerators target standard attention where accesses are denser and more regular [ 23 , 24 , 25 , 26 , 27 ] . In contrast, MSDeformAttn is inherently irregular , sampling from scattered references across multi-level features. Recent MSDeformAttn accelerators [ 19 , 20 ] leave critical gaps: (i) DEFA [ 19 ] processes queries in a fixed sequential order and relies on a sliding-window cache, which is ill-suited to the decoder and pruned encoder where sparsity dominates, leading to severe cache misses ; moreover, it runs bilinear interpolation, Softmax, and linear layers as separate micro-kernel passes , forcing full memory load–store between passes. (ii) UEDA [ 20 ] struggles to scale to standard Deformable DETR settings (e.g., N_{e}{=}20{,}097 , D{=}256 ) due to FPGA resource constraints and limited algorithmic leverage. To our knowledge, no prior art (1) addresses sparse query irregularity at runtime and (2) unifies encoder, decoder, and FFN in one execution path. We present QUILL , an algorithm–architecture co-design that turns deformable attention into cache-friendly work while preserving model semantics. Unlike fixed traversal/sliding-window schemes [ 19 ] or FPGA-restricted pipelines [ 20 ] , QUILL introduces a runtime, proximity-aware reordering that restructures execution for locality. Our contributions are: • DOOQ runtime (query-locality scheduling with aligned prefetch). Distance-based Out-of-Order Querying (DOOQ) reorders queries by spatial proximity to raise cache hit rate. Its lookup window exposes predictable addresses, enabling double-buffered prefetch aligned to the schedule, overlapping fetch with compute and cutting cache-miss stalls ( 1 ). • Fused MSDeformAttn execution path. A single-pass path that fuses sampling, weighting (Softmax), and aggregation to lift arithmetic intensity ( 2 ) and avoid intermediate stores; conflict-aware buffers curb bank conflicts ( 3 ), addressing inefficiencies in prior designs [ 19 ] . • RTL prototype & full-stack evaluation. A synthesizable RTL of the full accelerator (DOOQ scheduler, feature cache, fused core, gather–scatter, GEMM I/F), functionally verified against a reference MSDeformAttn, with cycle-accurate simulation, post-synthesis PPA, and end-to-end throughput/energy vs. RTX 4090 and DEFA (incl. ablations on w_{d} , r ). Across Deformable DETR variants, QUILL achieves up to 7.29 \times higher throughput and 47.3 \times better energy efficiency than an RTX 4090 GPU. Compared to DEFA [ 19 ] , QUILL improves throughput by 3.26–9.82 \times , attributable to DOOQ’s locality gains together with the fused execution path. II Preliminaries & Hardware Challenges We give a hardware-centric view of MSDeformAttn and explain why its sparse, data-dependent access pattern dominates latency on existing platforms. We then show how common sparsification (e.g., query pruning ) further degrades locality, motivating our algorithm–architecture co-design. II-A MSDeformAttn: A Hardware View MSDeformAttn [ 7 ] computes, for query q , reference point p and spatial embedding feature map x , \displaystyle MSDeformAttn(q,p,x)= (1) \displaystyle\sum_{m=1}^{M}W_{m}\cdot\Biggl[\sum_{l=1}^{L}\sum_{k=1}^{K}A_{qmlk} \displaystyle\cdot W_{m}^{\prime}\cdot x(\hat{p}_{q}+\Delta p_{qmlk})\Biggr] where m,l,k index head, feature level, and sampling point. Each query gathers a few fractional locations per head across multi-level features (via 2 \times 2 bilinear interpolation), applies attention weights A , and aggregates the result. FLOPs are modest, but the irregular, multi-level gathers fragment memory access