Pith. sign in

REVIEW 3 major objections 5 minor 53 references

For multitask algorithmic reasoning, the optimal branching structure can be found in O(nL) time instead of O(k^{nL}), by reading task affinities from gradients at one shared initialization; branching networks built this way beat shared and

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · deepseek-v4-flash

2026-08-03 19:16 UTC pith:ADIWB4QB

load-bearing objection AutoBRANE is a useful combination of existing ideas with a plausible but under-validated search algorithm; gains are real on Edge Transformer but not consistent, and the 5% approximation claim is not backed by the right metric. the 3 major comments →

arxiv 2512.01113 v2 pith:ADIWB4QB submitted 2025-11-30 cs.LG cs.AIcs.DS

Efficiently Learning Branching Networks for Multitask Algorithmic Reasoning

Dongyue Li , Zhenshuo Zhang , Minxuan Duan , Edgar Dobriban , Hongyang R. Zhang This is my paper
classification cs.LG cs.AIcs.DS
keywords branching neural networksmultitask learningalgorithmic reasoningtask affinitygradient-based approximationconvex relaxationparameter sharinggraph neural networks
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

Multitask algorithmic reasoning—one model executing many graph algorithms step by step—suffers from interference when algorithms with different execution traces (BFS vs. DFS) are trained together. The paper's central claim is that a tree-structured 'branching network,' in which similar tasks share early layers and split later, can capture these differences, and that the optimal tree can be found efficiently. Naively searching over all k-ary trees of L layers over n tasks takes O(k^{nL}) time; the paper's AutoBRANE procedure reduces this to O(nL) by estimating pairwise task affinities from gradients at a single multitask initialization and solving a convex relaxation at each layer. On twelve CLRS graph-algorithm tasks, the method improves average accuracy by 3.7% over a single shared Edge Transformer and by 1.2% over the strongest multitask baselines, while cutting GPU hours by 48% and memory by 26%. The same recipe works on text-based graph reasoning with LoRA adapters and on a 500-task community detection problem, suggesting the branching architecture, not the specific backbone, is what carries the gain.

Core claim

The central claim is that task affinities for algorithmic reasoning can be read off from the geometry of a shared initialization. For any pair of tasks, the paper defines a layer-wise affinity score by the loss of a model fine-tuned on random task subsets containing both tasks, then shows this score can be approximated without retraining: a first-order Taylor expansion of network outputs around the multitask initialization turns the problem into logistic regression on projected gradients. These affinities are clustered by a convex (semi-definite) relaxation at each layer, and the layers are searched top-down, so the whole structure is found in O(nL) time instead of O(k^{nL}). The paper argue

What carries the argument

The load-bearing object is the layer-wise gradient-based affinity score, computed from a first-order Taylor expansion of the network output around a multitask-trained initialization, combined with a convex (semi-definite) relaxation that partitions tasks at each layer. The first-order expansion converts what would require retraining on every task subset into a single gradient computation plus a low-dimensional logistic regression in the projected gradient space; the SDP relaxation turns the hard cluster-density maximization into a tractable optimization. Together they drive a top-down recursive tree search that runs in O(nL), with memory of about kB/L for k final branches.

Load-bearing premise

The whole search procedure rests on the assumption that a first-order Taylor expansion of network outputs around a multitask-trained initialization approximates the loss of fine-tuned models well enough—within a few percent—at the parameter distances where fine-tuning actually lands, so gradient-derived affinities identify the right branching structure.

What would settle it

Fully retrain all task subsets for a moderate n (say 12) to compute true affinity scores and the true best tree, then compare against AutoBRANE's gradient-approximated tree: if the gradient tree's test loss is worse than the true tree by more than the paper's stated ~5% approximation error, or if random branch assignments match AutoBRANE's accuracy, the load-bearing premise fails. A cheaper check: fine-tune a 1.7B model to 20% weight distance and measure RSS; if it exceeds 10%, the linear approximation regime is violated.

Watch this falsifier. Get emailed when new claim-graph text bears on it.

