その他の計算機科学 · 2026年10月27日(火)

分散計算、ゲーム理論、情報理論など。

arXiv cs.DC

TAO: Tool-Aware Joint Scheduling for LLM-Based Agentic Serving

説明TAO:LLMベースのエージェントサービス向けツール認識型共同スケジューリング

要約本論文は、LLMベースのエージェントサービスのためのツール認識型共同スケジューリングフレームワーク「TAO」を提案しています。ツールの戻り準備状況、時間減衰を伴うノード固有のキャッシュ価値、トークン占有量を組み合わせ、容量制約の下で動的計画法により待機中のセッションを選択・配置します。報告された12のモデル・ワークロード・並列度の設定において、各指標で最良の評価済みベースラインと比べ、遅延は最大26.8%、平均初トークン時間(TTFT)は最大36.3%削減され、デコードスループットは最大29.5%向上しました。

Shuhuai Li, Shengdong Ye, Dongdong Ge ほか

★★★★☆ 注目
arXiv cs.DC

PipeLink: Contract-Guided Linking of GPU Kernel Components

説明PipeLink:契約に基づくGPUカーネルコンポーネントのリンク手法

要約本論文は、GPUカーネルコンポーネントを契約に基づいてリンクするツールPipeLinkを提案する。各コンポーネントは要求と提供を記述した契約を持つLTOオブジェクトとして個別にコンパイルされ、PipeLinkが契約を照合し、SMの資源配置を一括で求めてコンポーネント間の転送を生成する。HopperおよびBlackwell GPU上の51構成で、一体としてコンパイルした場合との差は0.2%以内であった。

注目点契約に基づくGPUカーネル部品リンカを提案し、部品の独立したコンパイル・置換の課題に取り組む。51構成で単一ユニットとの差が0.2%以内、複数の実用的合成で高速化を実証。

Jize Guo, Xupeng Miao

arXiv eess.SP · cs.IT · math.IT

Negative Results for Reciprocity-Based Over-the-Air Split Learning Under Channel Aging: Stability, Alignment, and Geometry

説明チャネルエイジング下における互恵性ベースの空中分割学習の否定的結果:安定性、整列、幾何学

要約本論文は、チャネルエイジングによって送信機へ戻される微分信号が回転・減衰する、互恵性ベースの空中分割学習を検討しています。7つのケーススタディで数値予測、メカニズム検証、競合する予測を組み合わせて分析し、多くの学習精度の予測は支持されなかったものの、一部の局所的な物理関係は成り立つことを示しています。

Tianhao Guo, Xianzhong Li, Hao Luo

arXiv cs.IT · eess.SP · math.IT

Deep Holes and Aperture: Sign Laws for the Empirical Correlation of Lattice-Sampled Random Wave Fields

説明深い穴と開口:格子サンプリングされたランダム波場の経験相関に関する符号則(格子上でサンプリングしたランダム波の経験相関の符号規則に関する論文)

要約本論文は、有界な開口内で格子上にサンプリングしたガウス型ランダム波場について、再インデックス後の残差がVoronoi胞内で経験的ラグ相関の実部を正に保つかを検討する。正方格子、六角格子、単純立方格子、体心立方格子の符号クラス数を示し、失敗確率の漸近的および非漸近的な開口則を導出する。レイリーフェージングの鏡面経路がある場合の失敗の下限が生じる条件も扱う。

Tianhao Guo, Hao Luo, Xianzhong Li ほか

arXiv math.AC · cs.IT · math.AG

Counting the Fixed Points of Binary Belief Propagation: Generic Degree, Syzygies, and Real Solutions

説明二値信念伝播の不動点の個数の計算:一般次数、シジジー、実数解

要約本論文は、二値対ごとモデル上の信念伝播(belief propagation)の不動点の個数を研究する。複素パラメータの下で、有限な無ループ多重グラフから得られる代数族の一般次数を決定し、次数1の頂点を含まない辺集合上の和として与える。その二つの幾何学的実現を示し、強磁場の下で実不動点の下界を分析して、辺接続環の最小加群生成元の個数との関係を明らかにする。関連する結果は Lean 4 で形式化されている。

Yusuke Watanabe

arXiv cs.IT · eess.SP · math.IT

Digital Twin-Guided Wireless Localization via Probabilistic Inverse Learning

