acceptodds
Under review as a conference paper at ICLR 2027

Efficient Training of Linear Transformers with Block-diagonal Gates

Abstract

Linear Transformers have established themselves as efficient alternatives to softmax attention for sequence modeling, to the point that modern LLMs increasingly rely on hybrid designs for large-scale deployment. Their primary advantage stems from compressing context into a fixed-size hidden state that is updated recurrently, thus disposing of an ever-growing KV cache. The widespread adoption of Linear Transformers drives the push for their improvement, which hinges on enriching the structure of the state-transition matrix (or *gate*) governing their recurrent update. This structure has progressed from scalar, to diagonal, to diagonal plus a low-rank perturbation: each step broadened the transformations the state could undergo, and was unlocked by dedicated *chunk-wise parallel* algorithms that enabled efficient training at scale. Block-diagonal transitions have recently emerged as the relevant next step, to boost expressivity via richer state mixing. However, the lack of an adequate training algorithm has so far restricted their application to either small scales or to specific block families. In this work, we develop a *generalized chunk-wise parallel* algorithm that lifts these restrictions, together with efficient hardware-aware kernels for its implementation. We use it to introduce and train a Block-diagonal Gated Linear Transformer (BGLT) at 7B scale. To keep parameter count comparable to existing methods, BGLT employs transition blocks, further expressed as a Kronecker product of two factors. Despite this compact representation, BGLT attains superior performance on a range of synthetic tasks, solving in a single layer. On language modeling tasks, it shows results competitive with baselines at 7B. Ultimately, BGLT provides a blueprint for deploying more general recurrences that remain efficiently trainable at scale.

Primary area:
foundation or frontier models, including LLMs
Keywords:
Linear Transformer, SSM, RNN, expressivity, block-diagonal, sequence parallelism, chunk-wise parallelism

Reviews

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

This paper investigates efficient training algorithms for linear Transformers with block-diagonal gating. Although linear Transformers offer favorable computational complexity for long-sequence inference, more expressive gating mechanisms can make parallel training substantially more challenging. In particular, existing chunk-wise parallelization methods may rely on matrix inversion involving gating matrices, which can limit their applicability to general block-diagonal gating structures and raise concerns regarding numerical stability and GPU execution efficiency.To address these issues, the paper proposes a generalized chunk-wise parallel algorithm that avoids matrix inversion. By combining local factorization with hierarchical tiling, the algorithm reformulates recurrent computations into matrix operations that are better suited to GPU and Tensor Core execution. Building on this algorithm, the paper introduces BGLT, which reduces the number of gating parameters through Kronecker factorization and employs an SVD-style parameterization to improve numerical stability. The paper further proposes ΔBGLT, which incorporates the Delta Rule to enhance information mixing during state updates.The experiments cover synthetic tasks, language modeling with 7B-scale models, training throughput, and activation memory consumption. The results demonstrate clear advantages on several synthetic state-tracking tasks and competitive performance on language modeling benchmarks. However, the overall gains on real-world language modeling tasks appear relatively modest, and the trade-off between performance improvements and additional computational costs requires further justification.

Critical strengths
  1. The problem is technically important and well motivated.The paper addresses not merely the introduction of more expressive gating mechanisms, but the fundamental challenge of efficiently parallelizing the training of more expressive recurrent structures. This problem lies at the intersection of algorithm design, numerical stability, and GPU execution efficiency. 2. The core algorithmic contribution is clearly defined.The proposed inversion-free chunk-wise parallel algorithm combines local factorization and hierarchical tiling to provide an alternative to conventional sequential recurrence for general block-diagonal gating structures. This is a meaningful algorithmic direction for improving the trainability of structured linear Transformers. 3. The model design and training algorithm are reasonably well integrated.BGLT combines Kronecker factorization to reduce gating parameter overhead with a constrained parameterization intended to improve numerical stability. Together, these choices provide a coherent design that considers model expressiveness, parameter efficiency, and hardware execution. 4. The experimental evaluation covers multiple dimensions, and the synthetic results demonstrate substantial potential.The paper evaluates synthetic tasks, 7B-scale language models, training throughput, and activation memory consumption. On synthetic benchmarks, BGLT performs strongly on tasks such as state tracking, modular arithmetic, and Copy Memory. In particular, its state-tracking performance remains high beyond the training sequence length, suggesting promising generalization to longer sequences in this setting.
