[2505.20278] Characterizing Pattern Matching and Its Limits on Compositional Task Structures

Computer Science > Machine Learning arXiv:2505.20278 (cs) [Submitted on 26 May 2025 (v1), last revised 2 Mar 2026 (this version, v3)] Title:Characterizing Pattern Matching and Its Limits on Compositional Task Structures Authors:Hoyeon Chang, Jinho Park, Hanseul Cho, Sohee Yang, Miyoung Ko, Hyeonbin Hwang, Seungpil Won, Dohaeng Lee, Youbin Ahn, Minjoon Seo View a PDF of the paper titled Characterizing Pattern Matching and Its Limits on Compositional Task Structures, by Hoyeon Chang and 9 other authors View PDF HTML (experimental) Abstract:Despite impressive capabilities, LLMs' successes often rely on pattern-matching behaviors, yet these are also linked to OOD generalization failures in compositional tasks. However, behavioral studies commonly employ task setups that allow multiple generalization sources (e.g., algebraic invariances, structural repetition), obscuring a precise and testable account of how well LLMs perform generalization through pattern matching and their limitations. To address this ambiguity, we first formalize pattern matching as functional equivalence, i.e., identifying pairs of subsequences of inputs that consistently lead to identical results when the rest of the input is held constant. Then, we systematically study how decoder-only Transformer and Mamba behave in controlled tasks with compositional structures that isolate this mechanism. Our formalism yields predictive and quantitative insights: (1) Instance-wise success of pattern matching is well pr...