Long documents such as papers, reports, and statutes are trees: tokens make sentences, sentences make sections, sections make the document. Hierarchical attention exploits this by letting each token attend only within its own sentence and to a few summary tokens for its sentence, section, and document. That cuts the theoretical cost of attention from quadratic to roughly linear in document length. On a GPU, though, attention is computed in fixed square tiles of about 64×128 entries. A tile costs the same whether one entry is needed or all of them. The runtime of tree-structured attention is therefore set by how many tiles contain at least one needed entry, and that count depends on where each token sits in memory. Because the attention computation does not change its output when tokens are reordered (as long as position information is attached beforehand), a better ordering gives a pure speedup with mathematically identical model outputs.
This note proposes to treat token ordering as an algorithm-engineering problem in its own right. We would write down the tile count as an explicit objective, compute a lower bound on it, and build a layout procedure for the document tree. The procedure jointly decides where summary tokens go and how sentences are packed into tiles, using the freedom to reorder sentences inside a section. It is the gap between asymptotic and practical cost that the implementation-complexity literature keeps finding, here made concrete in a modern setting. The closest work, the Hierarchical Document Transformer, ships a simple sort-by-level layout and says plainly that better permutation algorithms might save much more. Nobody has measured how far that heuristic is from optimal, so we would measure it first.
Core Claim
For tree-structured sparse attention on tiled GPU kernels, the right cost measure is the number of non-empty tiles, not the number of attended pairs. We claim three things about it. It can be bounded from below and nearly minimized by a dynamic program over the document tree combined with a sentence-packing step. The resulting gains are largest exactly where current heuristics break: short sentences, wide sections, and skewed or deeply nested trees. Finally, the same tree metadata used for layout (each token's ancestor identifiers at each level) lets structural attention biases be computed inside the kernel without ever forming an $n \times n$ table. That combines the accuracy benefit of biasing with the speed of sparsity.
Background and What Is Missing
On the document side, three lines of work show that explicit structure helps accuracy, and they motivate the proposal. Cohan et al.'s discourse-aware model encodes words within sections and then sections within the paper. It raises arXiv ROUGE-1 from 32.06 to 35.80 over the previous best abstractive model (A Discourse-Aware Attention Model for Abstractive Summarization of Long Documents). Buchmann et al. probe long-context models for tree depth, node type, and ancestry, and find the models' implicit sense of structure imprecise. Adding structural tokens and embeddings lifts QASPER evidence selection by 14.04 F1 (Document Structure in Long Document Transformers). The cost is extra tokens, which the authors themselves flag as a problem for very long inputs. HIBRIDS adds learned scalars to attention scores, indexed by tree path length and depth difference between the sections two tokens belong to (HIBRIDS). It keeps a dense attention matrix, so it gains accuracy but saves no computation. None of these three changes how attention executes on hardware. We keep their structural signal and change only the execution.
The Hierarchical Document Transformer, HDT (HDT: Hierarchical Document Transformer), supplies the method we build on and the baseline we must beat. It inserts sentence, section, and document "anchor" tokens and restricts attention to siblings and parent or child anchors. It runs this on a FlashAttention-style tiled kernel, sorting keys and values by hierarchy level so that empty tiles cluster together and can be skipped. At 32k tokens it reports 5,909 MB of attention memory against 21,259 MB for dense attention. HDT does not report how many non-empty tiles its sort leaves relative to the minimum. It does not exploit the freedom to reorder sentences. It also does not study irregular trees, where its $O(n \times s)$ bound degrades toward quadratic once the longest sentence $s$ or the widest section grows.
On the algorithms side, two papers supply the lens and the method. GBBS shows that theoretically efficient graph algorithms reach top wall-clock performance once memory layout is treated as a first-class constraint (Theoretically Efficient Parallel Graph Algorithms Can Be Fast and Scalable). Cache blocking alone gives up to 1.8x, and contention-aware histograms cut memory stalls by more than 7x. Batch-parallel Euler tour trees store a tree as a flat array of its traversal (Batch-Parallel Euler Tour Trees), the kind of pointer-free representation we want for tree metadata on a GPU. A wider body of work constrains the design. Andoni et al.'s near-linear edit distance hides constants doubly exponential in $1/\epsilon$ (Andoni et al.). Dynamic-graph structures from Chekuri et al. and van den Brand et al. are routinely abandoned for flat arrays (Chekuri et al., van den Brand et al.). The lesson for us is that any layout algorithm must itself be cheap, flat-array, and run once per document. Elegant cache-oblivious layouts are only worth it if they reduce the count the hardware actually pays for.
Research Program
The first piece is the cost model. HDT's attention pattern is a union of cliques arranged as a tree. Each sentence's tokens and its sentence anchor form one clique. Each section's sentence anchors and its section anchor form another. The section anchors and the document anchor form a third. Every anchor belongs to exactly two cliques. For an ordering $\pi$ of the tokens and tile size $B$, the kernel cost is
$$C(\pi) = \#\{(I,J) : \exists\, i \in I,\ j \in J \text{ with } i \text{ allowed to attend to } j\},$$
where $I$ and $J$ range over the length-$B$ blocks of positions under $\pi$. Two lower bounds are easy to state. The first is the number of allowed pairs divided by $B^2$. The second, usually tighter, comes from forcing every clique of size $m$ to touch at least $\lceil m/B \rceil^2$ tiles. We would compute $C$ for natural reading order, HDT's sort, and our layouts on real corpora, and report the gap to the lower bound. This measurement comes first because it decides whether the rest of the project is worth doing.
The second piece is the layout itself. Each anchor faces a tension. Placed beside its children, it keeps the child clique contiguous. Placed beside its sibling anchors, it keeps the parent clique contiguous. HDT resolves this globally by level. We resolve it per node with a dynamic program over the tree. For each section, the program chooses whether its anchor block shares a tile with the section's tokens, and in which order child subtrees are emitted. It optimizes the exact tile count of the subtree given where the subtree starts within a tile, which is a state of only $B$ values. On top of this sits sentence packing. Within a section, sentences can be reordered freely without changing outputs, because positions are encoded before reordering. So we pack sentences into tiles so that few straddle a tile boundary. A straddling sentence of length 25 at $B=64$ roughly doubles its diagonal tile cost. This is a bin-packing problem with a quadratic per-bin cost. A first-fit-decreasing pass followed by the tree program should land within a few percent of the bound, and the bound tells us whether it does. Everything runs in time linear in document length on flat arrays: one parent-pointer array, one depth array, and the Euler-order offsets.
The third piece is in-kernel structural biasing. For HDT-like trees of depth at most about five, each token carries a short vector of ancestor identifiers. The depth of the two tokens' lowest common ancestor is the length of the common prefix of their ancestor vectors. Tree path length and level difference, the two quantities HIBRIDS uses, follow from it in a handful of integer operations. We compute them per tile inside the kernel and add a learned bias. This gives HIBRIDS-style attention over the sparse pattern with no extra tokens and no materialized pairwise table, which addresses the token-overhead limitation Buchmann et al. raise.
The fourth piece is adversarial topologies. We would build synthetic and real trees that stress each assumption. Legal-style statutes have huge flat sections. Some documents consist of single unbroken sentences, which are common in OCR output. Others are deep and narrow, or extremely wide, with thousands of sentences in one section. On these we would chart non-empty tiles, latency, and memory for every layout, following GBBS's insistence that heuristics be tested on worst-case structure and not only on average inputs.
Baselines
The naive reference point is dense FlashAttention-style attention with the hierarchical mask applied, in natural reading order. No tiles are skipped, so it shows how much sparsity is worth at all. We would also run the same kernel in natural reading order with tile skipping enabled. Reading order is already a depth-first traversal of the tree, so this isolates whether any reordering is needed. All kernels would share the same tile size, GPU, precision, and sequence lengths of 8k, 16k, 32k, and 64k, and each would be autotuned over tile shapes with the same budget.
The strongest existing method is HDT's hierarchical kernel with its sort-by-level layout (HDT). It is the only published kernel that already turns document structure into skipped tiles. Its reported figure is 5,909 MB of attention memory at 32k tokens, against 21,259 MB for standard attention. We found no reported latency or tile-count result on Lacuna for HDT. We would reimplement its sort inside our kernel, so that only the ordering differs between arms, and check that we reproduce its memory figure at 32k. Beating it means at least a 1.3x reduction in attention-kernel latency at 32k on arXiv and GovReport documents, with identical outputs to within floating-point tolerance. On adversarial topologies, beating it means a growth curve in tile count that stays near the lower bound where HDT's departs from it. If the measured gap between HDT's sort and the lower bound is under about 10% on real corpora, that is a negative result about headroom. We would report it as such and redirect effort to the adversarial and biasing pieces.
Three ablations isolate the key ingredient. Plain Euler-tour or van Emde Boas tree layout, which knows nothing about tiles, tests whether generic cache-oblivious orderings help or whether tile awareness is what matters. The tree program without sentence packing, and sentence packing without the tree program, separate the two parts of the layout. For the biasing piece, the accuracy baselines are HIBRIDS's dense biased attention (HIBRIDS) and the structural-token infusion of Buchmann et al. (Document Structure in Long Document Transformers). On QASPER the reference points are LED's 33.6 answer F1 and 39.37 evidence F1 (QASPER), and Buchmann et al.'s reported gains of +5.58 and +14.04 F1 from infusion. We found no reported absolute ROUGE number on Lacuna for HIBRIDS on GovReport-QS, so that comparison would be rerun under matched training. Success means matching infusion's accuracy within noise while using no extra tokens and running at the sparse kernel's speed.
Why not just…?
Why not just use dense FlashAttention and skip sparsity entirely? Dense tiled attention runs at peak tensor-core throughput, and for short documents it may well win. Direction 1 predicts this: Chekuri et al. and van den Brand et al. both note that intricate structures lose to flat loops at moderate sizes. HDT's memory figures show that dense attention is already four times heavier at 32k. Memory is not latency, though, so the dense baseline is run at every length. We would report the crossover length rather than assume sparsity always pays.
Why not just pad every sentence and section to a tile boundary? This simpler alternative is a real threat. Tile-aligned padding makes cliques line up with tiles trivially, and existing block-sparse kernels could then run with no layout algorithm. The cost is wasted compute and memory on padding tokens. With sentences averaging around 25 tokens and tiles of 64, padding can more than double sequence length, the same overhead problem Buchmann et al. hit with structural tokens. We would include padding as a baseline arm and compare it to the packed layout on latency and memory. If padding wins on real corpora, that is the answer and we would say so.
Why not just use a fixed sliding window with global tokens, as Longformer does? Fixed patterns need no parsing and execute efficiently. HDT reports that its document-dependent pattern beats Longformer on SciRepEval proximity tasks and converges in 10k pretraining iterations versus 64k. LED, which is built on this pattern, reaches only 33.6 answer F1 on QASPER, where 55.5% of questions need evidence from several paragraphs. Our proposal does not reargue accuracy; it takes HDT's pattern as given and makes it cheaper. A Longformer-pattern kernel at matched length is included only as an efficiency reference.
Why not just accept HDT's sort as good enough? It may be. That is why the lower-bound measurement comes before any engineering. If HDT's sort sits close to the bound on arXiv, PubMed, and GovReport, the layout contribution is limited to irregular trees, and the experiments on adversarial topologies would show whether even that holds.
Proposed Experiments
Kernel experiments use documents drawn from the arXiv and PubMed summarization sets, GovReport, and QASPER papers, all of which have explicit section structure. We also use the synthetic adversarial trees described above. Lengths are 8k to 64k tokens and tile sizes 64 and 128. For every layout we measure non-empty tiles relative to the lower bound, forward and backward kernel latency, peak memory, achieved throughput, and L2 hit rate from the GPU profiler. Layout preprocessing time is reported separately and must stay under a few percent of one forward pass.
End-to-end, we would pretrain a small HDT-style encoder with each layout under an identical seed and data order. This serves two purposes: confirming that losses match step for step, which checks the exactness claim, and measuring wall-clock time to HDT's 10k-iteration convergence point. Downstream we would evaluate SciRepEval proximity tasks, where SPECTER2's reported 71.2 average across all formats (SciRepEval) serves only as context, since layout cannot change accuracy. For the biasing piece we fine-tune on QASPER, Evidence Inference, and GovReport-QS, comparing in-kernel biases against dense HIBRIDS and against token infusion at matched compute.
Two checks decide the project. The first is the measured gap between HDT's sort and the tile lower bound on real corpora. If it is small, the layout contribution reduces to irregular trees. The second is whether the packed tree layout beats tile-aligned padding on both latency and memory at 32k. If it does not, the simpler method should be the recommendation.
References
- A Discourse-Aware Attention Model for Abstractive Summarization of Long Documents
- Document Structure in Long Document Transformers
- HIBRIDS: Attention with Hierarchical Biases for Structure-aware Long Document Summarization
- HDT: Hierarchical Document Transformer
- Theoretically Efficient Parallel Graph Algorithms Can Be Fast and Scalable
- Batch-Parallel Euler Tour Trees
- Edit Distance in Near-Linear Time: it's a Constant Factor
- Adaptive Out-Orientations with Applications
- Fast Deterministic Fully Dynamic Distance Approximation
- A Dataset of Information-Seeking Questions and Answers Anchored in Research Papers
- SciRepEval: A Multi-Format Benchmark for Scientific Document Representations