{"total":93,"rows":[{"id":"2305.15408","title":"Towards Revealing the Mystery behind Chain of Thought: A Theoretical Perspective","created":"2023-05-24","cited_by_count":294,"area":"lr"},{"id":"2402.12875","title":"Chain of Thought Empowers Transformers to Solve Inherently Serial Problems","created":"2024-02-20","cited_by_count":260,"area":"lr"},{"id":"2207.02098","title":"Neural Networks and the Chomsky Hierarchy","created":"2022-07-05","cited_by_count":217,"area":null},{"id":"2207.00729","title":"The Parallelism Tradeoff: Limitations of Log-Precision Transformers","created":"2022-07-02","cited_by_count":193,"area":null},{"id":"2404.08819","title":"The Illusion of State in State-Space Models","created":"2024-04-12","cited_by_count":187,"area":null},{"id":"2306.02896","title":"Representational Strengths and Limitations of Transformers","created":"2023-06-05","cited_by_count":133,"area":null},{"id":"2311.00208","title":"What Formal Languages Can Transformers Express? A Survey","created":"2023-11-01","cited_by_count":124,"area":null},{"id":"2305.16843","title":"Randomized Positional Encodings Boost Length Generalization of Transformers","created":"2023-05-26","cited_by_count":117,"area":null},{"id":"2402.09963","title":"Why are Sensitive Functions Hard for Transformers?","created":"2024-02-15","cited_by_count":74,"area":null},{"id":"2211.12316","title":"Simplicity Bias in Transformers and their Ability to Learn Sparse Boolean Functions","created":"2022-11-22","cited_by_count":70,"area":null},{"id":"2210.02671","title":"A Logic for Expressing Log-Precision Transformers","created":"2022-10-06","cited_by_count":67,"area":"lr"},{"id":"2405.18512","title":"Understanding Transformer Reasoning Capabilities via Graph Algorithms","created":"2024-05-28","cited_by_count":67,"area":"lr"},{"id":"2301.10743","title":"Tighter Bounds on the Expressivity of Transformer Encoders","created":"2023-01-25","cited_by_count":66,"area":null},{"id":"2402.18510","title":"RNNs are not Transformers (Yet): The Key Bottleneck on In-context Retrieval","created":"2024-02-28","cited_by_count":64,"area":null},{"id":"2310.07923","title":"The Expressive Power of Transformers with Chain of Thought","created":"2023-10-11","cited_by_count":50,"area":"lr"},{"id":"2310.13897","title":"Masked Hard-Attention Transformers Recognize Exactly the Star-Free Languages","created":"2023-10-21","cited_by_count":49,"area":null},{"id":"2307.14023","title":"Are Transformers with One Layer Self-Attention Using Low-Rank Weight Matrices Universal Approximators?","created":"2023-07-26","cited_by_count":47,"area":null},{"id":"2210.14698","title":"Autoregressive Structured Prediction with Language Models","created":"2022-10-26","cited_by_count":43,"area":null},{"id":"2306.01128","title":"Learning Transformer Programs","created":"2023-06-01","cited_by_count":41,"area":"mechinterp"},{"id":"2407.01178","title":"$\\text{Memory}^3$: Language Modeling with Explicit Memory","created":"2024-07-01","cited_by_count":40,"area":"rag"},{"id":"2310.03817","title":"Logical Languages Accepted by Transformer Encoders with Hard Attention","created":"2023-10-05","cited_by_count":38,"area":null},{"id":"2502.19249","title":"Between Circuits and Chomsky: Pre-pretraining on Formal Languages Imparts Linguistic Biases","created":"2025-02-26","cited_by_count":37,"area":null},{"id":"2310.07096","title":"Sparse Universal Transformer","created":"2023-10-11","cited_by_count":32,"area":"moe"},{"id":"2404.14994","title":"Transformers Can Represent $n$-gram Language Models","created":"2024-04-23","cited_by_count":32,"area":null},{"id":"2406.09347","title":"Separations in the Representational Capabilities of Transformers and Recurrent Architectures","created":"2024-06-13","cited_by_count":29,"area":null},{"id":"2411.07602","title":"Circuit Complexity Bounds for RoPE-based Transformer Architecture","created":"2024-11-12","cited_by_count":26,"area":null},{"id":"2405.20131","title":"Language Models Need Inductive Biases to Count Inductively","created":"2024-05-30","cited_by_count":25,"area":null},{"id":"2502.12317","title":"Can Language Models Learn Typologically Implausible Languages?","created":"2025-02-17","cited_by_count":23,"area":null},{"id":"2402.04084","title":"Provably learning a multi-head attention layer","created":"2024-02-06","cited_by_count":21,"area":null},{"id":"2412.06148","title":"The Computational Limits of State-Space Models and Mamba via the Lens of Circuit Complexity","created":"2024-12-09","cited_by_count":21,"area":"ssm"},{"id":"2310.16076","title":"Practical Computational Power of Linear Transformers and Their Recurrent and Self-Referential Extensions","created":"2023-10-24","cited_by_count":20,"area":null},{"id":"2402.13934","title":"Do Efficient Transformers Really Save Computation?","created":"2024-02-21","cited_by_count":20,"area":null},{"id":"2505.18948","title":"Exact Expressive Power of Transformers with Padding","created":"2025-05-25","cited_by_count":19,"area":"lr"},{"id":"2505.23623","title":"Characterizing the Expressivity of Fixed-Precision Transformer Language Models","created":"2025-05-29","cited_by_count":14,"area":null},{"id":"2507.12549","title":"The Serial Scaling Hypothesis","created":"2025-07-16","cited_by_count":13,"area":null},{"id":"2503.01805","title":"Depth-Width tradeoffs in Algorithmic Reasoning of Graph Tasks with Transformers","created":"2025-03-03","cited_by_count":11,"area":null},{"id":"2411.01992","title":"Ask, and it shall be given: On the Turing completeness of prompting","created":"2024-11-04","cited_by_count":10,"area":null},{"id":"2501.04299","title":"Circuit Complexity Bounds for Visual Autoregressive Model","created":"2025-01-08","cited_by_count":10,"area":null},{"id":"2503.14615","title":"Unique Hard Attention: A Tale of Two Sides","created":"2025-03-18","cited_by_count":10,"area":null},{"id":"2410.04271","title":"Fundamental Limitations on Subquadratic Alternatives to Transformers","created":"2024-10-05","cited_by_count":9,"area":"ssm"},{"id":"2505.11199","title":"The Counting Power of Transformers","created":"2025-05-16","cited_by_count":9,"area":null},{"id":"2404.02040","title":"Transformers as Transducers","created":"2024-04-02","cited_by_count":8,"area":null},{"id":"2503.16048","title":"Meta-Learning Neural Mechanisms rather than Bayesian Priors","created":"2025-03-20","cited_by_count":8,"area":null},{"id":"2505.21024","title":"Pause Tokens Strictly Increase the Expressivity of Constant-Depth Transformers","created":"2025-05-27","cited_by_count":8,"area":null},{"id":"2603.03612","title":"Why Are Linear RNNs More Parallelizable?","created":"2026-03-04","cited_by_count":8,"area":null},{"id":"2402.15478","title":"Transformers are Expressive, But Are They Expressive Enough for Regression?","created":"2024-02-23","cited_by_count":6,"area":null},{"id":"2501.12997","title":"Ehrenfeucht-Haussler Rank and Chain of Thought","created":"2025-01-22","cited_by_count":6,"area":"lr"},{"id":"2503.01544","title":"Compositional Reasoning with Transformers, RNNs, and Chain of Thought","created":"2025-03-03","cited_by_count":6,"area":"lr"},{"id":"2510.00368","title":"The Transformer Cookbook","created":"2025-10-01","cited_by_count":6,"area":null},{"id":"2512.25014","title":"Diffusion Language Models are Provably Optimal Parallel Samplers","created":"2025-12-31","cited_by_count":6,"area":"diffusion"},{"id":"2402.00976","title":"Investigating Recurrent Transformers with Dynamic Halt","created":"2024-02-01","cited_by_count":5,"area":null},{"id":"2405.18548","title":"Transformer Encoder Satisfiability: Complexity and Impact on Formal Reasoning","created":"2024-05-28","cited_by_count":5,"area":null},{"id":"2410.10101","title":"Learning Linear Attention in Polynomial Time","created":"2024-10-14","cited_by_count":5,"area":null},{"id":"2602.05896","title":"Parity, Sensitivity, and Transformers","created":"2026-02-05","cited_by_count":5,"area":null},{"id":"2403.09728","title":"Simulating Weighted Automata over Sequences and Trees with Transformers","created":"2024-03-12","cited_by_count":4,"area":null},{"id":"2407.00075","title":"Logicbreaks: A Framework for Understanding Subversion of Rule-based Inference","created":"2024-06-21","cited_by_count":4,"area":"safety"},{"id":"2510.19315","title":"Transformers are Inherently Succinct","created":"2025-10-22","cited_by_count":4,"area":null},{"id":"2512.00003","title":"Efficient Turing Machine Simulation with Transformers","created":"2025-09-28","cited_by_count":4,"area":"lr"},{"id":"2601.01754","title":"Context-Free Recognition with Transformers","created":"2026-01-05","cited_by_count":4,"area":null},{"id":"2412.20195","title":"Lower bounds on transformers with infinite precision","created":"2024-12-28","cited_by_count":3,"area":null},{"id":"2503.10542","title":"Language Models, Graph Searching, and Supervision Adulteration: When More Supervision is Less and How to Make More More","created":"2025-03-13","cited_by_count":3,"area":null},{"id":"2509.09001","title":"Fast attention mechanisms: a tale of parallelism","created":"2025-09-10","cited_by_count":3,"area":null},{"id":"2602.11175","title":"Barriers to Discrete Reasoning with Transformers: A Survey Across Depth, Exactness, and Bandwidth","created":"2026-01-19","cited_by_count":3,"area":null},{"id":"2309.00857","title":"Evaluating Transformer's Ability to Learn Mildly Context-Sensitive Languages","created":"2023-09-02","cited_by_count":2,"area":null},{"id":"2405.04515","title":"A Transformer with Stack Attention","created":"2024-05-07","cited_by_count":2,"area":null},{"id":"2509.10414","title":"Is In-Context Learning Learning?","created":"2025-09-12","cited_by_count":2,"area":null},{"id":"2601.19467","title":"On the Expressiveness of State Space Models via Temporal Logics","created":"2026-01-27","cited_by_count":2,"area":null},{"id":"2605.22471","title":"Lost in Tokenization: Fundamental Trade-offs in Graph Tokenization for Transformers","created":"2026-05-21","cited_by_count":2,"area":null},{"id":"2212.08482","title":"Implementation of general formal translators","created":"2022-12-16","cited_by_count":1,"area":null},{"id":"2312.09048","title":"On The Expressivity of Recurrent Neural Cascades","created":"2023-12-14","cited_by_count":1,"area":null},{"id":"2406.05564","title":"Automata Extraction from Transformers","created":"2024-06-08","cited_by_count":1,"area":null},{"id":"2407.10949","title":"Representing Rule-based Chatbots with Transformers","created":"2024-07-15","cited_by_count":1,"area":null},{"id":"2411.06403","title":"Overcoming a Learning Bottleneck in Impartial Games: A Circuit Complexity Approach","created":"2024-11-10","cited_by_count":1,"area":null},{"id":"2506.08978","title":"Propositional Logic for Probing Generalization in Neural Networks","created":"2025-06-10","cited_by_count":1,"area":null},{"id":"2506.18739","title":"On the Existence of Universal Simulators of Attention","created":"2025-06-23","cited_by_count":1,"area":null},{"id":"2509.23912","title":"From Neural Networks to Logical Theories: The Correspondence between Fibring Modal Logics and Fibring Neural Networks","created":"2025-09-28","cited_by_count":1,"area":null},{"id":"2509.24024","title":"The Role of Logic and Automata in Understanding Transformers","created":"2025-09-28","cited_by_count":1,"area":null},{"id":"2602.02707","title":"Every Bit Counts: A Theoretical Study of Precision-Expressivity Tradeoffs in Quantized Transformers","created":"2026-02-02","cited_by_count":1,"area":null},{"id":"2604.25800","title":"Barriers to Universal Reasoning With Transformers (And How to Overcome Them)","created":"2026-04-28","cited_by_count":1,"area":"lr"},{"id":"2605.30523","title":"Revisiting Padded Transformer Expressivity: Which Architectural Choices Matter and Which Don't","created":"2026-05-28","cited_by_count":1,"area":null},{"id":"2606.17522","title":"An expressivity analysis of hierarchical modelling in deep transformers via bounded-depth grammars","created":"2026-06-16","cited_by_count":1,"area":null},{"id":"2608.04243","title":"Attention-based representations for multi-task computation","created":"2026-08-04","cited_by_count":1,"area":null},{"id":"2608.11909","title":"Disentangling the Expressivity of RoPE","created":"2026-08-12","cited_by_count":1,"area":null},{"id":"2608.27339","title":"Beyond Parallel Blindness: Information Floors and Model Gaps in Block Drafting","created":"2026-08-27","cited_by_count":1,"area":null},{"id":"2502.00197","title":"Learning Model Successors","created":"2025-01-31","cited_by_count":0,"area":null},{"id":"2503.20088","title":"Generative Linguistics, Large Language Models, and the Social Nature of Scientific Success","created":"2025-03-25","cited_by_count":0,"area":null},{"id":"2506.03370","title":"Comparison of different Unique hard attention transformer models by the formal languages they can recognize","created":"2025-06-03","cited_by_count":0,"area":null},{"id":"2605.04683","title":"Average Attention Transformers and Arithmetic Circuits","created":"2026-05-06","cited_by_count":0,"area":null},{"id":"2605.16640","title":"Provably Shorter Scratchpads in Hybrid DeltaNet-Attention Decoders","created":"2026-05-15","cited_by_count":0,"area":null},{"id":"2605.22964","title":"Certification from Examples is Hard for Circuits and Transformers under Minimal Overparametrization","created":"2026-05-21","cited_by_count":0,"area":null},{"id":"2607.29496","title":"Transcript-Managed Transformers: Monotone Multi-Agent Collapse and Universality with Two Pop-Enabled Transcripts","created":"2026-07-31","cited_by_count":0,"area":null},{"id":"2608.12671","title":"On the Expressive Power of Transformers","created":"2026-08-13","cited_by_count":0,"area":null},{"id":"2610.04569","title":"From Transformers to Weighted Automata: Towards the Verification of Large Language Models","created":"2026-10-03","cited_by_count":0,"area":null}],"next_cursor":null}