If this is right

  • The search for branching structures becomes practical for large task sets: the O(nL) runtime makes it possible to consider hundreds of tasks where the naive O(k^{nL}) search would be impossible.
  • Because affinity estimation needs only one pass of gradients at a shared initialization, adding a new task to an existing branching network can be done incrementally without retraining the whole tree.
  • The learned tree is interpretable: it groups algorithms by the similarity of their intermediate steps (e.g., BFS with Bellman-Ford, Prim with Dijkstra), and swapping tasks between branches costs more than 2% in performance.
  • The same algorithm applies to different backbones—GNNs, edge transformers, and LLMs fine-tuned with LoRA—so the branching architecture, not the specific encoder, drives the measured gains.
  • In a 500-task community detection setting, branching still yields a 28% gain over baselines with a 4.5× runtime reduction, indicating the approach transfers beyond synthetic algorithmic benchmarks.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Inference: If gradient affinities at a shared initialization are this informative for algorithmic tasks, the same local-geometry principle should apply to other multitask settings where fine-tuning stays near initialization—e.g., multi-dataset instruction tuning—though the paper only demonstrates it for algorithmic reasoning and community detection.
  • Inference: The learned tree could be reused as a prior for task selection or curriculum design: a new task's gradient signature can be compared against branch centroids to decide which branch to extend, a use the paper mentions but does not fully test.
  • Inference: The approximation error grows with parameter distance (Table 2), so the method's success depends on fine-tuned models staying within roughly 10% weight distance of the initialization; if future training regimes move weights further, higher-order or layer-wise corrections may be needed.
  • Inference: The approach suggests a testable hypothesis about negative transfer: tasks whose branch affinities are low should show worse multitask performance in a shared network, so the affinity matrix itself could serve as a diagnostic before training.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

3 major / 5 minor

Summary. The paper introduces AutoBRANE, a method for automatically constructing branching (tree-structured) neural networks for multitask algorithmic reasoning. Starting from a shared initialization, it recursively partitions tasks into k groups per layer using task-affinity scores. Affinities are estimated from a first-order Taylor approximation of validation losses on random task subsets, using logistic regression on projected gradients, followed by SDP-based clustering. The authors claim this reduces the search complexity from O(k^{nL}) to O(nL), that the first-order approximation is accurate to within 5% across eight architectures up to 34B parameters, and that AutoBRANE improves CLRS multitask reasoning by 3.7% over a single Edge Transformer and by 1.2% over strong multitask baselines, while reducing runtime and memory. Additional experiments cover text-based graph reasoning benchmarks and a 500-task community detection task.

Significance. If the underlying approximation is reliable, this is a practically valuable contribution. The paper addresses a real scalability bottleneck in multitask algorithmic reasoning, is model-agnostic in design, ships code, and provides a broad empirical evaluation across GNNs, LLMs, and a large community-detection setting. The learned branching structures are also interpretable and align with algorithmic similarity. However, the central load-bearing premise—that gradient-based first-order approximations accurately estimate the validation losses and affinity scores that drive every split—is not directly validated by the reported metric. Moreover, on one of the base models (MPNN) the method does not improve over single-task training, which weakens the model-agnostic claim. The contribution is promising but not yet fully established as stated.

