{"id":5632,"date":"2024-10-24T05:08:00","date_gmt":"2024-10-23T20:08:00","guid":{"rendered":"https:\/\/devneko.jp\/wordpress\/?p=5632"},"modified":"2024-10-24T05:08:00","modified_gmt":"2024-10-23T20:08:00","slug":"fundamental-limitations-on-subquadratic-alternatives-to-transformers","status":"publish","type":"post","link":"https:\/\/devneko.jp\/wordpress\/?p=5632","title":{"rendered":"Fundamental Limitations on Subquadratic Alternatives to Transformers\u00a0"},"content":{"rendered":"\n<ul class=\"wp-block-list\">\n<li><strong>Fundamental Limitations on Subquadratic Alternatives to Transformers\u00a0<\/strong>[3.5]<br>\u6587\u66f8\u985e\u4f3c\u6027\u30bf\u30b9\u30af\u306b\u91cd\u70b9\u3092\u7f6e\u3044\u3066\u304a\u308a\u3001\u5165\u529b\u3055\u308c\u305f\u591a\u304f\u306e\u6587\u66f8\u3068\u3057\u3066\u4e0e\u3048\u3089\u308c\u3001\u6700\u3082\u3088\u304f\u4f3c\u305f\u30da\u30a2\u3092\u898b\u3064\u3051\u305f\u3044\u3068\u601d\u3063\u3066\u3044\u307e\u3059\u3002 \u6211\u3005\u306fTransformer\u304c\u3053\u306e\u30bf\u30b9\u30af\u3092\u5b9f\u884c\u3067\u304d\u308b\u3053\u3068\u3092\u8a3c\u660e\u3057\u3001\u3053\u306e\u30bf\u30b9\u30af\u306f\u3069\u3093\u306a\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u3067\u3082\u771f\u306b2\u6b21\u6642\u9593\u3067\u5b9f\u884c\u3067\u304d\u306a\u3044\u3053\u3068\u3092\u8a3c\u660e\u3057\u305f\u3002<br><a href=\"http:\/\/arxiv.org\/abs\/2410.04271v1\">\u8ad6\u6587<\/a>\u00a0\u00a0<a href=\"https:\/\/fugumt.com\/fugumt\/paper_check\/2410.04271v1\">\u53c2\u8003\u8a33\uff08\u30e1\u30bf\u30c7\u30fc\u30bf\uff09<\/a>\u00a0 \u00a0(Sat, 05 Oct 2024 19:21:13 GMT)<\/li>\n\n\n\n<li>\u300cWe focus on document similarity tasks, where one is given as input many documents and would like to \ufb01nd a pair which is (approximately) the most similar. We prove that Transformer is able to perform this task, and we prove that this task cannot be performed in truly subquadratic time by any algorithm.\u300d\u3068\u3044\u3046\u4e3b\u5f35\u3002<\/li>\n\n\n\n<li>\u305d\u306e\u624b\u306e\u30bf\u30b9\u30af\u304c\u3042\u308b\u306e\u306f\u305d\u3046\u3060\u308d\u3046\u3068\u3044\u3046\u306e\u3068\u30c9\u30ad\u30e5\u30e1\u30f3\u30c8\u985e\u4f3c\u6027\u30bf\u30b9\u30af\u306b\u95a2\u3059\u308b\u5206\u6790\u306f\u3068\u3066\u3082\u8208\u5473\u6df1\u3044\u3002\u7279\u306b\u300cTheorem 3.1. Assuming SETH or OVC, for every \u03b5 > 0, there exists a constant c > 0 such that \u03b3-LSDn,\u2113 cannot be solved in O(n^2\u2212\u03b5) time for any \u03b3 \u2265 1 when \u2113 = c log n.\u300d\u306f\u9762\u767d\u3044\u7d50\u679c\u3002\uff08\u5b9f\u7528\u4e0a\u306f\u3001\u3068\u3044\u3046\u3068\u8a71\u304c\u5909\u308f\u308b\u5834\u5408\u3082\u591a\u3044\u5370\u8c61\u3067\u306f\u3042\u308a\u3064\u3064\uff09\u3053\u306e\u624b\u306e\u7406\u8ad6\u89e3\u6790\u306f\u91cd\u8981\u3002<\/li>\n<\/ul>\n","protected":false},"excerpt":{"rendered":"","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[2],"tags":[235,415],"class_list":["post-5632","post","type-post","status-publish","format-standard","hentry","category-arxiv","tag-mamba","tag-transformer"],"_links":{"self":[{"href":"https:\/\/devneko.jp\/wordpress\/index.php?rest_route=\/wp\/v2\/posts\/5632","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/devneko.jp\/wordpress\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/devneko.jp\/wordpress\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/devneko.jp\/wordpress\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/devneko.jp\/wordpress\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=5632"}],"version-history":[{"count":0,"href":"https:\/\/devneko.jp\/wordpress\/index.php?rest_route=\/wp\/v2\/posts\/5632\/revisions"}],"wp:attachment":[{"href":"https:\/\/devneko.jp\/wordpress\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=5632"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/devneko.jp\/wordpress\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=5632"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/devneko.jp\/wordpress\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=5632"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}