acceptodds
Under review as a conference paper at ICLR 2027

Positions on Trees, Not Lines: Exact Length Generalization via Dyadic Attention

Abstract

We propose dyadic attention, which represents token offsets by their scale and divisibility by powers of two. Its hard-routing version, the Dyadic Scan Transformer (DST), learns finite-monoid composition and computes all prefix products in iterations of a single weight-shared block. Trained with intermediate scan supervision on sequences of at most 64 tokens, DST solves parity and the -complete word problem with zero token errors on sequences of 1,048,576 tokens: a 16,384-fold length extrapolation in 20 iterations, using codebook projection for . For this projected inference mode with a fixed sentinel, a machine-checked certificate proves correctness at arbitrary lengths while accounting for floating-point error. We also pretrain matched 1.3B- and 3B-parameter dense Llama-style decoder-only LLMs from scratch, adding a learned dyadic bias alongside RoPE without degrading perplexity at the pretraining context length. We derive a closed-form occupancy correction that requires no further training. At 1.3B, extending the dyadic table through finetuning on contexts up to 16k tokens and applying this correction gives PG-19 perplexity of 18.4 at 65,536 tokens (21.6 for long-context-finetuned RoPE), four times the maximum finetuning length. A variant finetuned up to 64k tokens reaches perplexity of 20.9 at 262,144 tokens without correction. A separate finetune combining dyadic table extension with positional interpolation achieves 94% and 75% passkey retrieval accuracy at 8k and 16k, compared with 60% and 22% for our full-budget YaRN-finetuned baseline.

Primary area:
foundation or frontier models, including LLMs
Keywords:
large language models, length generalization, positional encoding, context extension

Reviews

Among:
Shape:
1234this paper, Bottom 2%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.33 over 3 reviews, above 2% of the others.
Reviewer_BXrUOpenReview ↗
Rating
1
Confidence
4
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper proposes dyadic attention, a mechanism designed specifically for prefix-scan problems such as parity, S5S_5 and Z60\mathbb{Z}_{60}. The DST model reuses a single Transformer layer iteratively to imitate the prefix-scan algorithm. In each iteration, the attention mask is determined solely by the current iteration index. The model generalizes perfectly to these prefix-scan problems. For Δ=i−j\Delta = i - j where ii and jj are two positions, rr is the number of trailing zeros in the binary representation of Δ\Delta, and ss is ⌊log⁡2Δ⌋\left\lfloor \log_2 \Delta \right\rfloor. For language modeling, each attention head learns a bias term for every clipped (r,s)(r, s) pair. This dyadic model shows slightly better length generalization than YaRN on some tasks.

Critical strengths

None

Critical weaknesses
  1. Despite DST's perfect performance on synthetic tasks, the dyadic model improves the perplexity only marginally over a RoPE + YaRN baseline on language modeling tasks. Moreover, the model used for the synthetic tasks is highly customized for these tested tasks and substantially different from the model used in language modeling tasks.

  2. FoX [1] learns a bias term using the forget gate. RelAttn (used in Inkling [2] from Thinking Machines Lab) learns a query-dependent relative-position bias term. Both methods are closely related to the method proposed in this paper. However, this paper does not cite or discuss either method.

[1] Forgetting Transformer: Softmax Attention with a Forget Gate, ICLR 2025

[2] Inkling: Our Open-Weights Model, blog

Questions for authors

Can dyadic model outperform FoX or RelAttn in language modeling tasks?

4 comments

Thank you for the review and the related-work suggestions. We have added a controlled experiment and clarified the relation between our two models.

Weakness 1: LM performance.

Our original results show competitive perplexity with YaRN: 18.4 vs. 18.5 at 65k. Retrieval shows a larger improvement, but the original finetuning configurations differ.

To isolate the contribution beyond PI, we trained four 1.3B models: PI-only and dyadic+PI, each with two finetuning seeds. Both methods use identical training data and order, optimizer, learning-rate and context schedules, PI factor, and 1.573B-token budget.

Table 13(a)-(b) (updated manuscript, page 34, upper half) reports the results:

Passkey accuracy (%)

ContextPI-onlyDyadic+PI
2,04878.094.0
8,19279.288.8
16,38447.677.2
32,7680.00.0

Same-target PPL

ContextPI-onlyDyadic+PI
2,04822.2022.20
8,19220.5920.84
16,38420.5220.74
32,76847.3431.15

At 16k, dyadic+PI improves retrieval by 29.6 percentage points. The paired 95% confidence intervals are positive for both seeds: [13.6, 29.6] and [28.8, 46.4] percentage points. At 32k, dyadic+PI also achieves 34.2% lower perplexity than PI-only. These results provide direct evidence of benefits from dyadic pretraining and finetuning beyond PI alone.