説明デジタルツインと確率的逆学習に基づく無線測位手法

要約本論文は、サイト固有のデジタルツイン(DT)を、簡易な分散インフラで無線測位に活用する方法を検討しています。単一アンテナのアクセスポイントを用いる確率的手法PRISMを提案し、測位を確率的逆問題として定式化します。多ノードのチャネルインパルス応答から学習した提案分布で候補位置を生成し、DTとの整合性で候補を重み付けして推定を洗練します。10台の単一アンテナAPを用いた場合、中央値誤差は約0.7mで、再学習なしでもDT特徴が劣化した状況で有効性を保ちます。

Mahmoud Saad Abouamer, Henrik C. M. Frederiksen, Robin J. Williams ほか

arXiv cs.DC · cs.DB

Taming Multi-Dimensional Skew in Sparse Matrix Multiplication with Contention-Aware Scheduling [Technical Report]

説明稀疏行列積における多次元の偏りを、競合を考慮したスケジューリングで抑える(技術報告)

要約本論文は、データの偏りによって稀疏行列積(SpGEMM)の性能が低下する問題を扱う。原因として、計算コスト・出力密度・データ局所性の間の多次元的な不均衡と、密な部分構造によるキャッシュ競合の二つを挙げる。著者らは、適応的morselスケジューリング(AMS)を提案し、競合を考慮した負荷分散、データを考慮した同時マルチスレッディング起動機構、morselごとに累積器を選ぶハイブリッド方式を組み合わせる。行列の二乗、関係クエリ、グラフ解析などの評価では、偏りのある負荷でAMSが既存手法を大きく上回り、偏りのない負荷では同等の性能を示したと報告している。

Wentao Huang, Qiming Huang, Yunhong Ji ほか

arXiv cs.IT · math.IT

Rethinking Channel Estimation for Fluid Antenna Systems: A Physics-Informed Operator Learning

説明流体アンテナシステムのチャネル推定の再考:物理情報付き演算子学習

要約本論文は、流体アンテナシステムのチャネル推定を、射影されたヘルムホルツモデルで制約された確率的逆場再構成問題として定式化します。電磁情報理論に基づくスペクトル漏れ解析により、この問題が周波数領域の逆デコンボリューションに帰着することを示しています。雑音が多く劣決定な無線環境向けのU字型フーリエニューラル演算子(UFNO)を提案し、物理を考慮したSobolev損失で学習させます。シミュレーションでは、既存のベンチマークより高精度で、高い空間・周波数分解能において反復解法より推論遅延が桁違いに小さいことが示されています。

Zixin Wang, Lizhong Zheng, Yuanming Shi ほか

arXiv cs.IT · eess.SP · math.IT

Sensitivity of RMS Delay Spread Estimation to Power Delay Profile Thresholding in Time-Varying Channels at 33 GHz

説明33 GHz時変チャネルにおけるRMS遅延拡がり推定の電力遅延プロファイル閾値への感度

要約本論文は、33 GHzのミリ波時変チャネルにおいて、RMS遅延拡がりの推定値が相対的な電力遅延プロファイル(PDP)の閾値によってどう変化するかを調べたものです。解析には、移動車両のある動的な道路環境で行った広帯域チャネルサウンディング測定データを用いています。閾値を-20 dBから-50 dBまで変えたところ、中央値は約140 nsから168 nsへ、90パーセンタイル値は200 nsから210 nsへ増加しました。両統計量は低い閾値で収束し、-40 dBが実用的な収束水準となることが示されています。

Jaros{\l}aw Wojtu\'n, Bartosz Czaja, Tomasz Grasza ほか

arXiv cs.GT · math.PR

When do token systems stabilize? Compatibility constraints and community structure

説明トークン系はいつ安定するか:互換性制約とコミュニティ構造

要約本論文は、エージェント間に互換性制約がある場合のトークンによるサービス交換システムを研究している。システムが安定するための必要十分条件を示し、利用可能な提供者のうち残高が最も少ない者を選ぶ最小トークン規則が最適な安定領域を達成することを証明している。さらに、この判定基準を確率ブロックモデルから生成したランダムなトークン系に適用し、安定を妨げる要因として、コミュニティ群または個々のエージェントのサービス機会の不足という二つを挙げている。

