TL;DR
ALICE is an encoder-only Transformer that solves monoalphabetic substitution ciphers in a single forward pass, setting a new state-of-the-art for accuracy and decoding speed. By introducing a differentiable bijective decoding head via Gumbel-Sinkhorn permutations, ALICE guarantees valid one-to-one character mappings, enables direct key recovery, and achieves general cryptogram-solving ability after training on just ~1,500 ciphers—a mere $3.7 \times 10^{-24}$ fraction of the $26!$ combinatorial search space.
What Problem Does This Paper Address?
Monoalphabetic substitution ciphers (cryptograms) replace each letter in an alphabet with a distinct substitute character. Inferring the unknown inverse cipher $f^{-1}$ from ciphertext alone requires navigating a combinatorial space of $26! \approx 4 \times 10^{26}$ possible bijections.
Traditional solvers rely on heavy heuristic beam search or dictionary attacks, while existing neural models use autoregressive, character-by-character decoding or handcrafted frequency features. Meanwhile, standard large language models (LLMs) frequently hallucinate, omit characters, or violate bijectivity (mapping multiple ciphertext symbols to the same plaintext character). The authors leverage cryptograms as an ideal testbed to explore how neural networks learn structured reasoning, generalize across combinatorial spaces, and maintain structural constraints.
Methods
ALICE (Architecture for Learning Interpretable Cryptogram dEcipherment) is a non-autoregressive encoder-only Transformer based on a LLaMA-style backbone (pre-layer RMSNorm, SwiGLU activations, and Rotary Position Embeddings). The authors explore two primary variants and architectural components:
- Symbol-Wise Token Pooling: Standard contextual embeddings make identical characters vary across positions. To enforce consistency, ALICE pools (averages) embeddings for each unique symbol prior to decoding.
- ALICE-BASE: Uses standard linear classification over pooled states to predict output tokens independently.
- ALICE-BIJECTIVE: Enforces strict bijectivity. A cross-attention layer condenses representations into alphabet-sized dimensions, followed by the Gumbel-Sinkhorn algorithm during training to output a differentiable, doubly stochastic relaxation of a permutation matrix. At inference time, it solves a linear assignment problem to yield a discrete, valid permutation matrix $P^*$, providing direct access to the inferred cipher key.
- Interpretability via Early-Exits & Probing: The authors employ layer-wise early exits and train linear/MLP probes across intermediate layers to measure $n$-gram cosine similarity against true plaintexts.
Datasets
- QUOTES500K: ~500,000 English quotes filtered to lengths between 15 and 300 characters (97.5% training, 2.5% unseen testing). Substitution ciphers are generated randomly on-the-fly during training.
- Multilingual Corpus (OSCAR subset): 25,000 segments (~256 characters each) across seven languages: English, French, German, Italian, Latin, Portuguese, and Spanish, with accents normalized.
- Historical Benchmark (Borg Cipher): Evaluated on a 256-character excerpt from page 0011v of the 17th-century Latin Borg cipher without providing the model with language metadata.
Key Insights and Ideas
- Phase Change in Combinatorial Generalization: When training on fixed pools of ciphers, the model transitions sharply from memorization to generalization between 1,000 and 1,500 training ciphers. Training on only 1,500 unique ciphers ($3.7 \times 10^{-24}$ of all possibilities) is sufficient to decrypt entirely unseen ciphers with near-perfect accuracy.
- Human-Like Layerwise Reasoning: Layer-by-layer probing reveals that early layers focus heavily on 1-grams (matching letter frequencies), while middle and deeper layers progressively assemble higher-order $n$-grams (words and grammatical phrases).
- Direct Interpretability Over Attention Maps: Instead of analyzing noisy attention weights across hundreds of heads, ALICE-BIJECTIVE explicitly parameterizes the decryption key as a permutation matrix, allowing direct visualization of cipher hypotheses at every layer.
- Static vs. Dynamic Embeddings: Testing an embedding hypernetwork (ALICE-DYNAMIC) to dynamically adjust input embeddings yielded no performance gain over static embeddings, demonstrating that standard Transformer backbones naturally handle context-dependent token semantics.
Key Results
- Decryption Accuracy: On short English sequences ($<128$ characters), ALICE-BASE achieves a Symbol Error Rate (SER) of 1.09%, an 86% relative error reduction compared to the prior state-of-the-art seq2seq model (7.68%). ALICE-BIJECTIVE achieves 1.27%. On longer sequences ($>128$ characters), both variants achieve an SER of 0.06%.
- Historical Decipherment: On the Latin Borg cipher, multilingual ALICE-BASE achieves an error rate of 2.80%, outperforming causal LM baselines (4.10%) and seq2seq models (5.47%).
- Inference Speed: Because ALICE decodes in a single forward pass, it processes 1.2 million letters/second on an NVIDIA H100 (and 140,000 letters/second for ALICE-BIJECTIVE). Prior neural methods operate around 400 letters/second on an NVIDIA V100.
Limitations and Future Work
- Cipher Scope: The current implementation focuses strictly on monoalphabetic substitution ciphers and does not address polyalphabetic (e.g., Vigenère) or homophonic ciphers where one plaintext letter maps to multiple ciphertext symbols.
- Short-Sequence Accuracy Tradeoff: ALICE-BIJECTIVE performs slightly worse than ALICE-BASE on very short texts ($<32$ characters), where ciphertexts fall below the English unicity distance and lack sufficient information for unique decryption.
- Optimization Strategy: Sinkhorn temperature ($\tau = 4.75$) and iterations ($\ell = 6$) were held constant; annealing schedules could potentially improve convergence and accuracy.
- Broader Domains: The authors suggest applying the bijective decoding module to other structured problems involving permutation learning and bipartite matching.