論文の概要: Token Complexity Theory for AI-Augmented Computing

• arxiv url: http://arxiv.org/abs/2606.12647v1
• Date: Wed, 10 Jun 2026 20:16:58 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-06-12 15:55:27.44429
• Title: Token Complexity Theory for AI-Augmented Computing
• Title（参考訳）: AI強化コンピューティングのためのトークン複雑性理論
• Authors: Jie Wang,
• Abstract要約: AI強化コンピューティングは、自然言語クエリ、コード生成要求、その他のオープンなタスクを、クエリを処理し応答を生成するAIモデルのクラスタに委譲する。 このパラダイムは、古典的な時間や空間の複雑さが捉えないリソースの次元を導入します。 我々は,タスクにおける特定の出力品質を達成するために,期待される最小トークンコストとして定義される公式なリソース尺度であるトークン複雑性を導入する。
• 参考スコア（独自算出の注目度）: 2.345146665577353
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: AI-augmented computing delegates natural language queries, code generation requests, and other open-ended tasks to a cluster of AI models that processes queries and generates responses. This paradigm introduces a resource dimension that neither classical time nor space complexity captures: the cost of sending queries to and receiving responses from such a cluster. We introduce token complexity, a formal resource measure defined as the minimum expected token cost to achieve a specified level of output quality on a task, and develop a taxonomy classifying AI systems by the strength of their probabilistic properties. We develop token complexity within the framework of AI-Oracle Turing machines, in which a probabilistic Turing machine interacts with a stochastic oracle via dedicated query and response tapes. We prove basic theorems establishing that token complexity behaves as expected: monotonicity (higher quality costs more tokens), convexity (quality improvements become progressively more expensive), price sensitivity (small price changes produce bounded cost changes), and price-relativity of task ordering (the token complexity ordering of tasks can reverse depending on the query-to-response cost ratio). We prove that the complexity frontier, defined as the set of all feasible resource bounds in tokens, time, and space, is non-empty, upward-closed, and convex.
• Abstract（参考訳）: AI強化コンピューティングは、自然言語クエリ、コード生成要求、その他のオープンなタスクを、クエリを処理し応答を生成するAIモデルのクラスタに委譲する。 このパラダイムは、古典的な時間や空間の複雑さが捉えないリソースの次元を導入します。 本稿では,タスクにおける出力品質の特定レベルを達成するために,期待される最小トークンコストとして定義された公式なリソース尺度であるトークンの複雑性を導入し,確率特性の強さによってAIシステムを分類する分類法を開発した。 我々は,確率的チューリングマシンが専用クエリと応答テープを介して確率的オラクルと相互作用する,AI-Oracleチューリングマシンのフレームワーク内でトークン複雑性を開発する。 単調性(より高い品質コストのトークン)、凸性(品質改善が徐々に高価になる)、価格感度(小さな価格変更が境界価格の変化をもたらす)、タスク順序付けの価格-相対性(要求対応答コスト比によってタスクのトークン複雑性の順序が逆転する)である。 我々は、トークン、時間、空間におけるすべての実現可能なリソース境界の集合として定義される複雑性フロンティアが空で、上向きに閉じられ、凸であることを証明する。

関連論文リスト

• Understanding Dynamic Compute Allocation in Recurrent Transformers [23.760167933957707]
  トークンレベルの適応計算は、より難しいトークンにより多くの計算を割り当て、より簡単なものにすることで、推論コストを削減する。 以前の作業は主にタスクレベルのメトリクスを使用して、自然なベンチマークで評価されます。 本稿では,パラメータ化困難を伴うアルゴリズムおよび合成言語タスクを用いた複雑性制御評価パラダイムを提案する。
  論文  参考訳（メタデータ） (2026-02-09T16:27:52Z)
• Low-Complexity Semantic Packet Aggregation for Token Communication via Lookahead Search [32.63323958382152]
  本稿では,トークンのパケット化に着目し,平均トークン類似度(ATS)を最大化する。 これを解決するために,ルックアヘッド検索(SemPA-Look)を用いたセマンティックアグリゲーションの新しいフレームワークを提案する。 SemPA-Lookは、リプレースせずにパケット内のトークン候補をサンプリングするルックアヘッド検索インスパイアされたアルゴリズムを適用している。
  論文  参考訳（メタデータ） (2025-06-24T09:25:44Z)
• A complexity theory for non-local quantum computation [0.9895793818721335]
  非局所量子計算(NLQC)は、2つのシステム間の局所的な相互作用を1ラウンドの通信と共有絡みで置き換える。 本研究では,NLQCタスク間のリソース効率の低下を同定し,NLQCタスクの相対的硬度について検討する。 最も顕著なのは、NLQCの最もよく研究された2つのタスクである$f$-measureと$f$-routeが、実際は$O(1)$オーバーヘッド削減の下で等価であることを証明したことである。
  論文  参考訳（メタデータ） (2025-05-29T18:00:01Z)
• Efficient and Scalable Neural Symbolic Search for Knowledge Graph Complex Query Answering [50.1887329564127]
  複雑なクエリに対する効率的でスケーラブルなシンボル検索フレームワークを提案する。 我々のフレームワークは、ほぼ同じ性能を維持しながら、シンボリックメソッドの計算負荷を90%削減する。
  論文  参考訳（メタデータ） (2025-05-13T01:24:09Z)
• The Computational Complexity of Circuit Discovery for Inner Interpretability [0.30723404270319693]
  我々は古典的およびパラメータ化された計算複雑性理論を用いて回路発見を研究する。 私たちの発見は、難しい複雑さの風景を明らかにします。 このフレームワークは、解釈可能性クエリの範囲と限界を理解するのに役立ちます。
  論文  参考訳（メタデータ） (2024-10-10T15:22:48Z)
• Adaptive-RAG: Learning to Adapt Retrieval-Augmented Large Language Models through Question Complexity [59.57065228857247]
  Retrieval-augmented Large Language Models (LLMs) は、質問回答(QA)のようなタスクにおける応答精度を高めるための有望なアプローチとして登場した。 本稿では,クエリの複雑さに基づいて,LLMの最適戦略を動的に選択できる適応型QAフレームワークを提案する。 オープンドメインのQAデータセットを用いて、複数のクエリの複雑さを網羅し、QAシステムの全体的な効率性と精度を高めることを示す。
  論文  参考訳（メタデータ） (2024-03-21T13:52:30Z)
• When Do Program-of-Thoughts Work for Reasoning? [51.2699797837818]
  本稿では,コードと推論能力の相関性を測定するために,複雑性に富んだ推論スコア(CIRS)を提案する。 具体的には、抽象構文木を用いて構造情報をエンコードし、論理的複雑性を計算する。 コードはhttps://github.com/zjunlp/EasyInstructのEasyInstructフレームワークに統合される。
  論文  参考訳（メタデータ） (2023-08-29T17:22:39Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。