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

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

RSS で購読
arXiv cs.DC

Rethinking KV Cache Eviction for Agentic LLM Serving

説明エージェント型LLMサービス向けKVキャッシュ削除策の再検討

要約大規模言語モデルのサービスでは、KVキャッシュがGPUメモリを大きく圧迫し、容量不足時には削除が必要になります。本論文は、共有プレフィックスを保持し、残りの履歴の先頭からKVキャッシュを削除して後半部分を残す方式を提案し、これに基づくPenelopeを構築しました。SGLangに実装し、実際のエージェントトレースを用いて3つのQwen3モデルサイズで評価した結果、GPUのみのキャッシュではSGLangと比べて最大60%の初トークン時間短縮、最大37%のジョブ完了時間短縮が示されました。GPU-CPU二層キャッシュでは、それぞれ最大76%と60%の短縮となりました。

Jiakun Fan, Han Meng, Yuxuan Xia ほか

arXiv cs.IT · cs.DS · math.IT

The Pareto Secretary Problem

説明パレート秘書問題:オンラインでパレート最適な観測値を選ぶ問題

要約本論文は、独立同分布の標本を順に観測し、どの座標でも他の観測値に劣らず少なくとも一つで優れる(パレート極大な)観測値を選ぶオンライン選択問題を扱う。固定次元における最適な失敗確率のオーダーを示し、ガウス相関や任意の依存関係の場合についても結果を述べている。

Andr\'es Cristi, Yilin Kong, Jiechen Zhang

arXiv cs.GT

From Scalar Games to Unconstrained Network Zero-Sum Games: Transfer Principles for Gradient-Based Learning

説明スカラーゲームから制約なしネットワーク零和ゲームへ:勾配ベース学習のための転移原理

要約本論文は、勾配ベースの学習規則のクラスについて検討する。規則がすべてのスカラー零和ゲームで収束する場合、任意のネットワーク零和ゲームでも、ゲーム演算子のノルムに依存するステップ幅の条件のもとで収束することを示す。また、有限時間の収束速度もモードごとに転移し、最悪ケースのネットワーク応答は標量の正準ゲームの最大応答に等しいとする。

Gaoqi Xue, James P. Bailey

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

Embodied Movable Antennas

説明具身可動アンテナ:物理的エージェントの機械的自由度で無線チャネルを再構成する研究

要約本論文は、専用のアクチュエータを使わず、ロボットなどの物理的エージェントが既に持つ機械的自由度を利用してアンテナの位置と向きを変える「具身可動アンテナ(embodied MAs)」を提案する。タスク結合型とタスク保持型の二つのモードを区別し、冗長性のあるロボットマニピュレータを例に、マルチパスチャネルの厳密なフーリエ表現を導出している。数値結果では、タスク保持型の運動により通信性能が大きく向上することが示されている。

Yewen Cao, Dengke Wei, Yulin Shao

arXiv cs.IT · math.IT

Capacity Meets the Four Subspace Problem: Distributed Linear Computation and the Cross-Ratio

説明容量と四部分空間問題:分散線形計算と交比

要約複数のユーザーが共通データの固定線形関数をそれぞれ観測し、サーバーは各ユーザーが送る1つのメッセージから別の線形関数を誤りなしで復元する設定を研究している。最小総送信量(容量)は、関数が作る部分空間の配置にのみ依存するとされる。三ユーザーがa、b、a+bを観測し、サーバーがa+λbを求める場合を扱い、交比λに応じて容量は2、3/2、または3p/(2p-1)から2の範囲となることが示される。

Hua Sun

arXiv math.CO · cs.IT · math.IT

Extremal character spectra of finite projective systems

説明有限射影系の極値文字スペクトル(有限射影空間上の多重点集合の、余次元 r の平坦における文字関数の異なる値の個数の最大化を扱う数学論文)

要約有限射影空間 PG(k-1,q) 上の有限生成多重点集合の文字関数を扱う。総重複度の制約のもとで、余次元 r の平坦上で文字関数がとりうる異なる値の個数の最大値を研究している。r=k-1 の場合は、サイズ制約付きの極値問題を完全に解いている。r=1 の場合には、このような系の最小長に関する既知の上界を改善している。

Shitao Li, Yang Li, Gaojun Luo

arXiv cs.DC · cs.AR

Matching Workloads to Blackwell: Power-Resolved Benchmarking of NVIDIA B200 and B300 across HPC and AI Workloads

説明Blackwell へのワークロード適合:NVIDIA B200 と B300 の HPC・AI 向け電力考慮型ベンチマーク