Critical weaknesses
  1. The advantages on synthetic tasks do not yet translate into equally convincing gains on real-world language modeling, and the differences across tasks require further explanation.Although BGLT performs strongly on several synthetic tasks, Table 2 indicates that ΔBGLT achieves only a marginal difference from KDA in average language-modeling metrics, with limited improvement on the Recall task. Whether these gains are statistically robust and consistently generalize across different tasks remains unclear. Additional experiments across random seeds and task settings would help establish the reliability of the reported improvements.Furthermore, Table 3 reports an accuracy of 49.1% for BGLT on the k-HOPS task, compared with 99.2% for ΔBGLT. This substantial gap suggests that even with a more expressive block-diagonal gating structure, different tasks may benefit from different state-update mechanisms. The paper would be strengthened by a more detailed analysis of the reasons for this discrepancy and its implications for practical model selection. 2. The independent contributions of the individual components require more comprehensive ablation studies.The proposed approach incorporates several design choices, including the inversion-free chunk-wise algorithm, Kronecker factorization, SVD-style parameterization, and the Delta Rule. The current results do not fully disentangle the individual contributions of these components to the final performance.I encourage the authors to investigate the effects of varying the block size on accuracy, throughput, and memory consumption; removing Kronecker factorization; removing the SVD-based constraint and evaluating the resulting numerical stability; and incorporating the Delta Rule while measuring both capability improvements and additional computational costs. It would also be valuable to separate the gains attributable to the training algorithm from those resulting from changes to the model architecture.Without these comparisons, it remains difficult to determine whether the reported improvements primarily arise from the core algorithm, the parameterization strategy, or the additional state-update mechanism. 3. The claimed computational efficiency advantages require more comprehensive validation.Efficient training is a central motivation of this work, but more expressive gating structures may also introduce additional computational overhead. According to Figure 4, BGLT has approximately 5%–9% lower prefill throughput than GLA, while ΔBGLT incurs a further reduction of approximately 9%–11%. Figure G.4 also indicates that BGLT uses approximately 9%–13% more activation memory than KDA or GLA. Moreover, Figure G.7 reports that the forward and backward kernel runtimes of ΔBGLT are approximately 1.49× and 1.52× those of KDA, respectively, with a substantial portion of the overhead attributed to attention/Gram matrix construction.These results suggest that improvements in algorithmic parallelization do not necessarily translate into end-to-end training speedups. The current evaluation primarily reports throughput and memory consumption under specific configurations. A more comprehensive performance characterization across sequence lengths, batch sizes, and hardware platforms is still needed. It is also unclear whether the baseline implementations receive comparable levels of optimization.A more rigorous evaluation would compare end-to-end training time under consistent hardware and training configurations, clarify the implementation details of the compared methods, and quantify the practical effects of recomputation strategies on throughput and memory consumption. The throughput comparisons should also explicitly state their reference baselines and percentage-change definitions. 4. The scope of applicability and the rationale behind key design choices need further clarification.Although the proposed algorithm has potential applicability to general block-diagonal gating structures, its practical efficiency may depend strongly on block size, tiling strategy, and hardware execution characteristics. The paper would benefit from a clearer discussion of which structures and operating conditions are most suitable for the proposed method, as well as the circumstances under which its advantages may diminish.In particular, the effects of block size and hierarchical tiling on numerical stability, computational efficiency, and model performance remain insufficiently characterized. It would be useful to establish more general guidelines for selecting these design parameters and to explain how parameter efficiency, expressiveness, memory overhead, and training speed should be balanced in practice.
Questions for authors
  1. Efficiency and comparison conditions. What is the intended efficiency claim: making general block-diagonal gates practically trainable, or improving end-to-end training efficiency over existing linear Transformers? Please clarify which comparisons use matched hardware, precision, batch size, sequence length, and recomputation settings, and whether the baselines receive comparable implementation optimization. Do existing measurements establish a favorable end-to-end capability–cost trade-off in any operating regime?

  2. Component attribution and task dependence. Which controlled results isolate the effects of block size, Kronecker factorization, the SVD-style constraint, and the Delta Rule? In particular, what explains the 49.1% versus 99.2% k-HOPS gap between BGLT and ΔBGLT? Clarifying which conclusions are supported by existing controls, and providing targeted additional evidence where available, would affect my assessment of the architectural contribution.

  3. Reliability of the language-modeling gains. Are the small differences between ΔBGLT and KDA in Table 2 consistent across independent training runs or supported by uncertainty estimates? If only single-run results are available, please clarify this limitation and whether the task-level results provide evidence of a consistent advantage.

10 comments

We thank the reviewer for the thorough review. We address the raised concerns below, organised by topics

Q1 / W3: Kernel efficiency

What is the intended efficiency claim: making block-diagonal gates practically trainable, or improving efficiency over existing linear transformers?

The first. The goal of our algorithm is to make block-diagonal gates practically trainable at scale: that is, we want to generalise existing algorithms so that they can be applied to more complex gate structures, and not improve the runtime of already-existing, specialised ones. Since ours is a more general algorithm, and requires more complex operations than when simpler structures are involved (like for GLA, GDN, and KDA linear transformers), it would be unreasonable to expect it could beat those specialised ones at runtime. So our goal is only to show that its runtime is comparable with that of more specialised algorithms, and not that we provide improved efficiency over those. For comparison (FigG3), Δ\DeltaBGLT’s prefill overhead (+13%) is comparable to that of KDA over GLA (+11%).