Flore Sentenac, Mingwei Yang, Sophie H. Yu

arXiv math.NT · cs.IT · math.IT

Finite Fields: Root Sets, Frobenius, and Algebraic Structure

説明有限体:根集合、フロベニウス写像、代数構造(専門書)

要約根集合、フロベニウス軌道、トレース双対性、巡回加群を通じて有限体の理論を展開する専門書である。多項式の構成と代数符号理論への応用を扱い、巡回符号、BCH 符号、ランク距離符号、トレース符号などを取り上げている。指標の直交性、ガウス和、ヤコビ和、およびWeil 界の証明にも触れ、体の構造・軌道構造・線形従属性を結びつける明示的な議論を重視している。

Hongfeng Wu, Li Zhu

arXiv econ.TH · cs.GT

Characterizing Maximum Nash Welfare: Envy-Freeness and Proportionality

説明最大ナッシュ厚生の特徴づけ:羨望のなさと比例性

要約分割不可能な財の配分問題において、最大ナッシュ厚生ルールを検討する。このルールは「1財までの羨望のなさ」を満たす唯一の厚生主義ルールであることが知られている。本論文は、この公平性条件を、任意の固定された整数kに対する「k財までの羨望のなさ」または「k財までの比例性」というより弱い要件に置き換えてもよいことを示す。この特徴づけは、同一の財を含む選好プロファイルに対しても成り立つ。

Karen Frilya Celine, Warut Suksompong, Nicholas Teh

arXiv cs.IT · math.IT

The Exact Weight Spectrum of RM(m-7,m): A Counterexample to the Carlet-Solé Conjecture

説明Reed-Muller符号RM(m-7,m)の厳密な重みスペクトル:Carlet-Solé予想の反例

要約この論文は、ブール関数とReed-Muller符号RM(m-7,m)の重みスペクトル、すなわち各重みがどの程度現れるかを研究している。著者はアフィン幾何学とフーリエ解析を組み合わせ、RM(7,14)について従来予想されていた八つの重みを除外し、その結論をm≥14のすべての場合に拡張した。これによりCarlet-Solé予想の反例を与えている。

Yueying Lou, Qichun Wang

arXiv cs.IT · math.IT

Design of DoF-Robust MIMO via Generalized Pinching Antennas

説明一般化ピンチングアンテナによるDoF頑健なMIMO設計

要約本論文は、ユーザーと基地局の距離のばらつきによりマルチユーザーのチャネル行列がランク落ちし、空間自由度(DoF)が失われる問題を扱っている。ピンチングアンテナをユーザーの近くに配置することで、マルチユーザーのチャネルGram行列を条件の良いほぼ対角構造にできることを示している。ランク落ち確率と不通確率により評価され、解析とシミュレーションの結果から、空間的に離れたユーザーへの接続を支えつつ空間自由度を維持できることが示されている。

Zhiguo Ding, Robert Schober, H. Vincent Poor

arXiv cs.DC · cs.OS · cs.PF

Agar: What-If Analysis for Microservice Applications

説明Agar:マイクロサービス・アプリケーションのWhat-if分析

要約本論文はマイクロサービス向けの反事実的性能分析ツール AGAR を提案する。各コンポーネントの正確な値を予測する代わりに、観測されたすべての振る舞いを含み、かつ端から端までの結論に役立つ程度に厳密な、単純で解釈しやすい境界を学習し、それらを組み合わせてSLO(サービスレベル目標)の実現可能性を問う。これにより自動スケーリングを、SLOを満たす最小のリソース割り当ては何か、という反事実的な問いとして定式化する。三つのマイクロサービス・アプリケーションでの評価では、導出された自動スケーラーは最先端の水平自動スケーラーに比べ、アプリケーションのSLOを満たしつつCPU割り当てを最大36.8%削減した。

Saarth Deshpande, Neeraja J. Yadwadkar, Venkat Arun

★★★★☆ 注目
arXiv cs.GT

Noise Shapes the Surplus: Strategic Play Against No-Regret Learners

説明ノイズがもたらす余剰利得:後悔なし学習者に対する戦略的プレイ

