Fundamental Limitations on Subquadratic Alternatives to Transformers
Fundamental Limitations on Subquadratic Alternatives to Transformers [3.5] 文書類似性タスクに重点を置いており、入力された多くの文書として与えられ、最もよく似たペアを見つけたいと思っています。 我々はTransformerがこのタスクを実行できることを証明し、このタスクはどんなアルゴリズムでも真に2次時間で実行できないことを証明した。 論文参考訳（メタデータ） (Sat, 05 Oct 2024 19:21:13 GMT)
「We focus on document similarity tasks, where one is given as input many documents and would like to find 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.」という主張。
その手のタスクがあるのはそうだろうというのとドキュメント類似性タスクに関する分析はとても興味深い。特に「Theorem 3.1. Assuming SETH or OVC, for every ε > 0, there exists a constant c > 0 such that γ-LSDn,ℓ cannot be solved in O(n^2−ε) time for any γ ≥ 1 when ℓ = c log n.」は面白い結果。（実用上は、というと話が変わる場合も多い印象ではありつつ）この手の理論解析は重要。