“The claimed computational efficiency advantages require more comprehensive validation. Efficient training is a central motivation of this work, but more expressive gating structures may also introduce additional computational overhead. [...] These results suggest that improvements in algorithmic parallelization do not necessarily translate into end-to-end training speedups.

We hope that our clarification above can help address the reviewer’s concerns. To further reiterate, our generalised chunkwise parallel algorithm does not aim to provide computational advantages over existing baselines: indeed, since we develop it with more complex gates in mind, it necessarily introduces additional computation. What our algorithm allows for, is efficient training, even for more complex gates (with throughputs comparable to existing baselines). The generalised chunkwise parallel algorithm is not to be intended as a substitute to other, inverse-based ones (like KDA, GDN or GLA’s) but rather as an efficient alternative when explicit factorization via inversion is not feasible (see eg L23-35, L84-87, L200-205). For diagonal gates, inversion is very much feasible (each gate component can be treated in log-space, where inversion reduces to subtraction), similarly for 2x2 orthogonal gates (each gate is uniquely parameterised by an angle, so inversion reduces to rotation by the opposite angle), so a practitioner should rely on already-existing, specialised kernels in these cases. Our algorithm comes into play in cases like general block-diagonal gates, where explicit inversion is not feasible (see discussion around Lem3).

Do existing measurements establish a favorable end-to-end capability-cost trade-off in any operating regime?

Yes, for those tasks where the additional capability is actually needed. On A5, BGLT quickly reaches 100%, while KDA ends its full training run at 6.2% (see TabD1 in the Appendix). Similarly on copy-memory and modular arithmetic without brackets. In language modelling, Δ\DeltaBGLT is ahead of KDA on recall tasks at 7B, which is a particularly arduous tasks for linear RNNs.

Please clarify whether the baselines received comparable implementation optimization

The main baseline we consider is the one currently deployed in Kimi K3’s KDA cell. This is a hybrid Transformer used in production-level LLMs, so we can expect the kernel implementation to be reasonably optimized. If anything, the comparison is unfavourable to our side, as our core attention assembly kernel is entirely novel and built from the ground-up by the authors in the course of this project, whereas KDA’s kernel is already mature.

Please clarify which comparisons used matched hardware, precision, batch size, sequence length, and recomputation settings

All comparisons run on matched hardware (a B200 GPU, which is what the algorithms considered are more heavily optimised for) and at matched precision (generally speaking, bf16 except for anything involving operations along the sequence length, which is treated in fp32, as is the norm for linear RNNs: see also Fig captions in AppG4). Whenever we vary batch size and sequence length, we explicitly highlight this (FigG3-6). Regarding recomputation, all timing results are reported for the algorithm we actually deploy at training, which recomputes the most intermediate quantities, following the KDA recipe. In essence, we aimed at being as fair as possible throughout our comparisons, matching KDA’s configuration as closely as possible.

Q1 / W3: Kernel efficiency -- cont'd

The current evaluations primarily report throughput and memory consumptions under specific configurations. A more comprehensive performance characterization across sequence lengths, batch sizes, and hardware platforms is still needed

While due to space limitations in the main manuscript we could only report throughput timings for the configuration used for our large scale training (Fig4), we profile our kernel more in detail in AppG.4. There we provide, among other relevant information, training throughputs (FigG3) and decoding times (FigG5) for varying sequence lengths and batch sizes configurations. We conduct this analysis at different granularities, measuring runtimes needed for passes through the whole model (AppG4.1), through the single BGLT layer (AppG4.2), and through the sole BGLT recurrent cell (AppG4.3), both under torch.compile (closer to actual deployment configuration) and eager execution (to provide a more specific, per sub-kernel breakdown of runtimes, although suboptimal).

On hardware, we focus on B200 as this is the current target for large-scale training. Our kernels use specific features from the Blackwell architectures, so porting them to Hopper (or even more so to Ampere) would require ad-hoc optimizations and possibly re-implementations.

Quantify the practical effects of recomputation strategies on throughput and memory consumption

In FigG4 we already show memory consumption for the two extrema (store nothing and recompute everything vs store everything and recompute nothing), to give practitioners an idea of what the trade-off entails in terms of GPU utilisation. In practice, for large-scale deployment, GPUs are generally deployed at saturation, so it is preferable to reduce memory consumption whenever possible. For this reason, we focus our timing analysis on the same configuration we used for training, that is, full recomputation. We point out that, in terms of throughput, this is the most unfavourable scenario for us, as avoiding recomputation by storing intermediates from the forward pass reduces runtime. To get an idea of the impact of recomputing the various components on runtime, we refer to FigG7: shaded regions denote time spent recomputing quantities, which can potentially be saved at the cost of extra memory consumption.

