Padding Bounds for Transformer CFL Recognition

Interactive visualization of padding requirements for transformer-based context-free language recognition. Based on Jerad et al. (2026).

128
1.0x

Padding Scaling (Log-Log)

Depth vs Padding Tradeoff

Utilization at Upper Bound

Bounds Summary

ClassUpper BoundEmpiricalGap
GeneralO(n6)~n5.7~0.3
UnambiguousO(n3)~n2.7~0.3
LinearO(n2)~n1.7~0.3

Key Findings

Not Tight All three bounds show a consistent gap of ~0.3 in the exponent, suggesting room for improvement.
Log Factor The gap is primarily due to the O(log n) depth factor not being fully exploited.
Tradeoff Increasing depth by k reduces padding by factor k, suggesting depth-efficient algorithms could close the gap.