Cover Image

Hardness of Learning Regular Languages in the Next Symbol Prediction Setting

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Bhattamishra, Satwik, Blunsom, Phil, Kanade, Varun
Format:	Preprint
Published:	2025
Subjects:	Machine Learning
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Separations in the Representational Capabilities of Transformers and Recurrent Architectures
by: Bhattamishra, Satwik, et al.
Published: (2024)

Provably Learning Attention with Queries
by: Bhattamishra, Satwik, et al.
Published: (2026)

Pause Tokens Strictly Increase the Expressivity of Constant-Depth Transformers
by: London, Charles, et al.
Published: (2025)

Discovering Interpretable Algorithms by Decompiling Transformers to RASP
by: Huang, Xinting, et al.
Published: (2026)

Inshrinkerator: Compressing Deep Learning Training Checkpoints via Dynamic Quantization
by: Agrawal, Amey, et al.
Published: (2023)

A Formal Framework for Understanding Length Generalization in Transformers
by: Huang, Xinting, et al.
Published: (2024)

Benefits and Limitations of Communication in Multi-Agent Reasoning
by: Rizvi-Martel, Michael, et al.
Published: (2025)

How Global Calibration Strengthens Multiaccuracy
by: Casacuberta, Sílvia, et al.
Published: (2025)

The Transformer Cookbook
by: Yang, Andy, et al.
Published: (2025)

On the Hardness of Learning Regular Expressions
by: Attias, Idan, et al.
Published: (2025)

DEEDEE: Fast and Scalable Out-of-Distribution Dynamics Detection
by: Aljaafari, Tala, et al.
Published: (2025)

Set Prediction for Next-Day Active Fire Forecasting
by: Bai, Yuchen, et al.
Published: (2026)

DyPP: Dynamic Parameter Prediction to Accelerate Convergence of Variational Quantum Algorithms
by: Kundu, Satwik, et al.
Published: (2023)

Security Concerns in Quantum Machine Learning as a Service
by: Kundu, Satwik, et al.
Published: (2024)

Neural Proposals, Symbolic Guarantees: Neuro-Symbolic Graph Generation with Hard Constraints
by: Geng, Chuqin, et al.
Published: (2026)

Explainable Machine Learning for Pediatric Dental Risk Stratification Using Socio-Demographic Determinants
by: Kanade, Manasi, et al.
Published: (2026)

Gating Enables Curvature: A Geometric Expressivity Gap in Attention
by: Bathula, Satwik, et al.
Published: (2026)

Inverse-Transpilation: Reverse-Engineering Quantum Compiler Optimization Passes from Circuit Snapshots
by: Kundu, Satwik, et al.
Published: (2025)

STIQ: Safeguarding Training and Inferencing of Quantum Neural Networks from Untrusted Cloud
by: Kundu, Satwik, et al.
Published: (2024)

Towards the Next Frontier in Speech Representation Learning Using Disentanglement
by: Krishna, Varun, et al.
Published: (2024)

Beyond Regularity: Modeling Chaotic Mobility Patterns for Next Location Prediction
by: Wu, Yuqian, et al.
Published: (2025)

Adversarial Threats in Quantum Machine Learning: A Survey of Attacks and Defenses
by: Ghosh, Archisman, et al.
Published: (2025)

AttackGNN: Red-Teaming GNNs in Hardware Security Using Reinforcement Learning
by: Gohil, Vasudev, et al.
Published: (2024)

Robust Learning of Diverse Code Edits
by: Aggarwal, Tushar, et al.
Published: (2025)

BAM! Just Like That: Simple and Efficient Parameter Upcycling for Mixture of Experts
by: Zhang, Qizhen, et al.
Published: (2024)

Recoverability Has a Law: The ERR Measure for Tool-Augmented Agents
by: Vuddanti, Sri Vatsa, et al.
Published: (2026)

How Reinforcement Learning After Next-Token Prediction Facilitates Learning
by: Tsilivis, Nikolaos, et al.
Published: (2025)

Agentic Risk-Aware Set-Based Engineering Design
by: Kumar, Varun, et al.
Published: (2026)

Next-Latent Prediction Transformers Learn Compact World Models
by: Teoh, Jayden, et al.
Published: (2025)

RegMix: Adversarial Mutual and Generalization Regularization for Enhancing DNN Robustness
by: Liu, Zhenyu, et al.
Published: (2025)

Hard Regularization to Prevent Deep Online Clustering Collapse without Data Augmentation
by: Mahon, Louis, et al.
Published: (2023)

Discovering Predictive Relational Object Symbols with Symbolic Attentive Layers
by: Ahmetoglu, Alper, et al.
Published: (2023)

SetPINNs: Set-based Physics-informed Neural Networks
by: Nagda, Mayank, et al.
Published: (2024)

T-SHRED: Symbolic Regression for Regularization and Model Discovery with Transformer Shallow Recurrent Decoders
by: Yermakov, Alexey, et al.
Published: (2025)

On the Hardness of Bandit Learning
by: Brukhim, Nataly, et al.
Published: (2025)

Adaptively Private Next-Token Prediction of Large Language Models
by: Flemings, James, et al.
Published: (2024)

Effects of Common Regularization Techniques on Open-Set Recognition
by: Rabin, Zachary, et al.
Published: (2024)

Compress the Easy, Explore the Hard: Difficulty-Aware Entropy Regularization for Efficient LLM Reasoning
by: Luo, Qin-Wen, et al.
Published: (2026)

Efficient Learning Under Density Shift in Incremental Settings Using Cramér-Rao-Based Regularization
by: Khan, Behraj, et al.
Published: (2025)

Evaluating Efficacy of Model Stealing Attacks and Defenses on Quantum Neural Networks
by: Kundu, Satwik, et al.
Published: (2024)