要約本論文は、それぞれ8基のGPUを搭載した2つの独立したクラスタで NVIDIA B200 と B300(Blackwell Ultra)を評価したものです。対象はコンピュータビジョンの推論と学習、Llama-3-8B と 70B による LLM 推論、および6つの実運用 HPC コードです。B300 は B200 の単純な後継ではなく、畳み込み推論や3D ビジョントランスフォーマの学習などで性能が劣ることが示されています。著者らは GPU ごとの消費電力を用いて畳み込みの性能差を分析し、ワークロードごとの調達指針を示しています。

Mohsen Zand, Trung Dac Nguyen, H. Birali Runesha

★★★★☆ 注目
arXiv cs.DC

Decentralized Dynamic Stable Matching

説明分散型動的安定マッチング:共通クロックや直接通信がない条件で、プレイヤーとアーム間の最適安定マッチングを計算・学習する研究

要約本論文は、プレイヤーの参加・離脱が予告なく起こり、共通クロックも直接通信もない状況で、プレイヤー最適安定マッチング(POSM)を分散的に計算する問題を扱う。既知の選好の場合には、コスト O(t_*+K^2 log T) の決定的多項式時間の自己較正プロトコルを示し、従来の上界を改善した。未知の選好の場合には、コスト O(t_*+K^4 Δ_min^{-2} log T) の分散学習プロトコルを与え、T と Δ_min への依存性が文献由来の静的下界で tight であることを示した。

注目点共通クロックや直接通信がない下で動的安定マッチングを実現し、コストの界を O(T^{1-1/K}) から O(t*+K^2 log T) へ改善、紧界の下界も示す。

Jing Chen, Mengtong Gao, Zhenhe Zhang

arXiv math.FA · cs.IT · math.IT

On approximate support versions of Donoho--Stark uncertainty principles for k-Hadamard operators

説明k-アダマール作用素に対するDonoho–Stark不確定性原理の近似サポート版

要約本論文は、有限次元空間におけるk-アダマール作用素のDonoho–Stark型不確定性原理を扱う。Wigderson兄弟の既存研究を基に、ℓ^pノルムに関する近似サポート版の結果を検討している。特殊でないk-アダマール行列の場合、p>1への一般化は成り立たないことを示す。特殊k-アダマール作用素については、1≤p≤2の範囲で成り立つことを証明している。さらに、特殊性条件を満たしていてもp>2では成立しないことを示している。

Rami Ayoush

arXiv cs.DC

Layered Reproducibility for High-Performance Computing Applications: The Feel++ and Ktirio Urban Buildings Case Study

説明高性能計算アプリケーションのための階層的再現性:Feel++ と Ktirio Urban Buildings の事例研究

要約本論文は、複雑なソフトウェア環境や異種ハードウェア、高価な検証工程により再現が困難な高性能計算(HPC)の課題に対し、階層的な再現性戦略を提案する。Feel++ が追跡可能なソフトウェア供給連鎖を提供し、Ktirio Urban Buildings(KUB)がその上で、バージョン管理された都市建物データ、実行可能なシミュレーション、チェックサムで検証できる結果ファイルを管理する。再現性を後期の手作業による梱包から、ソースコミット、パッケージ、コンテナ、ベンチマーク設定、データセット版、来歴記録、生成結果を結ぶ成果物の連鎖へ移す。

Javier Cladellas, Vincent Chabannes (IRMA), Christophe Prud'Homme (IRMA)

arXiv cs.IT · math.IT

Rates and Nearly-Lossless State over a Multi-Access Channel with Causal State Information

説明因果的状態情報をもつ多元接続通路におけるレートとほぼ無損失の状態伝送

要約本論文は、因果的状態情報を持つ無記憶状態依存型多元接続通路において、データと状態を同時に伝送する問題を扱う。状態は三つの独立した成分からなり、一つは両符号化器に共通に知らされる共通成分、残り二つは各符号化器に個別に知らされる私的成分である。データは任意に小さい誤り確率で、状態系列は任意に小さい記号誤り率で復元することが求められる。状態再構成制約がない場合の容量領域が非空であるという仮定のもとで容量領域を導出し、ビニングと重ね合わせ符号化を用いたブロック・マルコフ符号化方式によって達成可能であることを示す。

Amos Lapidoth, Baohua Ni

arXiv cs.IT · math.IT

Batch Universal Prediction via Conditional Additive Smoothing

説明条件付き加法的平滑化によるバッチ汎用予測

要約本論文は、予測器が訓練用のバッチ系列を観測した後、同じ未知の情報源から生成された独立したテスト系列を予測する場合の「バッチ後悔」を扱う。二値無記憶情報源と一階マルコフ情報源について、条件付き加法的平滑化推定器の漸近的なバッチ後悔を分析している。二値無記憶情報源では、Krichevskyのポアソンに基づく解析を拡張し、最適バイアスとバッチ後悔が訓練バッチサイズnに応じてどう変化するかを示す。さらに、バッチ後悔のRényi版を導入し、対応する最適予測器を条件付きα-NML推定器として特定する。

Marco Bondaschi, Michael Gastpar