Clarify the implementation details of the compared methods

We provide a full guide of the mathematical operations necessary for our cell application in AppF, which is what the KDA baseline also follows, for the largest part. For the specific kernel components of our cell that differ from KDA, in AppG we provide a detailed walk-through both for forward (see also Sec3.1) and backward passes, together with pseudo-code for the most relevant parts (Alg1-6), and a description of how the mathematical operations map to stages in the algorithm. We will soon provide open access to the code implemented in the course of this project, so that practitioners can directly access the implementation details. For KDA, we use its shipped implementation. We will further clarify all these points in the main text, but if the reviewer deems this insufficient, we kindly ask them to point out precisely what other details they would like outlined.

The throughput comparisons should also explicitly state their reference baselines and percentage-change definitions

The main baselines are GLA and KDA (BGLT being interpretable as an extension of the former, and Δ\DeltaBGLT as an extension of the latter), and we report this in L380 and throughout the paper. Explicit throughput numbers are directly reported in the graphs, but we are happy to include percentages differences as well.

Q2 / W2: Ablations on individual components

The proposed approach incorporates several design choices, including the inversion-free chunkwise algorithm, Kronecker factorization, SVD-style parameterization, and the DeltaRule. The current results do not fully disentangle the individual contributions

While it’s true that we introduce a number of design choices in our BGLT definition, we provide justifications for each of them in Sec3.2: these boil down to a balance between computational efficiency (kronecker factors ensure good mapping to tensor cores while limiting memory movements and parameter count), training stability (L2 normalisation via SVD is useful to prevent state/gradient blow up during training), and expressivity (4x4 blocks are the minimal requirement for solving S5). Regarding the specific ablation requests from the reviewer:

  • The inversion-free chunkwise algorithm cannot impact model quality: it computes the exact quantity, only in a different manner, which is stable for block diagonal gates. It is also not something we can ablate over, as there is no viable alternative for training block-diagonal transformers at scale: sequential recurrence is too slow, parallel scans are too memory-intensive, and inverse-based factorisation cause immediate loss of numerical precision at best and NaNs at worst (see Lem3). That is precisely the reason why this algorithm is a key contribution in our paper.
  • For the SVD-style parameterization, we provide an ablation result in AppC2. For training stability, it is paramount to control the gates norm, as we need to compute cumulative products thereof, spanning whole chunks of sequences, which can grow exponentially if unbounded. L2L_2 normalisation controls in one go both forward and backward pass, and doing so via SVD parameterisation is a natural choice which gives us direct control over singular value distribution. As an alternative, we explore also L∞L_\infty normalisation, and provide results in FigC2: L2L_2 works slightly better in practice.
  • Regarding DeltaRule, we provide performance on all the synthetic tasks considered (AppD), and complete timing results variants (AppG) for both BGLT and its DeltaRule variant Δ\DeltaBGLT. In general Δ\DeltaBGLT performs better, which is why we prioritised the training of this version of our model at large-scale for language modeling tasks, also given the substantial GPU resources necessary to train at 7B. Nonetheless, in our response to Reviewer NgEX W3, we expand Tab2 with results from BGLT at 1.5B, spanning multiple seeds (see also discussion there).
Reviewer_vrgzOpenReview ↗
Rating
3
Confidence
2
Informativeness
3
Presentation
3
Soundness
2
Read review
Paper summary

The paper proposes an inverse-free chunk-wise parallel algorithm for block-diagonal linear recurrences, instantiates it as BGLT and Delta-BGLT, and evaluates these models on synthetic tasks and language modeling at scales up to 7B parameters.

Critical strengths
  1. The algorithm expands the state-transition structures compatible with practical parallel training. I consider this a meaningful contribution: enabling richer recurrent structures opens up architectural possibilities whose value extends beyond whether the particular models evaluated here outperform KDA at matched training cost.
  2. The evaluation includes synthetic tasks, large-scale language modeling, parameterization ablations, and detailed efficiency measurements, providing several perspectives on the proposed approach.
Critical weaknesses
  1. The quality–training-cost trade-off remains unclear. At 7B, Delta-BGLT improves general and recall averages over KDA by 0.1 and 2.0 percentage points, respectively, while the 1.5B recall result favors KDA (Table 2). Given the lower training throughput and larger memory footprint reported in Appendix G, matched-parameter and matched-token comparisons do not establish an advantage at matched training cost. This concern limits the evidence for practical cost-effectiveness; it does not, by itself, invalidate the algorithmic contribution. The paper should distinguish these two claims clearly.
  2. The source of the empirical gains deserves clearer attribution. Block-diagonal transitions permit interactions among state components within each block, making these interactions a natural candidate explanation for the improvements. Although the paper includes parameterization ablations, it would be useful to clarify whether they isolate the contribution of within-block interactions from differences in parameter count, state capacity, or other architectural choices. Such evidence would strengthen the connection between the proposed structure and its empirical benefits.
