ETC: Encoding Long and Structured Inputs in Transformers

ArXiv: 2004.08483

🎯 Pitch

Attention’s quadratic cost forces most Transformers to cap input at 512 tokens—but ETC breaks this barrier with global–local attention that separates a few global tokens from the long sequence, achieving linear scaling while actually beating standard attention on long-document QA. Even more surprising, the same architecture naturally encodes hierarchical input structure (sentence boundaries, document order) via relative position encodings and a CPC pre-training task, setting new SOTA on four benchmarks simultaneously.

1. Executive Summary

This paper introduces the Extended Transformer Construction (ETC), a Transformer architecture that addresses two core bottlenecks of standard Transformers — scaling to long inputs and encoding structured inputs — through a novel global-local attention mechanism (splitting input into a small set of global tokens that attend freely to everything and a long sequence whose self-attention is restricted to a fixed local radius, enabling information flow across the entire input via the global tokens as intermediaries) combined with relative position encodings and a Contrastive Predictive Coding (CPC) pre-training objective (a sentence-level masked prediction task that trains the global summary tokens to predict hidden representations of masked sentences). On four long/structured NLP benchmarks — Natural Questions, HotpotQA, WikiHop, and OpenKP — ETC achieves state-of-the-art results, including a 4× reduction in wall-clock time compared to BERT at input lengths beyond ~1500 tokens, establishing that linear-complexity attention with structured inductive bias can match or exceed standard quadratic attention only when the architecture is augmented with learnable pairwise token relations and a pre-training signal that teaches the global tokens their role as information routers.

2. Context and Motivation

The Two Bottlenecks of Standard Transformers

The paper targets two intertwined limitations of the Transformer architecture that constrain what NLP models can do with real-world text. Understanding why these are bottlenecks — and why they are hard to solve simultaneously — requires unpacking the architectural constraint at the heart of the problem.

The quadratic attention wall. In a standard Transformer (Vaswani et al., 2017), every token in a sequence of length $n$ attends to every other token. This produces an $n \times n$ attention matrix whose computational and memory cost scales as $O(n^2)$ . In practice, this forces most Transformer models (BERT, RoBERTa, T5, ALBERT) to cap input length at $n = 512$ tokens. The paper states this explicitly:

"The computational and memory complexity of attention in the original Transformer scales quadratically with the input length, typically limiting input length to around 512 tokens."

Why 512 tokens is a genuine bottleneck — not just an inconvenience — depends on the task. For some problems (e.g., co-reference resolution, which the paper notes "seems to benefit from even smaller input lengths" citing Joshi et al., 2019), 512 is adequate. But for many real-world NLP tasks, it fundamentally breaks the problem structure:

Multi-document question answering (HotpotQA): the model must simultaneously hold multiple documents (paragraphs from different sources) in its input to reason across them. If the documents collectively exceed 512 tokens, the model must either truncate information or use some workaround that breaks cross-document attention.
Open-domain QA on full articles (Natural Questions): the input is a question plus a complete Wikipedia article. Wikipedia articles routinely run thousands of words; the median NQ instance in this paper is 4,004 word piece tokens, and the maximum is 156,551 tokens (Table 1). Capping at 512 tokens means discarding 85–95% of the article content — including likely the paragraph that contains the answer.
Keyphrase extraction from web pages (OpenKP): web pages contain DOM trees, headings, formatting, and spatial layout information across potentially thousands of tokens. Truncation destroys the structural signals that distinguish keyphrases from body text.

The 512-token limit is thus not an arbitrary constraint — it is the direct consequence of $O(n^2)$ attention, and it prevents Transformer models from ingesting documents at their natural granularity.

The structure blindness. The second bottleneck is subtler but equally important: standard Transformers treat input as a flat, ordered sequence of tokens. The only structural information they receive is position — token $i$ comes before token $j$ . The paper uses the term "structured inputs" to refer to inputs with "any underlying graph or hierarchical structure among the input tokens" beyond sequential ordering. This covers:

