# Efficiently Learning Branching Networks for Multitask Algorithmic Reasoning

arXiv: https://arxiv.org/abs/2512.01113 · HTML: https://mlsanity.com/paper/2512.01113/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Placed in Test-time compute and efficient thinking, one of 17 directions in LLM reasoning.
- Builds on 45 of its 56 references that are in the map.
- First posted on arXiv 30 Nov 2025.

## Placed in

- LLM reasoning / [Test-time compute and efficient thinking](https://mlsanity.com/lr/test-time-compute-and-efficient-thinking/)

## Builds on (most cited first, 30 of 45)

- [LoRA: Low-Rank Adaptation of Large Language Models](https://mlsanity.com/paper/2106.09685/) (2021)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Neural Tangent Kernel: Convergence and Generalization in Neural Networks](https://mlsanity.com/paper/1806.07572/) (2018)
- [Show Your Work: Scratchpads for Intermediate Computation with Language Models](https://mlsanity.com/paper/2112.00114/) (2021)
- [An Overview of Multi-Task Learning in Deep Neural Networks](https://mlsanity.com/paper/1706.05098/) (2017)
- [SIGN: Scalable Inception Graph Neural Networks](https://mlsanity.com/paper/2004.11198/) (2020)
- [TRAK: Attributing Model Behavior at Scale](https://mlsanity.com/paper/2303.14186/) (2023)
- [Can Language Models Solve Graph Problems in Natural Language?](https://mlsanity.com/paper/2305.10037/) (2023)
- [Efficiently Identifying Task Groupings for Multi-Task Learning](https://mlsanity.com/paper/2109.04617/) (2021)
- [Datamodels: Predicting Predictions from Training Data](https://mlsanity.com/paper/2202.00622/) (2022)
- [Talk like a Graph: Encoding Graphs for Large Language Models](https://mlsanity.com/paper/2310.04560/) (2023)
- [GreaseLM: Graph REASoning Enhanced Language Models for Question Answering](https://mlsanity.com/paper/2201.08860/) (2022)
- [Do Large Language Models Latently Perform Multi-Hop Reasoning?](https://mlsanity.com/paper/2402.16837/) (2024)
- [Neural Execution of Graph Algorithms](https://mlsanity.com/paper/1910.10593/) (2019)
- [Let Your Graph Do the Talking: Encoding Structured Data for LLMs](https://mlsanity.com/paper/2402.05862/) (2024)
- [Learning to Branch for Multi-Task Learning](https://mlsanity.com/paper/2006.01895/) (2020)
- [DSelect-k: Differentiable Selection in the Mixture of Experts with Applications to Multi-Task Learning](https://mlsanity.com/paper/2106.03760/) (2021)
- [Understanding and Improving Information Transfer in Multi-Task Learning](https://mlsanity.com/paper/2005.00944/) (2020)
- [The CLRS Algorithmic Reasoning Benchmark](https://mlsanity.com/paper/2205.15659/) (2022)
- [Neural Algorithmic Reasoning](https://mlsanity.com/paper/2105.02761/) (2021)
- [Fully-adaptive Feature Sharing in Multi-Task Networks with Applications in Person Attribute Classification](https://mlsanity.com/paper/1611.05377/) (2016)
- [Hopping Too Late: Exploring the Limitations of Large Language Models on Multi-Hop Queries](https://mlsanity.com/paper/2406.12775/) (2024)
- [Branched Multi-Task Networks: Deciding What Layers To Share](https://mlsanity.com/paper/1904.02920/) (2019)
- [Iteratively Prompt Pre-trained Language Models for Chain of Thought](https://mlsanity.com/paper/2203.08383/) (2022)
- [Graph Neural Prompting with Large Language Models](https://mlsanity.com/paper/2309.15427/) (2023)
- [A Generalist Neural Algorithmic Learner](https://mlsanity.com/paper/2209.11142/) (2022)
- [GraphInstruct: Empowering Large Language Models with Graph Understanding and Reasoning Capability](https://mlsanity.com/paper/2403.04483/) (2024)
- [GraphArena: Evaluating and Exploring Large Language Models on Graph Computation](https://mlsanity.com/paper/2407.00379/) (2024)
- [GraphWiz: An Instruction-Following Language Model for Graph Problems](https://mlsanity.com/paper/2402.16029/) (2024)
- [Heat kernel based community detection](https://mlsanity.com/paper/1403.3148/) (2014)

## Built on by (most cited first, 1 of 1)

- [Quantifying the Stability of Multi-Step Reasoning via Error Amplification](https://mlsanity.com/paper/2610.06404/) (2026)

## Abstract (arXiv)

Algorithmic reasoning -- the ability to perform step-by-step logical inference -- is a synthetic benchmark for evaluating multi-step reasoning abilities, designed for graph neural networks and also for transformer models. Prior work has evaluated reasoning for executing a single algorithmic task, whereas a more desirable objective is to perform multiple algorithmic reasoning tasks simultaneously. We start by noting that this is inherently difficult due to differences arising from the execution traces of the algorithms (such as depth- vs. breadth-first search), which cause interference when they are trained together. In this paper, we introduce branching neural networks, a new architecture for multitask algorithmic reasoning. The main idea is to search for a recursive tree-structured partition of n algorithmic tasks into a k-ary tree (divided into L layers). Naive search requires O(knL) complexity; we develop an algorithm that reduces this to O(nL) by solving a convex relaxation at each layer to approximate an optimal partition. Our approach clusters these tasks using gradient-based affinity and can be used on top of any base model. We validate our approach on algorithmic reasoning benchmarks and their extensions with text descriptions. We show that gradient-based affinity scores help estimate true performance with less than 5% error, measured across eight different architectures with up to 34 billion parameters. On the CLRS benchmark, our approach outperforms existing graph neural networks by 3.7% and baselines by 1.2%, while reducing runtime by 48% and memory usage by 26%. The learned branching structure shows a hierarchical clustering of related algorithms. On three text-based graph reasoning benchmarks, our approach improves over baseline methods by 3.2%. Finally, we validate our approach for overlapping community detection.