Weakness 1: relation between the two architectures.

We clarified the shared geometry in Section 5 (updated manuscript, page 5, lower part). DST uses shifted binary coordinates to select scan partners. The LM uses the same coordinates to share positional-bias parameters. These are two applications of the same representation.

Importantly, the DST contribution includes a verified numerical guarantee. For S5S_5, we check 14,520 initialization cases and 14,520 transitions, with certified margins of 9.830 and 10.540. Projection and readout are also verified with floating-point bounds. Appendix E (pages 22-23) describes the certified deployment.

Weakness 2 and Question 1.

We thank the reviewer for these references. We added a comparison in Section 7 (page 9) and Appendix V (page 47).

FoX uses input-dependent cumulative forgetting, while RelAttn uses query-dependent relative-position biases. Our method instead groups offsets by their binary scale and divisibility, using a learned scalar for each cell. This structure also enables our occupancy analysis.

We selected PI and YaRN as established baselines for extending RoPE-based pretrained models. They allow us to evaluate context extension within a shared architecture and tokenizer. FoX and RelAttn introduce different attention mechanisms, so a direct architectural comparison would require a separate controlled training study.

Our new matched experiment directly tests the benefit of the dyadic-trained model beyond PI under identical finetuning conditions. Together with the verified scan result, this provides evidence for the two main contributions of our paper.

We hope the new evidence supports reconsideration of the overall assessment.

Thank you for the additional experiments. My main concerns remain.

  1. The new experiments show that dyadic+PI outperforms PI-only, but do not establish an advantage over YaRN under matched conditions. A controlled ablation against basic linear PI cannot replace a comparison against strong baselines.

  2. I acknowledge DST’s theoretical and empirical contributions on synthetic tasks. However, these tasks already have exact, efficient algorithms. I expect their study to provide explanations or improvements relevant to practical applications, not necessarily language modeling. Sharing a representation does not transfer DST’s results to the language model, which requires independent evaluation. Its practical advantages over strong baselines remain unestablished.

  3. The paper already trains RoPE and dyadic models from scratch, so I do not find architectural differences a sufficient reason to omit FoX and RelAttn comparisons. These methods may achieve competitive length extrapolation without PI or YaRN. Whether dyadic can additionally be combined with them is separate from their relevance as competing methods. Discussion alone cannot replace controlled experiments.

I will maintain my score of clear rejection.

Thank you for clarifying your remaining concerns. We would like to emphasize three points.

1. LM baselines. We pretrained matched 1.3B and 3B RoPE and dyadic models from scratch. Our experiments include RoPE-FT, PI-FT, and full-budget YaRN-FT, as well as smaller-scale NoPE and ALiBi controls.

Importantly, perplexity is not our only LM metric. Our dyadic+PI model achieves 94%/75% retrieval accuracy at 8k/16k, compared with 60%/22% for YaRN. These finetunes use the same token budget and context schedule, although some training settings differ. The new matched PI-only experiment directly tests whether PI alone explains the retrieval gain. It does not replace the YaRN comparison.

2. Certified DST result. We do not propose a new prefix-scan algorithm. Our contribution is showing that a weight-shared Transformer can learn this computation from short sequences, and that the correctness of the trained model can be verified for arbitrary lengths, including numerical errors, under the stated inference conditions.

This is a formal guarantee for a trained neural network, not simply high accuracy on long test sequences. What is more, we do not claim that this guarantee transfers to the LM, which we evaluate separately.

3. FoX and RelAttn. We have added both methods to Related Work and explained their differences. They are relevant alternatives, but our evaluation already covers several established approaches. A fair comparison with these different architectures would require new training at comparable scales, which is beyond the rebuttal period. Additionally, Inkling was introduced in a July 2026 technical blog post, shortly before our submission, and falls within the four-month window for contemporaneous work.

Taken together, our paper provides both a verified theoretical result for a trained Transformer and experimental evidence from 1.3B and 3B language models. We believe these contributions should be assessed on their own merits, rather than mainly on the absence of two additional architectural comparisons.

Thank you for considering these clarifications.

  1. Your retrieval comparison against YaRN uses different optimizers, learning rates, and data shards, without explaining why. It therefore does not provide reliable evidence of dyadic’s superiority. Why not compare dyadic+YaRN against YaRN under matched conditions? I see no justification for omitting this experiment.

  2. I acknowledge that the certified DST result is interesting, but I do not see its practical utility. Stating that the LM is evaluated separately does not address this concern: that evaluation still does not convincingly establish an advantage over strong baselines.

  3. The contemporaneous-work argument may apply to Inkling, but not to FoX, published at ICLR 2025. I agree that achieving SOTA is not mandatory. However, YaRN is an established, widely used baseline, with subsequent methods such as LongRoPE2 (ICML 2025) reporting stronger results. You have not convincingly established an advantage even over YaRN under matched conditions. Arguing that SOTA is unnecessary does not answer this concern.

  4. The discussion period has lasted at least 13 days. Training a FoX baseline at one scale during this period is not obviously infeasible. Despite the repeated replies, the requested experiment remains missing. I therefore maintain my rating of clear rejection.

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

