5 papers
Why Are Linear RNNs More Parallelizable?
William Merrill, Hongjian Jiang, Yanhong Li +2
The community is increasingly exploring linear RNNs (LRNNs) as language models, motivated by their expressive power and parallelizability. While prior work establishes the expressi…
Synthesis and Verification of Transformer Programs (Technical Report)
Hongjian Jiang, Matthew Hague, Philipp Rümmer +1
C-RASP is a simple programming language that was recently shown to capture concepts expressible by transformers. In this paper, we develop new algorithmic techniques for automatica…
Softmax Transformers are Turing-Complete
Hongjian Jiang, Michael Hahn, Georg Zetzsche +1
Hard attention Chain-of-Thought (CoT) transformers are known to be Turing-complete. However, it is an open problem whether softmax attention Chain-of-Thought (CoT) transformers are…
Extracting Robust Register Automata from Neural Networks over Data Sequences
Chih-Duo Hong, Hongjian Jiang, Anthony W. Lin +3
Automata extraction is a method for synthesising interpretable surrogates for black-box neural models that can be analysed symbolically. Existing techniques assume a finite input a…
HornStr: Invariant Synthesis for Regular Model Checking as Constrained Horn Clauses(Technical Report)
Hongjian Jiang, Anthony W. Lin, Oliver Markgraf +2
We present HornStr, the first solver for invariant synthesis for Regular Model Checking (RMC) with the specification provided in the SMT-LIB 2.6 theory of strings. It is well-known…