major comments (3)
  1. [§4.2, Table 2 and Eq. (2)] The 'less than 5% approximation error' claim is about the wrong quantity. Table 2 reports the normalized squared error of the network output (RSS), but Eq. (2) and Algorithm 1 require estimates of the validation loss Lhat^{(i)}(f_W(S_k)) for random subsets. Small output RSS does not imply small error in the estimated loss, nor in the ranking of affinities that determines the partition. Proposition 3.3 bounds training loss only (Eq. 4), with an additive 2δ + 2GDε term, and gives no bound on validation loss or on affinity ranking. To support the central premise, the paper should report e.g. correlation/rank agreement between predicted and true validation losses, or compare partitions obtained from approximate versus exact affinities on a subset of tasks. As written, the search could be misestimated while Table 2 still looks acceptable.
  2. [§4.3.2, Table 11 (MPNN)] With MPNN as the base model, AutoBRANE obtains an average score of 74.6, which is lower than single-task training (STN) at 75.2. This contradicts the abstract and introduction statements that AutoBRANE improves multitask algorithmic reasoning and 'can be used on top of any base model.' The paper should either restrict the strong-claim to Edge Transformer/GAT and discuss why MPNN does not benefit, or substantially temper the model-agnostic claim. Without this, the generality claim is not supported by the reported evidence.
  3. [§3.2, Table 1] The claimed complexity reduction from O(k^{nL}) to O(nL) is for a greedy top-down heuristic, not an exact optimizer. The paper does not characterize the suboptimality gap between the tree found by AutoBRANE and the optimum of the affinity-based objective, nor does it analyze error propagation when a wrong split at an early layer constrains all later splits. The comparison to exhaustive search is therefore somewhat misleading: the method does not actually search the full tree space, but replaces it with a different, heuristic objective. A formal statement of what is being optimized, or an empirical sensitivity analysis to early split errors, would make this claim more meaningful.
minor comments (5)
  1. [Abstract and §4.3.2] The abstract says 'outperforms existing graph neural networks by 3.7%' but the specific comparison in §4.3.2 is against a single multitask Edge Transformer (MTN). Given the MPNN result in Table 11, the wording should be more precise about the base model and baseline.
  2. [Eq. (3) and Algorithm 1] The notation W(0) vs W_{l:L} is not fully consistent; Algorithm 1 line 9 also contains a typo ('arg min P' and 'P X'). Please clarify that W(0) is the initialization after fine-tuning layers l..L with layers 1..l-1 frozen.
  3. [Table 10 / Appendix C.2] The text claims RSS falls below 0.06% after freezing the first three layers, but Table 10 shows values such as 6.7×10^-4 = 0.067%. Please check the arithmetic and the wording.
  4. [Appendix C.2] There is a typo: 'B2 yields 4.8% better lower error rates than B2' should presumably read 'B1 ... than B2'.
  5. [Figure 5 / §4.3.4] The validation of learned branching structures via 'randomly varying the positions of tasks' is only briefly described. State how many random permutations were tried, whether the 2% drop is an average or maximum, and whether the difference is statistically significant.

Circularity Check

0 steps flagged

No circular derivation; core affinity approximation is independently validated and results are measured on external benchmarks.

full rationale

AutoBRANE's derivation chain starts from a defined affinity score T (Eq. 2) and estimates it via a first-order Taylor expansion (Eq. 3) plus a logistic regression on projected gradients. The estimate is not defined in terms of the final branching structure or the reported test scores; the target quantity (validation loss of fine-tuned models) is external to the approximation. The paper's Table 2 directly measures the fidelity of the Taylor approximation against actually fine-tuned models, and downstream comparisons on CLRS, CLRS-Text, GraphQA, GraphWiz, and Orkut are external benchmarks that are not used to fit the affinity estimator. Proposition 3.3 is a bound on the training loss of the approximate solution, not an assumption of the conclusion. The most substantial caveat is that Table 2 reports RSS of output approximation rather than error in the estimated validation losses or affinity rankings, and Prop 3.3 bounds training loss only; that is a correctness/robustness concern, not a circularity. Self-citations to the authors' prior gradient-affinity work (e.g., GradTAG [20]) are present and used as building blocks, but they are backed by new experiments in this paper and are not invoked as an unverified uniqueness theorem, so they do not make the derivation circular. Score 2 reflects only minor self-citation presence; no step reduces a predicted quantity to its own input by construction.

Axiom & Free-Parameter Ledger

6 free parameters · 5 axioms · 0 invented entities

The method introduces a new architecture (branching network) and a search algorithm, but no new physical entities. The free parameters are mostly standard hyperparameters; the key load-bearing assumption is the accuracy of the first-order approximation for estimating task affinities.

