Abstract
Transformers have excelled in natural language processing and vision domains. This leads to the intriguing proposition: can Transformers be adapted to a more generalized framework, such as understanding general finite state machines? To explore this, we trained a Transformer network on compression algorithms such as Huffman and LZ4, viewing them as stepping stones towards mastering general finite state machines. Our analysis indicates that Transformers can adeptly internalize these methods and replicate essential states, echoing human-like interpretation via their attention mechanisms. This provides evidence of their capability to decipher practical finite state machines. Examining the attention maps offers insights into the Transformer’s methodology when engaging with these compression techniques. In Huffman encodings, the encoder predominantly focuses on input statistics to define the present state, which the decoder subsequently leverages to produce output bits. Remarkably, with a 2nd-order Markov input, the encoder’s attention is prominently directed at the previous two symbols, underscoring its proficiency in summarizing input statistics. The cross-attention maps further elucidate the exact association between input symbols and output bits. For the more complex LZ4 compression, the attention maps vividly portray the Transformer’s processing of input sequences and the close linkage between the input and resulting output bit stream. This study underscores the Transformer’s proficiency in comprehending compression algorithms and its keen ability to grasp input statistics, implying that its mechanisms, as illustrated by attention maps, provide profound interpretability.
Introduction
While Transformers have revolutionized Natural Language Processing (NLP), a lingering question remains: are they merely sophisticated statistical mimics, or can they be adapted to more generalized, rule-based frameworks? Specifically, can they master Finite State Machines (FSMs)—the backbone of many computational processes?
Researchers have demonstrated that Transformers can successfully learn and replicate deterministic compression algorithms like Huffman and LZ4, effectively treating them as practical FSMs. By analyzing attention maps, the study reveals that the model’s internal "reasoning" mirrors human-like logic: the encoder summarizes input statistics to define a "state," while the decoder uses that state to generate precise output bits.
Methods
The authors employed a standard Encoder-Decoder Transformer architecture and compared it against encoder-only and ablated (no self-attention) versions. These architectures were tested on three progressively difficult tasks to evaluate the model's ability to track states and internalize deterministic rules.
The study focused on visualizing average attention maps, specifically how self-attention (within the encoder) and cross-attention (between encoder and decoder) evolved during the learning process. This visualization serves as a window into the model's interpretability.
Datasets
The study used synthetically generated data to ensure controlled environments:
- Huffman Datasets: Created using random probability distributions across alphabet sizes of 5, 10, and 20, with sequence lengths up to 50.
- Markov Datasets: Generated using 1st and 2nd-order Markov chains to test the model's ability to track context.
- LZ4 Datasets: Specifically designed with repetitive patterns (e.g., 'abc', 'bca', 'aaa') to ensure the data was actually compressible, as i.i.d. data often results in incompressible LZ4 streams for short lengths.
Key Insights and Results
The experimental results demonstrate the Transformer's proficiency in comprehending compression algorithms:
- The "State-Generator" Encoder: In Markov-based tasks, the encoder’s self-attention was not random. For a 2nd-order Markov input, the model learned to attend specifically to the previous two symbols. This suggests the encoder acts as a "state-generating module," distilling raw input into a contextual summary.
- Division of Labor: The study highlights a clear functional split. The encoder handles the "what is the current state?" question, while the decoder focuses on the "what bit should I output?" task. This is evidenced by cross-attention maps showing a nearly perfect 1-to-1 correspondence between input symbols and their resulting binary codewords.
- LZ4 Block Recognition: Unlike the symbol-by-symbol nature of Huffman, LZ4 is block-based. The attention maps for LZ4 showed distinct "block-like" patterns, indicating the Transformer successfully learned to identify and group recurring units of data.
- Performance Metrics: The encoder-decoder model achieved near-perfect accuracy (>0.998) for Huffman coding and maintained high accuracy (>0.99) for Markov inputs. Despite the complexity of LZ4, the model achieved an accuracy of 0.943 with 8 attention heads.
- Architecture Comparison: The encoder-decoder model significantly outperformed the encoder-only model on longer sequences. Furthermore, ablation studies showed that without self-attention, the model's accuracy plummeted, proving its necessity for state tracking.
Conclusion
The authors acknowledge that while the model handles LZ4 well, it isn't perfect (94% vs 99%+ for Huffman). This is likely due to LZ4's various "heuristics"—rules that change based on whether a literal exceeds a certain length—which are harder for the model to generalize perfectly.
Future research could explore even more complex FSMs or attempt to "hard-code" the state-tracking logic discovered in these attention maps to create more efficient, specialized architectures for data processing. The study ultimately reinforces the idea that attention maps are not just decorative; they are a legitimate tool for reverse-engineering the "logic" of a trained Transformer.
Summary updated