Do Large Language Models Learn Order-Dependent Rules?

Can large language models (LLMs) capture sequential structure when outcomes depend on order? Theoretically and experimentally, we prove that ordered-compliance inherently leaks information through frequency patterns, creating predictive shortcuts that allow models to succeed without truly capturing causal sequential structure. To isolate true order learning, we introduce a shortcut-auditing protocol that quantifies the predictive power of non-sequential features (e.g., k-grams, pair counts) under label noise. We develop a controlled, semantic-free sequence framework with three mechanisms over a hidden set of key letters: ordered compliance, driven by key order at a fixed lag; global-property compliance, driven by the parity of the total key count; and key-inversion parity, driven by the parity of key-order inversions. Empirically, encoder and recurrent models reach the theoretical optimum (measured by AUC and F1) on ordered-compliance more efficiently than fine-tuned decoder-only LLMs. On global-property compliance, the tested sequence models remain near chance under standard training unless explicitly guided on feature relevance. On key-inversion parity, recurrent and transformer models can solve the task with four keys, while all tested models remain near chance with six. Our results demonstrate that high-quality performance on order-sensitive tasks often masks shortcut exploitation.