Unlocks parallelism in recurrent memory transformers through diagonal batching of the layers-segments grid, achieving 3.3x speedup on 131K-token sequences without model retraining.
Unlocks parallelism in recurrent memory transformers through diagonal batching of the layers-segments grid, achieving 3.3x speedup on 131K-token sequences without model retraining.
Diagonal Batching for Recurrent Memory Transformers
Core Concept
Recurrent Memory Transformers (RMTs) achieve linear time and constant memory complexity theoretically, but their sequential execution on GPUs undermines practical performance. The core bottleneck isn't algorithmic complexity—it's scheduling constraints that prevent GPU parallelism. Diagonal batching reorganizes the computation grid (layers × segments) into independent diagonals that can execute concurrently, unlocking substantial speedups without requiring model retraining or architectural changes.
Architecture Overview
Problem Identification: RMT sequential execution creates GPU idle time despite constant memory requirements
Diagonal Reorganization: Transforms (layer, segment) dependency graph into parallel-executable diagonals
Dependency Preservation: Maintains exact layer-level recurrence through grouped weight organization
GroupedGEMM Operations: Batches matrix multiplications across layers within diagonals
GPU Kernel Optimization: Single grouped kernel launch per diagonal layer replaces many individual launches
Zero Model Modification: Pure runtime optimization compatible with frozen pre-trained weights
Implementation
The following code demonstrates the diagonal batching algorithm:
"""
Generate list of diagonals where each diagonal contains
(layer, segment) pairs that can execute in parallel.
Constraint: segment_i depends on segment_{i-1} and layer_{l} depends on layer_{l-1}
Therefore: positions with constant (segment + layer) can run in parallel.
"""
# Iterate over all possible diagonal indices
for
in
range
self
self
1
# For each position (layer, segment), check if it's on this diagonal
for
in
range
self
# Valid if segment is in valid range
if
0
self
if
return
def
create_grouped_weights
self, model_layers: List[nn.Module]
"""
Stack layer weights for grouped GEMM execution.
Instead of [L, H, D, D] (individual layers), produces stacked weights
suitable for batched matrix multiplication.
"""
for
in
# Assume each layer has a weight matrix (e.g., attention projection)
"""
Execute grouped GEMM: multiple matrix multiplications in one kernel.
inputs: (B, D) or (B*num_selected_layers, D)
grouped_weights: (num_layers, D, D) or similar
batch_indices: which layers to execute
Returns: stacked outputs for all selected layers
"""
# Reshape for batched multiplication
0
len
1
# Batched matrix multiplication
# Using einsum for clarity: b (batch), l (layer), d (dimension)
len
'lbx,lxy->lby'
return
1
class
DiagonalRMT
"""
RMT with diagonal batching for efficient inference.
"""
def
__init__
self, num_layers: int, segment_length: int, hidden_dim: int = 1024
super
self
self
self
# Build standard RMT layers
self
8
4
True
True
for
in
range
self
1
# -1 = dynamic segments
self
None
def
prepare_grouped_weights
self
"""Pre-compute grouped weights for efficient execution."""
self, x: torch.Tensor, memory: List[torch.Tensor],
num_segments: int
Tuple
List
"""
Diagonal batching forward pass.
Reorganizes computation to run diagonals in parallel.
"""
# Reshape input into segments
self
1
self
# Generate diagonal schedule
self
self
self
# Process by diagonals
for
in
range
self
min
self
# Process this segment through all layers (using diagonal batching)
for
in
enumerate
# Collect all (layer, segment) pairs in this diagonal relevant to current segment
for
in
if
if
for
in
# Execute grouped GEMM for these layers
if
self
is
not
None
# This is simplified; actual implementation would handle memory states
for
in
self
# Concatenate all segments
1
return
def
forward
self, x: torch.Tensor, use_diagonal: bool = True
"""Main forward pass with optional diagonal batching."""
if
self
is
None
self
0
1
self
for
in
range
self
if
self
1
else
self
return
Practical Guidance
Diagonal Dependency Analysis: The key constraint is that computation at (layer l, segment s) depends only on (layer l-1, segment s) and (layer l, segment s-1). This creates the diagonal structure; verify your RMT variant satisfies this before applying diagonal batching.
GroupedGEMM Kernel Implementation: Modern frameworks like Triton or custom CUDA kernels can implement grouped matrix multiplication efficiently. For standard PyTorch, use torch.einsum or batched operations with proper reshaping.
Memory State Management: Keep per-layer memory states (recurrent state) on GPU between diagonal executions. Don't copy back to CPU; synchronize only at the end of inference.
Segment Length Tuning: Smaller segments (e.g., 512 tokens) create more parallelism but increase kernel launch overhead. Larger segments (e.g., 4096 tokens) reduce overhead but serialize more. Benchmark for your specific hardware.
Numerical Stability: Diagonal batching uses exact recurrence—numerical error is identical to sequential execution. No special stabilization required.
Hardware Compatibility: Works on any GPU supporting grouped matrix multiplication. H100, A100 show best results; older GPUs may have less efficient grouped GEMM kernels.
3.3× speedup over standard transformers on 131K-token sequences
1.8× improvement over sequential RMT implementations
Negligible error accumulation (<2% for 32K tokens)
The technique is particularly valuable for deploying long-context models in production where latency is critical, as it requires no model retraining or architectural modifications—it's a pure scheduling optimization.