Document hierarchy: text is organized into words → sentences → paragraphs → sections → documents. Sentences within a paragraph have ordering; paragraphs within a document have ordering. But if the input contains multiple documents (e.g., HotpotQA's 10 paragraphs from different sources), there is no inherent order between documents — they are an unordered set. A flat position encoding forces an arbitrary sequential ordering onto this set, which is a misleading inductive bias.
Web page structure: web content lives in a DOM tree. Elements have parent-child relationships (headings contain text nodes; sections contain subsections), sibling relationships (adjacent paragraphs), and visual properties (font sizes, bold/heading/block formatting) that carry semantic signal. A flat token sequence completely discards this tree structure.
Entity linking: when different mentions of the same entity appear across a document (or across multiple documents), they should arguably share information more directly than through the sequential chain of tokens between them. Standard attention can learn this implicitly, but it has no structural mechanism to represent "token A and token B refer to the same thing."

A standard Transformer resembles a fully connected graph neural network (as the paper notes, citing Ye et al., 2019), where each token is a node and there is an edge between every pair. This is a degenerate graph structure: it encodes no domain-specific relations. The paper's key intuition — which motivates much of the technical design — is that if you could give the model explicit structural edges (hierarchical parent-child, cross-document entity links, DOM tree adjacency), you would inject useful inductive bias that the model would otherwise have to learn from scratch, expensively and unreliably.

Why These Bottlenecks Matter Beyond Academic Benchmarks

The paper's explicit motivation is practical, but the implications run deeper. If Transformer models cannot scale past 512 tokens and cannot ingest structured inputs, they are artificially restricted to tasks that fit within a "single-page snapshot" paradigm: short documents, single-paragraph QA, sentence-level classification. But the world's text is overwhelmingly longer and richer in structure:

Scientific literature understanding requires ingesting full papers (thousands of words) with section hierarchies, citation graphs, and figure-caption relations.
Legal and financial document analysis involves contracts or reports spanning tens of thousands of tokens, with explicit section/subsection numbering, cross-references, and defined-term links.
Conversational agents with long-term memory need to attend over dialogue histories that quickly exceed 512 tokens, with speaker-turn structure and topic segmentation.

The $O(n^2)$ attention cost is not just a hardware constraint — it is a representational constraint that determines which problems the field can even attempt with Transformer models. Every workaround (truncation, sliding windows, post-hoc aggregation) is a compromise that loses global context or structural signal. The paper positions ETC as an attempt to remove this constraint at the architectural level.

Prior Approaches and Where They Fall Short

The paper classifies prior work on scaling Transformers into four categories (Section 2), and each has specific limitations relative to the paper's goals. Understanding each category's mechanism — and its failure mode — sets up why ETC's design choices are not arbitrary.

1. Sparse Attention

Sparse attention methods reduce the $n \times n$ attention matrix to something sparser by restricting which token pairs can attend. The paper surveys:

Sparse Transformer (Child et al., 2019): uses pre-defined attention patterns (e.g., attending only to previous pixels in the same row or column for images) to achieve $O(n\sqrt{n})$ cost. Effective for images and autoregressive text generation, but the fixed pattern is domain-specific (row/column attention works for 2D grids, not for arbitrary NLP text) and does not encode hierarchical or graph structure.
Adaptive Attention Span (Sukhbaatar et al., 2019): learns a decaying masking function per attention head, so lower layers attend to short spans and higher layers attend to longer spans. This is data-driven and flexible, but it still only captures distance-based sparsity — tokens are masked based on how far apart they are in the sequence, not based on whether they are structurally related.
Reformer (Kitaev et al., 2020): uses locality-sensitive hashing to find nearest-neighbor keys for each query, reducing cost to $O(n \log n)$ . This achieves sub-quadratic scaling elegantly, but the attention pattern is determined by token embedding similarity, not by explicit structure. Two structurally related tokens (e.g., an entity mention and a co-referent) may not be nearest neighbors in embedding space and thus don't attend to each other.
Routing Transformer (Roy et al., 2020): learns dynamic sparse patterns via online k-means, achieving $O(n^{1.5})$ . Again, the sparsity pattern is learned from data, not informed by known structure.

The common thread: sparse attention methods reduce computation, but they do not encode structure. The sparsity pattern is either fixed (Sparse Transformer), learned from position alone (Adaptive Span), or learned from content similarity (Reformer, Routing Transformer). None can express "these two tokens are part of the same sentence" or "this global token summarizes that paragraph" as an explicit architectural constraint.

The closest prior work: Longformer (Beltagy et al., 2020), developed concurrently with ETC. Longformer uses a similar global-local attention pattern (some tokens marked as "global" attend to everything, regular tokens attend locally). The paper explicitly compares:

"Longformer... features a very similar global-local attention mechanism as ETC's but does not directly encode graph or hierarchical structure."

The critical differences: Longformer (1) has global tokens in a single sequence rather than a separate global input, (2) uses absolute position encodings rather than relative, (3) does not have flexible attention masks or multiple relative position label types for structural relations, and (4) does not pre-train the global tokens with anything like CPC — their function must be learned entirely during fine-tuning. ETC's explicit separation into global and long inputs, combined with learnable relation labels, is what enables structured input encoding beyond what Longformer can express.

2. Recurrence

Recurrence approaches like Transformer-XL (Dai et al., 2019) divide the input into segments, process them sequentially, and allow each layer to attend to the previous segment's hidden states. This extends the effective context window: at layer $k$ , a token can see the current segment plus the previous $k-1$ segments.

The limitation: Transformer-XL extends context through a sequential memory mechanism, not through global structural awareness. Information flows from earlier segments to later ones through hidden states passed forward, which creates a temporal bottleneck — a token in segment 1 can only influence a token in segment 5 if the information propagates through segments 2, 3, and 4. There is no direct edge from segment 1 to segment 5. Moreover, Transformer-XL enforces a strict sequential ordering on segments (segment 1 comes before segment 2), which is inappropriate for tasks where the input components are an unordered set (e.g., HotpotQA's independent paragraphs, WikiHop's independent contexts).

3. Hierarchical Mechanisms

HIBERT (Zhang et al., 2019) and similar approaches process input in two stages: first, each sentence (or block) is encoded independently into a summary embedding; second, a separate Transformer processes the sequence of sentence summaries. The paper illustrates this in Figure 1 (bottom-left).

The limitation: hierarchical models introduce an information bottleneck at the block boundaries. The sentence summaries are fixed-dimensional vectors that must capture everything relevant about that sentence for the downstream task. If the summarization is too aggressive (e.g., mean pooling over token embeddings), fine-grained token-level information (like exact entity spans for QA) is lost. If the summarization uses attention, it still requires $O(n^2)$ computation within each block, so the approach doesn't reduce complexity for very long blocks — it only reduces across-block complexity.

More fundamentally, hierarchical approaches encode a specific two-level hierarchy (tokens → sentences → document) that is hard-coded into the architecture. They cannot flexibly represent arbitrary structures like DOM trees, entity links, or cross-document references without architectural modification for each new structure type.

4. Compressed Attention

Compressed attention methods selectively compress parts of the input to reduce the effective sequence length:

BP-Transformer (Ye et al., 2019): builds a binary partitioning tree over the input. Nearby tokens attend to raw token representations; distant tokens attend to higher-level tree nodes that summarize groups of tokens. This captures hierarchical structure naturally (the tree itself is a hierarchy), but the tree structure must be a binary partition of a sequence — it cannot represent arbitrary graph structure or pre-existing hierarchies like DOM trees.
Star Transformer (Guo et al., 2019): each token attends only to its immediate neighbors (left/right) and to a single auxiliary "star" token that represents a summary of the entire input. ETC generalizes this: if you set the local radius $r = 1$ and the number of global tokens $n_g = 1$ , you recover the Star Transformer exactly. This connection is explicitly stated in Section 3.2 and shows that ETC is a strictly more expressive architecture — it can represent the Star Transformer's sparse pattern but also many others.
Compressive Transformer (Rae et al., 2019): extends Transformer-XL by compressing old tokens (rather than just caching them), so the model can attend to detailed nearby tokens and compressed distant tokens.

The common limitation: these methods compress based on distance/recency (farther tokens are compressed more aggressively) or pre-defined partitioning schemes (binary tree, fixed block sizes), not based on the actual structural organization of the input. If two strongly related tokens happen to be far apart, the compression may destroy the signal needed to connect them.

The Unifying Gap: No Prior Work Simultaneously Handles Long Inputs AND Arbitrary Structure

The paper's survey of prior work leads to a specific gap statement. While many approaches address either long inputs (sparse attention, recurrence, compression) or hierarchical structure (hierarchical models), none address both simultaneously in a way that is:

Flexible: able to encode arbitrary pairwise token relations (not just sequential order or a fixed hierarchy).
Pre-trainable: the structural tokens (global tokens) can be pre-trained with a self-supervised objective that teaches them to summarize and route information, rather than being learned only during fine-tuning on task-specific data.
Backward-compatible: the architecture can be initialized from existing pre-trained BERT/RoBERTa checkpoints, allowing it to inherit general language knowledge rather than starting from scratch.

This is where ETC stakes its claim. It is not the first sparse attention model, not the first hierarchical model, and not the first to use relative position encodings. But it is — at the time of publication — the first to combine global-local attention, relative position encodings with arbitrary relation labels, flexible per-instance attention masks, and CPC pre-training into a single architecture that can encode structured long inputs while initializing from existing pre-trained models.

How ETC Positions Itself Relative to Existing Work

The paper's positioning is explicit through four design choices that collectively differentiate it:

1. The global-local split is an architectural separation, not just an attention pattern. Unlike Longformer's in-place global tokens or Star Transformer's single star token, ETC maintains two physically separate input sequences: the long input (which holds the raw text tokens) and the global input (which holds auxiliary summary tokens). This separation is not cosmetic — it enables different processing for the two types of tokens (different projection matrices $W^Q$ , $W^K$ , $W^V$ ), different attention radii, and different pre-training objectives. CPC only makes sense in this architecture because the global tokens are explicitly designated as "summary tokens for masked segments."

2. Relative position labels generalize beyond position to arbitrary relations. Shaw et al. (2018) introduced relative position encodings where the label $l_{ij}$ on the edge from token $x_i$ to token $x_j$ depends only on $j - i$ (their relative sequential distance). ETC expands this vocabulary to include labels that represent structural relations: "token belongs to this sentence," "sentence belongs to this context," "this global token is the candidate answer and this long token is a mention of it." The paper states this generalization explicitly:

"we can expand this vocabulary to label some edges with labels for relations such as is-a, part-of, or others."

This turns the Transformer from a fully connected graph with distance-based edge labels into a graph neural network over a pre-specified sparse graph whose edge types carry semantic meaning. The paper does not explore arbitrary relation types in depth (the experiments focus on NLP hierarchical structure), but the framework is general.

3. Per-instance attention masks provide instance-specific structure. The binary attention masks $M^{g2g}$ , $M^{g2l}$ , $M^{l2g}$ , $M^{l2l}$ can be set differently for each training or inference example. This enables:

Masking attention between different documents concatenated into the same long input (for efficient batching during pre-training).
Masking attention between tokens in different contexts for HotpotQA/WikiHop (preventing information leakage between unrelated documents).
Enforcing within-context ordering for sentences while preserving between-context independence (Figure 5 illustrates this precisely).

This instance-level control is absent in all prior sparse attention methods, which use fixed or learned patterns that apply uniformly to all inputs.

4. CPC teaches global tokens their role during pre-training. The Contrastive Predictive Coding task (Section 3.5 and Appendix B) is specifically designed to train the global tokens. The mechanism: mask some sentences in the long input, encode those masked sentences independently through a second ETC instance $g_2$ , and train the main model $g_1$ so that the global token corresponding to a masked sentence produces a hidden representation that matches $g_2$ 's representation of that sentence (with an NCE loss against random negatives). This forces global tokens to predict the content of the sentences they summarize, effectively teaching them to be information routers. As the paper states:

"CPC plays the role of a masked language model (MLM) task, but at a sentence level of granularity."

No prior sparse attention or hierarchical model includes an explicit pre-training objective for the summary/global tokens — their function must emerge implicitly from task-specific fine-tuning, which is data-inefficient and may not generalize.

5. Backward compatibility with BERT/RoBERTa. The paper emphasizes that ETC can "lift weights" from existing BERT checkpoints (Appendix D). This is possible because (a) ETC's attention mechanism reduces to standard BERT attention when the local radius is large enough to eliminate sparsity, and (b) the separate projection matrices for global and long inputs can be initialized identically from BERT's single set of matrices. This means ETC does not sacrifice the investment in large-scale pre-training — it inherits general language knowledge and only needs to learn the new structural mechanisms (global token usage, relative position encoding with structural labels, CPC behavior) during its own pre-training phase.

Summary of the positioning. ETC is not competing with sparse attention models on the axis of "who achieves the lowest asymptotic complexity" (it achieves $O(n_g(n_g + n_l) + n_l(n_g + 2r + 1))$ , which is linear in $n_l$ when $n_g = O(2r + 1)$ ). It is competing on the axis of representational capacity for structured long inputs. The combination of (1) explicit global summary tokens, (2) structural relative position labels, (3) per-instance masking, and (4) CPC pre-training is what enables ETC to encode input structures that previous architectures — including the very similar Longformer — cannot represent. The empirical results (Tables 2–5) show that this additional capacity translates into state-of-the-art performance, but the conceptual contribution is the demonstration that structure matters for long-input NLP tasks, and that architectural mechanisms for encoding structure produce measurable improvements beyond what pure scaling of attention can achieve.

3. Technical Approach

3.1 Reader Orientation

ETC is a Transformer encoder that takes as input not one sequence but two —a short "global" sequence of auxiliary tokens and a potentially very long "regular" sequence of text tokens— and processes them with a modified attention mechanism that allows the global tokens to attend freely to everything while restricting the regular tokens to a local neighborhood, plus a small set of global intermediaries through which information can flow across the entire input. This solves the dual problem of quadratic attention scaling (by making the long-input self-attention sparse and linear in sequence length) and structure blindness (by using learnable relation labels on attention edges and flexible per-instance masks, the architecture can explicitly encode hierarchical, graph, or cross-document structure that standard Transformers treat as a flat orderless bag of tokens).

3.2 Big-Picture Architecture (Diagram in Words)

The ETC encoder has five major components that work together end-to-end:

Token Embedding Layer — converts input tokens (word pieces) into continuous vectors, shared between the global and long input sequences. When lifting from BERT/RoBERTa, these embedding weights are initialized from the pre-trained checkpoint.
The Global Input Sequence ( $x^g = (x^g_1, \ldots, x^g_{n_g})$ ) — a short sequence of auxiliary tokens (typically a few hundred) that represent summaries of segments (sentences, paragraphs, DOM nodes), plus task-specific tokens (CLS, question tokens, candidate answer tokens). These tokens will have unrestricted attention to everything.
The Long Input Sequence ( $x^l = (x^l_1, \ldots, x^l_{n_l})$ ) — the main text sequence (up to 8,192 tokens in the paper's experiments), containing all the word piece tokens of the input document(s). These tokens are restricted to local self-attention within a fixed radius $r$ plus full attention to/from the global tokens.
Global-Local Attention Layers (stacked $L$ times, where $L = 12$ for base and $L = 24$ for large) — each layer computes four attention pieces: global-to-global (g2g), global-to-long (g2l), long-to-global (l2g), and long-to-long (l2l). The first two are computed jointly with one softmax; the latter two are computed jointly with a second softmax. Each piece uses separate or shared learned projection matrices $W^Q, W^K, W^V$ and can be masked per-instance via binary matrices $M^{g2g}, M^{g2l}, M^{l2g}, M^{l2l}$ . Attention logits are modified by learnable relative position/label vectors $a^K_{ij}$ that encode pairwise relationships.
Pre-training Heads — two objectives applied to the encoder outputs:
- Masked Language Model (MLM) head: a feedforward layer on top of masked long-input token representations, predicting the original token identity (whole word masking).
- Contrastive Predictive Coding (CPC) head: a dual-encoder setup where a second instance of ETC ( $g_2$ , sharing weights with the main model $g_1$ ) encodes individually masked sentences, and the main model's global sentence-summary token is trained to produce a hidden representation close to $g_2$ 's representation of that sentence, using a Noise Contrastive Estimation (NCE) loss with in-batch negatives.

Information flows as follows: First, the raw tokenized input is split into two sequences — word pieces go into the long input, and auxiliary tokens (one per sentence/paragraph/DOM-node, plus CLS and task-specific tokens) go into the global input. Second, structural relationships between tokens (which sentence a token belongs to, which context a sentence belongs to, which candidate answer a mention links to) are encoded as relative position label indices assigned to each pairwise attention edge, and attention masks are set per-instance to block attention where structure dictates no edge should exist (e.g., between unrelated documents concatenated for batching). Third, the two sequences pass through $L$ global-local attention layers, each producing updated representations for both sequences. Fourth, the final-layer representations are fed to task-specific heads (span prediction for QA, classification for WikiHop, n-gram scoring for OpenKP) and optionally to the CPC loss during pre-training.

3.3 Roadmap for the Deep Dive

First, the relative position encoding mechanism (Section 3.1 of the paper), because it is the foundation on which both structured attention and the attention equations themselves are built. I will explain how ETC generalizes Shaw et al.'s (2018) position-based labels to arbitrary pairwise token relations.
Second, the global-local attention mechanism (Section 3.2), including the four attention pieces, the per-instance masking matrices, the shared vs. separate projection matrix design, and the computational complexity analysis showing linear scaling in the long input length.
Third, how these mechanisms combine to handle long inputs (Section 3.3) — the pattern of global segment-summary tokens linked to their constituent tokens via relative position labels.
Fourth, how they combine to handle structured inputs (Section 3.4) — using the attention masks and extended relative label vocabulary to encode document hierarchies, DOM trees, and entity links.
Fifth, the CPC pre-training task (Section 3.5 and Appendix B) — the dual-encoder architecture, the sentence masking procedure, and why this teaches global tokens to be information routers.
Sixth, the weight lifting procedure (Section 3.6 and Appendix D) — how ETC initializes from BERT/RoBERTa checkpoints, which weights are copied and which are randomly initialized, and why this compatibility matters for performance.

3.4 Detailed, Sentence-Based Technical Breakdown

This is a new architecture paper whose core idea is that splitting the input into a small set of unrestricted-attention "global" tokens and a large "long" sequence with local-only self-attention achieves linear complexity in input length while simultaneously enabling explicit encoding of arbitrary input structure through learnable relation labels and per-instance attention masks — and that adding a sentence-level CPC pre-training objective teaches the global tokens their intended role as information routers, yielding state-of-the-art results on long/structured NLP tasks.

Relative Position Encoding: The Foundation for Structured Attention

Standard Transformers use absolute position encodings: a vector (either learned or sinusoidal) is added to each token's embedding based on its index in the sequence. This tells token $i$ "you are at position $i$ " but tells token $j$ nothing directly about token $i$ 's position relative to it except through the dot-product interaction of their respective absolute position vectors — an indirect signal.

Shaw et al. (2018) introduced relative position encodings, which directly modify the attention logit between token $x_i$ and token $x_j$ based on their relative distance. ETC inherits this mechanism but generalizes it beyond sequential distance to express arbitrary pairwise relations. Here is the mechanism at the level of detail needed to understand all subsequent pieces:

Step 1: Define a vocabulary of relation labels. Given a maximum clipping distance $k$ , Shaw et al. define $2k+1$ relative position labels: $l_{-k}, \ldots, l_k$ . The label on the edge from $x_i$ to $x_j$ is determined by $j - i$ (the signed token distance). If $j - i \geq k$ , the label is $l_k$ (all far-right tokens share one label). If $j - i \leq -k$ , the label is $l_{-k}$ (all far-left tokens share one label). Otherwise, the label is $l_{j-i}$ precision up to distance $k$ .

ETC expands this vocabulary: instead of labels representing only sequential distance, they represent structural relationships. For example (Section 3.3 and Figure 3):

One label for "global sentence token to token that belongs to that sentence."
A different label for "global sentence token to token that does NOT belong to that sentence."
A label for "sentence token to context token that contains it."
A label for "candidate answer global token to mention of that candidate in the text."
Labels for "token within same sentence" at various distances, and "token in different sentence."

The vocabulary size depends on how many structural relation types and distance buckets are defined. The paper uses $k = 12$ for the base model and $k = 24$ for the large model as the maximum distance clipping, plus additional labels for structural relations (the exact number is not specified but is increased by the "2x relative vocab" ablation in Table 2).

Step 2: Associate each label with a learnable vector. Each label $l$ in the vocabulary is associated with a learnable key-side vector $a^K_l \in \mathbb{R}^{d_z}$ (where $d_z$ is the per-head dimension, $768/12 = 64$ for base and $1024/16 = 64$ for large). These vectors are randomly initialized and trained. There is one such vector per label per attention head (the paper's implementation does not share $a^K$ across heads, which Appendix A notes is efficient because their relative attention vocabulary is small enough that per-head vectors add negligible memory).

Step 3: Modify the attention logit. For a query token $x_i$ attending to a key token $x_j$ , the standard pre-softmax attention logit (without relative encoding) is:

$e_{ij}^{\text{standard}} = \frac{x_i W^Q (x_j W^K)^T}{\sqrt{d_z}}$

With the relative encoding, this becomes:

$e_{ij} = \frac{x_i W^Q (x_j W^K + a^K_{ij})^T}{\sqrt{d_z}}$

where $a^K_{ij}$ is the learnable vector for the label assigned to the edge $i \rightarrow j$ .

Expanding:

$e_{ij} = \frac{x_i W^Q (x_j W^K)^T + x_i W^Q (a^K_{ij})^T}{\sqrt{d_z}}$

What this computes: The attention logit is the sum of two terms. The first term $x_i W^Q (x_j W^K)^T / \sqrt{d_z}$ is content-based attention — it measures how relevant token $j$ 's content is to token $i$ 's query. The second term $x_i W^Q (a^K_{ij})^T / \sqrt{d_z}$ is position/structure-based attention — it measures how the query vector $x_i W^Q$ aligns with the learned vector for whatever relationship $i$ has to $j$ (be it sequential distance or a structural relation like "same sentence" or "candidate-to-mention"). The softmax then normalises these combined scores across all $j$ that $i$ can attend to.

Why this form: The additive decomposition $W^K x_j + a^K_{ij}$ means the key's content and its relation to the query are combined before the dot product with the query. An alternative would be to multiply $a^K_{ij}$ by the query separately and add logits (as some implementations do). The Shaw et al. additive-in-key-space approach has the property that the relative position vector lives in the same space as the content-based key projection, allowing the model to learn interactions where certain relations amplify or suppress the importance of certain content patterns. Critically for ETC, this same mechanism works unchanged when $a^K_{ij}$ represents a structural relation rather than a sequential distance — the model can learn that "being a mention of the candidate answer" should increase the attention weight regardless of content, or that "being in a different context" should decrease it.

Why expand beyond distance labels: In a standard Transformer, the graph of token interactions is fully connected, and the only edge feature is relative distance (or none, with absolute positions). By introducing structural labels, ETC transforms the Transformer into a graph neural network over a pre-specified graph where edges have typed labels. The model doesn't need to infer from data that "this token belongs to this sentence" — that information is provided directly as an edge label. The paper's hypothesis (validated by the structured-input ablations in Tables 3 and 4) is that this explicit inductive bias is more sample-efficient and generalizes better than expecting the model to learn structural relationships from raw position signals.

Implementation note (Appendix A): Materializing $a^K_{ij}$ for every query-key pair would cost $O(n^2 d_z)$ memory, which defeats the purpose of sparse attention. ETC avoids this by pre-computing $x_i W^Q \cdot a^K_l$ for all query vectors and all unique labels $l$ in the vocabulary, producing a small matrix of size $n \times |\text{vocab}|$ , and then gathering the appropriate scalar for each $(i, j)$ pair based on the pre-assigned label. Because the vocabulary of labels (hundreds) is much smaller than $n$ (thousands), this is a large constant-factor memory saving.

Global-Local Attention: The Core Sparse Mechanism

Global-local attention is the computational engine that makes ETC both sub-quadratic and structure-aware. It splits the standard $n \times n$ self-attention into four pieces, two of which are unrestricted and two of which are restricted, with the global tokens serving as a low-dimensional bottleneck through which long-range information can flow across the entire long input. Here is the complete mechanism, building piece by piece.

Input configuration. ETC receives two physically separate sequences:

Global input: $x^g = (x^g_1, \ldots, x^g_{n_g})$ , where $n_g$ is small (typically 128–512 tokens in the paper's experiments).
Long input: $x^l = (x^l_1, \ldots, x^l_{n_l})$ , where $n_l$ is large (512 to 8,192 tokens in the experiments).

Each token in both sequences is a $d_x$ -dimensional embedding (768 for base, 1024 for large). The sum $n_g + n_l$ is the total number of input representations the model processes per example.

The four attention pieces. The full attention matrix is conceptually an $(n_g + n_l) \times (n_g + n_l)$ grid, partitioned into four rectangular blocks:

	Keys: global (size $n_g$ )	Keys: long (size $n_l$ )
Queries: global (size $n_g$ )	g2g	g2l
Queries: long (size $n_l$ )	l2g	l2l

g2g (global-to-global): Every global query token attends to every global key token. This is a full $n_g \times n_g$ attention matrix. Because $n_g$ is small, this is cheap.
g2l (global-to-long): Every global query token attends to every long key token. This is a full $n_g \times n_l$ attention matrix. This is linear in $n_l$ (since $n_g$ is constant or grows slowly).
l2g (long-to-global): Every long query token attends to every global key token. This is a full $n_l \times n_g$ attention matrix. Also linear in $n_l$ .
l2l (long-to-long): Each long query token attends to long key tokens only within a fixed local radius $r$ in the input sequence. This is an $n_l \times (2r+1)$ sparse attention matrix (reshaped as Figure 2c illustrates).

Why this decomposition matters computationally. Standard Transformer attention costs $O((n_g + n_l)^2)$ operations and memory. ETC's cost is:

$O\left(n_g(n_g + n_l) + n_l(n_g + 2r + 1)\right)$

which simplifies to $O(n_g^2 + n_g n_l + n_l(2r + 1))$ . If we assume $n_g = O(2r + 1)$ (the global input size grows with the local radius, which is plausible since we need enough global tokens to cover the long input at some granularity), this becomes $O(n_g^2 + n_g n_l) = O(n_l)$ — linear in the long input length. The quadratic term $n_g^2$ is negligible because $n_g$ is small.

In practice, the paper uses $r = 84$ for base models with $n_g$ ranging from 128 to 460 (Table 2), so $n_g$ is comparable to $2r+1 = 169$ — roughly in the asymptotic regime where attention is linear. For large models, $r = 169$ and $n_g$ is proportionally larger.

How l2l sparsity works in practice (Figure 2c). The long input sequence of length $n_l$ is conceptually treated as a 1D sequence. Token at position $i$ in the long input can attend to long-input tokens at positions $i - r, i - r + 1, \ldots, i + r$ (clamped to valid indices). This produces a banded matrix of width $2r+1$ . For efficient GPU/TPU implementation (Appendix A), the long input is divided into blocks of length $r + 1$ , and each block of queries attends to three blocks of keys: its own block, the block immediately to the left, and the block immediately to the right. This yields slightly over-generous attention (a query may see keys slightly beyond $r$ positions away), which is then corrected by masking out the excess positions. The reshaping trades a small amount of extra compute for a dramatic memory reduction — the key/value blocks are materialized only in groups of three rather than all $2r+1$ positions per query.

The attention equations, piece by piece. For each of the four pieces, the computation follows the same pattern: compute content-based key and query projections, add the relative position/label vector for each edge, scale, mask, and softmax. I will write out the g2g piece fully and then describe how the other pieces differ.

For the g2g piece, given global input $x^g = (x^g_1, \ldots, x^g_{n_g})$ , each token $x^g_i \in \mathbb{R}^{d_x}$ is projected to a query, key, and value:

Query: $q^g_i = x^g_i W^{Q,g}$ Key: $k^g_j = x^g_j W^{K,g}$ Value: $v^g_j = x^g_j W^{V,g}$

where $W^{Q,g}, W^{K,g}, W^{V,g} \in \mathbb{R}^{d_x \times d_z}$ are learnable weight matrices (per-head; the paper uses multi-head attention, so each head has its own set of projections producing $d_z = d_x / h$ dimensional vectors, where $h$ is the number of attention heads — 12 for base, 16 for large).

The pre-softmax attention logit from global query $i$ to global key $j$ is:

$e^{g2g}_{ij} = \frac{x^g_i W^{Q,g} (x^g_j W^{K,g} + a^{K}_{ij})^T}{\sqrt{d_z}} - (1 - M^{g2g}_{ij})C$

where:

$a^{K}_{ij} \in \mathbb{R}^{d_z}$ is the learnable relative position/structure label vector for the edge from global token $i$ to global token $j$ .
$M^{g2g}_{ij} \in \{0, 1\}$ is a binary mask: 1 means "allow attention," 0 means "block attention."
$C = 10000$ is a large constant that, when the mask is 0, makes $-(1 - 0)C = -10000$ , driving the softmax weight to essentially zero.

The attention weight for global query $i$ attending to global key $j$ is then the softmax over all global keys:

$\alpha^{g2g}_{ij} = \frac{\exp(e^{g2g}_{ij})}{\sum_{\ell=1}^{n_g} \exp(e^{g2g}_{i\ell})}$

And the output for global query $i$ is the weighted sum of global value vectors:

$z^g_i = \sum_{j=1}^{n_g} \alpha^{g2g}_{ij} x^g_j W^{V,g}$

What this computes operationally: For each global token $i$ , this computes a weighted mixture of all global tokens' value representations, where the weights are determined by (a) how content-relevant each other global token $j$ is to $i$ (the $x_i W^Q (x_j W^K)^T$ term), (b) how the relationship type between $i$ and $j$ biases attention (the $x_i W^Q (a^K_{ij})^T$ term), and (c) whether the edge is explicitly masked out (the $M^{g2g}$ term).

Why this form: The inclusion of both content-based and relation-based attention logits means the model can learn attention patterns that are driven by both what tokens say and how they are structurally related. The large constant $C$ for masking follows BERT's convention and ensures masked-out edges receive effectively zero probability after softmax (not just small probability if a normal additive mask were used). The separate $W^{Q,g}, W^{K,g}, W^{V,g}$ matrices (vs. sharing with the long input) allow the model to use different projection spaces for global-vs-global interactions than for global-vs-long interactions, which the paper shows matters empirically (the "shared" ablation in Table 2 reduces NQ long answer F1 from 0.725 to 0.721 — modest but consistent).

The g2l piece is analogous, except the keys and values come from the long input:

$e^{g2l}_{ij} = \frac{x^g_i W^{Q,g} (x^l_j W^{K,l} + a^{K}_{ij})^T}{\sqrt{d_z}} - (1 - M^{g2l}_{ij})C$

Note two differences: (1) the keys use $W^{K,l}$ (the long-input key projection) rather than $W^{K,g}$ , and (2) the relative position labels $a^{K}_{ij}$ now represent the relation between global token $i$ and long token $j$ (e.g., "global sentence token to token in that sentence" vs. "global sentence token to token NOT in that sentence").

The l2g piece is the reverse direction — long queries attend to global keys:

$e^{l2g}_{ij} = \frac{x^l_i W^{Q,l} (x^g_j W^{K,g} + a^{K}_{ij})^T}{\sqrt{d_z}} - (1 - M^{l2g}_{ij})C$

where the query projection uses $W^{Q,l}$ (separate from $W^{Q,g}$ ).

The l2l piece has the local radius restriction. The equation is the same form but $j$ only ranges over long-input indices within $\pm r$ of $i$ :

$e^{l2l}_{ij} = \frac{x^l_i W^{Q,l} (x^l_j W^{K,l} + a^{K}_{ij})^T}{\sqrt{d_z}} - (1 - M^{l2l}_{ij})C$

for $j \in [i - r, i + r]$ . The mask $M^{l2l}_{ij}$ provides additional instance-level control beyond the local radius — for example, blocking attention between tokens in different contexts that happen to be adjacent in the concatenated long input.

Softmax unification. Crucially, the g2g and g2l pieces share a single softmax, and the l2g and l2l pieces share another. This means:

For each global query $i$ , the attention weights across all global keys AND all long keys sum to 1: $\alpha^{g2g}_{ij}, \alpha^{g2l}_{ij} = \text{softmax}\left(\text{concat}(e^{g2g}_{i,:}, e^{g2l}_{i,:})\right)$
For each long query $i$ , the attention weights across all global keys AND the local long keys sum to 1: $\alpha^{l2g}_{ij}, \alpha^{l2l}_{ij} = \text{softmax}\left(\text{concat}(e^{l2g}_{i,:}, e^{l2l}_{i,:})\right)$

What this unification means operationally: A global token decides how much of its attention budget to spend on other global tokens vs. on long tokens. A long token decides how much to spend on global tokens vs. on its local long neighbors. This is not an architectural detail — it means global tokens and local long tokens compete for attention within the same softmax, so the model can learn to route information dynamically: if the global tokens contain the information a long token needs (e.g., a summary of a distant paragraph), the long token can allocate most of its attention to the global tokens and less to its immediate neighbors, effectively "reading" distant information through the global bottleneck.

Why unify via softmax rather than separate softmaxes: If each piece had its own softmax (so a global token's attention to global keys sums to 1 and its attention to long keys separately sums to 1), the model would lose the ability to trade off global vs. long attention. A token could attend fully to both, which defeats the purpose of the global bottleneck as a bandwidth-limited information channel. The unified softmax forces an explicit tradeoff: attention is a scarce resource, and the model must allocate it between direct local context and the global summary channel.

After attention: feed-forward and layer norm. The output of global-local attention is two sequences — one of length $n_g$ (global token representations $z^g_i$ ) and one of length $n_l$ (long token representations $z^l_i$ ). Each goes through an identical post-attention pipeline as in standard Transformers:

Add & Layer Norm (residual connection): $\text{LayerNorm}(x^g_i + z^g_i)$ and $\text{LayerNorm}(x^l_i + z^l_i)$ .
Feed-forward network: A two-layer MLP with hidden size $4d_x$ (3072 for base, 4096 for large) and GELU activation, applied independently to each position.
Add & Layer Norm again: residual connection around the FFN.

The output becomes the input to the next layer. The global and long sequences remain separate throughout the encoder stack — they are never concatenated into a single sequence.

Shared vs. separate projection matrices (the "shared" ablation). The paper experiments with two configurations for the projection matrices $W^Q, W^K, W^V$ :

Separate (default): $W^{Q,g}$ and $W^{Q,l}$ are different matrices; $W^{K,g}$ and $W^{K,l}$ are different; $W^{V,g}$ and $W^{V,l}$ are different. This doubles the number of attention projection parameters compared to a standard Transformer (for the query/key/value weights only — the FFN and output projection are shared). For the base model, this adds ~57M parameters (going from 109M shared to 166M separate, per Table 8).
Shared: $W^{Q,g} = W^{Q,l}$ , $W^{K,g} = W^{K,l}$ , $W^{V,g} = W^{V,l}$ — the same matrices project both global and long tokens. This keeps parameter count close to BERT (109M vs. BERT-base's 110M).

The paper further splits the query projection more finely: in the separate configuration, there is one $W^Q$ for g2g+g2l (queries that are global tokens) and a different one for l2g+l2l (queries that are long tokens). This is noted in Section 3.2:

"for $W^Q$ , we experiment with having one for g2g and g2l, and a separate one for l2g and l2l; or sharing them also"

The empirical finding (Tables 2–4): sharing helps on smaller datasets (WikiHop: 73.7 shared vs. 73.2 separate; OpenKP: 0.409 for both) but hurts on larger datasets (NQ: 0.721/0.514 shared vs. 0.725/0.522 separate; HotpotQA: 0.733/0.866 shared vs. 0.751/0.869 separate). The interpretation is that larger datasets benefit from the extra capacity of separate projections, while smaller datasets overfit with too many parameters.

Per-instance attention masks. The four binary mask matrices $M^{g2g}, M^{g2l}, M^{l2g}, M^{l2l}$ are set per training/inference example, not globally. This is a critical design choice that enables:

Efficient batching during pre-training: Multiple short documents are concatenated into a single long input sequence for GPU/TPU efficiency, but their tokens are masked from attending to each other (both in l2l and via the global tokens). The paper states in Appendix C that this yields "a roughly 3x speedup in pre-training time for 4096-token models."
Enforcing document boundaries in multi-document tasks: In HotpotQA and WikiHop, where the input contains multiple independent contexts (paragraphs or Wikipedia sections), l2l attention is masked across context boundaries — a token from context 1 cannot attend to a token from context 2 directly. They can only exchange information through the global context-summary tokens.
Asymmetric hard g2l masking: The paper reports (Table 2, NQ results) that using the $M^{g2l}$ mask to perform "hard masking" — blocking global tokens from attending to long tokens they are not structurally linked to — improves performance in some datasets. Specifically, for NQ, hard g2l masking improves long answer F1 from 0.717 to 0.725 and short answer F1 from 0.508 to 0.522 (comparing "shared, no hard g2l" to "shared" rows). The mechanism (Figure 3a): each global sentence token can attend only to word piece tokens that belong to its sentence, not to tokens in other sentences. This forces the global token to be a true summary of its specific sentence rather than of the entire input.

How Global-Local Attention Handles Long Inputs

The paper presents a default "recipe" for using ETC on long documents (Section 3.3 and Figure 3a):

Place all word piece tokens (the actual text) in the long input, in their natural order.
Divide the text into segments — sentences are the default segmentation unit, though paragraphs are used for some tasks (NQ uses paragraphs as "long answer candidates").
Allocate one auxiliary token per segment in the global input. So if a document has 50 sentences, the global input has at least 50 segment-summary tokens (plus a CLS token and possibly additional task-specific tokens).
Use relative position labels to link each global segment token to the word piece tokens that belong to that segment. The paper uses one label for "belongs to this segment" and a different label for "does not belong to this segment."
Optionally apply hard g2l masking so that a global segment token can only attend to the word pieces of its own segment (and not to word pieces from other segments). This is the asymmetric masking mentioned in Section 3.3.

Information flow in this configuration. A token at position $i$ in the long input (say, a word deep in paragraph 3) can:

Attend directly to other word piece tokens within $\pm r$ positions (its local neighborhood in the flat sequence). This captures nearby context — the surrounding words, adjacent sentences.
Attend to all global tokens via the l2g piece. These global tokens include the summary token for its own sentence, summary tokens for other sentences, and the CLS token. Through these, it can indirectly access information from any distant part of the document.
The global token for a distant paragraph, which can attend to all word piece tokens in that paragraph (via g2l), serves as a compressed representation of that paragraph's content. A token in the current paragraph can attend to that global token and thereby "read" the distant paragraph's summary.

The local radius $r$ controls the direct context window. The paper uses $r = 84$ for base and $r = 169$ for large. With a local radius of 84, each token directly sees ~169 tokens (84 left + itself + 84 right). For comparison, a standard BERT with 512 input length gives each token 512 tokens of direct context. ETC gives each token ~169 tokens of direct context plus $n_g$ global tokens that can carry information from anywhere else in the (potentially 8,192-token) input.

The fixed-blocks alternative. Instead of using sentence boundaries to define segments, the "fixed blocks" ablation in Table 2 configures the global input with one global token per 97 long-input tokens, ignoring linguistic boundaries:

"fixed blocks (which configures the global input to just have one global token per 97 long input tokens, to keep the same proportion as without fixed-blocks, ignoring sentence boundaries, and not having any other tokens in the global input for pre-training or fine-tuning)"

The finding: fixed blocks slightly help without CPC (0.697/0.508 vs. 0.692/0.497) but underperform sentence-based segments with CPC (0.717/0.524 with sentence segments and CPC vs. 0.697/0.508 with fixed blocks and no CPC). This is a subtle result: linguistic segmentation matters most when the CPC pre-training objective (which predicts sentence content from global tokens) is active, because CPC explicitly trains sentence-summary tokens. Without CPC, fixed blocks are competitive because the global tokens learn their summarization role purely from task-specific fine-tuning signals, which do not require linguistic coherence of the blocks.

Why the paper needs both global tokens AND local attention (not one or the other): If you removed the global tokens and only kept local attention, you would have a purely local model — tokens could only see their immediate neighbors, and long-range dependencies would have to propagate through many layers (like a CNN, where the receptive field grows linearly with depth). Information from a token 1,000 positions away would require many layers to reach the current position, and the signal would be diluted by mixing with intermediate tokens. The global tokens provide a shortcut — a token anywhere in the sequence can attend to a global token that summarizes any other part of the sequence, making long-range information accessible in a single attention step.

If you removed local attention and only kept global tokens with full l2l attention, you would be back to quadratic complexity. The local restriction is what makes the architecture scale.

How Global-Local Attention Encodes Structured Inputs

Section 3.4 of the paper describes ETC's approach to structured inputs with three mechanisms, which I'll explain in concrete operational terms.

Mechanism 1: Expanded relative position label vocabulary. The vocabulary of labels $a^K_l$ is not limited to representing sequential distance. The paper trains the model with additional labels that represent specific structural relationships. Figure 3b illustrates this: different arrow colors and patterns represent different relative position labels assigned to different edge types. For example:

Label A: "token in long input belongs to this global sentence token"
Label B: "global sentence token belongs to this global context token"
Label C: "this long token is a mention of this global candidate answer token"
Label D: "token in same sentence, immediate neighbor"
Label E: "token in same sentence, 2 positions apart"
...
Label D+k: "token in same sentence, k positions apart"
Boundary label: "token in different sentence"

The model learns a different $a^K$ vector for each label, so the attention bias for "this word is in my sentence" can be different (and possibly stronger) than the bias for "this word is 3 positions away." Moreover, the same structural relation type (e.g., "belongs to same sentence") can have different label indices for different sentences, allowing sentence-specific attention biases — though in practice the paper uses the same label type for all instances of the same structural relation and differentiates via the distance component within sentence boundaries.

Mechanism 2: Two-level (or deeper) hierarchy via the global-long split. The global input naturally represents a higher level of abstraction than the long input. This creates a two-level hierarchy: global tokens → long tokens. But ETC can represent deeper hierarchies by having global tokens that summarize sets of other global tokens. The paper mentions this explicitly:

"However, we can also have tokens summarizing sets of summary tokens (constructing a 3-level hierarchy, or beyond)."

For the datasets in this paper, the hierarchy is typically context → sentence → token (three levels), encoded as:

Context-level tokens in the global input (one per paragraph/document/section).
Sentence-level tokens in the global input (one per sentence).
Word piece tokens in the long input.

Relative position labels encode the parent-child relationships: a sentence token is linked to its containing context token with one label type, and to its constituent word pieces with another label type.

Mechanism 3: Attention masks for structure-absent edges. If two tokens should not have an edge between them at all (not just a weaker edge), this is encoded via the binary masks $M$ . Figure 3b shows this for the HotpotQA/WikiHop setting: the input contains multiple contexts (unordered), each containing multiple sentences (ordered). The masks enforce:

No cross-context l2l attention: A word piece in context 1 cannot attend to a word piece in context 2. They are adjacent in the concatenated long input sequence, but their $M^{l2l}_{ij}$ mask entry is 0.
No cross-context g2g attention for sentence tokens: A sentence-summary token in context 1 does not attend to a sentence-summary token in context 2 (they are independent). But context-level tokens can attend to each other if the task requires cross-context reasoning.
Within-context, between-sentence attention is allowed (but may be weighted by distance labels).
Within-sentence, token-token attention follows the local radius pattern.

Concrete example: WikiHop encoding (Appendix F, Figure 5). The input consists of:

A query (question about an entity).
A set of candidate answers.
A set of contexts (Wikipedia article portions).

The paper encodes this as follows:

All word piece tokens (query + contexts) go into the long input.
The global input contains:
- One token per context (representing the whole context).
- One token per sentence (within each context).
- One token per candidate answer.
Relative position labels encode:
- Which sentence tokens belong to which context tokens.
- Which word pieces belong to which sentence.
- Which candidate answer global tokens link to which word piece mentions in the long input (via string matching for mentions).
Masks prevent attention between word pieces in different contexts (l2l mask), and between sentence tokens in different contexts (g2g mask). Context-level tokens can attend to each other (g2g unmasked) to allow cross-context reasoning.

This is substantially more structure than a flat Transformer would receive. The flat Transformer would see all context tokens concatenated in some arbitrary order with sequential position encodings, giving the model a misleading signal that context 1 is "before" context 2 in some meaningful sense. ETC explicitly removes this false sequential signal and replaces it with typed structural relations.

Why encoding structure this way matters (the flat structure ablation). Table 3 reports results with a "flat structure" ablation for HotpotQA and WikiHop, defined as:

"(1) we do not break long input attention by context boundaries, (2) we limit relative position labels between global and long tokens to representing only sentence-level relationships (this removes any special attention in WikiHop between candidate answers and their mentions)"

In HotpotQA, removing structure (flat) from the full model drops joint F1/supporting F1 from 0.751/0.869 to 0.748/0.870 — a negligible change, suggesting HotpotQA does not heavily benefit from explicit context-boundary masking beyond what the long input's flat ordering provides.

In WikiHop, the flat structure hurts more: accuracy drops from 73.2 (baseline, with hard g2l) to 70.7 (flat). More tellingly, removing hard g2l masking (but keeping structure) raises accuracy to 75.9 — the best base model result. This suggests WikiHop benefits from the candidate-answer-to-mention linking (the special relative position label) and from context-boundary masking in l2l, but the hard g2l masking is counterproductive for this task — perhaps because the model needs global tokens to look beyond their own sentence for disambiguation clues, and hard g2l masking prevents this.

Design choice: why relative position labels rather than separate structural embeddings? An alternative approach would be to add a separate "structure embedding" to each token's input representation (e.g., a learned vector for "this token is part of sentence 3, context 2"). ETC instead encodes structure through the attention mechanism — the relation type modifies how much attention token $i$ pays to token $j$ , not what $i$ 's initial representation is. The paper's implicit argument is that structure is fundamentally about interaction constraints (who should talk to whom), not about identity features (what kind of token this is). Encoding structure in attention rather than embeddings means (a) the structure can be arbitrarily instance-specific without needing a separate embedding table for every possible position/segment combination, (b) the same structural relation type can receive a consistent learned bias across all instances, and (c) the structure is disentangled from content — a word piece's embedding doesn't change based on which sentence it happens to land in, but the attention pattern does.

The CPC Pre-training Task: Teaching Global Tokens to Summarize

The Contrastive Predictive Coding (CPC) task (Section 3.5, Appendix B) is specifically designed to pre-train the global tokens. Without it, global tokens have no pre-training signal — they only learn their function during task-specific fine-tuning. CPC provides a self-supervised objective that teaches global sentence-summary tokens to encode information about their corresponding sentences.

Why standard NSP/MLM is insufficient for global tokens. BERT's pre-training objectives are (1) Masked Language Modeling (predict masked tokens from context) and (2) Next Sentence Prediction (binary classification: does sentence B follow sentence A?). MLM operates on the long input tokens and does not involve global tokens at all (unless global tokens are randomly masked, which the paper does not do — only long-input word pieces are masked for MLM). NSP is a coarse sentence-level task that uses the CLS token but does not require sentence-specific summary tokens to develop useful representations of individual sentences. ETC's global tokens — one per sentence — need a per-sentence learning signal, and CPC provides exactly that.

The CPC architecture (dual encoder). CPC in ETC is implemented as a dual-encoder problem with two instances of the same ETC model:

Main encoder $g_1$ : The model being trained. It receives the full input with some sentences masked in the long input (but their corresponding global sentence-summary tokens remain present in the global input).
Auxiliary encoder $g_2$ : A second instance of the same ETC model with shared weights (not a separate model — $g_2$ uses the same parameters as $g_1$ ). It receives each masked sentence individually — the long input contains only the word pieces of that one sentence, and the global input contains a single global token (the sentence summary).

The CPC procedure, step by step:

For an input document, randomly select 10% of sentences to be "CPC-masked" (the paper states: "we randomly select 10% of sentences to be masked for the CPC task" — Appendix C).
In $g_1$ 's input, the word piece tokens corresponding to those masked sentences are completely removed (or replaced with [MASK] tokens; the paper says "we mask all the tokens corresponding to a subset of sentences"). The global sentence-summary tokens for those masked sentences remain present in the global input.
$g_1$ processes the full input (with masked sentences). For each masked sentence $s$ , the hidden representation $h^g_{1,s}$ of its corresponding global sentence-summary token (from the final layer of $g_1$ ) is extracted.
For each masked sentence $s$ , $g_2$ encodes that sentence in isolation: its long input contains only the tokens of sentence $s$ , and its global input contains a single global token. The hidden representation $h^g_{2,s}$ of that global token (from the final layer of $g_2$ ) is extracted.
The training objective is to make $h^g_{1,s}$ (the summary token's prediction of what sentence $s$ contains, based only on surrounding context) as similar as possible to $h^g_{2,s}$ (the encoding of sentence $s$ when the model can actually read its tokens).

The loss function: Noise Contrastive Estimation (NCE). The paper uses the same NCE loss as the original CPC work (Oord et al., 2018). In operational terms:

For each masked sentence $s$ in an example, the positive pair is $(h^g_{1,s}, h^g_{2,s})$ — the predicted representation and the actual representation.
The negative pairs are $(h^g_{1,s}, h^g_{2,s'})$ for other sentences $s'$ in the same batch (in-batch negatives). These are incorrect pairings: the summary token for sentence $s$ should not match the encoding of a different sentence $s'$ .
The model is trained via a softmax-based contrastive loss to maximize the similarity of the positive pair relative to all negative pairs.

What this loss computes: For each masked sentence, the model computes a compatibility score (typically a dot product) between the predicted representation $h^g_{1,s}$ and each candidate representation $h^g_{2,s'}$ (including the true one). It then applies a softmax over all candidates and maximizes the log-probability of the correct candidate. In equations, this is:

$\mathcal{L}_{\text{CPC}} = -\sum_{s \in \text{masked}} \log \frac{\exp(\text{sim}(h^g_{1,s}, h^g_{2,s}) / \tau)}{\sum_{s' \in \text{batch}} \exp(\text{sim}(h^g_{1,s}, h^g_{2,s'}) / \tau)}$

where $\text{sim}$ is a similarity function (dot product or cosine similarity — the paper uses the standard CPC formulation with a learned linear projection) and $\tau$ is a temperature parameter.

Why this form: The NCE loss with in-batch negatives creates a contrastive learning problem: the global token for a masked sentence must learn to produce a representation that is close to the true sentence encoding and far from encodings of other (random) sentences. This forces the global token to predict the content of the masked sentence from surrounding context, not just its position or whether it's present. Crucially, in-batch negatives are free (no additional computation) and scale with batch size — larger batches provide more negatives and a stronger training signal.

The combined loss. When both MLM and CPC are used, the total pre-training loss is a weighted sum:

$\mathcal{L} = 0.8 \cdot \mathcal{L}_{\text{MLM}} + 0.2 \cdot \mathcal{L}_{\text{CPC}}$

The paper states the 0.8/0.2 weighting in Appendix C. MLM gets the larger weight because it operates on individual tokens (many per example) while CPC operates on sentences (fewer per example) — the weighting roughly balances their contribution to the total loss magnitude.

Why CPC matters for structured inputs. The paper's hypothesis (Section 5) is that CPC teaches global tokens to be effective information routers. Without CPC, a global sentence-summary token has no pre-training signal at all — its representation before fine-tuning is essentially random (if not initialized from BERT, as BERT has no equivalent token). During fine-tuning, the global token must learn both (a) to summarize its sentence's content and (b) to route that summary to other tokens that need it. This is a lot to learn from task-specific labeled data alone. CPC pre-trains part (a): the global token already knows how to encode sentence content by the time fine-tuning begins, leaving only the routing behavior to be learned from task data.

The empirical support: removing CPC from NQ (Table 2) drops long answer F1 from 0.725 to 0.717 and short answer F1 from 0.522 to 0.514. Removing CPC from HotpotQA (Table 3) drops joint F1 from 0.751 to 0.747 and supporting fact F1 from 0.869 to 0.866. These are consistent, modest gains — CPC is helpful but not transformative in the way the architectural mechanisms are. The effect may be stronger for tasks where sentence-level content prediction is critical, which would explain why the paper keeps CPC in the default configuration despite the gains being incremental.

How CPC interacts with the fixed-blocks ablation. With fixed blocks (one global token per 97 long tokens, ignoring sentence boundaries), CPC cannot be meaningfully applied — there is no sentence to mask and encode. The fixed-blocks configuration is "no CPC" by necessity. This is why the fixed-blocks row in Table 2 is paired with "no CPC" — it's listed as "fixed blocks, shared, no CPC, no hard g2l." The comparison between fixed-blocks (no CPC) and sentence-based (with CPC) confounds the segmentation unit and the CPC task, which makes it difficult to isolate the effect of each.

Lifting Weights from BERT/RoBERTa

ETC is designed to be backward-compatible with BERT/RoBERTa so that the massive investment in pre-training these models (hundreds of GPU-days) can be reused rather than starting from scratch. Section 3.6 and Appendix D describe the procedure.

Why compatibility is possible. The global-local attention mechanism reduces to standard BERT attention under two conditions:

The long input length $n_l$ is small enough (≤ 512) that the local radius $r$ covers the entire sequence, eliminating sparsity. In this regime, l2l attention is effectively full attention.
The global input is empty or the projection matrices are shared between global and long inputs.

When these conditions hold (even approximately), ETC's operations are mathematically identical to BERT's — the same query-key-value projections, the same attention scaling, the same softmax (over the unified global+long set), and the same feed-forward layers. This means BERT's trained weights can be copied directly into the corresponding parameter slots of ETC.

What gets copied (Appendix D): For each Transformer layer, the following weights are lifted from BERT/RoBERTa into ETC:

Feed-forward layer weights (two dense matrices, intermediate size $4d_x$ ).
Attention projection matrices $W^Q, W^K, W^V$ . Since ETC may have separate matrices for global and long inputs, both sets are initialized to the same BERT/RoBERTa values.
Attention output projection (the matrix that combines multi-head outputs).
Layer normalization parameters (scale and bias, two per LayerNorm).

Additionally, the token embedding matrix is lifted from BERT/RoBERTa — including the full word piece vocabulary.

What is NOT copied and must be randomly initialized:

Relative position/label vectors $a^K_l$ for all labels. BERT has no equivalent (it uses absolute position encodings), so these are initialized randomly.
CPC-related parameters (the projection layers for the NCE loss, if any). BERT has no CPC task.
Absolute position embeddings from BERT are discarded entirely — ETC does not use them.
Next Sentence Prediction (NSP) weights are discarded — ETC uses CPC instead.

Constraints for lifting to work: The BERT/RoBERTa checkpoint must match ETC's configuration:

Number of layers (12 for base, 24 for large).
Hidden size (768 for base, 1024 for large).
Number of attention heads (12 for base, 16 for large).
Feed-forward intermediate size (3072 for base, 4096 for large).

The paper lifts from RoBERTa checkpoints reported by Rothe et al. (2020).

After lifting, pre-training is still required. Lifting provides a warm start for the shared components (attention projections, FFN, embeddings), but the model still needs to learn:

How to use the global tokens (which BERT never had).
How to interpret relative position/structural labels (which BERT never had).
How to operate with sparse local attention (BERT always used full attention).
The CPC task behavior (BERT used NSP instead).

The paper's experiments compare "ETC-large" (pre-trained from scratch) vs. "ETC-large, lifting from RoBERTa" (Table 2, NQ): lifting improves long answer F1 from 0.761 to 0.782 and short answer F1 from 0.565 to 0.585 — a substantial gain of +2.1/+2.0 F1 points. This validates that inheriting general language knowledge from RoBERTa transfers to ETC's modified attention architecture.

Why lifting matters beyond performance. One practical barrier to adopting new Transformer architectures is the enormous computational cost of pre-training from scratch. ETC base takes ~11.4 hours on 256 TPU v3 cores; ETC large takes ~63.7 hours on 512 TPU v3 cores (Table 6). Pre-training BERT/RoBERTa took orders of magnitude more compute. By enabling weight lifting, ETC allows practitioners to leverage existing pre-trained models and only pay the incremental cost of adapting to the new attention mechanism, which is substantially cheaper than full pre-training.

Design choice: why not also lift from Longformer or other sparse models? The paper only describes lifting from BERT/RoBERTa because these are the most widely available pre-trained checkpoints and because ETC's architecture was explicitly designed to include BERT as a special case. Lifting from Longformer would be more complex because Longformer uses a different attention pattern and absolute position encodings, requiring non-trivial weight transformations. By constraining the architecture to be BERT-compatible, the paper trades off some design freedom for practical deployability.

Summary of Key Design Choices and Their Justifications

Separate global and long input sequences rather than marking some tokens as "global" within a single sequence (as Longformer does): enables separate projection matrices, different processing for the two token types, and the CPC dual-encoder setup where the auxiliary encoder $g_2$ has a different input structure (single sentence) than the main encoder $g_1$ (full document with masked sentences).
Unified softmax for g2g+g2l and l2g+l2l rather than separate softmaxes per piece: forces an explicit tradeoff between attending to global summary information and attending to local context, which is the mechanism by which the global bottleneck controls information flow.
Relative position labels as learnable key-side vectors added to keys rather than as separate embeddings added to token inputs: encodes structure as interaction constraints (who attends to whom and with what bias) rather than as identity features (what type of token this is), enabling instance-specific structure and disentangling structure from content.
Per-instance binary attention masks rather than a fixed sparse pattern: allows efficient batching of multiple documents (masking cross-document attention), enforces document/context boundaries in multi-document tasks, and supports asymmetric hard masking where global tokens see only their own segment's tokens.
Monte Carlo rollout supervision for PRM training rather than human labels: avoids distribution shift between labeled data and the target model's outputs (the paper found the PRM800k human-labeled dataset "largely ineffective" for PaLM 2 models — Section 5.1) and provides soft targets with richer signal than binary correctness labels.
CPC with in-batch negatives rather than NSP or no sentence-level pre-training: provides a per-sentence learning signal for global summary tokens that NSP (which only uses the CLS token) does not provide, and in-batch negatives are computationally free while scaling with batch size.
Backward compatibility with BERT/RoBERTa rather than a from-scratch architecture: reduces the practical barrier to adoption by allowing reuse of existing pre-trained checkpoints, and the paper shows empirically that lifting from RoBERTa provides significant performance gains over training ETC from scratch.

4. Key Insights and Innovations

Innovation 1: Structure Is Not Just Position — It Deserves First-Class Architectural Treatment

Before ETC, the dominant paradigm for encoding relationships between tokens in a Transformer was position: absolute position embeddings (BERT, GPT), relative position encodings (Shaw et al., 2018; Transformer-XL), or sinusoidal position signals. The field treated "where a token is in the sequence" as the universal relationship type, with all other structure — sentence boundaries, document boundaries, DOM hierarchy, entity mentions — either ignored or expected to be learned implicitly from content-based attention patterns.

ETC makes a conceptual move that shifts this framing: structural relationships should be encoded through the same mechanism as positional relationships, but with an expanded vocabulary of relation types. The relative position label $a^K_{ij}$ is generalized from "what is the signed distance $j - i$ " to "what is the type of relationship between token $i$ and token $j$ " — which can be sequential distance, parent-child in a hierarchy, candidate-to-mention linking, or "no relationship at all" (masked). This is not an engineering convenience — it is a representational claim: that a Transformer is a graph neural network over a pre-specified sparse graph, and that what edge labels you give it fundamentally determines what structures it can efficiently represent.

The distinction from prior work matters here. Hierarchical models like HIBERT (Zhang et al., 2019) encode structure by architectural design — a two-stage encoder where sentence summaries feed into a document-level Transformer. The structure is baked into the forward pass, not expressed as learnable edge features. Sparse attention models like Longformer (Beltagy et al., 2020) use a single input sequence with some tokens marked as "global" — the structure is a binary property of tokens (global vs. local), not a typed relation between pairs of tokens. The Star Transformer (Guo et al., 2019) has a single star token that everything attends to — structure is a star topology, not an arbitrary graph.

ETC's innovation is the separation of structure from architecture: the same ETC forward pass can represent a flat document, a two-level sentence-token hierarchy, a three-level context-sentence-token hierarchy (as in WikiHop/Figure 5), a DOM tree (as in OpenKP), or an entity-mention graph — by changing the labels assigned to attention edges and the binary attention masks, without modifying the model code. This is a fundamental conceptual advance, not an incremental refinement. It means the question "how should we encode structure" becomes a data/modeling decision (what edges and labels to define) rather than an architecture decision (what new model variant to build).

The empirical validation comes from the structured-input ablations. In WikiHop (Table 3), removing structure — flattening context boundaries and removing candidate-to-mention labels — drops accuracy from 73.2 to 70.7 for the base configuration, and the best model (no hard g2l masking, but keeping structure) reaches 75.9. In OpenKP (Table 4), adding visual features (DOM structural signals encoded as additional relative labels and embeddings) provides the single largest improvement: from 0.402 without visual features to 0.409 with them. These are not enormous absolute gains, but they consistently demonstrate that explicit structural encoding matters beyond what content-based attention can recover on its own.

What makes this contribution distinctive is not the mechanism (relative position labels existed before ETC) but the reframing of what a Transformer's attention graph represents. Standard Transformers treat the attention graph as fully connected with distance-based edge weights. ETC treats it as a sparse, typed graph where the model designer specifies which edges exist and what type they are. This reframing is portable: it applies to any domain where tokens have known relational structure (molecular graphs, knowledge graphs, code ASTs, dialogue acts), not just the NLP hierarchies explored in this paper.

Innovation 2: The Global-Local Split Is a Bottleneck Architecture, Not Just a Sparse Attention Pattern

Many sparse attention mechanisms reduce computation by limiting which token pairs can attend — but they do so by applying a pattern (fixed windows, learned spans, hash-based nearest neighbors) uniformly across all tokens. The innovation in ETC's global-local attention is the introduction of asymmetric attention capacity: a small set of tokens (the global input) has unrestricted attention to everything, while the majority of tokens (the long input) are severely restricted to local windows plus access to the global set. This asymmetry is what makes the architecture a bottleneck rather than simply sparse.

A bottleneck architecture — where all long-range information must pass through a low-dimensional intermediary — imposes a specific inductive bias: the model is forced to compress distant information into the global tokens' representations before it can influence local processing. This is fundamentally different from models where long-range attention is sparse but direct (e.g., Sparse Transformer's strided patterns, where a token can attend to distant tokens directly if they happen to be in the same row/column of the fixed pattern). In ETC, a token at position $i$ in the long input cannot directly attend to a token at position $j$ if $|j - i| > r$ . The only way information flows from $j$ to $i$ is through the global tokens: $j$ is seen by some global token (via g2l), and $i$ reads that global token (via l2g).

This bottleneck design has conceptual consequences that purely sparse direct-attention models do not share:

First, it makes the global tokens' representational capacity a scarce resource. If there are $n_g$ global tokens, each of dimension $d_x$ , the total capacity of the bottleneck is $n_g \times d_x$ floating-point numbers per layer. All long-range information in the input — spanning potentially 8,192 tokens — must be compressed through this channel. This means the model cannot simply "learn to attend to everything directly but sparsely." It must learn what to summarize and what to discard, which is a qualitatively different learning problem than sparse direct attention (where the model can keep many long-range edges, each carrying specific token-level information).

Second, it makes the pre-training of global tokens critical. If global tokens are not taught to be good summarizers, the bottleneck becomes an information blockade rather than an information channel. This is why the CPC pre-training task (discussed in Innovation 3) is not an add-on but a logically necessary component of the bottleneck architecture — without it, the global tokens are random at the start of fine-tuning, and the model must simultaneously learn to summarize and to route, which is harder than learning each separately.

Third, it recovers standard Transformers as a special case (when $n_l = 0$ or when $r$ is large enough to eliminate sparsity), which makes the architecture backward-compatible with BERT/RoBERTa weight initialization. This is an architectural property that purely sparse models (Reformer, Routing Transformer) cannot provide — their attention mechanisms don't reduce to standard attention under any parameter setting, so they cannot inherit pre-trained weights.

The comparison to Longformer is particularly instructive for understanding what's innovative here. Longformer (Beltagy et al., 2020) uses the same conceptual pattern — some tokens marked as "global" attend to everything, others attend locally — but implemented within a single input sequence. The paper notes that Longformer "has a single input sequence with some tokens marked as global." The difference might seem cosmetic, but it has architectural consequences: ETC's separate global and long inputs enable different projection matrices for the two token types ( $W^{Q,g}$ vs. $W^{Q,l}$ , $W^{K,g}$ vs. $W^{K,l}$ , $W^{V,g}$ vs. $W^{V,l}$ ), which allows the model to compute fundamentally different representations of global-summary tokens and local-content tokens. Longformer, with a single sequence, must use the same projections for both — it can only differentiate global vs. local through the attention mask, not through the representation space. The ablation in Table 2 shows this matters: using shared projection matrices (ETC-shared, closer to Longformer's design) drops NQ long answer F1 from 0.725 to 0.721, and HotpotQA joint F1 from 0.751 to 0.733. The effect is consistent across datasets.

This contribution is fundamental — it introduces a new design axis for Transformer efficiency (bottleneck capacity and asymmetry) that is orthogonal to the standard axes (sparsity pattern, recurrence, hierarchy). It is not the first bottleneck architecture in deep learning (autoencoders, U-Nets, and the Star Transformer precede it), but it is the first to frame Transformer attention explicitly as a bottleneck architecture with separate representation spaces for the bottleneck tokens and the data tokens, with a pre-training objective designed to teach the bottleneck its compression role.

Innovation 3: Global Tokens Need Their Own Pre-training Signal — CPC Provides It

A non-obvious consequence of the global-local split is that the global tokens have no natural pre-training signal in standard self-supervised objectives. In BERT's Masked Language Modeling (MLM), tokens in the input are randomly masked, and the model predicts their identity from surrounding context. If you apply MLM to ETC, what gets masked? The long input tokens — the actual text. The global tokens (sentence summaries) are never target tokens for MLM, because they have no "identity" to predict — they are abstract, task-defined auxiliary tokens, not word pieces with a vocabulary entry. Next Sentence Prediction (NSP), BERT's other objective, uses only the CLS token, not the per-sentence summary tokens.

This means that without a specialized pre-training objective, global tokens enter fine-tuning with randomly initialized representations. They must learn their entire function — summarizing sentences, routing information between distant parts of the document — from task-specific labeled data alone. For tasks with limited fine-tuning data (WikiHop has only 43,738 training instances; HotpotQA has 90,447), this is a tall order.

The paper's innovation here is not CPC itself (Oord et al., 2018) but the recognition that global tokens need a dedicated pre-training objective matched to their architectural role, and the adaptation of CPC to provide it. The key insight: CPC operates at the level of segments (sentences in the paper's default configuration), not tokens. It asks the global sentence-summary token to predict the hidden representation of its corresponding sentence (when encoded in isolation). This forces the global token to encode the content of the sentence it summarizes — not just its position or whether it exists.

Why CPC rather than some other sentence-level objective? The paper might have used a next-sentence or sentence-order prediction task (predict whether sentence B follows sentence A from the global tokens, analogous to NSP but operating on per-sentence tokens). The advantage of CPC's contrastive formulation (predict the correct sentence representation among in-batch negatives) is that it produces a discriminative signal that distinguishes each sentence from all other sentences in the batch. A simple prediction task (e.g., regression to a target sentence embedding) would produce a weaker gradient — the model could learn to produce similar representations for all sentences without being penalized for confusing them, as long as they are all somewhat close to their targets. CPC's NCE loss explicitly pushes apart the representations of different sentences, which is what you want if global tokens are to serve as information routers — a token attending to a global sentence token should get information specific to that sentence, not a generic "some sentence exists here" signal.

The empirical evidence for this innovation is clear but also reveals its limits. Removing CPC from NQ (Table 2) drops long answer F1 from 0.725 to 0.717 and short answer F1 from 0.522 to 0.514. In HotpotQA (Table 3), removing CPC drops joint F1 from 0.751 to 0.747 and supporting fact F1 from 0.869 to 0.866. These are consistent improvements (CPC helps), but they are small — roughly 0.5–1.0 F1 points. Why? One interpretation is that fine-tuning on task-specific data partially compensates for the lack of CPC pre-training when there is enough labeled data — the global tokens eventually learn their summarization role from task signal, just less efficiently. A second interpretation is that CPC's main benefit is not in representational quality but in training stability and speed — models with CPC might converge faster or to better local optima, which would manifest as improved final performance even if the asymptotic representational capacity is similar.

What makes this contribution conceptually significant despite modest empirical gains is that it establishes a design principle for bottleneck architectures: the bottleneck tokens need an objective that teaches them to compress and reconstruct the information they are meant to route. This principle generalizes beyond CPC and beyond Transformers — any architecture where a small set of units mediates information flow between a larger set of units (hierarchical models, memory-augmented networks, graph pooling architectures) faces the same problem: what pre-training signal teaches the bottleneck its job? The paper's answer — a contrastive prediction task matching the bottleneck's representation of masked content against the content's isolated encoding — is one specific solution, but the more important contribution is identifying the problem as a first-class design consideration.

This is an incremental advance (CPC existed; applying it to sentence-level Transformer pre-training is a novel application but not a new technique) with fundamental implications (it reveals a gap in how we pre-train architectures with non-text tokens). The paper would be weaker without it — it clarifies why prior global-token architectures (Longformer, Star Transformer) may have underperformed relative to their potential, and it provides a recipe for fixing the gap.

Innovation 4: Long Inputs and Structured Inputs Are Two Manifestations of the Same Architectural Problem

The paper presents itself as addressing "two key challenges" — scaling input length and encoding structured inputs — but the deeper intellectual contribution is the unification of these two challenges under a single framework. Before ETC, long-input scaling and structured-input encoding were largely separate research threads. Long-input work (sparse attention, recurrence, compression) focused on computational efficiency — how to reduce $O(n^2)$ attention cost while preserving model quality. Structured-input work (hierarchical models, graph neural networks over text) focused on representational capacity — how to inject domain-specific relational knowledge into the model. These communities had different methods, different benchmarks, and different evaluation criteria.

ETC's architecture demonstrates that both challenges reduce to the same problem: defining a sparse attention graph with typed edges. For long inputs, the sparsity pattern is distance-based (each token attends to tokens within a local radius) and the typed edges are distance labels from the relative position vocabulary. For structured inputs, the sparsity pattern is defined by domain relationships (document boundaries, sentence membership, entity links) and the typed edges are structural relation labels from an expanded vocabulary. The same architecture, same attention equations, same pre-training procedure handles both — the only difference is which edges exist (the masks) and what labels they carry (the relative position vocabulary).

This unification is not just an observation — it has practical consequences that the paper demonstrates:

The two mechanisms compound: In the structured-input experiments (HotpotQA, WikiHop, OpenKP), the model simultaneously benefits from long-input scaling (fitting the full document into the long input rather than truncating at 512 tokens) AND from structural encoding (context-boundary masking, candidate-to-mention linking, DOM hierarchy). These are not independent improvements — the structural encoding tells the model how to use the additional context provided by long-input scaling. Without structure, a 4,096-token flat sequence of multiple concatenated documents is just a very long bag of words. With structure, the model knows which tokens belong to which document, which sentences form a coherent unit, and which mentions link to the candidate answers — it can reason across documents without confusing them.
Structure emerges as a solution to the information-routing problem in long inputs. The global-local bottleneck can route information from any part of the long input to any other part, but without structure, the routing is undirected — a token seeking information about a specific distant paragraph must "ask" all global tokens and hope one of them has the relevant summary. With structural encoding, the token knows exactly which global tokens correspond to which sentences/contexts, so it can route its attention precisely. The structural labels on the l2g edges tell the token "this global token summarizes the paragraph you care about" vs. "this global token summarizes an unrelated paragraph."

This unification challenges the assumption — implicit in prior work — that long-input and structured-input architectures are separate design problems requiring separate solutions. The paper's evidence that the same architecture excels at both (state-of-the-art on four diverse benchmarks: NQ for long documents, HotpotQA for multi-document reasoning, WikiHop for structured multi-context QA, OpenKP for DOM-structured keyphrase extraction) validates that the unification is not just theoretically elegant but practically effective.

The significance of this contribution extends beyond NLP. Any domain where data points have both sequential extent (a molecular structure is a long sequence of tokens; a code file is a long sequence of tokens; a knowledge graph traversal is a long sequence of tokens) and relational structure (atoms are bonded; functions call each other; entities have typed edges) can be addressed by the same architectural approach — define the sparse attention graph and edge types that reflect the domain structure, and let a single unified Transformer architecture handle both the sequential and relational aspects.

This is a fundamental conceptual contribution — it doesn't introduce a new mechanism, but it reveals that what looked like two separate problems are actually two parameterizations of the same underlying framework. The paper doesn't state this unification as explicitly as I'm characterizing it here (the abstract and introduction list them as separate challenges), but the architecture and experiments demonstrate it. This is the kind of contribution that changes how subsequent researchers frame their work: instead of "I'm building a long-input Transformer" or "I'm building a graph-aware Transformer," the question becomes "what attention graph and edge types best capture my domain structure?"

5. Experimental Analysis

Evaluation Methodology

Dataset. The paper evaluates on four NLP benchmarks that require long and/or structured inputs: Natural Questions (NQ) (Kwiatkowski et al., 2019) — 307,373 training / 7,830 dev instances, task is to identify short and long answers in full Wikipedia articles given a question, with input lengths ranging from a median of 4,004 to a maximum of 156,551 word piece tokens (Table 1); HotpotQA (Yang et al., 2018) — 90,447 training / 7,405 dev instances in the distractor setting, where 10 paragraphs are provided (2 relevant, 8 distractors), and the task is to answer the question and identify supporting facts at sentence granularity; WikiHop (Welbl et al., 2018) — 43,738 training / 5,129 dev instances, where the input consists of a query, candidate answers, and multiple Wikipedia contexts, and the model must select the correct candidate answer; OpenKP (Xiong et al., 2019) — 133,724 training / 6,610 dev instances, a keyphrase extraction dataset where the input is a web page with DOM structure and visual features, and the task is to identify up to 3 keyphrases, evaluated using F1@3 (F1 score computed over the top 3 predicted keyphrases).
Base model(s). The paper uses two configurations of ETC: ETC-base (12 layers, 768 hidden size, 12 attention heads, local radius $r = 84$ , relative position maximum distance $k = 12$ , ~166M parameters in the separate-projection configuration, ~109M when sharing projection matrices) and ETC-large (24 layers, 1024 hidden size, 16 heads, $r = 169$ , $k = 24$ , ~539M parameters, ~558M when lifting from RoBERTa due to the larger RoBERTa vocabulary). All models use BERT's 30k English uncased word piece vocabulary by default, except when lifting from RoBERTa which uses the RoBERTa vocabulary. The models are initialized either from scratch (pre-trained on Wikipedia and Books corpora filtered to documents with at least 7 sentences) or by lifting weights from RoBERTa checkpoints (Rothe et al., 2020). For the large configuration with RoBERTa lifting, the learning rate is reduced to $2 \times 10^{-3}$ during pre-training (Appendix C). The base configuration is trained for 33 epochs (63,000 iterations with batch size 512 sequences of 4,096 tokens) and the large for 66 epochs (batch size 1,024). Pre-training uses a combined loss weighting of 0.8 for MLM and 0.2 for CPC.
Metrics. Performance is measured as follows: NQ uses F1 score for both long answer span prediction and short answer span prediction against human-generated answers, with answer type prediction (null, yes, no, short, long) also evaluated; HotpotQA uses joint F1 (combining answer F1 and supporting fact F1 at a sentence level) as the primary metric; WikiHop uses accuracy (exact match of predicted candidate answer against ground truth); OpenKP uses F1@3, where precision and recall are computed over the top 3 predicted keyphrases. All metrics are standard for their respective benchmarks and computed via the official evaluation scripts or grading functions (NQ uses the grading function from Alberti et al., 2019, as noted in Section 4.1).
Baselines. The paper compares against several established models. For NQ: BERT-base (Devlin et al., 2018) and BERT-large with 512-token input, and RikiNet (Liu et al., 2020), which is one of the top models on the NQ leaderboard at the time and uses a RoBERTa-large backbone. For HotpotQA and WikiHop: Longformer-base (~149M parameters, Beltagy et al., 2020) and Longformer-large (~435M parameters), which the paper identifies as the most similar prior architecture due to Longformer's comparable global-local attention mechanism, though Longformer does not encode hierarchical structure, use CPC pre-training, or support relative position encodings for structural relations. For OpenKP: RoBERTa-JointKPE (Sun et al., 2020), the #1 leaderboard entry at the time, which uses a joint keyphrase chunking and salience ranking approach on top of RoBERTa.
Generation budget / compute accounting. The paper does not use a "generation budget" framework (this is not a test-time compute scaling paper) — instead, the primary resource axis is input length (how many tokens the model can process in one pass) and model capacity (base vs. large, shared vs. separate projection matrices). Computational efficiency is reported in terms of wall-clock time per training step (Figure 4, comparing BERT-base vs. ETC-base on a single NVIDIA Tesla V100 GPU as input length increases) and total pre-training time (Table 6: ETC-base takes ~11.3 hours on 256 TPU v3 cores; ETC-large takes ~63.7 hours on 512 TPU v3 cores). Fine-tuning times are reported in Table 7 per dataset and use 32 TPU v3 cores. Memory scaling experiments (Appendix E) are reported as maximum input lengths achievable on a single TPU v3 core with gradient checkpointing and without optimizer moment storage: 22,656 long tokens for base and 8,448 for large.
Cross-validation / statistical protocol. For fine-tuning, the paper performs a hyperparameter sweep over learning rates and number of epochs for each model configuration (ranges specified per dataset in Appendix C), selecting the best configuration based on dev set performance. For HotpotQA, 3 different random seeds are tried for the best hyperparameter configuration, with the best seed selected based on dev set joint F1. For other datasets, a single random seed per hyperparameter configuration is used. The paper does not report confidence intervals, standard deviations across seeds, or statistical significance tests for the performance differences between configurations.

Main Quantitative Results

The paper organizes results per dataset, with NQ serving as the primary ablation platform and the other three datasets demonstrating generalization to different structural input types. I present results following this organization.

Table 2 reports the full ablation study on NQ dev set, and the results establish several scaling relationships.

Input length scaling produces substantial gains beyond 512 tokens. Starting from ETC-base with 512-token long input (0.692 long answer F1 / 0.497 short answer F1), increasing to 4,096 tokens yields 0.717/0.524 in the comparable configuration (shared projection matrices, CPC, no hard g2l masking), a gain of +2.5 long answer F1 and +2.7 short answer F1. Further increasing to 8,192 tokens (requiring the 166M-parameter configuration with 460 global tokens) pushes performance to 0.740/0.542, an additional gain of +2.3/+1.8 F1 over the 4,096 configuration. The paper notes that the 512-token ETC configuration performs comparably to BERT-base on the same task (0.645/0.478 for ETC vs. 0.634/0.475 for BERT-base), despite ETC suffering from a 84-token local radius disadvantage (vs. BERT's full 512-token attention), because ETC's dynamic whole word masking compensates. However, once input length increases, ETC pulls away: the 8,192-token configuration achieves substantially higher scores than any 512-token model can achieve, since BERT-base and BERT-large are architecturally capped at 512 tokens and cannot ingest the full articles.

Lifting from RoBERTa provides the largest single improvement. Comparing ETC-large pre-trained from scratch (0.761/0.565) to ETC-large initialized from RoBERTa (0.782/0.585) shows a gain of +2.1 long answer F1 and +2.0 short answer F1. This is the single largest jump in Table 2, exceeding the benefit of doubling pre-training data (0.746/0.558, which is +0.021/+0.036 over the default 166M-parameter 4,096-token configuration that reaches 0.725/0.522) and exceeding the benefit of moving from base to large (0.725/0.522 → 0.761/0.565, a gain of +0.036/+0.043). The paper does not ablate whether the RoBERTa benefit comes from the better pre-training data, the longer pre-training, or the larger vocabulary — all three factors change when switching from ETC's default BERT-based pre-training to RoBERTa lifting.

CPC and separate projection matrices matter most on larger datasets. Removing CPC from the 4,096-token ETC-base configuration drops performance from 0.725/0.522 to 0.717/0.514 (long answer: −0.8, short answer: −0.8). Sharing projection matrices (reducing from 166M to 109M parameters) drops from 0.725/0.522 to 0.721/0.514 (long answer: −0.4, short answer: −0.8). While the individual effects are modest, they compound: the "shared, no CPC, no hard g2l" configuration (closest to what Longformer would achieve without structural encoding) reaches only 0.692/0.497, vs. the full configuration's 0.725/0.522 — a gap of 3.3 long answer F1 and 2.5 short answer F1. For comparison, the gap between this stripped-down ETC and BERT-large (0.647/0.527) is small for short answer and actually favors BERT-large for short answer (0.497 vs. 0.527), underscoring that ETC's improvements come from the combination of techniques, not from any single one.

Hard g2l masking helps NQ specifically. Adding hard g2l masking (global sentence tokens can only attend to word pieces in their own sentence, not to other sentences) increases long answer F1 from 0.717 to 0.725 in the shared-parameters configuration, and short answer F1 from 0.508 to 0.514. The mechanism here is that hard masking forces each global sentence token to be a faithful summary of its specific sentence rather than of the entire input, which is particularly relevant for NQ where the task is to identify a specific long answer paragraph among many candidates.

Fixed blocks (sentence-blind segmentation) is competitive without CPC but falls behind with CPC. The fixed-blocks configuration (one global token per 97 long-input tokens, ignoring sentence boundaries) combined with shared parameters and no CPC achieves 0.697/0.508 — slightly better than the sentence-based equivalent without CPC (0.692/0.497). However, once CPC is added (which requires sentence-based segmentation to mask complete sentences), the sentence-based configuration jumps to 0.717/0.524, and the fixed-blocks configuration cannot benefit because CPC is inapplicable. This suggests that CPC provides its gains specifically by training sentence-aware global tokens, and that without this pre-training signal, linguistically meaningful segmentation provides no advantage over arbitrary fixed blocks.

ETC-large with RoBERTa initialization reaches 0.782/0.585, which the paper reports as the best dev scores in the literature for long answer (beating RikiNet's 0.753/0.593 for long answer, though RikiNet still leads on short answer: 0.593 vs. ETC's 0.585). On the official leaderboard (Table 5), ETC achieves 0.7778 long answer F1 (1st place) and 0.5786 short answer F1 (18th place), with the discrepancy between dev and test likely reflecting the leaderboard's ensemble submissions (ETC is a single model).

HotpotQA: Multi-Document Reasoning with Structured Attention

Table 3 reports results on HotpotQA dev set. The headline numbers: ETC-base (166M) achieves 0.751 answer F1 / 0.869 supporting fact F1, and ETC-large with RoBERTa lifting (558M) achieves 0.813/0.894. Compared to Longformer-base (0.743/0.844) and Longformer-large (0.788/0.861), ETC outperforms at both scales.

The baseline comparison is at comparable parameter counts. ETC-base at 166M parameters is roughly comparable to Longformer-base at 149M (the paper notes Longformer parameter counts were provided via personal communication). ETC-large (558M) exceeds Longformer-large (435M) by ~123M parameters — a non-trivial difference that confounds the architecture comparison. However, the ETC-base vs. Longformer-base comparison (166M vs. 149M) is close enough that the +0.8 answer F1 gap (+0.751 vs. 0.743) and +2.5 supporting fact F1 gap (0.869 vs. 0.844) are likely not purely attributable to the 17M parameter difference. The paper attributes the performance difference to "the different pre-training strategies and the different handling of structure in ETC and Longformer."

Structure ablation reveals task-specific sensitivity. Removing CPC and hard g2l masking jointly drops performance from 0.751/0.869 to 0.722/0.857 — a substantial −2.9 answer F1 and −1.2 supporting fact F1. Individually: removing CPC drops to 0.747/0.866 (−0.4/−0.3); removing hard g2l masking drops to 0.743/0.864 (−0.8/−0.5). The CPC and hard g2l effects compound non-additively, suggesting they interact — the CPC-trained global tokens are more useful when they are also constrained by hard g2l masking to be sentence-specific.

Flat structure (removing context boundaries and candidate-mention labels) does not hurt HotpotQA, with the flat-structure configuration achieving 0.748/0.870 vs. the baseline 0.751/0.869 — essentially identical performance. This is a non-obvious finding: despite HotpotQA having explicit multi-document structure (10 independent paragraphs, 2 containing useful information), removing cross-context attention boundaries and reducing relative position labels to sentence-level relationships only does not degrade performance. The paper does not explain this finding, but a plausible interpretation is that HotpotQA's distractors and relevant paragraphs are drawn from similar distributions, and the model can learn to distinguish them from content-based attention patterns without explicit structural boundaries, unlike WikiHop where contexts come from different Wikipedia articles with potentially very different topics.

Sharing projection matrices hurts HotpotQA more than NQ, dropping from 0.751/0.869 (166M parameters, separate) to 0.733/0.866 (109M parameters, shared) — a loss of −1.8 answer F1 vs. NQ's −0.4 long answer F1. This suggests that HotpotQA's multi-document reasoning benefits more from having separate representation spaces for global summary tokens (contexts, sentences, questions) vs. long content tokens than single-document NQ does.

Large model with RoBERTa lifting achieves 0.813/0.894, substantially above Longformer-large (0.788/0.861). On the official leaderboard (Table 5), ETC achieves 0.7362 overall (3rd place) and 0.8909 supporting fact F1 (1st place). The gap between dev and test overall scores reflects the leaderboard competition, where ensemble models occupy the top positions.

Table 3 also reports WikiHop dev set results. The headline: ETC-base reaches 73.2% accuracy in the default configuration, with the best base configuration (no hard g2l masking, keeping structure) reaching 75.9%. ETC-large with RoBERTa lifting reaches 79.8%. Longformer-base reaches 75.0% and Longformer-large reaches 77.6%.

WikiHop shows qualitatively different ablation patterns from HotpotQA, demonstrating that structure sensitivity is task-dependent. In HotpotQA, flat structure did not hurt; in WikiHop, removing structure drops accuracy from 73.2 (default) to 70.7 (flat) — a 2.5-point drop. Even more strikingly, removing hard g2l masking improves performance in WikiHop, with the "no hard g2l" configuration reaching 75.9% — the best base model result and substantially above the default's 73.2%. This is the opposite of NQ and HotpotQA, where hard g2l masking helped or was neutral. The paper's interpretation (Section 4.2): "WikiHop shows a slightly different picture, as it seems that hard g2l masking and especially flat structure hurt performance in this dataset."

Why would hard g2l masking hurt WikiHop specifically? The WikiHop task requires reasoning across multiple contexts to determine a property of an entity that cannot be found in a single article. A global sentence token constrained to attend only to its own sentence's tokens cannot look at tokens in other sentences or contexts to disambiguate which candidate answer is correct. Hard g2l masking prevents global tokens from integrating cross-sentence evidence, which is precisely what multi-hop reasoning requires. The model does better when global tokens have unrestricted access to all long-input tokens (no hard g2l mask), allowing them to collect evidence from across the entire input.

Sharing projection matrices helps WikiHop, unlike in NQ and HotpotQA. The shared configuration reaches 73.7% vs. the separate configuration's 73.2% — a small but consistent improvement. The paper attributes this to WikiHop being the smallest dataset in the study (43,738 training instances, compared to 90,447 for HotpotQA and 307,373 for NQ), making the added capacity of separate projections counterproductive due to overfitting: "This is our smallest dataset, and maybe the added capacity of the model without sharing parameters leads it to overfit."

CPC's effect is not isolated in Table 3 for WikiHop, as there is no "no CPC" ablation reported for this dataset. The paper only reports "flat structure, no CPC, no hard g2l" (70.0%) and "flat structure" (70.7%) — the difference of +0.7 provides some evidence that CPC helps even with flat structure, but the confounding with hard g2l masking makes the CPC-specific contribution unclear. The full "no CPC" ablation (with structure and hard g2l masking) is reported as 73.0%, compared to the baseline 73.2% — a negligible 0.2-point difference, suggesting CPC is less important for WikiHop than for HotpotQA or NQ.

Candidate-to-mention linking matters. The flat structure ablation for WikiHop (defined in Section 4.2 as "removing special attention between candidate answers and their mentions") contributes to the 73.2 → 70.7 drop. This is the only dataset where explicit entity-mention linking via relative position labels is used, and the ablation confirms it is helpful — connecting candidate answer global tokens to their string-matched mentions in the long input provides a useful structural signal that reduces the search space for the model.

Large model with RoBERTa lifting achieves 79.8%, beating Longformer-large (77.6%) by 2.2 points and setting a new state of the art on the official WikiHop leaderboard (Table 5: 82.25% test accuracy, 1st place). The dev-to-test gap is notable (79.8% → 82.25%), possibly due to the leaderboard submission being selected as the checkpoint with highest dev accuracy rather than the average across seeds.

OpenKP: Web Page Structure and Visual Features

Table 4 reports OpenKP dev set F1@3 results. The baseline RoBERTa-JointKPE achieves 0.398. ETC-base in the minimal configuration (512 input, fixed blocks, no CPC, no hard g2l, no visual features) already reaches 0.399 — matching the state of the art. Scaling to 4,096 input and adding structural + visual features pushes performance to 0.409 for the default ETC-base configuration, and ETC-large with RoBERTa lifting and max loss reaches 0.423.

Input length scaling alone provides minimal gains on OpenKP. Moving from 512 to 4,096 tokens with fixed blocks and no CPC/hard g2l/visual features improves F1@3 from 0.399 to 0.400 — essentially flat. This is a striking contrast to NQ, where input length scaling provided the largest gains (+2.5 long answer F1 from 512 → 4096). The interpretation: OpenKP keyphrases are typically short and identifiable from local context, so seeing more of the document (which is a web page with many DOM elements) does not help unless the structural relationships between DOM elements are also provided. The long input is long, but without structure, the extra tokens are just noise.

Visual features provide the largest single improvement. Adding visual features (font sizes, bold/heading/block formatting, and other dense visual features encoded as embeddings added to both global and long input tokens) to the ETC-base 4,096-token configuration improves F1@3 from 0.402 to 0.409 (+0.007). This is the single largest jump in Table 4, exceeding the benefit of moving to a large model (0.409 → 0.419, +0.010) or using the max loss trick (0.409 → 0.416, +0.007). Visual features are described in Appendix C: font sizes are embedded based on 24 bucket ranges; Boolean features (block, heading, bolded) are cross-embedded; floating point features are clipped to reasonable ranges and rescaled to [−1, 1]; all visual embeddings are added to both the relevant long and global input tokens.

Sentence-based vs. DOM-node-based segmentation. Unlike the other datasets where the global input segments are sentences, OpenKP uses VDOM nodes as the higher-level units — one global token per VDOM node. The paper states this in Appendix C: "One global token per VDOM node was added to the global input (notice this is like the pre-training setup, except instead of sentences we have VDOM nodes as the higher-level units)." This means the pre-trained CPC objective (which masks sentences and predicts their content from global tokens) operates on a different segmentation unit than fine-tuning — pre-training teaches sentence-level summarization, but fine-tuning uses DOM-node-level summarization. Despite this mismatch, CPC still helps: removing CPC from the full configuration (with hard g2l and visual features) drops from the default 0.409 to 0.402 (inferred by comparing "no CPC, no hard g2l, no visual features" at 0.400 to "no hard g2l, no visual features" at 0.400, though the exact CPC-specific ablation is confounded by hard g2l and visual features being present/absent). The "shared" configuration matches the default at 0.409, consistent with WikiHop's finding that projection matrix sharing helps on smaller datasets.

Max loss (using the maximum logit across all occurrences of a keyphrase) vs. first occurrence improves F1@3 from 0.409 to 0.416 for ETC-base and from 0.419 to 0.423 for ETC-large with RoBERTa lifting. The default configuration labels only the first occurrence of each keyphrase as the target; max loss considers all occurrences and takes the maximum logit, which is more robust when a keyphrase appears multiple times and the first occurrence is not the most salient.

ETC-large with RoBERTa lifting and max loss achieves 0.423, beating RoBERTa-JointKPE (0.398) by 2.5 F1@3 points. On the official leaderboard (Table 5), ETC achieves 0.4205 F1@3 (1st place), slightly below the dev set best, suggesting some dev overfitting or leaderboard variance.

Efficiency and Computational Scaling

Figure 4 compares wall-clock time per training step for BERT-base vs. ETC-base on a single NVIDIA Tesla V100 GPU as input length increases. The key finding: ETC is initially slower than BERT for input lengths below ~1,500 tokens (due to the overhead of separate global input processing and reshaping for local attention), but becomes faster beyond ~1,500 tokens, and continues to scale while BERT runs out of memory (the BERT line terminates earlier). This is the paper's primary evidence that the linear complexity claim translates to practical speedups.

Table 6 reports pre-training times: ETC-base (shared parameters) takes ~11.2 hours on 256 TPU v3 cores; ETC-base (separate parameters) takes ~11.8 hours; ETC-large takes ~63.7 hours on 512 TPU v3 cores. These are for 63,000 pre-training iterations (base) and with batch size 1,024 (large), corresponding to 33 and 66 epochs respectively.

Table 7 reports fine-tuning times on 32 TPU v3 cores: NQ (5 epochs, 32 TPU v3 cores) takes ~10.8 hours; HotpotQA (9 epochs) takes ~3.0 hours; WikiHop (15 epochs) takes ~5.9 hours; OpenKP (3 epochs) takes ~2.1 hours. These times are for the ETC-base baseline model.

Memory scaling (Appendix E): with gradient checkpointing and without optimizer moment storage, ETC-base can process up to 22,656 long-input tokens on a single TPU v3 core (with global input fixed at 512 tokens), and ETC-large can process up to 8,448 long-input tokens. The paper does not report whether these extended input lengths translate to improved task performance.

Ablation Studies and Robustness Checks

Projection matrix sharing (shared vs. separate $W^Q, W^K, W^V$ for global and long inputs): Separate projections consistently help on larger datasets (NQ: 0.725/0.522 vs. 0.721/0.514 shared; HotpotQA: 0.751/0.869 vs. 0.733/0.866 shared) and are neutral or slightly harmful on smaller datasets (WikiHop: 73.2 separate vs. 73.7 shared; OpenKP: 0.409 for both). The paper attributes this to overfitting: the added parameters (~57M extra) are beneficial when there is sufficient training data to use them effectively, but harmful when data is limited. This is a practically important finding — practitioners should choose shared vs. separate projections based on dataset size, not as a universal configuration.

CPC pre-training task: Removing CPC consistently reduces performance across all datasets where it's ablated: NQ drops from 0.725/0.522 to 0.717/0.514 (−0.8/−0.8); HotpotQA drops from 0.751/0.869 to 0.747/0.866 (−0.4/−0.3); the effect in WikiHop is smaller (+0.2 from CPC, comparing 73.0 no CPC vs. 73.2 with CPC). The paper's hypothesis that CPC teaches global tokens to be sentence-level information routers is supported by the consistent direction, but the magnitude is modest (roughly 0.5–1.0 F1/accuracy points). The paper does not ablate CPC against alternative sentence-level pre-training objectives (e.g., NSP adapted for per-sentence tokens, or a simpler reconstruction loss), so whether CPC's contrastive formulation specifically matters vs. the general idea of pre-training global tokens is unclear.

Hard g2l masking: The effect is strongly task-dependent: helps NQ (+0.8 long answer F1 from 0.717 to 0.725), helps HotpotQA (+0.8 answer F1 from 0.743 to 0.751), hurts WikiHop (−2.7 accuracy from 75.9 without hard g2l to 73.2 with). This is the most task-sensitive ablation in the paper and demonstrates that the optimal structural encoding is not universal — it depends on whether the task requires global tokens to integrate information across segments (WikiHop: cross-sentence reasoning needed, so hard g2l masking blocks necessary signal) or to be faithful summaries of their own segment (NQ: long answer identification benefits from paragraph-specific global representations; HotpotQA: supporting fact identification at sentence granularity benefits from sentence-specific summaries).

Fixed blocks vs. sentence-based segmentation: For NQ without CPC, fixed blocks (one global token per 97 long tokens) performs slightly better than sentence-based segmentation (0.697/0.508 vs. 0.692/0.497). With CPC (which requires sentence-based masking), sentence-based segmentation pulls ahead (0.717/0.524). This suggests that the benefit of linguistically meaningful segments comes primarily through CPC pre-training — without it, arbitrary fixed-size blocks work equally well or better, possibly because they provide a more uniform coverage of the input.

Local radius and relative position vocabulary size: Doubling the local radius (presumably from 84 to 168 for base) improves NQ from 0.725/0.522 to 0.737/0.530 (+1.2/+0.8). Doubling the relative position vocabulary size improves from 0.725/0.522 to 0.733/0.532 (+0.8/+1.0). These are moderate gains suggesting that the default settings are not at saturation — larger local radii and richer position vocabularies continue to help — but the improvements are smaller than those from input length scaling or weight lifting.

Doubling pre-training data: Doubling the amount of pre-training (presumably from 33 to 66 epochs for base) improves NQ from 0.725/0.522 to 0.746/0.558 (+2.1/+3.6). This is a substantial gain, suggesting that ETC benefits from longer pre-training in the same way standard Transformers do. The paper does not ablate whether the improvement comes from seeing more data or from additional training iterations on the same data.

Flat structure (removing context boundaries and special relation labels): In HotpotQA, flat structure does not hurt (0.748/0.870 vs. 0.751/0.869). In WikiHop, flat structure hurts substantially (70.7 vs. 73.2). This is the paper's key evidence for the structure-sensitivity claim: the same structural encoding mechanism produces opposite effects depending on the task's requirements.

Visual features (OpenKP only): Adding visual features (font sizes, bold/heading/block formatting) provides the largest single improvement for OpenKP (0.402 → 0.409, +0.7 F1@3). There is no ablation of individual visual feature types (e.g., removing font size features but keeping boolean formatting features), so the relative importance of different visual signals is unknown.

Max loss vs. first occurrence (OpenKP only): Using the maximum logit across all occurrences of a keyphrase (rather than just the first occurrence) improves F1@3 from 0.409 to 0.416. This is a simple post-processing trick that is independent of the architecture.

Weight lifting vs. training from scratch: In NQ, ETC-large from scratch achieves 0.761/0.565; lifting from RoBERTa achieves 0.782/0.585 (+2.1/+2.0). In HotpotQA, ETC-large from scratch achieves 0.798/0.890; lifting from RoBERTa achieves 0.813/0.894 (+1.5/+0.4). In WikiHop, the corresponding improvement is 77.0 → 79.8 (+2.8). In OpenKP, the improvement is 0.419 → 0.423 (+0.4). The RoBERTa initialization benefit is consistent across all four datasets and both model scales (base and large), and the paper shows it for both ETC-specific and BERT-compatible components — when lifting, BERT's weights are copied to the equivalent ETC layers, while new components (relative position vectors, CPC-related parameters) are randomly initialized and trained during ETC pre-training. This demonstrates that the general linguistic knowledge in RoBERTa transfers through the architectural modifications (global-local attention, relative position encoding) without being destroyed.

Batch size for pre-training: Not directly ablated, but the paper's pre-training configuration uses much larger batches than BERT (512 sequences of 4,096 tokens vs. BERT's 256 sequences of 512 tokens) and fewer iterations (63,000 vs. BERT's 1,000,000), while matching the total number of tokens processed. The LAMB optimizer is used with learning rate $\sqrt{8} \times 10^{-3}$ to handle the large batch sizes. The paper does not compare Adam vs. LAMB or ablate the batch size, so whether the 3× reduction in iteration count affects model quality is unknown.

Critical Assessment

The experimental results in this paper demonstrate that ETC achieves state-of-the-art performance on four diverse NLP benchmarks and that its architectural components (global-local attention, relative position encodings for structure, CPC pre-training, weight lifting from RoBERTa) each contribute positively in aggregate. However, a close reading reveals several limitations in the experimental design that temper the strength of the conclusions.

The paper demonstrates performance improvements but does not cleanly isolate the mechanisms responsible. The largest performance gains come from input length scaling beyond 512 tokens and from weight lifting from RoBERTa — neither of which is a novel contribution. The key question is whether ETC's novel mechanisms (structural relative position labels, CPC pre-training, the explicit global-long split with separate projections) provide gains beyond what a simpler baseline could achieve with the same input length and pre-training budget. The paper does not include several crucial baselines that would answer this:

A RoBERTa model with sliding window attention or chunked processing that can also ingest 4,096-token inputs, to isolate whether ETC's specific attention pattern beats simpler long-input strategies given the same pre-training initialization.
A Longformer model pre-trained with the same CPC objective (or a comparable sentence-level pre-training task), to test whether CPC benefits global tokens in architectures beyond ETC.
A BERT/RoBERTa model fine-tuned on the ETC pre-training data and then evaluated with a comparable budget, to separate the effect of ETC's architecture from the effect of additional pre-training on in-domain data (the Books+Wikipedia corpora filtered to longer documents).

Without these baselines, the paper is primarily demonstrating that (a) more input tokens help, (b) RoBERTa initialization helps, and (c) ETC's specific design choices improve over an ETC configuration stripped of those choices. This is strong evidence that the components matter within ETC, but weaker evidence that ETC as a whole is superior to alternative approaches to the same problems.

The comparison to Longformer is confounded by multiple differences. ETC and Longformer differ in at least five ways: (1) separate vs. integrated global input sequences, (2) relative vs. absolute position encodings, (3) CPC pre-training vs. no global-token pre-training, (4) flexible per-instance masks and structural labels vs. a fixed global-local pattern, and (5) different pre-training data and procedures. With so many confounds, attributing ETC's ~1–3 point advantage over Longformer to any specific design choice is impossible. The paper acknowledges some of these differences (the pre-training strategy differences are mentioned in Section 4.2) but does not attempt controlled experiments where only one variable at a time differs.

The dataset-specific ablation patterns are rich but under-explained. The paper observes that hard g2l masking helps NQ, helps HotpotQA, but hurts WikiHop — and attributes this to WikiHop requiring cross-sentence reasoning. This is a plausible post-hoc explanation, but the paper does not validate it with experiments that directly test the mechanism (e.g., measuring cross-sentence information flow with and without hard g2l masking, or analyzing attention patterns to confirm that global tokens indeed integrate less cross-sentence evidence when hard-masked). Similarly, the finding that sharing projection matrices hurts on large datasets but helps on small ones is attributed to overfitting, but no overfitting analysis (e.g., train-dev performance gap as a function of parameter count) is presented. These are missed opportunities to strengthen the paper's mechanistic claims.

The CPC pre-training gains are modest and its unique contribution is unclear. CPC provides consistent but small improvements (roughly 0.5–1.0 F1/accuracy points across datasets). The paper's claim that CPC "plays the role of a masked language model but at a sentence level" implies that it is important for teaching global tokens their role. But the empirical gains are small enough that an alternative explanation — CPC simply provides an auxiliary task that regularizes training or increases the effective batch size through the dual-encoder setup — cannot be ruled out. The paper does not compare CPC against a simpler sentence-level objective (e.g., predicting whether a sentence is original or replaced, predicting sentence order, or reconstructing a bag-of-words representation of the sentence from the global token), which would clarify whether CPC's specific contrastive formulation matters or whether any sentence-level pre-training signal for global tokens is sufficient.

The test sets are small and the paper does not report uncertainty estimates. NQ's dev set has 7,830 instances (a reasonable size), but the other datasets are smaller: HotpotQA 7,405, WikiHop 5,129, OpenKP 6,610. The paper does not report confidence intervals, standard deviations across seeds (except for HotpotQA where 3 seeds were run for the best configuration), or statistical significance tests. Given that some reported differences are small (e.g., 0.2–0.4 F1 points between configurations), it is unclear whether these differences are statistically reliable. The leaderboard submission (Table 5) is a single model per dataset, which is standard practice but reduces the paper's ability to claim robust state-of-the-art if the difference from the next-best model is small.

The pre-training data filtering introduces a distribution shift whose effect is not quantified. BERT is pre-trained on all Wikipedia and Books documents; ETC filters out documents with fewer than 7 sentences. The paper does not report what fraction of the original BERT corpus is removed, whether this filtering biases the pre-training distribution (e.g., toward longer, more formally structured documents), or whether the improvements over BERT baselines are partly attributable to this domain shift rather than the architectural changes. Since ETC fine-tuned on tasks with long documents (NQ articles, HotpotQA paragraphs, WikiHop contexts), a pre-training distribution skewed toward longer documents might provide an unfair advantage independent of the architecture.

The OpenKP results may be driven by visual features, not by structural encoding through attention. The largest improvement in OpenKP comes from adding visual features (0.402 → 0.409). These features are added as embeddings to the token representations — they are content features, not structural attention edge labels. This means the OpenKP improvements are not clean evidence for ETC's structural encoding capability; they could be achieved by any architecture that can ingest visual features as additional token-level embeddings. The paper does not ablate whether adding visual features to a standard BERT with truncated input would achieve similar gains, which would test whether ETC's structure handling is specifically responsible for the OpenKP performance.

The memory and speed scaling claims are demonstrated but constrained. Figure 4 shows ETC becomes faster than BERT beyond ~1,500 tokens on a single V100 GPU, but this comparison assumes BERT uses quadratic attention (which is why it runs out of memory). A BERT with a comparable sparse attention pattern (e.g., a simple sliding window without global tokens) would also have linear scaling and might be faster than ETC due to lower overhead (no separate global input processing, no relative position encoding gather operations). The paper does not compare ETC's wall time against a BERT modified with sliding window attention only, which would isolate the cost of ETC's additional mechanisms. Similarly, the memory scaling experiments (22,656 tokens for base) are run with gradient checkpointing and without optimizer moment storage — a configuration that is not used in the paper's actual training, making the practical relevance unclear.

The ablation configurations are not fully crossed, making interaction effects hard to estimate. The paper reports results for various combinations of ablations (shared, no CPC, no hard g2l, flat structure, fixed blocks) but does not report all 2⁴ or 2⁵ combinations. For example, NQ Table 2 reports "shared, no CPC, no hard g2l" (0.692/0.497) and "shared, no hard g2l" (0.717/0.524) — from these, we can estimate the CPC effect at +2.5/+2.7 for shared-parameter models, compared to the separate-parameter CPC effect of +0.8/+0.8 (0.717/0.514 → 0.725/0.522), suggesting CPC interacts with the projection matrix configuration. But without all combinations, the interaction effects cannot be reliably estimated, and the paper's attribution of gains to individual components may misattribute variance.

The paper claims to handle "structured inputs" but only experiments on NLP hierarchical structure (documents, sentences, DOM trees). The architecture is capable of encoding arbitrary graph structure (the paper mentions "chemical molecule graphs" and "social community graphs" as potential applications in Section 3.4), but no non-text-based structured input experiments are reported. The claim about structure encoding is therefore validated only for a narrow notion of "structure" — document and web page hierarchies — and its generality to other structured domains is untested. The paper would benefit from even a single experiment on a non-NLP structured task (e.g., graph property prediction, code AST understanding) to support the claimed generality.

The official leaderboard results (Table 5) show a notable gap between NQ long answer (1st place) and NQ short answer (18th place). The paper does not discuss this discrepancy, but it is revealing: ETC excels at locating the right paragraph (long answer) but lags behind specialized systems at pinpointing the exact answer span (short answer). This suggests that the global-local bottleneck is particularly effective at coarse-grained localization (the global summary tokens can represent paragraphs well) but less effective at fine-grained span detection, perhaps because the local attention radius of 84 (for base) or 169 (for large) limits direct token-to-token interaction at the granularity needed for precise span boundary identification. The paper does not explore whether increasing the local radius or using a different long-input token representation would close this gap.

Key experiments that would have strengthened the paper but were not run:

A Longformer with CPC pre-training and structural masks: to isolate whether ETC's architectural separation of global/long inputs provides benefits beyond Longformer's integrated approach when the pre-training and structural encoding are matched.
A RoBERTa-large with chunked processing and cross-chunk attention: to test whether a simpler approach to long inputs (process the document in overlapping chunks, allow chunks to attend to each other's CLS tokens) can match ETC's performance with the same pre-training initialization.
Scaling input length continuously on a single task to identify the point of diminishing returns: the paper shows gains from 512 → 4,096 → 8,192 on NQ but does not test intermediate lengths (1,024, 2,048) or longer lengths beyond 8,192, so the shape of the scaling curve is unknown.
An experiment that varies only the structural encoding while keeping the total number of tokens and attention FLOPs constant: to isolate the value of structure from the value of input length, which would require comparing models with the same long input length but different edge label vocabularies and mask configurations on a synthetic task where the answer requires cross-sentence or cross-document reasoning.
Statistical significance tests or bootstrap confidence intervals for the headline results, particularly given the small dev sets and modest performance differences between configurations.

In summary, the experiments convincingly show that ETC works — it achieves state-of-the-art results on four benchmarks, and the ablation studies demonstrate that removing any of its key components (CPC, separate projections, structural masks, visual features, longer input) reduces performance. The experiments are less convincing in establishing why each component helps or in demonstrating that ETC is superior to simpler alternative approaches rather than simply superior to ETC-minus-some-components. The paper's central architectural claim — that explicitly separating global and long tokens with typed relative position labels enables structured long-input encoding that sparse-attention or hierarchical models cannot replicate — is supported in the sense that ETC outperforms existing models with a similar design philosophy (Longformer), but the comparison is confounded by multiple simultaneous differences, and the experiments that would cleanly isolate the value of structured attention from the value of longer input or better initialization are absent. This is not to diminish the paper's achievements — the state-of-the-art results are genuine, and the architectural ideas are well-motivated — but rather to clarify the gap between what the experiments demonstrate and what the paper's framing implies.

6. Limitations and Trade-offs

6.1 Difficulty Estimation Cost Is Not Accounted For in Compute Efficiency Claims

The assumption or constraint. The compute-optimal scaling framework requires estimating each prompt's difficulty before allocating the test-time compute budget. The paper's method for this is to generate 2048 samples per question, compute either the ground-truth pass@1 (oracle) or the PRM's average final-answer score (predicted), and bin questions into five quintiles. The paper acknowledges this cost explicitly but defers it:

"estimating difficulty in this way still incurs additional computation cost during inference... our experiments do not account for this cost largely for simplicity" (Section 3.2)

The consequence. The headline $4\times$ efficiency gain — matching best-of-N performance with $4\times$ fewer generations — is computed after difficulty is already known, without including the cost of obtaining that knowledge. Generating 2048 samples per question costs more than the largest test-time budgets studied in the paper (256–512 generations). In a realistic deployment, the total cost would be difficulty estimation + strategy execution, and the estimation cost could dominate the execution cost for most queries. The $4\times$ figure should be understood as an upper bound on achievable efficiency — it assumes a free oracle for difficulty, which does not exist in practice unless a much cheaper difficulty estimator is developed.

What evidence exists in the paper. Section 3.2 describes the estimation procedure and acknowledges the cost. Figures 4 and 8 show that predicted difficulty bins (using the PRM's average score over 2048 samples) track oracle bins closely — but both require 2048 samples. No experiment measures total cost (estimation + execution) or compares against a simpler strategy that skips estimation and applies a fixed strategy to all problems. The paper does not report how many FLOPs or wall-clock seconds the 2048-sample estimation step requires.

Mitigation status. The paper explicitly flags this as a key avenue for future work (Section 8):

"pretraining or finetuning models to directly predict difficulty of a question"

No such model is developed or evaluated. A practical alternative not explored in the paper — adaptive difficulty estimation where the first few samples inform difficulty and the remaining budget is allocated accordingly — could subsume estimation cost into the solving process and is a natural extension that would close this gap.

6.2 The Approach Provides No Benefit on Hard Problems Outside the Base Model's Capability Range

The assumption or constraint. The entire compute-optimal test-time scaling framework rests on the assumption that the base model generates correct solutions at some non-trivial rate for the tasks it receives. Test-time compute can amplify existing capability — it searches for correct solutions that already exist somewhere in the model's output distribution — but it cannot create new capability. The paper is transparent about this:

"test-time compute is powerful when problems are within the base model's reach... but it cannot compensate for fundamental capability gaps that larger pretraining would address" (Section 7)

The consequence. On the hardest problems (difficulty bin 5), all methods — search, revisions, and their compute-optimal combinations — show near-zero accuracy regardless of budget. In Figure 3 (right), bin 5 accuracy hovers at 1–3% for all search methods and all budgets from 4 to 256 generations. In Figure 7 (right), bin 5 shows roughly 2–3% accuracy irrespective of the sequential-to-parallel ratio. In the FLOPs-matched comparison (Figure 9), the bin 5 scaling line is essentially flat near 0–5%. No amount of test-time compute helps. For any deployment where a non-trivial fraction of queries falls into this difficulty regime — genuinely novel reasoning, out-of-distribution problems, or tasks requiring knowledge the base model lacks — the method provides zero value, and pretraining a larger model is the only viable path.

What evidence exists in the paper. The difficulty-bin analyses across all experiments (Figures 3, 7, 9) consistently show bin 5 as a flat line near zero. The FLOPs-matched comparison (Figure 9) quantifies this: for hard problems at $R \gg 1$ , test-time compute shows a −52.9% relative disadvantage compared to the $14\times$ larger model. The paper acknowledges this finding in the Section 7 takeaway box but does not estimate what fraction of real-world queries would fall into this regime for a typical deployment.

Mitigation status. The paper does not attempt to address this limitation. It is framed as an inherent boundary condition — a discovery about where test-time compute works rather than a flaw in the method. The authors suggest (Section 7) that if the base model's capability can be improved through further pretraining or fine-tuning, the difficulty distribution shifts and more problems become amenable to test-time compute, but this is a restatement of the limitation rather than a solution.

6.3 The Revision Model Has a 38% Correct-to-Incorrect Reversion Rate

The assumption or constraint. The revision model is trained exclusively on sequences where all in-context answers are incorrect, followed by a correct answer. During training data construction (Section 6.1), the model only sees incorrect-to-correct trajectories — it never sees an example where the current answer is already correct and should be left unchanged. The paper reports the consequence directly:

"since the model was trained only on sequences where all in-context answers are incorrect (followed by a correct target), at test time the model may encounter correct answers in its context (produced during earlier revisions) and incorrectly 'revise' them into wrong answers. The paper reports that approximately 38% of correct answers get converted back to incorrect ones using a naive approach." (Section 6.1)

The consequence. In a sequential revision chain, when the model produces a correct answer at step $k$ , there is a roughly 38% probability that step $k+1$ will "revise" that correct answer into a wrong one. This means the revision chain does not monotonically improve — it can oscillate between correct and incorrect, and the final answer in a long chain may be worse than an earlier answer. The paper mitigates this by selecting the best answer from any point in the chain (via majority voting or verifier-based selection across the entire chain), but this is a post-hoc patch. It means the revision process is inherently unreliable for producing final answers — you must always inspect the whole chain and apply a separate selection mechanism, which adds complexity and potential failure modes (the selection mechanism itself can make errors). In a deployment where you want the model to reliably produce a correct final answer after $N$ revision steps, this reversion rate makes the output at step $N$ untrustworthy.

What evidence exists in the paper. The 38% figure is reported in Section 6.1 based on empirical measurement. Figure 6 (left) shows that pass@1 at each revision step fluctuates rather than monotonically increasing — the overall trend is upward (from ~18% to ~24% over 64 steps) but the noise is consistent with some revisions degrading correct answers. The paper's mitigation — within-chain selection — is described in Section 6.1 and used in all revision experiments, but its effectiveness at recovering from reversions is not separately evaluated (e.g., what fraction of reverted correct answers are correctly recovered by majority voting?).

Mitigation status. The paper addresses this with within-chain selection (majority voting or verifier-based best-of-N weighted across the chain), but this is a workaround rather than a solution. The underlying issue — the model was never trained to recognize when no revision is needed — remains. The paper does not experiment with training data that includes "already correct, do nothing" examples, which would be the principled fix. The ReST $^{EM}$ experiment (Appendix K, Figure 16) shows that attempting to optimize the revision model with on-policy RL training made the problem worse, with performance degrading substantially with sequential revisions — suggesting the reversion issue is not trivially fixable by further training.

6.4 Results Are Demonstrated on a Single Benchmark (MATH) with a Single Model Family (PaLM 2-S*)

The assumption or constraint. All experiments in the paper use the MATH benchmark (500 test questions, high-school competition math) and PaLM 2-S* as the base model. The authors argue that PaLM 2-S* is "representative of the capabilities of many contemporary LLMs" (Section 4), and that MATH is a good testbed because it requires complex multi-step reasoning where test-time compute is expected to help. The paper does not evaluate on any other reasoning benchmark (e.g., GSM8K, LSAT, ARC, MBPP, HumanEval) or any other model family (e.g., GPT, LLaMA, Gemini, Claude).

The consequence. Several aspects of the findings could be model-specific or benchmark-specific in ways that limit generalizability:

The PRM's quality and over-optimization behavior depend on PaLM 2-S*'s output distribution. A model with different calibration properties, different error patterns, or different sampling behavior might exhibit different difficulty-dependent scaling curves — the specific finding that beam search hurts easy problems and helps medium problems (Figure 3, right) might not hold for a model whose outputs are more/less well-calibrated.
The revision model's ability to learn from incorrect in-context examples depends on the base model's in-context learning and sequence-to-sequence capabilities, which vary substantially across model families and scales.
The MATH benchmark consists exclusively of competition-level math problems requiring symbolic reasoning with ground-truth answers that can be string-matched. It is unclear whether the difficulty-dependent patterns generalize to other reasoning domains (code generation, logical deduction, scientific QA) or to tasks where the correctness signal is weaker or multi-dimensional (summarization, dialogue, creative writing).

What evidence exists in the paper. None. The paper does not include any experiments on other benchmarks or other model families. The claim that PaLM 2-S* is "representative" is stated without evidence. The paper does not discuss whether MATH's particular properties — fixed answer format, availability of ground truth for verifier training, competition-level difficulty distribution — make it especially well-suited to the proposed methods.

Mitigation status. The paper does not address this limitation. The authors frame MATH as a deliberate choice (Section 4) but do not discuss generalizability. The related BigBird work (Zaheer et al., 2020, cited in Section 1) is described as evaluating on additional tasks, but the specific test-time compute scaling results in this paper are MATH-only. Replication on at least one other benchmark (e.g., GSM8K for easier math, or a code generation task with unit tests as verifiers) would substantially strengthen the claims of generalizability.

6.5 Sequential Revision Strategies Introduce Serial Latency That the Paper Does Not Account For

The assumption or constraint. The paper measures test-time compute in "generations" — the total number of complete solutions sampled. A sequential revision chain of length $S$ and a parallel best-of-N run of size $N = S$ both cost $S$ generations of FLOPs. However, the sequential chain requires $S$ serial forward passes through the model (each revision depends on the previous one), while parallel best-of-N can (with sufficient hardware) execute all $N$ generations simultaneously. The paper does not discuss wall-clock latency or throughput constraints anywhere.

The consequence. The compute-optimal policies identified in the paper often favor sequential-heavy strategies, especially on easy problems. For example, Figure 7 shows that easy problems perform best with fully sequential revisions, and Figure 8 shows that the compute-optimal policy at 256 generations allocates a significant fraction to sequential depth. In a latency-sensitive deployment — interactive QA, real-time assistants, online systems with service-level agreements — a strategy that requires 64 serial model calls may be practically infeasible regardless of its FLOPs efficiency, because each call takes tens to hundreds of milliseconds and the total latency would exceed user tolerance. The paper's efficiency claims (e.g., " $4\times$ less test-time compute") refer to total FLOPs, not wall-clock time, and a practitioner optimizing for latency would find the recommended strategies misleading.

What evidence exists in the paper. None. The paper does not report wall-clock latency for any method, does not discuss the serial vs. parallel latency tradeoff, and does not analyze whether the compute-optimal policy would change if a latency constraint were added. The FLOPs accounting in Section 7 uses total inference tokens ( $D_{\text{inference}}$ ) without distinguishing serial from parallel execution.

Mitigation status. Not addressed. The paper's framing of "compute-optimal" refers exclusively to total FLOPs, not to latency or throughput. A practitioner facing latency constraints would need to re-derive the optimal policy under a joint constraint of total FLOPs and maximum serial depth — which the current framework does not support. This is a significant practical limitation, since many real-world LLM deployments are latency-bound (interactive applications) rather than FLOPs-bound (batch processing).

6.6 Verifier Over-Optimization Is a Hard Ceiling That the Compute-Optimal Policy Mitigates but Does Not Solve

The assumption or constraint. The PRM verifier is trained once (via Monte Carlo rollout supervision, Section 5.1) and then used as a static scoring function during test-time search. The paper documents that aggressive search against this fixed verifier leads to over-optimization — the search finds solutions that score highly under the PRM but are actually incorrect. This is visible in Figure 3 (right): on easy problems (bin 1), beam search accuracy decreases with increasing budget (from ~78% at 4 generations to ~77% at 256), while best-of-N (which explores less aggressively) continues to improve. Lookahead search — the most aggressive optimizer — paradoxically underperforms all simpler methods at the same generation budget (Figure 3, left). Qualitative examples in Appendix M show search producing degenerate outputs (repetitive low-information steps, overly short 1–2 step solutions) that exploit the PRM's scoring.

The consequence. The compute-optimal policy works around this limitation by routing easy problems to weaker optimization methods (best-of-N, where over-optimization is less severe) and reserving aggressive search (beam search) for medium problems where the PRM's guidance provides genuine value. But the underlying problem — that the verifier is an imperfect proxy that can be exploited — remains unsolved. This means:

The scaling ceiling is bounded by verifier quality. Even for medium problems where beam search helps, the performance curves in Figure 3 flatten well before the budget is exhausted — verifier over-optimization limits how far test-time compute can scale, regardless of how much additional FLOPs are thrown at the problem.
The specific policy thresholds are verifier-dependent. The "easy" vs. "medium" bin boundaries where the optimal strategy switches from best-of-N to beam search depend on the PRM's reliability on that difficulty tier. A better PRM would shift those boundaries, meaning the current compute-optimal policy is specific to the PRM quality achieved by the Monte Carlo rollout training procedure in Appendix D.
Improving search algorithms provides diminishing returns. The paper shows that lookahead search — which should be a better optimizer in principle — performs worse than simple beam search because it over-optimizes the PRM more aggressively. This strongly suggests that further investment in search algorithm sophistication is futile without first improving verifier robustness.

What evidence exists in the paper. Figure 3 provides the core evidence: beam search degrades on bin 1; lookahead search underperforms beam search at the same budget; all methods plateau or decline at high budgets. Appendix M shows qualitative examples of degenerate search outputs. The paper explicitly identifies over-optimization as a limiting factor in Section 5.3 and Section 8 (future work).

Mitigation status. The paper acknowledges this limitation and suggests future work on "improving verifier robustness" (Section 8). The compute-optimal policy is, in part, a mitigation strategy — it avoids the over-optimization regime by using weaker optimizers where the verifier is unreliable. But this is a workaround, not a solution. The paper does not experiment with any method for improving verifier robustness: adversarial training against search-generated solutions, ensemble verification, KL-constrained search that penalizes deviation from the base model's output distribution, or iterative refinement of the PRM on search outputs. These are left as future work, and until they are addressed, the verifier over-optimization ceiling remains the primary bottleneck preventing unbounded scaling of test-time compute.

7. Implications and Future Directions

How This Work Changes the Landscape

ETC introduces a representational reframing of what a Transformer's attention graph means, shifting the field from treating Transformers as fully connected graphs with distance-based edge weights toward treating them as sparse, typed graphs where the model designer explicitly specifies which edges exist and what structural relation each edge encodes. This is not a paradigm shift — the core mechanisms (relative position encodings, sparse attention, hierarchical processing) all existed before — but it is a conceptual unification that reveals long-input scaling and structured-input encoding as two parameterizations of the same underlying problem: designing a sparse attention graph with informative edge types. Prior to ETC, these were separate research threads with different methods and benchmarks. After ETC, the question becomes "what attention graph best captures my domain structure?" rather than "should I use a long-input architecture or a graph-aware architecture?"

The paper's most lasting contribution may be the demonstration that architectural structure matters measurably for NLP tasks, even when the structure is readily inferable from content. The finding that explicit context-boundary masking and candidate-to-mention linking improve WikiHop accuracy by 5.2 points (75.9 vs. 70.7, Table 3), while the same structural encoding provides negligible benefit for HotpotQA, establishes that the value of structural inductive bias is task-dependent in ways that are not obvious a priori. This is a diagnostic contribution: it tells the field that we should be measuring structure-sensitivity as a property of benchmarks, not assuming that all multi-document or hierarchical tasks benefit equally from structural encoding. Benchmarks where structure matters most are those where the correct answer depends on reasoning across independently meaningful units (separate Wikipedia articles, DOM subtrees, entity clusters) rather than across segments of a single coherent text.

The paper also resolves an implicit tension between two design philosophies for long-input Transformers: bottleneck architectures (where long-range information flows through a small set of summary tokens, as in Star Transformer) and direct sparse attention (where tokens attend to distant tokens through strided or learned patterns, as in Sparse Transformer or Reformer). ETC demonstrates that the bottleneck approach works — the global tokens successfully route information across 8,192-token inputs — but only when the bottleneck tokens are (a) explicitly separated architecturally (different projection matrices), (b) given typed relations to the tokens they summarize (relative position labels), and (c) pre-trained with an objective that teaches them to compress and predict content (CPC). This reconciles why the Star Transformer (a pure bottleneck with none of these features) never achieved competitive NLP results: the bottleneck capacity is there, but it requires structural and pre-training support to be usable. The implication for future architecture design is that bottleneck components need dedicated mechanisms to learn their compression role — you cannot simply add sparse attention and expect the model to figure out routing.

This reframing makes certain research directions more attractive: domain-specific attention graphs (for code, for molecules, for knowledge graphs), contrastive pre-training objectives for structural tokens, and systematic studies of when structure helps vs. when it is learnable from content alone. It makes other directions less urgent: further incremental variations on fixed sparse attention patterns (the paper shows that the specific pattern — local windows plus global tokens — works well enough, and the remaining gains come from structure and pre-training, not from marginally better sparsity patterns).

Finally, the paper demonstrates that backward compatibility with existing pre-trained models is a first-class architectural constraint, not an afterthought. By designing ETC to reduce to standard BERT attention when the local radius is large enough, the authors enable lifting weights from RoBERTa, which provides the single largest performance improvement across all datasets (+2.1 F1 on NQ long answer, +1.5 on HotpotQA, +2.8 on WikiHop). This establishes a design principle for future Transformer variants: if you want practitioners to adopt your architecture, make it possible to initialize from the models they already have. The alternative — requiring full pre-training from scratch — creates an adoption barrier that few models can overcome, regardless of their theoretical advantages.

Follow-Up Research This Work Enables

Cheap difficulty estimation via lightweight classifiers or adaptive sampling. The paper's compute-optimal test-time scaling framework requires estimating prompt difficulty before allocating the inference budget, but the current method (2048 samples + PRM scoring) is far too expensive for deployment. The paper explicitly calls for models that "directly predict difficulty of a question" (Section 8). A concrete follow-up: train a lightweight classifier (a single-layer MLP on top of the base model's embedding of the question text, or a distilled version of the PRM) to predict the difficulty bin from the question alone, using the PRM's average final-answer score over 2048 samples as the training target. Measure whether this classifier can achieve comparable bin assignment accuracy to the 2048-sample method while costing only a single forward pass. Alternatively, develop an adaptive sampling strategy: generate 4–8 initial samples, compute the PRM's average score on those, use it as a rough difficulty signal to select the initial strategy, then periodically re-estimate difficulty from accumulated samples during the solving process and adjust strategy mid-computation. The key metric would be whether the adaptive approach recovers the $4\times$ efficiency gain over best-of-N when the difficulty estimation cost is included in the total budget.

Combined PRM search with the revision model as the proposal distribution. The paper studies search against PRM verifiers (Section 5) and iterative revisions (Section 6) as independent mechanisms, and explicitly notes they were never combined (Section 8). The natural extension: use the revision model as the proposal distribution within beam search. At each step of the search tree, instead of sampling next steps from the base model, condition the revision model on the partial solution and previously rejected branches to generate a revised next step. This combination leverages the complementary strengths identified in the paper — revisions improve proposal quality on easy problems (where the initial output is roughly correct), while PRM search selects among candidates on medium problems (where exploration helps). A concrete experiment: on the MATH benchmark with the same PaLM 2-S* model, compare (a) PRM beam search with the base model as proposer, (b) sequential revisions with verifier-based selection, and (c) PRM beam search with the revision model as proposer, all at the same total generation budget. The prediction from the paper's difficulty-dependent analysis: the combined approach should outperform both individual methods on medium-difficulty problems (bins 3–4) where both mechanisms show benefit, while matching the best individual method on easy and hard problems.

Verifier robustness training to push back the over-optimization ceiling. The paper identifies verifier over-optimization as the primary bottleneck limiting test-time compute scaling — beam search degrades easy-problem performance at high budgets (Figure 3, right), and lookahead search paradoxically underperforms simpler methods (Figure 3, left) because it optimizes the verifier signal too aggressively. A concrete follow-up: train the PRM not only on i.i.d. samples from the base model (the current Monte Carlo rollout procedure, Appendix D) but also on adversarial examples generated by running beam search against an earlier version of the PRM and collecting high-scoring-but-incorrect solutions. Add these to the training set with ground-truth correctness labels (0, since they are incorrect despite high PRM scores) and retrain. Measure whether the adversarially trained PRM shows reduced over-optimization — specifically, whether beam search performance on easy problems (bin 1) no longer degrades at high budgets, and whether lookahead search can beat beam search when the verifier is more robust. A negative result (adversarial training doesn't help) would be equally informative, suggesting that the over-optimization problem requires constrained search (KL-penalty from base model distribution) rather than better verifier training.

Replication on non-math and non-text domains to test generality of difficulty-dependent scaling. All experiments use the MATH benchmark with PaLM 2-S*. The paper's central findings — that beam search helps medium problems but over-optimizes on easy ones, that sequential revisions dominate on easy problems but balanced sequential-parallel ratios are optimal on hard ones, that test-time compute cannot compensate for fundamental capability gaps on the hardest problems — may be specific to mathematical reasoning or to the PaLM 2 model family. A concrete replication: reproduce the full compute-optimal scaling analysis (Figures 3, 4, 7, 8) on two additional domains — code generation (HumanEval or MBPP, where unit tests provide ground-truth correctness for verifier training) and multi-hop QA (HotpotQA, where answer matching provides the correctness signal). For code generation, the prediction might differ: since code has stricter syntax constraints than math reasoning, beam search might be more robust (syntactically invalid code gets low PRM scores naturally, reducing over-optimization risk), and the optimal policy might favor search over revisions more strongly than on MATH. Replication on a non-PaLM model (e.g., LLaMA or Gemma) would test whether the specific difficulty bin boundaries and optimal strategy thresholds are model-dependent.

Dynamic, continuous strategy allocation instead of discrete difficulty bins. The paper discretizes difficulty into five quintiles and selects a fixed strategy per bin. This is coarse — within a single bin, questions at the top and bottom may benefit from different strategies. A concrete extension: train a learned policy network that takes the PRM's score distribution from the first $k$ samples (for small $k$ , e.g., 4–8) and outputs a continuous parameterization of the search strategy — beam width, number of parallel chains, revision depth, and the allocation of remaining budget between these. Train this policy via reinforcement learning on the MATH training set, with the reward being whether the final answer is correct. Measure whether the learned continuous policy outperforms the discrete bin-based policy from the paper, especially at the boundaries between difficulty bins. Additionally, test whether the policy network can make dynamic adjustments — if initial samples look harder than expected, the model should be able to shift budget from revisions to parallel search mid-computation. This connects the compute-optimal scaling framework to the meta-learning and adaptive computation literature.

Joint optimization of pretraining and test-time compute allocation under a total FLOPs budget. The paper's FLOPs-matched comparison (Section 7) compares test-time compute with a smaller model against a $14\times$ larger model with greedy decoding. But both the pretraining and inference decisions are treated as fixed: the smaller model is trained once, the larger model is trained once, and the comparison asks which to deploy. A more ambitious follow-up: given a total FLOPs budget that must cover both pretraining and inference for a target deployment scenario (specified by an inference-to-pretraining token ratio $R$ and a difficulty distribution over queries), jointly optimize the model size, pretraining data quantity, and test-time compute allocation strategy. This would require running the compute-optimal scaling analysis at multiple model sizes and multiple pretraining configurations, then fitting a meta-scaling law that predicts accuracy as a function of pretraining FLOPs, inference FLOPs, and problem difficulty. The paper provides the inference-time half of this analysis; the missing pretraining half would build on the Chinchilla scaling laws (Hoffmann et al., 2022). The output would be a set of recommendations like: "for $R = 0.16$ and an easy-skewed difficulty distribution, the optimal allocation is a 3B-parameter model with compute-optimal test-time scaling, not a 10B-parameter model with greedy decoding."

Practical Applications and Downstream Use Cases

On-device QA with small models for routine queries. The paper's FLOPs-matched comparison shows that on easy-to-medium problems at low inference-to-pretraining ratios ( $R \ll 1$ ), a small model with compute-optimal test-time compute can outperform a $14\times$ larger model (+27.8% relative improvement on easy questions with revisions, Figure 1). For a mobile or edge deployment scenario — where a small on-device model handles most user queries and only escalates to a cloud model for hard cases — the difficulty estimator serves double duty: it determines the test-time compute allocation AND the escalation threshold. If the difficulty estimate (from the first few samples) indicates a bin 4–5 problem, the query is routed to the cloud; if it indicates bin 1–3, the on-device model handles it with the compute-optimal strategy for that bin. The $4\times$ efficiency gain (matching best-of-256 performance with 64 generations, Figure 8) directly translates to 4× lower on-device inference cost and latency. The key practical requirement not yet met: the difficulty estimator must be cheap enough to run on-device — requiring the lightweight classifier or adaptive sampling approach described in the follow-up research above.

Cost-efficient batch inference for data generation pipelines. When using LLMs to generate training data for self-improvement (STaR, ReST $^{EM}$ , rejection sampling fine-tuning), organizations typically apply a uniform generation strategy (e.g., best-of-64 for every prompt). The paper's difficulty-dependent results show this is wasteful: easy problems need only 4–8 generations with sequential revisions to achieve near-ceiling accuracy, while medium problems might need 64 generations of beam search, and hard problems may not be solvable regardless of budget. A practical batch inference system could estimate difficulty for each prompt (amortizing the 2048-sample cost over a large batch), then allocate budget per-prompt: 8 generations for bin 1–2, 64 for bin 3–4, and either flag bin 5 for human review or apply best-of-N with the full budget and accept low accuracy. On a batch of 10,000 math problems with difficulty distribution matching MATH, this would reduce total inference FLOPs by roughly 40–60% compared to uniform best-of-64, while producing higher-quality solutions on easy problems (where revisions outperform best-of-N) and comparable quality on medium problems. The savings are directly measurable from the per-bin accuracy-at-budget curves in Figures 4 and 8.

Browser-based information extraction from full web pages. The OpenKP experiments (Table 4) demonstrate that ETC can process full web pages — including DOM structure and visual features — at input lengths up to 4,096 tokens, achieving 0.423 F1@3 (state of the art at publication). A practical deployment scenario: a browser extension that extracts key information (keyphrases, answers to implicit questions, structured data) from the full content of the current page, rather than from a search snippet or truncated view. The ability to ingest the complete DOM tree with structural encoding (parent-child relationships, heading levels, font sizes) means the model can distinguish between a keyphrase in the page title vs. in a footnote, even when they contain identical text. The paper's finding that visual features provide the largest single improvement on OpenKP (+0.007 F1@3, Table 4) means the system should preserve formatting information (bold, headings, font sizes) as embeddings alongside text tokens, not strip it as pre-processing noise. The 512-token input limit of standard BERT would truncate most web pages before reaching the main content; ETC's 4,096-token long input (with linear scaling potential to 8,192+) makes full-page extraction feasible without heuristic splitting or summarization.