Questions for authors
  1. Using existing training logs where possible, does Delta-BGLT retain its quality advantage over KDA at matched training time or compute?
  2. Do the existing ablations compare variants that allow versus restrict off-diagonal interactions within each block, while keeping the state dimension, delta-update mechanism, and training configuration as consistent as possible? If so, what do these results establish about the contribution of within-block state interactions?
2 comments

We thank the reviewer for the positive assessment and the relevant question.

Q3b: Does Δ\DeltaBGLT retain advantage over KDA at matched training time or compute?

We point out that our current comparison follows the standard protocol of previous work, in that we test models at matched parameter count and training tokens. Since most of the training FLOPs are still associated with the MLPs, matching parameter counts also roughly matches overall compute: Δ\DeltaBGLT and KDA are then already close to compute parity (differences in the recurrence only adds roughly 1% to the total compute), and Tab2 is already a comparison under matched compute. As such, we treat throughput mainly as a variable to control for, and not the main target.

Still, the reviewer raises a good point in that comparison under matched training time is a relevant matter. We do not shy away from the fact that, with current kernels, Δ\DeltaBGLT is slower than KDA (with some 13% overhead, comparable to KDA’s overhead of 11% over GLA), and even with optimal kernels we’d expect this overhead to remain (as our gate is strictly more complex). Normalising by training time, we would expect the two models to be roughly on par. Unfortunately, existing logs can’t be recycled to cleanly verify this: we’d be comparing a truncated Δ\DeltaBGLT with a completed KDA run, which the cosine schedule leaves at different regimes.

Nonetheless, we point out that the primary goal of the paper is to make a more expressive class of gates trainable at scale. What the overhead buys, then, is boosted expressivity which additional training cannot give KDA (eg, on the A5 task in TabD1, a single BGLT layer reaches 100% in 8 minutes, while KDA is still at 6.2% after its full 36-minute run). To what extent this benefit is reflected on language modelling tasks depends on the specific task at hand: from the results in Tab2, the advantage seems to fall more prominently on recall-intensive tasks, while general LM tasks remain close to parity with KDA. We will include a more in-depth discussion about this in the final version, and thank the reviewer for raising this issue.

Dear Reviewer vrgz,

Thank you again for your review and the time you spent on our paper. As the discussion period draws to a close, we wanted to follow up on our rebuttal. In response to your comments, we clarified that our comparisons at matched parameters and tokens are effectively compute-matched (BGLT is within ~1% of KDA in FLOPs), and discussed the trade-off between training time and expressivity, including where it pays off (eg, A5 and recall tasks).

If you feel these revisions address your concerns, we would be grateful if you could consider updating your score. If anything remains unclear or insufficiently addressed, we would be happy to continue the discussion.

Best regards, The authors

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

The paper develops a chunked training algorithm for linear recurrences with block-diagonal gates. It uses local factorizations to assemble attention matrices without inverting the gates.

BGLT uses small Kronecker factors to keep block products compact and limit their parameter cost. DeltaBGLT adds a Delta Rule correction to the recurrence.

The experiments cover synthetic state tracking, language models up to 7B, and training speed and memory use. On S5, BGLT generalizes well to sequences longer than those seen during training.

At 7B, DeltaBGLT performs similarly to KDA on general language tasks and has a higher recall average. The kernel measurements show the extra computation and memory needed for the richer transitions.

Critical strengths
  1. Local factorization allows chunked training with general block-diagonal transitions, including gates that are not invertible.
  2. The Kronecker representation avoid materializing full blocks. The component timings and memory measurements show the costs of using this structure on GPUs.
  3. The paper tests the method at 7B and on S5 length generalization. It also reports how results vary with the optimizer, gate spectrum and random seed.
Critical weaknesses
  1. The written backward pass leaves unclear where gradients from diagonal attention entries and gates in strictly intermediate tiles are accumulated. Please connect these steps to the reported reference checks.

  2. The synthetic experiments use test accuracy for early stopping. Large seed-to-seed differences on some tasks leave open how reliably the models learn them.

  3. The main language-model table includes DeltaBGLT but not plain BGLT. The smaller training ablations do not show how much the Delta Rule adds on downstream tasks.

Questions for authors
  1. Where are these two gradient contributions included, and do the reference checks cover query and key tiles separated by at least one intermediate tile?
  2. Can you report mean performance or success rates across seeds on fresh synthetic test data, separate from early stopping and model selection?
  3. Could you reconcile the full-chunk condition number in the lemma statement with the prefix condition number used in its proof? The worst-case bound may be unaffected. The general-task margin over KDA does not consistently grow with model size. Please qualify the scaling claim.