free parameters (6)
  • m (number of random subsets) = 200-5000
    Tuned until affinity scores stabilize; m > 10n is suggested.
  • α (subset size) = 3-25
    Number of tasks sampled per subset; chosen by stability.
  • d (gradient projection dimension) = 200-1000
    Projection dimension; authors state d > 400 gives <5% error, but Table 2 suggests higher error.
  • L (number of layers) = 3-6 for GNNs, 28/16 for LLMs
    Tuned on validation; corresponds to network depth.
  • k (number of clusters per layer) = 10 (CLRS), 22 (Orkut)
    Chosen to maximize within-cluster affinity while limiting tree growth.
  • λ (SDP regularization) = not reported
    Controls penalty on number of clusters; value not specified in paper.
axioms (5)
  • domain assumption The first-order Taylor expansion of the network output around a multitask-initialized W(0) has bounded error δ (assumed in Prop. 3.3).
    Section 3.1 and Eq. 3; the whole affinity estimation relies on this approximation being accurate enough to cluster tasks correctly.
  • standard math The logistic loss is 1-Lipschitz continuous.
    Used in the proof of Prop. 3.3 to bound approximation error via the mean value theorem.
  • standard math Johnson-Lindenstrauss lemma holds for random projections of gradients.
    Used to justify reducing gradient dimension from p to d with bounded distortion.
  • domain assumption Gradient-based affinity scores predict the success of parameter sharing in multitask learning.
    The method clusters tasks by these affinities; if they do not reflect transfer, the branch structure will not help. This is an empirical assumption validated only indirectly.
  • domain assumption The SDP relaxation of the clustering problem yields a good approximation to the NP-hard cluster assignment.
    Used in Appendix B.1; no guarantee is provided for the rounding step.

pith-pipeline@v1.3.0-alltime-deepseek · 27517 in / 11619 out tokens · 117204 ms · 2026-08-03T19:16:30.363824+00:00 · methodology

0 comments
read the original abstract

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(k^{nL})$ 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.

Figures

Figures reproduced from arXiv: 2512.01113 by Dongyue Li, Edgar Dobriban, Hongyang R. Zhang, Minxuan Duan, Zhenshuo Zhang.