The paper proposed dyadic attention applied with two models. The method encodes each token offset by its divisibility by powers of two and its distance scale. The proposed Dyadic scan transformer would achieve zero erros at about 1M tokens, while standard transformers fail at two time of the training length when it's at most of 64 tokens. The proposed soft dyadic bias brings occupancy correction which reduces long-context perplexity without extra training.

Critical strengths

Based on my understanding, the proposed method could provide provably length generalization on state-tracking tasks.

Critical weaknesses

Sounds to me that the retrieval improvement likely comes from PI used alongside it. Adding the method to real LMs gives about the same long-context performance as established techniques like YoRN.

Questions for authors

In the appendix G, it suggests that it would cause failure on short sequences after removing those intermediate labels. So is it realistic to assume the routing pattern and labels being available?

1 comment

Thank you for recognizing the length-generalization result. We have added a matched experiment to address the concern about PI.

Weakness 1.

We finetune four 1.3B models: PI-only and dyadic+PI, each with two seeds. Within each seed, both methods use identical training data and order, optimizer, learning-rate and context schedules, and PI factor. Each run uses 1.573B tokens, with all parameters trainable.

Table 13(a-b) (updated manuscript, page 34, upper half) reports:

Passkey accuracy (%)

ContextPI-onlyDyadic+PI
2,04878.094.0
8,19279.288.8
16,38447.677.2
32,7680.00.0

Same-target PPL

ContextPI-onlyDyadic+PI
2,04822.2022.20
8,19220.5920.84
16,38420.5220.74
32,76847.3431.15

At 16k, dyadic+PI improves retrieval by 29.6 percentage points. The gain is positive for both seeds, with paired 95% bootstrap intervals of [13.6, 29.6] and [28.8, 46.4] percentage points. This demonstrates a retrieval benefit from the dyadic-trained model beyond PI alone under matched finetuning conditions. The full protocol is in Appendix M.1 (page 33, lower part).

Weakness 2.

Our corrected deep-16k model achieves comparable 65k perplexity to YaRN (18.4 vs. 18.5), and lower perplexity on identical target tokens (18.3 vs. 19.3). YaRN performs better at 32k in the main PPL grid.

For retrieval, our separate joint dyadic+PI model achieves 94%/75% at 8k/16k, compared with 60%/22% for YaRN. The new matched experiment confirms that the retrieval advantage of the dyadic-trained model cannot be explained by PI alone.

Question 1.

DST learns a local composition rule within a fixed prefix-scan structure. Intermediate labels are computed directly from the known task operation on short training sequences. At inference, no intermediate labels are needed.

The ablation in Appendix G shows the importance of this supervision. For the projected fixed-sentinel deployment, finite verification of initialization, transitions, projection, and readout establishes correctness at arbitrary lengths.

The language-model experiments use ordinary next-token training and require neither scan routing nor intermediate labels.

We hope the matched control and the clarified scope address the concerns and support reconsideration of the recommendation.

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

The background for this paper is rooted in state tracking problems like the S_5 word problem: prior work showed these are genuinely hard for some transformers/SSMs to solve (i.e. both for Transformers "Transformers Learn Shortcuts to Automata" and SSMs "The Illusion of State in State-Space Models", though recent variants like S5 are somewhat better); whereas LSTMs can solve some of them easily. Thought of as balls A, B, C, D, E in cups, the goal of S_5 is to take a sequence of cup position swaps and report back where the balls ended up.

The paper introduces first introduces a scan model that Table 1 suggests gets full accuracy on state tracking problems like S_5, but this is a pure model based solution that uses hard routing, not an actual language model solving the problems.

Then the paper applies the idea underlying that solution to a language model via soft routing. The idea is to incorporate a specific additive table into the RoPE scores which would normally weight query/key pairs. This is intended to be an inductive bias inspired by the scan model, but the exact connection is unclear to me.

Finally, the paper runs long context experiments (fairly typical) on a 1.3B llama-style model on PG-19 evaluating perplexity on books and passkey retreival from PG-19 filler.