3 comments

We thank the reviewer for their review and for the useful recommendations. We comment on the reported critical weaknesses and address their questions in order

W1/Q1: Where are these two gradients contributions included

First of all, we want to reassure the reviewer that our code implementation tracks the whole gradient propagation correctly, as verified by direct comparison against PyTorch autograd: the incongruences highlighted are then limited to the reported derivations, which we proceeded to thoroughly double-check. The gradient contributions from the diagonal tiles are accounted for in paragraph Phase1: diagonal tiles and Alg4 in AppG3, but as per the reviewer’s suggestion, we noticed an index mismatch in the pseudo-code loop, which we proceeded to correct. Contributions from intermediate tiles are actually a simpler case of the ones from key- and query-side ones, in the sense that they can be directly computed via 2 subsequent matrix-matrix-multiplications, one reducing along s, the other along t, and need no additional HS parallel scan to complete. We revised the paper to include a sub-paragraph directly expanding upon this and addressing this case explicitly, and we thank the reviewer for the recommendation.

W2/Q2: Can you report performance across seeds on fresh synthetic test data?

We have updated TabD1 in the Appendix to report results from 6 seeds (as opposed to 3 from the original submission), and to include mean and standard deviation across those. Regarding using the test-set for both early-stopping and final accuracy measurement, we agree this can introduce bias: we have therefore updated the experiment protocol to use two separate validation and testing sets, used respectively for early-stopping and evaluation. Updated results are reported below

Updated TabD1: Single-layer models accuracy on synthetic tasks (mean % ± std over 6 seeds on unseen test split)

TaskLSTMGRUTransf.GLAKDABGLTΔBGLT
MQAR62.6 ± 6.664.2 ± 17.6100.0 ± 0.099.6 ± 0.299.5 ± 0.199.6 ± 0.199.5 ± 0.2
1-Hop99.8 ± 0.3100.0 ± 0.099.7 ± 0.199.7 ± 0.0100.0 ± 0.099.9 ± 0.1100.0 ± 0.0
4-Hops51.4 ± 2.349.6 ± 1.248.5 ± 0.148.6 ± 0.399.0 ± 0.149.0 ± 0.399.1 ± 0.1
Cycle Nav99.2 ± 0.198.4 ± 0.799.2 ± 0.198.7 ± 0.398.5 ± 0.999.3 ± 0.299.4 ± 0.2
Mod. Arithm.82.4 ± 14.087.8 ± 6.737.3 ± 5.039.5 ± 2.855.5 ± 10.595.8 ± 2.093.8 ± 4.1
Mod. Arithm. w/()83.0 ± 5.581.8 ± 4.758.3 ± 3.748.7 ± 18.164.3 ± 0.570.0 ± 0.871.7 ± 2.5
Copy Memory7.9 ± 1.89.1 ± 4.7100.0 ± 0.043.2 ± 1.754.9 ± 5.999.0 ± 0.199.0 ± 0.0
NCA86.4 ± 0.685.0 ± 1.978.3 ± 0.570.5 ± 0.271.1 ± 0.176.9 ± 1.178.0 ± 0.7
State Tracking (A5)99.3 ± 1.060.2 ± 44.95.6 ± 0.65.8 ± 0.55.5 ± 0.4100.0 ± 0.0100.0 ± 0.0

Key: bold = best result; italic = best result among linear RNN; bold italic = both.

The overall trend is not affected and our final conclusions still stand. This is evident from the summary table below, where the only rank change observed between our submitted results and our updated-for-rebuttal results is that on Modular Arithmetic (without brackets) some LSTM seeds completed the task early (we note the LSTM presents large variance in this task).

TaskSubmitted Top ModelsUpdated Top Models
MQARTransf.=GLA=KDA=BGLT=ΔBGLTTranfs.=GLA=KDA=BGLT=ΔBGLT
1-HopALLALL
4-HopsKDA=ΔBGLTKDA=ΔBGLT
Cycle NavALLALL
Mod. Arithm.BGLTLSTM>BGLT
Mod. Arithm. w/()LSTM>ΔBGLTLSTM>ΔBGLT
Copy MemoryTransf.=BGLT=ΔBGLTTransf.=BGLT=ΔBGLT
NCALSTM>ΔBGLTLSTM>ΔBGLT
A5LSTM=GRU=BGLT=ΔBGLTLSTM=GRU=BGLT=ΔBGLT

We point out that in the original submission, to provide an indication of seed-to-seed variation, we were reporting maximum and minimum results over the 3 seeds considered. In the case of these synthetic tasks, we believe maximum performance to be a more relevant metric than average performance, since the goal is to showcase the capability of a given model to solve a specific problem (ie, to represent the target function class). Nonetheless, we thank the reviewer for their suggested experimental improvements which help showcase the robustness of our synthetic tasks results.

