論文の概要: Efficiently Learning Branching Networks for Multitask Algorithmic Reasoning
- arxiv url: http://arxiv.org/abs/2512.01113v1
- Date: Sun, 30 Nov 2025 22:19:55 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-12-02 19:46:34.5898
- Title: Efficiently Learning Branching Networks for Multitask Algorithmic Reasoning
- Title（参考訳）: マルチタスクアルゴリズム推論のための分岐ネットワークの学習
- Authors: Dongyue Li, Zhenshuo Zhang, Minxuan Duan, Edgar Dobriban, Hongyang R. Zhang,
- Abstract要約: AutoBRANEはマルチタスクのアルゴリズム推論のための原則的アーキテクチャである。
勾配ベースの親和性スコアを使用してタスクをクラスタリングし、任意のベースモデル上で使用することができる。
既存のマルチタスクやブランチアーキテクチャよりも28%の精度向上を実現している。
- 参考スコア（独自算出の注目度）: 28.332657856837788
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Algorithmic reasoning -- the ability to perform step-by-step logical inference -- has become a core benchmark for evaluating reasoning in graph neural networks (GNNs) and large language models (LLMs). Ideally, one would like to design a single model capable of performing well on multiple algorithmic reasoning tasks simultaneously. However, this is challenging when the execution steps of algorithms differ from one another, causing negative interference when they are trained together. We propose branching neural networks, a principled architecture for multitask algorithmic reasoning. Searching for the optimal $k$-ary tree with $L$ layers over $n$ algorithmic tasks is combinatorial, requiring exploration of up to $k^{nL}$ possible structures. We develop AutoBRANE, an efficient algorithm that reduces this search to $O(nL)$ time by solving a convex relaxation at each layer to approximate an optimal task partition. The method clusters tasks using gradient-based affinity scores and can be used on top of any base model, including GNNs and LLMs. We validate AutoBRANE on a broad suite of graph-algorithmic and text-based reasoning benchmarks. We show that gradient features estimate true task performance within 5% error across four GNNs and four LLMs (up to 34B parameters). On the CLRS benchmark, it outperforms the strongest single multitask GNN by 3.7% and the best baseline by 1.2%, while reducing runtime by 48% and memory usage by 26%. The learned branching structures reveal an intuitively reasonable hierarchical clustering of related algorithms. On three text-based graph reasoning benchmarks, AutoBRANE improves over the best non-branching multitask baseline by 3.2%. Finally, on a large graph dataset with 21M edges and 500 tasks, AutoBRANE achieves a 28% accuracy gain over existing multitask and branching architectures, along with a 4.5$\times$ reduction in runtime.
- Abstract（参考訳）: アルゴリズム推論 -- ステップバイステップの論理推論を実行する能力 -- が、グラフニューラルネットワーク(GNN)と大規模言語モデル(LLM)の推論を評価するためのコアベンチマークになった。
理想的には、複数のアルゴリズム推論タスクを同時に実行可能な単一のモデルを設計したい。
しかし、アルゴリズムの実行ステップが互いに異なる場合、これらが一緒に訓練された場合、負の干渉を引き起こすため、これは難しい。
本稿では,マルチタスクアルゴリズム推論の原理的アーキテクチャである分岐ニューラルネットワークを提案する。
最適な$k$-ary木を$n$のアルゴリズム的タスクより$L$の層で探索することは組合せであり、最大$k^{nL}$可能な構造を探索する必要がある。
我々は,各層での凸緩和を解き,最適なタスク分割を近似することにより,この探索時間を$O(nL)$ timeに削減するアルゴリズムであるAutoBRANEを開発した。
このメソッドは勾配ベースの親和性スコアを使用してタスクをクラスタリングし、GNNやLLMを含む任意のベースモデル上で使用することができる。
グラフアルゴリズムとテキストベースの推論ベンチマークを用いてAutoBRANEを検証する。
4つのGNNと4つのLLM(最大34Bパラメータ)で5%の誤差で真のタスク性能を推定する。
CLRSベンチマークでは、最強のシングルマルチタスクGNNを3.7%、最高のベースラインを1.2%、ランタイムを48%、メモリ使用量を26%上回っている。
学習された分岐構造は、関連するアルゴリズムの直感的に合理的な階層的クラスタリングを明らかにする。
3つのテキストベースのグラフ推論ベンチマークでは、AutoBRANEは最高の非分岐マルチタスクベースラインを3.2%改善している。
最後に、21Mエッジと500タスクのグラフデータセット上で、AutoBRANEは既存のマルチタスクとブランチアーキテクチャよりも28%の精度で、実行時の4.5$\times$reduceを達成している。
関連論文リスト
- Log-Time K-Means Clustering for 1D Data: Novel Approaches with Proof and Implementation [0.0]
この論文は、1D$k$-meansクラスタリングの理論と実践を橋渡しし、効率的で健全なアルゴリズムを提供する。
ベンチマークでは、大規模なデータセットのScikit-learnと比較して、4500倍のスピードアップが示されている。
論文 参考訳（メタデータ） (2024-12-19T09:03:39Z) - On Statistical Learning of Branch and Bound for Vehicle Routing
Optimization [3.6922704509753084]
我々は,計算コストの高いStrong Branching戦略の決定過程をエミュレートするためにニューラルネットワークを訓練する。
このアプローチは分岐とバウンドのアルゴリズムの性能にマッチするか、改善することができる。
論文 参考訳（メタデータ） (2023-10-15T23:59:57Z) - Autonomous Tree-search Ability of Large Language Models [58.68735916408101]
大規模言語モデルは、高度なプロンプト技術で顕著な推論能力に優れています。
近年の研究では、LLMがより困難な推論タスクを解くために受動的木探索を行えるように、検索ロジックを定義するために外部プログラムを活用することが提案されている。
我々は,LLMの自律木探索能力という新しい概念を提案し,正しい解を求める探索軌跡を含む応答を自動生成する。
論文 参考訳（メタデータ） (2023-10-14T14:14:38Z) - Breaking 3-Factor Approximation for Correlation Clustering in
Polylogarithmic Rounds [0.23633885460047763]
相関クラスタリング問題に対する並列アルゴリズムについて検討する。
目標は、エンティティをクラスタに分割し、ラベルとの相違を最小限にすることである。
現在、全ての効率的な並列アルゴリズムは、近似比が少なくとも3である。
3 より優れた近似比を実現するための最初の多元対数アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-07-13T12:32:49Z) - On the Sample Complexity of Representation Learning in Multi-task
Bandits with Global and Local structure [77.60508571062958]
マルチタスク・バンディット問題に対する最適アーム学習の複雑さについて検討した。
アームは2つのコンポーネントで構成されます。1つはタスク間で共有され(表現と呼ばれます)、もう1つはタスク固有のもの(予測器と呼ばれます)です。
サンプルの複雑さが下界に近づき、最大で$H(Glog(delta_G)+ Xlog(delta_H))$でスケールするアルゴリズムOSRL-SCを考案する。
論文 参考訳（メタデータ） (2022-11-28T08:40:12Z) - Communication-Efficient Adam-Type Algorithms for Distributed Data Mining [93.50424502011626]
我々はスケッチを利用した新しい分散Adam型アルゴリズムのクラス(例:SketchedAMSGrad)を提案する。
我々の新しいアルゴリズムは、反復毎に$O(frac1sqrtnT + frac1(k/d)2 T)$の高速収束率を$O(k log(d))$の通信コストで達成する。
論文 参考訳（メタデータ） (2022-10-14T01:42:05Z) - Arch-Graph: Acyclic Architecture Relation Predictor for
Task-Transferable Neural Architecture Search [96.31315520244605]
Arch-Graphはタスク固有の最適アーキテクチャを予測するトランスファー可能なNASメソッドである。
Arch-Graphの転送性と,多数のタスクにわたる高いサンプル効率を示す。
わずか50モデルの予算の下で、2つの検索スペースで平均して0.16%と0.29%のアーキテクチャを見つけることができる。
論文 参考訳（メタデータ） (2022-04-12T16:46:06Z) - Neural network relief: a pruning algorithm based on neural activity [47.57448823030151]
重要でない接続を非活性化する簡易な重要スコア計量を提案する。
MNIST上でのLeNetアーキテクチャの性能に匹敵する性能を実現する。
このアルゴリズムは、現在のハードウェアとソフトウェアの実装を考えるとき、FLOPを最小化するように設計されていない。
論文 参考訳（メタデータ） (2021-09-22T15:33:49Z) - An Empirical Comparison of Off-policy Prediction Learning Algorithms in
the Four Rooms Environment [9.207173776826403]
我々は,11の非政治予測学習アルゴリズムと2つの小さなタスクに対する線形関数近似を経験的に比較した。
アルゴリズムの性能は、重要サンプリング比によって引き起こされるばらつきに強く影響される。
強調的なTD($lambda$)は、他のアルゴリズムよりもエラーが少ない傾向にあるが、場合によってはよりゆっくりと学習することもある。
論文 参考訳（メタデータ） (2021-09-10T21:15:41Z) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。
問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。
本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-07T08:00:02Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。