Critical strengths
  • The paper's approach when incorporated into a Transformer LM, is able to achieve good performance on a state tracking problem (parity, Figure 2) and match LSTM performance, whereas standard Transformers do not.
  • The paper appears to improve on PG-19 long context extension and passkey retrieval. (Though it's difficult to compare these to prior work on those benchmarks.)
Critical weaknesses
  • The key problem with this paper is its lack of clarity. The narrative of what the paper is trying to accomplish is unclear from the outset. It requires careful digging to uncover related work. Is the paper trying to solve the state tracking problems in Transformers? Is it trying to shed light on the theoretical limitations of state tracking due to existing long-context methods? Is the paper's goal to improve long context extension? Maybe it's some combination of these. If so, the paper should simply state its goals and how/whether it accomplishes them. As written, it appears to be a technical report outlining what was done without any time spent discussing why it was done.
  • The paper relegates related work to a section at the end and essentially does an incomplete job of actually compariign this work to prior papers. This leaves it uncontextualized in a harmful way: it's difficult to understand how one should interpret this paper relative to prior theoretical and empirical work studying Transformer / SSM behavior on state tracking problems. It's also difficult to understand where this should live in the more empirical work on long-context extention, with a parictular emphasis on relative positional embedding methods. Overall, this paper may be headed in a good direction but it's difficult to assess whether one should treat its results as impactful.
  • The experimental design around the PG-19 and passkey retreival work seems the most likely to be eventually impactful, but the discussion of how the method influences the architecture (i.e. Section 5) is not straightfoward.
  • The PG-19 results are token-level PPL, but it's good practice to report word-level PPL so that results are comparable across different tokenizers. Given that they are token-level, the results seem unexpectedly high. For example, Table 5 in the DeciMamba paper includes some 1.4B SSM and 2.8B transformer results which are in the 9-11 range, rather than the 17 range at 2K context that Table 2 in this paper presents. Why is that?
Questions for authors
  • What model was used in Section 6? Why isn't it named there?
  • What is the connection between Section 1 and Section 5? In particular, how did you come up with the particular additive table that is augmenting rope and how does it relate to the dyadic geometry?
  • What are the high level goals of this paper?
1 comment

Thank you for the detailed comments and for recognizing the potential of the LM results. We have made the goals and model descriptions clearer. We also added a controlled PI-only versus dyadic+PI experiment with two finetuning seeds.

Weakness 1 and Question 3. Our paper has two goals: to verify length generalization of a learned scan, and to test the same offset geometry in a conventional language model. We state these goals at the start of Contributions and scope (provided in the updated manuscript, page 2, middle part). The scan contribution includes a finite, floating-point-aware certificate for the specified projected model. The LM contribution is empirical. The new matched experiment strengthens this part: at 16k, retrieval increases from 47.6% to 77.2%, with a positive paired interval in each seed. The full results are in Table 13(a)-(b) (provided in the updated manuscript, page 34, upper half).

Weakness 2. We have added discussion of FoX and the relative attention used in Inkling, alongside the existing discussion of parallel scan, RegularGPT, PI, and YaRN. Section 7 (provided in the updated manuscript, page 9, middle part) gives the short comparison. Appendix V (provided in the updated manuscript, pages 46-47) explains the architectural differences. Our scan contribution is learning an update whose complete numerical execution can be verified through a finite set of cases.

Weakness 3 and Question 2. We clarified the connection at the start of Section 5 (provided in the updated manuscript, page 5, lower part). For an offset Δ\Delta, v2(Δ)v_2(\Delta) measures divisibility by powers of two, and ⌊log⁡2Δ⌋\lfloor\log_2\Delta\rfloor gives its distance scale. The scan partner at iteration tt has Δ=2t\Delta=2^t, so its shifted coordinates are (0,0)(0,0). In the LM, the unshifted coordinates group offsets into cells. Each head learns one additional bias per cell:

+b_{c(i-j)}.$$ Thus the shared object is the geometry. DST uses it to select scan partners, while the LM uses it to share positional-bias parameters in ordinary causal attention. **Question 1 and clarification of Strength 1.** The model specification was already in the opening paragraph of Section 6. We have now separated it into **Models** and **Training (provided in the updated manuscript, page 6, lower part)**. The models are dense 1.3B Llama-style decoders with 24 layers, width 2048, and 32 heads, trained from scratch on about 21B FineWeb-Edu tokens at context 2048. They are our own pretrained models. Figure 2 reports the task-trained DST parity experiment. The LM results are in Section 6 and Tables 2-3. **Weakness 4.** The reported values from DeciMamba are not directly comparable because the models use different tokenizers, training budgets, and evaluation protocols. It scores the last 100 tokens of each window, while our evaluation scores the second half. Word- or byte-normalization would address tokenizer differences, but would not remove the difference in evaluated positions and context. A direct comparison requires the same text and scoring protocol. Our comparisons in Tables 2 and 11 use the same tokenizer and evaluation procedure across models. We hope the clearer presentation and new controlled results support reconsideration of the assessment.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.