W3: The main language model table includes Δ\DeltaBGLT but not plain BGLT

We agree with the reviewer that the additional ablation is relevant: to address this, we report a small-scale (1.5B) result including BGLT below

Model#SeedsCELMB. pplWiki. pplLMB. accPIQA accHella. acc_nWino. accARC-e accARC-c acc_nAvg.SWDEFDASQuADTQAAvg.
Transformer++31.8763 ± 0.00057.31 ± 0.1215.26 ± 0.0358.1 ± 0.675.9 ± 0.364.7 ± 0.261.6 ± 0.172.4 ± 0.240.2 ± 1.362.2 ± 0.256.9 ± 1.573.4 ± 0.949.7 ± 0.666.0 ± 0.861.5 ± 0.2
KDA31.8529 ± 0.00166.37 ± 0.0314.97 ± 0.0859.8 ± 0.376.2 ± 0.166.3 ± 0.163.8 ± 1.575.3 ± 0.442.1 ± 1.363.9 ± 0.246.4 ± 2.052.8 ± 4.947.4 ± 0.364.6 ± 0.952.8 ± 1.9
BGLT31.8526 ± 0.00076.25 ± 0.0614.97 ± 0.0360.0 ± 0.576.4 ± 0.366.7 ± 0.364.0 ± 1.574.7 ± 0.841.7 ± 1.563.9 ± 0.345.8 ± 2.749.6 ± 10.747.3 ± 1.664.8 ± 0.651.9 ± 3.7
Δ\DeltaBGLT31.8523 ± 0.00036.34 ± 0.0414.82 ± 0.1059.9 ± 0.776.3 ± 0.567.0 ± 0.564.3 ± 0.674.9 ± 0.342.4 ± 1.164.1 ± 0.542.9 ± 5.646.0 ± 8.344.6 ± 2.363.5 ± 2.849.3 ± 4.7

However, we point out the difficulty in highlighting performance gaps: at small scale (like the 1.5B we report above), the three cells behave pretty much indistinguishably (PPL generally follows the expected order KDA ~= BGLT < Δ\DeltaBGLT, but differences remain within seed variance), and performance differences begin to arise only at larger scales (see the original Tab2 in the paper: Δ\DeltaBGLT starts gaining ground over KDA on recall tasks at 3B+). A meaningful ablation, then, should be conducted at the 7B scale, but this requires substantial number of GPUh. For this reason, in the paper we prioritized KDA and Δ\DeltaBGLT, as they’re the direct competitors (since they both implement the DeltaRule correction) as well as the best performing models, which makes their direct comparison the most relevant one.


Q3: Could you reconcile the full-chunk condition number with the prefix condition number in its proof?

The goal of Lem3 is to showcase how relying on matrix inversion for gate factorization is not a viable approach, as it imposes tight constraints on each gate’s spectrum (σ∈[0.83,1]\sigma\in[0.83,1] for fp32 gates, see TabB1b), thus further justifying our inverse-free approach. Indeed, the matrix inversion approach requires inverting a product of gates: this operation incurs a loss of numerical precision which scales with the condition number of said product, which in turn depends on the ratio of its larger and smaller singular values. In our proof, we consider a worst-case scenario where, for each gate, σmax=1\sigma_{max}=1 (larger values are not viable due to stability considerations) and σmin=σ\sigma_{min}=\sigma (the one free parameter we can change to increase the range of the gates), and the corresponding singular vectors are aligned, so that the condition number of the product of gates directly depends on the product of singular values of the individual gates. Since in the chunkwise formulation we multiply up to CC such gates together, the bound depends on σC\sigma^C. While this is a worst-case scenario, it can easily verify itself in the case of repeated tokens, meaning it can very well be encountered in practice. We assume the confusion comes from the fact that we directly jumped to considering κ(GnS→nE)\kappa(G_{n_S\to n_E}) without passing by max⁡tκ(GnS→t)\max_t\kappa(G_{n_S\to t}) first, but we will make sure to illustrate these passages more in detail, and we thank the reviewer for the recommendation.


Q3b: Please qualify the scaling claim

We believe the reviewer refers to L402-404 in our paper, where we claim “On general language modeling, Δ\DeltaBGLT performs on average better than KDA, the gap widening with model scale”. We agree this is not true for all metrics considered (avg downstream task performance goes from 67.9 vs 68.8 at 3B to a more modest 71.9 vs 72 at 7B), so we will drop the “the gap widening with model scale” claim accordingly, and thank the reviewer for pointing this out.

Dear Reviewer NgEX,

Thank you again for your review and the time you spent on our paper. As the discussion period draws to a close, we wanted to follow up on our rebuttal. In response to your comments, we corrected the backward-pass pseudo-code and clarified the intermediate-tile contributions, reran all synthetic tasks with 6 seeds and separate validation and test splits, added a 3-seed comparison of BGLT vs Δ\DeltaBGLT at 1.5B, and revised the Lem3 proof and the scaling claim.