要約本論文は、ゼロ和ゲームにおいて、摂動された利得情報と減衰する学習率を用いる後悔なし学習者(FTRL型アルゴリズム)から、オプティマイザーがミニマックス基準を上回る累積利得(余剰)をどの程度得られるかを検討している。被択的な戦略では定数オーダーの余剰しか得られないこと、更新規則と平均応答を知る最適化者は平均応答が有利な場合にΩ(1/η_T)の余剰を得られること、平均応答が不利な場合でも交互の能動的プレイによりΩ(∑η_t)の余剰を得られることを示している。標準的な学習率では、平均ゼロで有限分散の摂動に対してΩ(√T)の速度が回復されるとしている。

注目点ノイズ下のFTRL学習者に対する新たな搾取機構を提案し、減衰学習率でも√Tオーダーの戦略的余剰を示す。理論的な前進は大きいが、適用範囲はゼロ和ゲームに限られる。

Yiheng Su, Emmanouil-Vasileios Vlatakis-Gkaragkounis

arXiv cs.GT

Optimality and Impossibility in Multidimensional Strategyproof Facility Location

説明多次元における戦略耐性のある施設配置の最適性と不可能性

要約本論文は、社会的費用(各エージェントから最寄りの施設までの距離の総和)の最小化を目的として、多次元ノルム空間における施設配置問題を検討する。ユークリッド平面における単一施設について、決定論的な戦略耐性(SP)メカニズムの最適近似比が、座標ごとの中央値(CM)で得られる比と一致することを示し、その最適性結果から匿名性の仮定を除いている。また、非ユークリッド空間ではCMが常に最適とは限らないことを示し、二つ以上の施設の場合については不可能性結果を提示している。

Jianan Lin

★★★★☆ 注目
arXiv cs.GT

Learning-Augmented Coordination Mechanisms

説明学習強化型調整メカニズム:需要予測を用いて渋滞ゲームの均衡効率を改善する研究

要約本論文は、利己的行動によって資源配分の効率が低下する問題を扱う。需要の予測(不正確な場合もある)を用いてコストを修正する学習強化型調整メカニズムを提案し、信頼度パラメータβによって予測が正確な場合は最適に近い性能を、最悪の場合でも良い均衡(PoS)を保証する。さらに、PoAロバスト性の上界や不可能性の結果も示している。

注目点混雑ゲームの協調機構に学習強化の考えを導入し、予測が正確な場合と最悪均衡の保証を両立させ、不可能性結果も示している。

George Christodoulou, Vasilis Christoforidis, Alkmini Sgouritsa ほか

arXiv cs.DC

JustGoal: With Only a Goal, the AI Baseline Is Above the Expert Kernels

説明JustGoal:目標だけで与えるAIベースラインが専門家によるGPUカーネルを上回る

要約本論文は、汎用エージェントに最適化目標と制約のみを与え、カーネル専用の知識ベースや事前定義されたワークフローを与えないベースライン手法JustGoalを提案している。NVIDIA B200 GPUでは、10個の演算子のうち8個でオープンソースライブラリを上回り、演算子ごとの幾何平均高速化率は1.14倍から2.34倍であった。比較可能な9個の演算子のうち5個では、公開されている最速の専用エージェントによるカーネルも上回った。著者らは、専用の仕組みは同じモデル・同じ範囲の目標専用ベースラインに対して明確な利点を示すべきであり、基盤モデルが変わるたびに再評価すべきだと結論づけている。

Yaojian Chen, Dazhi Peng, Zhui Zhu ほか

★★★★★ 注目
arXiv cs.IT · math.IT

On the Fundamental Limits of Bistatic ISAC Over Vector Channels

説明ベクトルチャネル上のバイスタティックISACの基本限界

要約本論文は、ベクトルチャネル上のバイスタティック統合センシング・通信(ISAC)システムの基本限界を研究している。まず並列チャネルのクラスについて、可達性と逆定理を示し、容量-歪み関数C(D)の単一文字による特徴づけを得ている。加法的ガウス状態を持つベクトルガウスチャネルについては、ガウス重畳符号化の最適性を証明し、容量-歪み-電力関数C(D,P)の厳密な特徴づけを導いている。

注目点ベクトル通信路上のバイスタティックISACについて容量-歪み関数を単一文字で厳密に特徴づけ、フィッシャー情報行列の不等式でガウス重畳符号化の最適性を示した。

Dongsheng Peng, Lei Yu, Ping Chen ほか

arXiv cs.IT · cond-mat.stat-mech · math.IT