Figure 1
Figure 1. Figure 1: An illustration of our problem setup and the proposed solution. [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: We give three examples of algorithmic reasoning tasks: Breadth-first search (BFS), [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: We present three examples of branching GNNs, each designed to learn a pair of algorithms. [PITH_FULL_IMAGE:figures/full_fig_p006_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Illustration of the trade-off between error rate, GPU hours, and memory usage for [PITH_FULL_IMAGE:figures/full_fig_p013_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Illustration of the tree structure of the branching network learned on twelve algorithmic [PITH_FULL_IMAGE:figures/full_fig_p013_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: We illustrate the sample complexity scaling for learning three graph algorithms on graphs [PITH_FULL_IMAGE:figures/full_fig_p015_6.png] view at source ↗

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

53 extracted references · 5 linked inside Pith

  1. [1]

    Local computation of pagerank contributions

    R. Andersen, C. Borgs, J. Chayes, J. Hopcraft, V. S. Mirrokni, and S.-H. Teng. “Local computation of pagerank contributions”. In:International Workshop on Algorithms and Models for the Web-Graph. Springer. 2007, pp. 150–165 (page 16)

    2007

  2. [2]

    Transformers meet Neural Algorithmic Reasoners

    W. Bounsi, B. Ibarz, A. Dudzik, J. B. Hamrick, L. Markeeva, A. Vitvitskyi, R. Pascanu, and P. Veličković. “Transformers meet Neural Algorithmic Reasoners”. In:arXiv preprint arXiv:2406.09308(2024) (page 16)

    Pith/arXiv arXiv 2024

  3. [3]

    GraphWiz: An Instruction-Following Language Model for Graph Problems

    N. Chen, Y. Li, J. Tang, and J. Li. “GraphWiz: An Instruction-Following Language Model for Graph Problems”. In:KDD(2024) (pages 2, 3, 10, 16, 26, 28)

    2024

  4. [4]

    T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein.Introduction to algorithms. MIT press, 2022 (page 15)

    2022

  5. [5]

    Talk like a Graph: Encoding Graphs for Large Language Models

    B. Fatemi, J. Halcrow, and B. Perozzi. “Talk like a Graph: Encoding Graphs for Large Language Models”. In:ICLR. 2023 (pages 2, 3, 10, 16, 25, 26, 28)

    2023

  6. [6]

    Computers and thought

    E. A. Feigenbaum and J. Feldman. “Computers and thought.” In: (1963) (page 1)

    1963

  7. [7]

    Efficiently identifying task groupings for multi-task learning

    C. Fifty, E. Amid, Z. Zhao, T. Yu, R. Anil, and C. Finn. “Efficiently identifying task groupings for multi-task learning”. In:Advances in Neural Information Processing Systems34 (2021), pp. 27503–27516 (pages 8, 9, 12)

    2021

  8. [8]

    Sign: Scalable inception graph neural networks

    F. Frasca, E. Rossi, D. Eynard, B. Chamberlain, M. Bronstein, and F. Monti. “Sign: Scalable inception graph neural networks”. In:arXiv preprint arXiv:2004.11198(2020) (page 11)

    Pith/arXiv arXiv 2004

  9. [9]

    Beyond erdos-renyi: Generalization in algorithmic reasoning on graphs

    D. G. Georgiev, P. Lio, J. Bachurski, J. Chen, T. Shi, and L. Giusti. “Beyond erdos-renyi: Generalization in algorithmic reasoning on graphs”. In:The Second Learning on Graphs Conference. 2023 (page 4)

    2023

  10. [10]

    Learning to branch for multi-task learning

    P. Guo, C.-Y. Lee, and D. Ulbricht. “Learning to branch for multi-task learning”. In:ICML. PMLR. 2020 (pages 3, 4, 8–10, 12–15, 24)

    2020

  11. [11]

    Dselect-k: Differentiable selection in the mixture of experts with applications to multi-task learning

    H. Hazimeh, Z. Zhao, A. Chowdhery, M. Sathiamoorthy, Y. Chen, R. Mazumder, L. Hong, and E. Chi. “Dselect-k: Differentiable selection in the mixture of experts with applications to multi-task learning”. In:NeurIPS(2021) (pages 9, 16)

    2021

  12. [12]

    Lora: Low-rank adaptation of large language models

    E. J. Hu, Y. Shen, P. Wallis, Z. Allen-Zhu, Y. Li, S. Wang, L. Wang, and W. Chen. “Lora: Low-rank adaptation of large language models”. In:ICLR(2021) (pages 5, 10, 11, 25, 29). 17

    2021

  13. [13]

    A generalist neural algorithmic learner

    B. Ibarz, V. Kurin, G. Papamakarios, K. Nikiforou, M. Bennani, R. Csordás, A. J. Dudzik, M. Bošnjak, A. Vitvitskyi, Y. Rubanova, A. Deac, B. Bevilacqua, Y. Ganin, C. Blundell, and P. Veličković. “A generalist neural algorithmic learner”. In:Learning on graphs conference. 2022 (pages 2, 3, 11, 12, 15)

    2022

  14. [14]

    Datamodels: Predicting predictions from training data

    A. Ilyas, S. M. Park, L. Engstrom, G. Leclerc, and A. Madry. “Datamodels: Predicting predictions from training data”. In:International conference on machine learning(2022) (page 3)

    2022

  15. [15]

    Neural tangent kernel: Convergence and generalization in neural networks

    A. Jacot, F. Gabriel, and C. Hongler. “Neural tangent kernel: Convergence and generalization in neural networks”. In:Advances in neural information processing systems31 (2018) (pages 3, 7)

    2018

  16. [16]

    Extensions of Lipshitz mapping into Hilbert space

    W. B. Johnson. “Extensions of Lipshitz mapping into Hilbert space”. In:Conference modern analysis and probability, 1984. 1984, pp. 189–206 (pages 10, 22)

    1984

  17. [17]

    Heat kernel based community detection

    K. Kloster and D. F. Gleich. “Heat kernel based community detection”. In:Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining. 2014, pp. 1386–1395 (page 16)

    2014

  18. [18]

    Boosting multitask learning on graphs through higher-order task affinities

    D. Li, H. Ju, A. Sharma, and H. R. Zhang. “Boosting multitask learning on graphs through higher-order task affinities”. In:KDD. 2023 (pages 6, 9, 29)

    2023

  19. [19]

    Identification of Negative Transfers in Multitask Learning Using Surrogate Models

    D. Li, H. Nguyen, and H. R. Zhang. “Identification of Negative Transfers in Multitask Learning Using Surrogate Models”. In:Transactions on Machine Learning Research(2023) (pages 6, 16)

    2023

  20. [20]

    Scalable Multitask Learning Using Gradient-based Estimation of Task Affinity

    D. Li, A. Sharma, and H. R. Zhang. “Scalable Multitask Learning Using Gradient-based Estimation of Task Affinity”. In:KDD. 2024 (pages 6, 7, 10, 12–14)

    2024

  21. [21]

    Scalable Fine-tuning from Multiple Data Sources: A First-Order Approximation Approach

    D. Li, Z. Zhang, L. Wang, and H. Zhang. “Scalable Fine-tuning from Multiple Data Sources: A First-Order Approximation Approach”. In:Findings of the Association for Computational Linguistics: EMNLP 2024. 2024, pp. 5608–5623 (pages 3, 4, 29, 31)

    2024

  22. [22]

    Efficient Ensemble for Fine-tuning Language Models on Multiple Datasets

    D. Li, Z. Zhang, L. Wang, and H. R. Zhang. “Efficient Ensemble for Fine-tuning Language Models on Multiple Datasets”. In:ACL(2025) (page 16)

    2025

  23. [23]

    Topological structure of complex predictions

    M. Liu, T. K. Dey, and D. F. Gleich. “Topological structure of complex predictions”. In:Nature Machine Intelligence5.12 (2023), pp. 1382–1389 (page 16)

    2023

  24. [24]

    Fully-adaptive feature sharing in multi-task networks with applications in person attribute classification

    Y. Lu, A. Kumar, S. Zhai, Y. Cheng, T. Javidi, and R. Feris. “Fully-adaptive feature sharing in multi-task networks with applications in person attribute classification”. In:CVPR. 2017 (pages 15, 24)

    2017

  25. [25]

    Simulation of Graph Algorithms with Looped Transform- ers

    A. B. de Luca and K. Fountoulakis. “Simulation of Graph Algorithms with Looped Transform- ers”. In:International Conference on Machine Learning. 2024 (page 4)

    2024

  26. [26]

    Graphinstruct: Empowering large language models with graph understanding and reasoning capability

    Z. Luo, X. Song, H. Huang, J. Lian, C. Zhang, J. Jiang, and X. Xie. “Graphinstruct: Empowering large language models with graph understanding and reasoning capability”. In:arXiv preprint arXiv:2403.04483(2024) (page 16)

    arXiv 2024

  27. [27]

    Modeling task relationships in multi-task learning with multi-gate mixture-of-experts

    J. Ma, Z. Zhao, X. Yi, J. Chen, L. Hong, and E. H. Chi. “Modeling task relationships in multi-task learning with multi-gate mixture-of-experts”. In:KDD. 2018 (pages 9, 12, 16)

    2018

  28. [28]

    The CLRS-Text Algorithmic Reasoning Language Benchmark

    L. Markeeva, S. McLeish, B. Ibarz, W. Bounsi, O. Kozlova, A. Vitvitskyi, C. Blundell, T. Goldstein, A. Schwarzschild, and P. Veličković. “The CLRS-Text Algorithmic Reasoning Language Benchmark”. In:arXiv preprint arXiv:2406.04229(2024) (pages 3, 10, 11, 16, 24, 25, 29). 18

    Pith/arXiv arXiv 2024

  29. [29]

    Towards Principled Graph Transformers

    L. Müller, D. Kusuma, B. Bonet, and C. Morris. “Towards Principled Graph Transformers”. In: NeurIPS(2024) (pages 2, 3, 6, 10–13, 15, 29)

    2024

  30. [30]

    Show Your Work: Scratchpads for Intermediate Computation with Language Models

    M. Nye, A. J. Andreassen, G. Gur-Ari, H. Michalewski, J. Austin, D. Bieber, D. Dohan, A. Lewkowycz, M. Bosma, D. Luan, C. Sutton, and A. Odena. “Show Your Work: Scratchpads for Intermediate Computation with Language Models”. In:Deep Learning for Code Workshop. 2022 (page 2)

    2022

  31. [31]

    Trak: Attributing model behavior at scale

    S. M. Park, K. Georgiev, A. Ilyas, G. Leclerc, and A. Madry. “Trak: Attributing model behavior at scale”. In:ICML(2023) (page 3)

    2023

  32. [32]

    Let your graph do the talking: Encoding structured data for llms

    B. Perozzi, B. Fatemi, D. Zelle, A. Tsitsulin, M. Kazemi, R. Al-Rfou, and J. Halcrow. “Let your graph do the talking: Encoding structured data for llms”. In:arXiv preprint arXiv:2402.05862 (2024) (page 16)

    Pith/arXiv arXiv 2024

  33. [33]

    An Overview of Multi-Task Learning in Deep Neural Networks

    S. Ruder. “An Overview of Multi-Task Learning in Deep Neural Networks”. In:arXiv preprint arXiv:1706.05098(2017) (pages 12, 14)

    Pith/arXiv arXiv 2017

  34. [34]

    Artificial Intelligence: A modern approach

    S. Russell and P. Norvig. “Artificial Intelligence: A modern approach”. In:Artificial Intelligence. Prentice-Hall, Egnlewood Cliffs25.27 (1995), pp. 79–80 (page 1)

    1995

  35. [35]

    Understanding transformer reasoning capabilities via graph algorithms

    C. Sanford, B. Fatemi, E. Hall, A. Tsitsulin, M. Kazemi, J. Halcrow, B. Perozzi, and V. Mirrokni. “Understanding transformer reasoning capabilities via graph algorithms”. In:NeurIPS(2024) (page 2)

    2024

  36. [36]

    Grapharena: Evaluating and exploring large lan- guage models on graph computation

    J. Tang, Q. Zhang, Y. Li, N. Chen, and J. Li. “Grapharena: Evaluating and exploring large lan- guage models on graph computation”. In:International Conference on Learning Representations (2024) (page 16)

    2024

  37. [37]

    Graph neural prompting with large language models

    Y. Tian, H. Song, Z. Wang, H. Wang, Z. Hu, F. Wang, N. V. Chawla, and P. Xu. “Graph neural prompting with large language models”. In:AAAI. 2024 (page 16)

    2024

  38. [38]

    Fast random walk with restart and its applications

    H. Tong, C. Faloutsos, and J.-Y. Pan. “Fast random walk with restart and its applications”. In: Sixth international conference on data mining (ICDM’06). IEEE. 2006, pp. 613–622 (page 16)

    2006

  39. [39]

    Branched multi-task networks: Deciding what layers to share

    S. Vandenhende, S. Georgoulis, B. De Brabandere, and L. Van Gool. “Branched multi-task networks: Deciding what layers to share”. In:BMVC(2020) (pages 15, 24)

    2020

  40. [40]

    The CLRS algorithmic reasoning benchmark

    P. Veličković, A. P. Badia, D. Budden, R. Pascanu, A. Banino, M. Dashevskiy, R. Hadsell, and C. Blundell. “The CLRS algorithmic reasoning benchmark”. In:ICML. 2022 (pages 2–4, 10–12, 15, 26, 29)

    2022

  41. [41]

    Neural algorithmic reasoning

    P. Veličković and C. Blundell. “Neural algorithmic reasoning”. In:Patterns2.7 (2021) (pages 2, 4)

    2021

  42. [42]

    Graph Attention Networks

    P. Veličković, G. Cucurull, A. Casanova, A. Romero, P. Liò, and Y. Bengio. “Graph Attention Networks”. In:International Conference on Learning Representations. 2018 (pages 10–12)

    2018

  43. [43]

    Neural execution of graph algorithms

    P. Veličković, R. Ying, M. Padovano, R. Hadsell, and C. Blundell. “Neural execution of graph algorithms”. In:ICLR(2020) (pages 13, 15)

    2020

  44. [44]

    Iteratively Prompt Pre-trained Language Models for Chain of Thought

    B. Wang, X. Deng, and H. Sun. “Iteratively Prompt Pre-trained Language Models for Chain of Thought”. In:Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing. 2022, pp. 2714–2730 (page 2)

    2022

  45. [45]

    Can Language Models Solve Graph Problems in Natural Language?

    H. Wang, S. Feng, T. He, Z. Tan, X. Han, and Y. Tsvetkov. “Can Language Models Solve Graph Problems in Natural Language?” In:NeurIPS(2023) (pages 2, 16). 19

    2023

  46. [46]

    Overlapping community detection using neighborhood-inflated seed expansion

    J. J. Whang, D. F. Gleich, and I. S. Dhillon. “Overlapping community detection using neighborhood-inflated seed expansion”. In:IEEE Transactions on Knowledge and Data Engi- neering28.5 (2016), pp. 1272–1284 (page 3)

    2016

  47. [47]

    Understanding and improving information transfer in multi-task learning

    S. Wu, H. R. Zhang, and C. Ré. “Understanding and improving information transfer in multi-task learning”. In:ICLR(2020) (page 16)

    2020

  48. [48]

    Precise high-dimensional asymptotics for quantifying heterogeneous transfers

    F. Yang, H. R. Zhang, S. Wu, C. Ré, and W. J. Su. “Precise high-dimensional asymptotics for quantifying heterogeneous transfers”. In:Journal of Machine Learning Research26.113 (2025), pp. 1–88 (page 16)

    2025

  49. [49]

    Overlapping community detection at scale: a nonnegative matrix factorization approach

    J. Yang and J. Leskovec. “Overlapping community detection at scale: a nonnegative matrix factorization approach”. In:WSDM. 2013 (pages 11, 14)

    2013

  50. [50]

    Approximate personalized pagerank on dynamic graphs

    H. Zhang, P. Lofgren, and A. Goel. “Approximate personalized pagerank on dynamic graphs”. In:Proceedings of the 22nd ACM SIGKDD international conference on knowledge discovery and data mining. 2016, pp. 1315–1324 (page 16)

    2016

  51. [51]

    Greaselm: Graph reasoning enhanced language models for question answering

    X. Zhang, A. Bosselut, M. Yasunaga, H. Ren, P. Liang, C. D. Manning, and J. Leskovec. “Greaselm: Graph reasoning enhanced language models for question answering”. In:ICLR (2022) (page 16)

    2022

  52. [52]

    Linear-Time Demonstration Selection for In-Context Learning via Gradient Estimation

    Z. Zhang, Z. Zhang, D. Li, L. Wang, J. Dy, and H. R. Zhang. “Linear-Time Demonstration Selection for In-Context Learning via Gradient Estimation”. In:Proceedings of the 2025 Conference on Empirical Methods in Natural Language Processing. 2025, pp. 16470–16488 (page 16). 20 A Proof of Proposition 3.3 We provide a proof for the Proposition 3.3 using the log...

    2025

  53. [53]

    We evaluate the error rates as one minus the average exact match across output text sequences

    as the base fine-tuning method. We evaluate the error rates as one minus the average exact match across output text sequences. First, we find that the sample complexity of generating intermediate steps can be higher than predicting only the final step. We compare (A1) fine-tuning with intermediate steps and (A2) fine- tuning with only the final step, in t...