If you feel these revisions address your concerns, we would be grateful if you could consider updating your score. If anything remains unclear or insufficiently addressed, we would be happy to continue the discussion.

Best regards, The authors

Comments on the paper

1 comment
AuthorsOpenReview ↗

Summary of contributions and rebuttal

We thank the reviewers for their time and feedback, which helped improve the paper. Below we summarize our contributions, how these were recognized by the reviewers, and how their concerns were addressed.

Contributions

Every major step in the evolution of Linear Transformers has been achieved by designing efficient algorithms for large-scale training for gates with ever-richer structures (scalar -> diagonal -> diagonal plus low-rank). With this work, we unlock the natural next step in boosting expressivity, allowing the use of block-diagonal gates. In doing this, we provide:

  1. A generalized, stable, chunk-wise parallel algorithm for arbitrary block-diagonal transitions, based on local factorization and hierarchical tiling (Sec3.1)
  2. Dedicated, optimized CuTe kernels for its deployment at scale, plus improvements over existing kernels for DeltaRule application, which achieve runtimes comparable to KDA, arguably the current state-of-the-art (codebase soon to be released)
  3. BGLT, a Linear RNN cell with block-diagonal gates, together with the parameterization and initialization recipes to make it stably trainable at scale, at parameter count comparable with existing baselines
  4. Empirical validation on a number of synthetic tasks, and on language modeling up to 7B model size, showing that:
    • On synthetic tasks, a single Δ\DeltaBGLT layer consistently matches or outperforms KDA, confirming the superior expressive power granted by more complex gating mechanisms
    • On language modelling, at 7B, Δ\DeltaBGLT is a competitive LLM, matching KDA on general LM tasks and improving upon it in perplexity and recall tasks (the latter being the main weakness of linear RNNs relative to Transformers)

What reviewers recognized

The reviewers appreciated the paper, all three of them recommending acceptance and praising its clarity and significance:

The algorithm "expands the state-transition structures compatible with practical parallel training" (vrgz) and "allows chunked training with general block-diagonal transitions, including gates that are not invertible" (NgEX)

The problem is "technically important and well motivated," addressing "the fundamental challenge of efficiently parallelizing the training of more expressive recurrent structures"; "the core algorithmic contribution is clearly defined" (Trsx)

The evaluation covers "synthetic tasks, large-scale language modeling, parameterization ablations, and detailed efficiency measurements" (vrgz), and "the synthetic results demonstrate substantial potential" (Trsx)

Concerns raised and how we addressed them

  • Statistical reliability of synthetic tasks results (NgEX, Trsx). We ran synthetic tasks again using 6 seeds (up from 3), and separating validation and test sets for early stopping and evaluation. We now report mean ± std (TabD1). Our conclusions are unchanged
  • Statistical reliability of LM results (Trsx). We added bootstrapped std for all 1.5B/3B/7B results in Tab2, and re-run 3-seed runs at 1.5B to report seed-to-seed variance. At 7B, Δ\DeltaBGLT's gains over KDA in perplexity and recall are statistically significant
  • Component ablations (NgEX, Trsx)
    • We added a 3-seed comparison of BGLT vs Δ\DeltaBGLT at 1.5B
    • We added a non-Kronecker block ablation (TabD3), showing our currently-deployed Kronecker factorization maintains accuracy on synthetic tasks, while reducing parameter count and memory use
    • We pointed to the existing SVD vs L∞L_\infty-normalization parameterization ablation (AppC2)
    • We added a table detailing the expressivity, cost and kernel trade-offs of alternative block structures
    • We clarified that our inverse-free algorithm for generalized attention assembly cannot impact model quality, as it computes the exact same target quantity (but in a stable manner): this is what makes block-diagonal gates trainable at scale in the first place
  • Efficiency and cost (vrgz, Trsx)
    • We clarified our claim: making a more expressive gate structure trainable at scale with overhead comparable to KDA, and not outperforming specialized kernels for simpler gates
    • We clarified that our comparisons are at matched parameters (~1% of KDA in FLOPs, so effectively compute-matched), and thus we are following standard practices
    • We highlighted profiling details to better surface that the timing comparisons are fair: we match hardware and datatypes, conduct comparisons under different settings (batch size / sequence lengths), and levels (cell, layer, model), and the KDA baseline uses a heavily optimized, production-ready algorithm
  • Corrections to appendix derivations (NgEX). We fixed the index mismatch in Alg4, added an explicit treatment of intermediate tiles contribution, and expanded the steps of Lem3. Code implementation was always verified against PyTorch autograd and was not impacted by this

We believe these revisions address the concerns raised by the reviewers, and thank them again for their input.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.