Thermodynamic characterization of message-passing: Framework and initial study

説明メッセージパッシング復号器の熱力学的特徴づけ:枠組みと初期研究

要約本論文は、ミスマッチコスト枠組みを用いてメッセージパッシング復号器の熱力学的効率を研究する。この枠組みは、回復不能なエネルギー損失の計算可能な下限を与える。二元消失通路上で伝送された[7,4]ハミング符号を例に、チャネルが誘導する初期化統計と復号中のアルゴリズム状態分布の段階的な変化が、総ミスマッチコストをどのように決めるかを示す。復号動態、入力統計、ハードウェア特性が共同で熱力学的コストを決定し、省エネルギーな復号器設計への道筋を示す。

Kalana G. Abeywardena, Stark C. Draper

arXiv cs.DC

INC-MoE: Overlapping In-Network Collectives and Expert Computation for Expert-Parallel Mixture-of-Experts Inference

説明INC-MoE:ネットワーク内集合通信と専門家計算を重ね合わせる専門家並列MoE推論手法

要約本論文は、専門家並列の混合専門家(MoE)層を提案し、トークンの配送と結果の集約という2つの通信処理をネットワークスイッチにオフロードし、それらの集合通信と専門家計算を互いに重ね合わせる手法(INC-MoE)を示している。四ノードの拡張構成をエミュレートした環境で、OLMoEのプリフィル処理を用いて評価され、vLLMの標準の集合通信経路と比べて、最初のトークンまでの時間が最大33%短縮、スループットが最大50%向上し、出力は一致したと報告されている。

John Stephan, Razvan Puscasu, Xu Yong ほか

★★★★★ 注目
arXiv cs.GT

How Learning Selects Equilibria and When It Leads to Collusion

説明学習が均衡をどのように選択し、いつ共謀につながるか

要約本論文は、有限の状態と行動を持つ無限期割引マルコフゲームにおいて、学習アルゴリズムの設計が均衡選択にどう影響するかを検討している。確率的に安定な状態が、各プレイヤーの変換後割引価値の最小値を最大化する近似定常ナッシュ均衡に対応することを示す。繰り返しクールノー競争では、確率的に安定なすべての状態が、各企業の割引利潤の最小値がクールノー・ナッシュ基準を上回る近似的公共完全均衡に対応し、これらの条件下では共謀が不可避であるとしている。

注目点確率的安定性によって均衡選択を特徴づけ、反復クールノー博弈で学習動学が近似的共謀を必然的に生むことを示し、アルゴリズム共謀研究に影響する。

Hanzhang Wang, Manxi Wu

★★★★☆ 注目
arXiv cs.GT

The Complexity of Strategizing Against No-Regret Learners: Pure When It Is Easy, Hard Even When Mixed

説明無後悔学習者に対する戦略最適化の計算複雑性:容易な場合は純粋戦略、混合戦略でも困難

要約本論文は、有限期間の繰り返しゲームにおいて既知のオンライン学習者に対する先見的な戦略最適化の計算複雑性を研究している。一般和ゲームでは、P≠NPの仮定の下で、混合戦略を出力できても、多項式時間の最適化器は最適な純粋行動系列の報酬に対し定数cの範囲内の報酬を達成できないことを示す。対照的に、ゼロ和ゲームでは決定論的な純粋行動で、混合戦略に匹敵する利得保証を効率的に得られる。

注目点既知の計算困難性の結果を平均ベースの学習者へ拡張し、ゼロ和ゲームで純粋戦略が混合戦略と同等の保証を得られることを示した点が新しい。

Yiheng Su, Emmanouil-Vasileios Vlatakis-Gkaragkounis

★★★★★ 注目
arXiv cs.IT · cs.CC · math.IT

Explicit Reed-Solomon Subspace Designs: Optimal List and Line Decoding

説明明示的なリード・ソロモン部分空間設計:最適なリストおよび線形復号

要約本論文は、拡大体上のリード・ソロモン符号を明示的に構成する方法を示し、誤り割合1-R-εまでリスト復号でき、リストサイズがO((1-R)/ε)で最適であることを述べています。より単純な強明示的構成として、リストサイズ(1/ε)^O(1/ε)の評価点の構成も与えています。両構成に対して決定的なリスト復号アルゴリズムを提示しています。

