{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,3]],"date-time":"2026-02-03T01:39:00Z","timestamp":1770082740664,"version":"3.49.0"},"reference-count":63,"publisher":"Association for Computing Machinery (ACM)","issue":"2","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Knowl. Discov. Data"],"published-print":{"date-parts":[[2026,2,28]]},"abstract":"<jats:p>\n                    This work addresses a key challenge in the effective adoption of Recurrent Neural Networks (RNNs) by reducing inference time and expanding the scope of a prediction. It introduces compressed learning, a novel approach that integrates Context-Free Grammar (CFG) and online tokenization into the training and inference of RNNs for streaming inputs. Through a hierarchical compression algorithm, it compresses an input sequence to a CFG and makes predictions based on the compressed sequence. Its algorithm design employs a set of techniques to overcome the issues from the myopic nature of online tokenization, the tension between inference accuracy and compression rate, and other complexities in sequence compression and prediction. Its effectiveness is theoretically analyzed and empirically validated on 16 real-world sequences, including program function calls, memory traces, and system logs. Empirical results demonstrate that compressed learning can successfully recognize and leverage repetitive patterns in input sequences, and effectively translate them into dramatic (1\u20131,762\n                    <jats:inline-formula content-type=\"math\/tex\">\n                      <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\times\\)<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    ) inference speedups as well as much (1\u20137,830\n                    <jats:inline-formula content-type=\"math\/tex\">\n                      <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\times\\)<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    ) expanded prediction scope, while keeping the inference accuracy satisfactory.\n                  <\/jats:p>","DOI":"10.1145\/3785464","type":"journal-article","created":{"date-parts":[[2025,12,18]],"date-time":"2025-12-18T16:01:56Z","timestamp":1766073716000},"page":"1-22","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Recurrent Neural Networks Meet Context-Free Grammar: Two Birds with One Stone"],"prefix":"10.1145","volume":"20","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9128-2231","authenticated-orcid":false,"given":"Hui","family":"Guan","sequence":"first","affiliation":[{"name":"College of Information and Computer Sciences, University of Massachusetts, Amherst, Massachusetts, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0005-6654-6617","authenticated-orcid":false,"given":"Umang","family":"Chaudhary","sequence":"additional","affiliation":[{"name":"College of Information and Computer Sciences, University of Massachusetts, Amherst, Massachusetts, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4165-9138","authenticated-orcid":false,"given":"Yuanchao","family":"Xu","sequence":"additional","affiliation":[{"name":"North Carolina State University, Raleigh, North Carolina, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9458-7946","authenticated-orcid":false,"given":"Lin","family":"Ning","sequence":"additional","affiliation":[{"name":"North Carolina State University, Raleigh, North Carolina, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1946-7105","authenticated-orcid":false,"given":"Lijun","family":"Zhang","sequence":"additional","affiliation":[{"name":"College of Information and Computer Sciences, University of Massachusetts, Amherst, Massachusetts, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3599-8010","authenticated-orcid":false,"given":"Xipeng","family":"Shen","sequence":"additional","affiliation":[{"name":"North Carolina State University, Raleigh, North Carolina, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2026,2,2]]},"reference":[{"key":"e_1_3_1_2_2","unstructured":"AmberMD. 2020. Molecular Modeling. Retrieved September 9 2020 from http:\/\/ambermd.org\/"},{"key":"e_1_3_1_3_2","unstructured":"Perl.Org. 2020. Perl Interpreter. Retrieved September 9 2020 from http:\/\/www.perl.org\/"},{"key":"e_1_3_1_4_2","unstructured":"ROMS. 2020. Regional Ocean Modeling System. Retrieved September 9 2020 from http:\/\/www.myroms.org\/"},{"key":"e_1_3_1_5_2","doi-asserted-by":"publisher","DOI":"10.1145\/3373376.3378498"},{"key":"e_1_3_1_6_2","doi-asserted-by":"publisher","DOI":"10.1145\/1553374.1553380"},{"key":"e_1_3_1_7_2","doi-asserted-by":"crossref","first-page":"46","DOI":"10.1145\/3159652.3159727","volume-title":"Proceedings of the Eleventh ACM International Conference on Web Search and Data Mining","author":"Beutel Alex","year":"2018","unstructured":"Alex Beutel, Paul Covington, Sagar Jain, Can Xu, Jia Li, Vince Gatto, and Ed. H. Chi. 2018. Latent cross: Making use of context in recurrent recommender systems. In Proceedings of the Eleventh ACM International Conference on Web Search and Data Mining, 46\u201354."},{"key":"e_1_3_1_8_2","doi-asserted-by":"publisher","DOI":"10.1145\/3307650.3322207"},{"key":"e_1_3_1_9_2","unstructured":"Philip Bille Anders Roy Christiansen Patrick Hagge Cording and Inge Li G\u00f8rtz. 2015. Finger search in grammar-compressed strings. arXiv:1507.02853. Retrieved from https:\/\/arxiv.org\/abs\/1507.02853"},{"key":"e_1_3_1_10_2","doi-asserted-by":"publisher","DOI":"10.1137\/130936889"},{"key":"e_1_3_1_11_2","doi-asserted-by":"crossref","first-page":"106","DOI":"10.1016\/j.ins.2019.01.035","article-title":"Gract: A grammar-based compressed index for trajectory data","volume":"483","author":"Brisaboa Nieves R.","year":"2019","unstructured":"Nieves R. Brisaboa, Adri\u00e1n G\u00f3mez-Brand\u00f3n, Gonzalo Navarro, and Jos\u00e9 R. Param\u00e1. 2019. Gract: A grammar-based compressed index for trajectory data. Information Sciences 483 (2019), 106\u2013135.","journal-title":"Information Sciences"},{"key":"e_1_3_1_12_2","doi-asserted-by":"publisher","DOI":"10.1145\/3217871.3217872"},{"key":"e_1_3_1_13_2","doi-asserted-by":"publisher","DOI":"10.1145\/1541880.1541882"},{"key":"e_1_3_1_14_2","doi-asserted-by":"crossref","first-page":"765","DOI":"10.1007\/11731139_89","volume-title":"Proceedings of the Pacific-Asia Conference on Knowledge Discovery and Data Mining","author":"Cheng Haibin","year":"2006","unstructured":"Haibin Cheng, Pang-Ning Tan, Jing Gao, and Jerry Scripps. 2006. Multistep-ahead time series prediction. In Proceedings of the Pacific-Asia Conference on Knowledge Discovery and Data Mining. Springer, 765\u2013774."},{"key":"e_1_3_1_15_2","doi-asserted-by":"publisher","DOI":"10.1145\/3441454"},{"key":"e_1_3_1_16_2","doi-asserted-by":"publisher","DOI":"10.1145\/381694.378840"},{"key":"e_1_3_1_17_2","first-page":"14","volume-title":"Proceedings of the 28th Annual International Symposium on Computer Architecture","author":"Collins Jamison D.","year":"2001","unstructured":"Jamison D. Collins, Hong Wang, Dean M. Tullsen, Christopher Hughes, Yong-Fong Lee, Dan Lavery, and John P. Shen. 2001. Speculative precomputation: Long-range prefetching of delinquent loads. In Proceedings of the 28th Annual International Symposium on Computer Architecture. IEEE, 14\u201325."},{"key":"e_1_3_1_18_2","doi-asserted-by":"crossref","first-page":"607","DOI":"10.1016\/j.neunet.2021.07.021","article-title":"Continual learning for recurrent neural networks: An empirical evaluation","volume":"143","author":"Cossu Andrea","year":"2021","unstructured":"Andrea Cossu, Antonio Carta, Vincenzo Lomonaco, and Davide Bacciu. 2021. Continual learning for recurrent neural networks: An empirical evaluation. Neural Networks 143 (2021), 607\u2013627.","journal-title":"Neural Networks"},{"key":"e_1_3_1_19_2","doi-asserted-by":"publisher","DOI":"10.3233\/ICG-2007-30403"},{"key":"e_1_3_1_20_2","volume-title":"Proceedings of the 11th International Conference on Learning Representations","author":"Del\u00e9tang Gr\u00e9goire","year":"2023","unstructured":"Gr\u00e9goire Del\u00e9tang, Anian Ruoss, Jordi Grau-Moya, Tim Genewein, Li Kevin Wenliang, Elliot Catt, Chris Cundy, Marcus Hutter, Shane Legg, Joel Veness, and Pedro A. Ortega. 2023. Neural networks and the Chomsky hierarchy. In Proceedings of the 11th International Conference on Learning Representations."},{"key":"e_1_3_1_21_2","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2015.2485980"},{"key":"e_1_3_1_22_2","first-page":"37","volume-title":"Proceedings of the International Symposium on High-Performance Parallel and Distributed Computing","author":"Dimitra Doudali Thaleia","year":"2019","unstructured":"Thaleia Dimitra Doudali, Sergey Blagodurov, Abhinav Vishnu, Sudhanva Gurumurthi, and Ada Gavrilovska. 2019. Kleio: A hybrid memory page scheduler with machine intelligence. In Proceedings of the International Symposium on High-Performance Parallel and Distributed Computing, 37\u201348."},{"key":"e_1_3_1_23_2","doi-asserted-by":"publisher","DOI":"10.1145\/3133956.3134015"},{"key":"e_1_3_1_24_2","doi-asserted-by":"publisher","DOI":"10.1207\/s15516709cog1402_1"},{"key":"e_1_3_1_25_2","unstructured":"Dan Fu and Gabriel Guimaraes. 2016. Using Compression to Speed Up Image Classification in Artificial Neural Networks. Retrieved from https:\/\/danfu.org\/files\/CompressionImageClassification.pdf"},{"issue":"2","key":"e_1_3_1_26_2","first-page":"23","article-title":"A new algorithm for data compression","volume":"12","author":"Gage Philip","year":"1994","unstructured":"Philip Gage. 1994. A new algorithm for data compression. C Users Journal 12, 2 (1994), 23\u201338.","journal-title":"C Users Journal"},{"key":"e_1_3_1_27_2","doi-asserted-by":"crossref","first-page":"1078","DOI":"10.1109\/ICDM51629.2021.00125","volume-title":"Proceedings of the 2021 IEEE International Conference on Data Mining (ICDM)","author":"Guan Hui","year":"2021","unstructured":"Hui Guan, Umang Chaudhary, Yuanchao Xu, Lin Ning, Lijun Zhang, and Xipeng Shen. 2021. Recurrent neural networks meet context-free grammar: Two birds with one stone. In Proceedings of the 2021 IEEE International Conference on Data Mining (ICDM). IEEE, 1078\u20131083."},{"key":"e_1_3_1_28_2","first-page":"3933","article-title":"Faster neural networks straight from jpeg","volume":"31","author":"Gueguen Lionel","year":"2018","unstructured":"Lionel Gueguen, Alex Sergeev, Ben Kadlec, Rosanne Liu, and Jason Yosinski. 2018. Faster neural networks straight from jpeg. In Advances in Neural Information Processing Systems, Vol. 31, 3933\u20133944.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_3_1_29_2","volume-title":"Proceedings of the International Conference on Machine Learning","author":"Hashemi Milad","year":"2018","unstructured":"Milad Hashemi, Kevin Swersky, Jamie Smith, Grant Ayers, Heiner Litz, Jichuan Chang, Christos Kozyrakis, and Parthasarathy Ranganathan. 2018. Learning memory access patterns. In Proceedings of the International Conference on Machine Learning."},{"key":"e_1_3_1_30_2","unstructured":"Shilin He Jieming Zhu Pinjia He and Michael R. Lyu. 2020. Loghub: A large collection of system log datasets towards automated log analytics. arXiv:2008.06448. Retrieved from https:\/\/arxiv.org\/abs\/2008.06448"},{"key":"e_1_3_1_31_2","doi-asserted-by":"publisher","DOI":"10.1145\/1346281.1346293"},{"key":"e_1_3_1_32_2","doi-asserted-by":"publisher","DOI":"10.1145\/1356058.1356071"},{"key":"e_1_3_1_33_2","unstructured":"Minje Kim. 2023. A Page Scheduler Using Machine Learning for Hybrid Memory Systems. Master\u2019s thesis. Ulsan National Institute of Science and Technology (UNIST) Ulsan South Korea. Retrieved from https:\/\/scholarworks.unist.ac.kr\/handle\/201301\/73941"},{"key":"e_1_3_1_34_2","volume-title":"Proceedings of the International Conference on Learning Representations","author":"Kingma Diederik P.","year":"2015","unstructured":"Diederik P. Kingma and Jimmy Ba. 2015. Adam: A method for stochastic optimization. Proceedings of the International Conference on Learning Representations."},{"key":"e_1_3_1_35_2","first-page":"135","volume-title":"Proceedings of the IEEE International Symposium on Performance Analysis of Systems and Software (ISPASS \u201905)","author":"Lau Jeremy","year":"2005","unstructured":"Jeremy Lau, Erez Perelman, Greg Hamerly, Timothy Sherwood, and Brad Calder. 2005. Motivation for variable length intervals and hierarchical phase behavior. In Proceedings of the IEEE International Symposium on Performance Analysis of Systems and Software (ISPASS \u201905). IEEE, 135\u2013146."},{"key":"e_1_3_1_36_2","doi-asserted-by":"publisher","DOI":"10.5555\/3524938.3525514"},{"key":"e_1_3_1_37_2","volume-title":"Proceedings of the 55th Annual Design Automation Conference","author":"Liu Zihao","year":"2018","unstructured":"Zihao Liu, Tao Liu, Wujie Wen, Lei Jiang, Jie Xu, Yanzhi Wang, and Gang Quan. 2018. DeepN-JPEG: A deep neural network favorable JPEG-based image compression framework. In Proceedings of the 55th Annual Design Automation Conference."},{"key":"e_1_3_1_38_2","doi-asserted-by":"publisher","DOI":"10.1145\/1064978.1065034"},{"key":"e_1_3_1_39_2","first-page":"4505","volume-title":"International Conference on Machine Learning","author":"Mendis Charith","year":"2019","unstructured":"Charith Mendis, Alex Renda, Saman Amarasinghe, and Michael Carbin. 2019. Ithemal: Accurate, portable and fast basic block throughput estimation using deep neural networks. In International Conference on Machine Learning. PMLR, 4505\u20134515."},{"key":"e_1_3_1_40_2","doi-asserted-by":"publisher","DOI":"10.18653\/v1\/W19-3901"},{"key":"e_1_3_1_41_2","doi-asserted-by":"crossref","first-page":"48","DOI":"10.1145\/3229543.3229555","volume-title":"Proceedings of the 2018 Workshop on Network Meets AI & ML","author":"Narayanan Arvind","year":"2018","unstructured":"Arvind Narayanan, Saurabh Verma, Eman Ramadan, Pariya Babaie, and Zhi-Li Zhang. 2018. Deepcache: A deep learning based framework for content caching. In Proceedings of the 2018 Workshop on Network Meets AI & ML, 48\u201353."},{"key":"e_1_3_1_42_2","first-page":"3882","article-title":"Phased LSTM: Accelerating recurrent network training for long or event-based sequences","volume":"29","author":"Neil Daniel","year":"2016","unstructured":"Daniel Neil, Michael Pfeiffer, and Shih-Chii Liu. 2016. Phased LSTM: Accelerating recurrent network training for long or event-based sequences. In Advances in Neural Information Processing Systems, Vol. 29, 3882\u20133890.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_3_1_43_2","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1613\/jair.374","article-title":"Identifying hierarchical structure in sequences: A linear-time algorithm","volume":"7","author":"Nevill-Manning C. G.","year":"1997","unstructured":"C. G. Nevill-Manning and I. H. Witten. 1997. Identifying hierarchical structure in sequences: A linear-time algorithm. Journal of Artificial Intelligence Research 7 (1997), 67\u201382.","journal-title":"Journal of Artificial Intelligence Research"},{"key":"e_1_3_1_44_2","doi-asserted-by":"publisher","DOI":"10.1109\/DSN.2007.103"},{"key":"e_1_3_1_45_2","doi-asserted-by":"publisher","DOI":"10.1109\/TNNLS.2019.2953622"},{"key":"e_1_3_1_46_2","doi-asserted-by":"publisher","DOI":"10.1109\/IVS.2018.8500658"},{"key":"e_1_3_1_47_2","doi-asserted-by":"publisher","DOI":"10.1209\/0295-5075\/17\/6\/001"},{"key":"e_1_3_1_48_2","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2023.3240567"},{"key":"e_1_3_1_49_2","doi-asserted-by":"publisher","DOI":"10.1561\/2200000018"},{"key":"e_1_3_1_50_2","volume-title":"Proceedings of the 52nd Annual IEEE\/ACM International Symposium on Microarchitecture","author":"Shi Zhan","year":"2019","unstructured":"Zhan Shi, Xiangru Huang, Akanksha Jain, and Calvin Lin. 2019. Applying deep learning to the cache replacement problem. In Proceedings of the 52nd Annual IEEE\/ACM International Symposium on Microarchitecture."},{"key":"e_1_3_1_51_2","first-page":"440","volume-title":"Proceedings of the 5th Annual Workshop on Computational Learning Theory","author":"Siegelmann Hava T.","year":"1992","unstructured":"Hava T. Siegelmann and Eduardo D. Sontag. 1992. On the computational power of neural nets. In Proceedings of the 5th Annual Workshop on Computational Learning Theory. 440\u2013449."},{"key":"e_1_3_1_52_2","doi-asserted-by":"publisher","DOI":"10.5555\/545215.545235"},{"key":"e_1_3_1_53_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ins.2023.120034"},{"key":"e_1_3_1_54_2","doi-asserted-by":"publisher","DOI":"10.1145\/3502731"},{"key":"e_1_3_1_55_2","volume-title":"Proceedings of the International Conference on Learning Representations","author":"Torfason R\u00f3bert","year":"2018","unstructured":"R\u00f3bert Torfason, Fabian Mentzer, Eir\u00edkur \u00c1g\u00fastsson, Michael Tschannen, Radu Timofte, and Luc Van Gool. 2018. Towards image understanding from deep compression without decoding. In Proceedings of the International Conference on Learning Representations."},{"key":"e_1_3_1_56_2","unstructured":"Ashish Vaswani Noam Shazeer Niki Parmar Jakob Uszkoreit Llion Jones Aidan N. Gomez Lukasz Kaiser and Illia Polosukhin. 2017. Attention is all you need. arXiv:1706.03762. Retrieved from https:\/\/arxiv.org\/abs\/1706.03762"},{"key":"e_1_3_1_57_2","unstructured":"Arsi Vaziri and Mark Kremenetsky. 1995. Visualization and Tracking of Parallel CFD Simulations. Technical Report NAS-95-004. NASA Ames Research Center Numerical Aerodynamic Simulation Systems Division Moffett Field CA. Retrieved from https:\/\/www.nas.nasa.gov\/assets\/nas\/pdf\/techreports\/1995\/nas-95-004.pdf"},{"key":"e_1_3_1_58_2","unstructured":"Hanson Wang Zehui Wang and Yuanyuan Ma. 2019. Predictive precompute with recurrent neural networks. arXiv:1912.06779. Retrieved from https:\/\/arxiv.org\/abs\/1912.06779"},{"key":"e_1_3_1_59_2","unstructured":"Gail Weiss Yoav Goldberg and Eran Yahav. 2018. On the practical computational power of finite precision RNNs for language recognition. arXiv:1805.04908. Retrieved from https:\/\/arxiv.org\/abs\/1805.04908"},{"key":"e_1_3_1_60_2","doi-asserted-by":"crossref","unstructured":"Sam Wiseman and Alexander M. Rush. 2016. Sequence-to-sequence learning as beam-search optimization. arXiv:1606.02960. Retrieved from https:\/\/arxiv.org\/abs\/1606.02960","DOI":"10.18653\/v1\/D16-1137"},{"key":"e_1_3_1_61_2","doi-asserted-by":"publisher","DOI":"10.1145\/3300061.3345448"},{"key":"e_1_3_1_62_2","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1145\/3132402.3132405","volume-title":"Proceedings of the International Symposium on Memory Systems","author":"Zeng Yuan","year":"2017","unstructured":"Yuan Zeng and Xiaochen Guo. 2017. Long short term memory based hardware prefetcher: A case study. In Proceedings of the International Symposium on Memory Systems, 305\u2013311."},{"key":"e_1_3_1_63_2","unstructured":"Matthew Shunshi Zhang and Bradly Stadie. 2019. One-shot pruning of recurrent neural networks by Jacobian spectrum evaluation. arXiv:1912.00120. Retrieved from https:\/\/arxiv.org\/abs\/1912.00120"},{"key":"e_1_3_1_64_2","unstructured":"Maohua Zhu Jason Clemons Jeff Pool Minsoo Rhu Stephen W. Keckler and Yuan Xie. 2018. Structurally sparsified backward propagation for faster long short-term memory training. arXiv:1806.00512. Retrieved from https:\/\/arxiv.org\/abs\/1806.00512"}],"container-title":["ACM Transactions on Knowledge Discovery from Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3785464","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,2,2]],"date-time":"2026-02-02T12:36:08Z","timestamp":1770035768000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3785464"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,2,2]]},"references-count":63,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2026,2,28]]}},"alternative-id":["10.1145\/3785464"],"URL":"https:\/\/doi.org\/10.1145\/3785464","relation":{},"ISSN":["1556-4681","1556-472X"],"issn-type":[{"value":"1556-4681","type":"print"},{"value":"1556-472X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,2,2]]},"assertion":[{"value":"2024-02-25","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-12-06","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2026-02-02","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}