注目点明示的なReed-Solomon符号の近最適リスト復号と部分空間設計の構成を与え、リストサイズを定数に抑え、厳密な証明を示す。

Omar Alrabiah, Rohan Goyal, and Venkatesan Guruswami

★★★★★ 注目
arXiv cs.GT

Exploring the Tractability Frontier of Hylland-Zeckhauser Models

説明Hylland-Zeckhauser モデルの計算可能性の境界を探る

要約本論文は、一方向マッチングのための Hylland-Zeckhauser(HZ)機構における均衡計算の難しさを扱う。二値効用は強多項式時間で解けることが知られているが、本論文は効用値が {0,a,1} に限られる場合でも近似均衡の計算が PPAD 困難であることを示す。分離可能な凹効用では、共通の限界傾きが二つなら多項式時間で厳密解が得られ、三つなら PPAD 困難となり、境界は二と三の間にあることを示している。

注目点未解決問題を解決し、効用値3種で既にPPAD困難であることを示し、可解と困難の境界を明確化する厳密な証明を与えた。

Ioannis Panageas, Avi Shein, Shayan Taherijam ほか

arXiv cs.IT · cs.SY · eess.SY

World Model for Energy Efficiency Maximization in Dynamic Metasurface Antennas

説明動的メタサーフェスアンテナにおけるエネルギー効率最大化のためのワールドモデル

要約本論文は、時変チャネル下で動的メタサーフェスアンテナ(DMA)のデジタルビームフォーミングとDMA素子の重みを同時に最適化する問題を扱い、時間平均エネルギー効率を最大化します。送信電力、ローレンツ位相、最低伝送速度の制約を考慮しています。著者らは環境とのやり取りから潜在的なシステム動態を学習し、想像上の軌道を通じて両パラメータを最適化するワールドモデルの枠組みを提案し、制約を満たすための実行可能性保存の行動写像と安全コスト信号を組み込んでいます。シミュレーションでは、深層Qネットワークのベースラインと比べて時間平均エネルギー効率が約20%向上し、サンプル効率が高く、制約充足もより確実であったと報告されています。

Abdolrasoul Sakhaei Gharagezlou, Mehdi Monemi, Matti Latva-aho ほか

arXiv cs.DC · cs.NI · cs.SE

Making the Telemetry Pipeline Measurable: An Edge IoT Testbed and Dataset for End-to-End Latency, Provenance, and Energy-Aware Benchmarking

説明遥測パイプラインを測定可能にする:エンドツーエンド遅延・来歴・省エネ評価のためのエッジIoT試験基盤とデータセット

要約本論文は、計測を最優先に据えたエッジIoT試験基盤とデータセットを提示し、即時性・来歴・エネルギーを遥測の第一級の指標として扱います。システムは役割ベースのイベント駆動アーキテクチャとAvro形式の遥測メッセージを用い、MQTTブローカー(Mosquitto)には入出力時刻を記録するプラグインを追加しています。データセットは再生可能な生イベントとクエリ可能なParquetの表形式の両方で公開されています。一つの配備事例の遅延・計測文脈・エネルギーの集計を示していますが、新しい帰属手法や統制された性能ベンチマークは確立していません。

Dimitris Gkoulis

arXiv cs.DC

A Unified Queueing-Based Framework for Comparative Evaluation of Serverless Autoscaling Strategies under Bursty Workloads

説明バースト負荷下におけるサーバーレス自動スケーリング方式の比較評価のための統一キューイングモデル

要約本論文は、バースト性の高いワークロードに対するサーバーレス計算基盤の自動スケーリング方式を比較しています。対象は、リクエストごとのスケーリング(SPR)、同時実行数に基づくスケーリング(CLS)、メトリクスに基づくスケーリング(MBS)の三方式です。解析的キューイングネットワークモデルと、Java Modeling Tools(JMT)で実装したキューイングPetriネットを組み合わせ、二相超指数到着の下でスループット、平均応答時間、システム人口、システムパワーの四指標で評価しています。結果として、SPRは中程度の負荷で最も低遅延ですが容量上限付近では脆弱であり、CLSは突発的な条件下で設定に敏感であり、MBSは負荷範囲全体で最も安定したQoSを示すと報告しています。

Zahra Zafarzade, Ehsan Ataie