Transferable knowledge graphs with executable learned operators for algorithm design
Authors: Camilo Chacón Sartori, José H. García, Andrei Voicu Tomut, Christian Blum
Organizations: Catalan Institute of Nanoscience and Nanotechnology (ICN2), CSIC and BIST, Campus UAB, Bellaterra, 08193, Barcelona, Spain · Artificial Intelligence Research Institute (IIIA-CSIC), Bellaterra, Spain
Procedural knowledge in algorithm design is embedded in source code and rebuilt for each new domain. We introduce Generative Executable Algorithm Knowledge Graphs (GEAKG), a representation in which this knowledge is stored as a generative, executable, transferable graph: typed nodes hold validated operators, edges encode admissible compositions, and learned edge weights record effective sequences. The same engine instantiates the structure across domains by changing only a role ontology (RoleSchema) and a binding. We study GEAKG as a representation mechanism rather than a state-of-the-art optimizer, asking what transfers and when. Layer ablations localize transfer by granularity: within a neural-architecture-search family the learned snapshot transfers across 70 dataset pairs - its weights stay correlated across datasets and one frozen snapshot remains competitive with Regularized Evolution at zero deployment-token cost; across combinatorial domains only the ontology-constrained executable structure transfers, not the learned weights. That structure pays off where target-side search is expensive - a Traveling Salesman snapshot beats an equally untuned from-scratch search on large scheduling instances even at one-fifth its budget - but does not improve on an effective local search where one is cheap, as in assignment and linear ordering. Executable procedural knowledge can thus be acquired offline, compacted, inspected, and reused without runtime language-model calls.
Figures & tables
Figure 1: End-to-end GEAKG pipeline. Offline generation and ACO learning produce a snapshot; online symbolic execution applies it through a domain binding with zero runtime language-model tokens.
Figure 2: Two MetaGraphs produced by the same GEAKG engine from different RoleSchemas.
Claim
Test (vs. comparator)
Result
One engine, multiple domains
same pipeline on NAS and optimization
runs unchanged on NAS + 3 optimization domains
Within-family: weights transfer
NAS cross-dataset vs. random ordering
62/70 significant; rˉ=0.91
Cross-domain: only structure transfers
L2 learned vs. uniform weights (JSSP, QAP, LOP)
learned ≈ uniform ( p=0.71,0.64 )
Each layer is load-bearing
L0/L1/L2 ablations
L0 lowers gap; no-op L1 collapses; L2 in-domain only
Transfer pays where search is expensive
JSSP vs. untuned ILS at 1× and 5× budget
GEAKG wins even at ILS 5×
Boundary where search is cheap
QAP/LOP vs. ILS at one-fifth budget
ILS at 51 budget still wins
Table 1: Claim-to-evidence map: each central claim, the controlled comparison that tests it, and the outcome. “ ≈ ” denotes statistically indistinguishable.
Figure 3: Aggregate comparison across the 70 NAS transfer pairs. The Symbolic Executor improves over Random Search on every pair and remains competitive with Regularized Evolution while using a frozen GEAKG snapshot at deployment.
Dataset
Cross-seed ρ (200ep)
12ep → 200ep ρ
Seed noise (pp)
Top-10 overlap
CIFAR-10
0.985
0.875
0.17
0.40
CIFAR-100
0.982
0.829
0.33
0.40
ImageNet16-120
0.988
0.812
0.37
0.50
Table 2: Surrogate fidelity of NAS-Bench-201/NATS-Bench tabular accuracies over 1,500 architectures per dataset.
Figure 4: Size-dependent zero-shot transfer from TSP to JSSP under precedence-aware evaluation. Each point is one JSSP instance; the vertical axis is GEAKG’s makespan advantage over ILS, (ILS−GEAKG)/ILS . Eight-seed means, 30 seconds per instance; GEAKG wins 10/14 overall.
Figure 5: L2 ablation. Learned operator edge weights versus uniform weights, holding operators, rules, and phases fixed. The learned ordering lowers the gap, modestly and most on the larger instances.
Figure 6: L0 ontology ablation. The RoleSchema-constrained topology (valid category transitions only) versus an unrestricted topology (all role pairs), under the real ACO trained from scratch (eight seeds). The constrained topology lowers the mean TSP gap, so the ontology improves search rather than only restricting it.
Figure 7: L1 operator-quality ablation and robustness. Holding L0 and L2 fixed, a fraction p of operator bodies is degraded to no-ops ( dead ) or role-agnostic random swaps ( noisy ); each degraded node retains its learned edge weight, so the learned policy still routes traffic to it. Mean TSP gap over four instances and eight seeds (log scale). A no-op pool collapses to the multistart baseline at p=1 , confirming L1 is load-bearing, whereas a random-swap pool degrades far less because accept-if-improving traversal filters most harmful moves.
Component
NAS
Optimization
Roles ∣R∣
18
11
Categories ∣K∣
5
3
Category transitions ∣T∣
12
7
Entry categories ∣K0∣
1
1
Revisitable categories
3/5
2/3
Representative L0 edges
42
14
Table 3: RoleSchema instantiations used in the two case studies.
Figure 8: Learned edge-weight matrix for the NAS GEAKG on Cora. Darker entries correspond to reinforced role transitions. The block structure follows RoleSchema categories and exposes the learned architecture-design pipeline.
Antecedent ( ri )
Consequent ( rj )
Conf.
Support
reg_weight_decay
eval_full
0.94
0
act_parametric
act_mixed
0.91
9
topo_recursive
act_mixed
0.88
3
topo_residual
act_modern
0.86
4
act_modern
act_parametric
0.70
7
reg_structural
reg_dropout
0.60
6
Table 4: Representative non-redundant rules from the NAS Cora GEAKG with confidence and trace support.
Instance
n
GEAKG (10k)
GEAKG (50k)
LLaMEA (50k)
Winner
berlin52
52
1.99±1.03
2.13±0.99
0.03±0.00
LLaMEA
kroA100
100
2.24±0.99
2.05±0.91
0.55±0.14
LLaMEA
ch150
150
6.21±1.25
6.11±1.45
2.37±0.02
LLaMEA
pr226
226
2.17±0.55
2.39±0.66
1.46±0.82
LLaMEA
pcb442
442
13.25±1.03
14.41±1.77
—
GEAKG
rat783
783
50.10±2.03
49.22±1.75
—
GEAKG
Supplementary Table S1 : TSP performance with mid-tier model gpt-4o-mini. Gap (%) is mean ± std over 15 runs. A dash means the method returned no valid tour within the token budget.
Instance
n
GEAKG
LLaMEA
Improvement
berlin52
52
0.031±0.00
0.031±0.00
—
kroA100
100
0.025±0.02
0.016±0.00
—
ch150
150
0.578±0.18
0.828±0.26
30%
pr226
226
0.628±0.27
1.810±0.00
65%
pcb442
442
3.444±0.37
7.408±0.00
54%
rat783
783
9.158±2.89
12.246±0.16
25%
Supplementary Table S2 : GEAKG versus LLaMEA on TSP with gpt-5.2 and 50k total token budget each. Gap (%) is mean ± std over 15 runs.
Instance
Ops
GEAKG
ILS
Best simple baseline
Winner
ft06
36
60 (9.1%)
57 (3.6%)
SPT 109 (98.2%)
ILS
ft10
100
1348 (44.9%)
1350 (45.2%)
SPT 2648 (184.7%)
GEAKG
ft20
100
1633 (40.2%)
1416 (21.5%)
LPT 2580
ILS
la01
50
747 (12.2%)
682 (2.4%)
SPT 1462 (119.5%)
ILS
la06
75
1023 (10.5%)
1007 (8.7%)
SPT 2367 (155.6%)
ILS
la16
100
1199
1286
LPT 3115
GEAKG
Supplementary Table S3 : TSP → JSSP transfer (eight-seed means) under precedence-aware evaluation. Time limit: 30 seconds per instance. SPT and LPT denote the shortest- and longest-processing-time dispatching rules. Makespans are reported for all instances; gaps to the best-known makespan are given in parentheses where available.
Instance
n
Learned
Uniform
ILS
nug12
12
3.32
3.04
0.00
nug20
20
2.61
4.14
0.14
nug30
30
2.33
2.89
0.47
chr15a
15
17.77
17.73
0.32
chr20a
20
24.62
25.24
7.41
chr25a
25
47.54
45.69
6.24
Supplementary Table S4 : QAP transfer ablation. The table compares learned operator edge weights, uniform operator edge weights, and a from-scratch ILS over eight QAPLIB instances at five seeds each (mean gap to the known optimum, %). Learned is indistinguishable from uniform (lower mean on 4/8 instances, paired Wilcoxon p=0.64 ). Thus, the L2 weights do not transfer to QAP. A from-scratch ILS is stronger than the transferred snapshot on every instance.
Instance
n
GEAKG
ILS
GL
Winner
nug12
12
0.00±0.00
0.00±0.00
25.26
Tie
nug15
15
0.00±0.00
0.00±0.00
28.00
Tie
nug20
20
0.09±0.18
0.00±0.00
33.46
ILS
nug25
25
0.25±0.20
0.06±0.07
36.06
ILS
nug30
30
0.93±0.46
0.56±0.15
29.59
ILS
tai20a
20
1.47±0.46
0.62±0.27
30.15
ILS
Supplementary Table S5 : QAP transfer reference results over a wider set of QAPLIB instances, obtained under an earlier evaluation protocol (mean ± std over repeated runs) and retained for completeness. GL is the deterministic Gilmore–Lawler lower bound. The definitive learned-versus-uniform-versus-ILS comparison is Supplementary Table S4 .
Group
Parameter
Value
ACO/MMAS
pheromone exponent α
2.0
heuristic exponent β
2.0
evaporation ρ
0.1
deposit constant Q
100
ants per iteration
10
pheromone bounds [τmin,τmax]
[0.001,1.0]
Supplementary Table S6 : Hyperparameters used across experiments.
Supplementary Figure S1 : Perturbation sensitivity (bifurcation test). The plot shows output deviation of the Symbolic Executor as the learned edge weights are perturbed by magnitude ε (mean over random perturbations; shaded band to the maximum). The response is smooth and bounded. It has no discontinuous jumps, which indicates a stable learned policy.
Supplementary Figure S2 : Cross-dataset transfer on NAS-Bench-Graph. Each cell reports the test-accuracy difference (percentage points) between the GEAKG Symbolic Executor and Random Search for a source → target dataset pair under a matched evaluation budget. Rows are source datasets, and columns are target datasets. Warmer cells favour GEAKG. All 64 pairs are positive, matching the 64/64 improvement reported in the main text.
Supplementary Figure S3 : Cross-dataset transfer on NAS-Bench-201. This panel follows Supplementary Fig. S2 for the six NAS-Bench-201 transfer pairs over CIFAR-10, CIFAR-100, and ImageNet16-120. Each cell reports the GEAKG-minus-Random-Search test-accuracy difference (percentage points). Positive values indicate cases where the transferred snapshot wins. GEAKG improves over Random Search on all six pairs.
Supplementary Figure S4 : Run-to-run variance of the GEAKG Symbolic Executor versus Regularized Evolution across representative NAS transfer pairs. Markers show each method’s standard deviation of test accuracy over repeated runs. The Symbolic Executor has 1.2–4.8 × lower standard deviation at comparable mean accuracy. This shows that a fixed procedural snapshot gives more repeatable behaviour than per-target evolutionary search.
Supplementary Figure S5 : Entropy of the learned edge-weight distribution in the NAS GEAKG. Results are grouped by topology source (baseline RoleSchema vs. LLM-generated topologies) and compare learned edge weights with a uniform baseline. Lower learned entropy means that ACO concentrates probability mass on preferred role transitions. MMAS bounds prevent collapse (a 3–4% reduction from the uniform maximum).
Supplementary Figure S6 : Dominant traversal paths in the NAS GEAKG on NAS-Bench-Graph (Cora). The most frequent role sequences from top execution traces follow the category order Topology → Activation → Training → Regularization. Edge weight indicates how often each transition recurs. These paths are executable procedural sequences that the Symbolic Executor reuses at deployment.
Large language models have advanced automated algorithm discovery by synthesizing executable code, but existing frameworks trap them in rigid search pipelines with pre-defined control flows. This limitation restricts adaptive reasoning, blocks cross-paradigm transfer, and overlooks richer execution feedback. To bridge this gap, we introduce an end-to-end framework, AlgoEvo, a unified agentic architecture that transforms automated algorithm discovery into an interactive, knowledge-accumulating process. An autonomous agent dynamically inspects, diagnoses, and edits code based on runtime feedback. A design skill hub decouples paradigm-specific knowledge from the core discovery engine, allowing a unified workflow to seamlessly handle single-heuristic, multi-objective, and multi-component design. Meanwhile, a hierarchical experience bank organizes search trajectories into a task-level tree to guide exploration and consolidates cross-task patterns into reusable skills. Across six representative benchmark tasks, AlgoEvo reaches state-of-the-art performance with as little as 7% of the evaluation budget and reduced token consumption, demonstrating strong intra-task accumulation, cross-task transfer, and the ability to reproduce or exceed the strongest existing methods through flexible skill activation.
Junhao Qiu, Qinglong Hu, Ji Cheng +3
Department of Computer Science, City University of Hong Kong · Huawei Noah’s Ark Lab · Institute of Advanced Intelligence and Computing, A*STAR
Searching text-rich knowledge graphs requires following relations while examining textual evidence. Predefined graph interfaces constrain what evidence agents can access, even when they write code to combine tool calls or process retrieved subgraphs. We propose direct knowledge graph interaction (DKGI), a harness in which language model agents create graph access tools directly over complete node and edge files. The agent writes Python code to follow relations, combine node sets, and select textual evidence, interleaving execution with shell search and file inspection. This lets agents process large node sets in bulk while returning selected text for the model to assess. Execution feedback guides tool creation and revision, while the evolving tools determine what evidence the agent gathers next. On benchmark datasets spanning three domains, training-free DKGI exceeds the strongest published baseline by at least 6.7 Hit@1 points on every graph, even with a minimal harness. Controlled ablations show the benefits of multi-turn programming over shell-only access and predefined graph tools, while trajectories show agents revising code to extend searches or address errors. These findings highlight the value of allowing tool creation and tool use to co-evolve during graph search. Our code and data are available at https://github.com/leopoldwhite/DKGI.
Large language models (LLMs) have emerged as powerful tools for automatic algorithm design (AAD). However, existing pipelines remain inefficient. They operate at the granularity of full algorithms, redundantly rewriting recurring substructures and discarding low-fitness candidates that may contain valuable algorithmic features. We formalize budget-efficient automatic algorithm design, wherein the search policy maximizes realized fitness subject to limited computational cost. We propose a directed acyclic graph representation of algorithms and build a search framework that fully exploits the LLM's output. Instead of querying the LLM for full algorithms, we use it to obtain corrections: compact operators that add, replace, or remove code blocks. Each correction augments the graph, yielding new algorithms that compose with prior corrections. This graph structure decomposes algorithms into sets of corrections, enabling correction-level credit assignment that informs subsequent queries. We complement this framework with theoretical insights into the ideal balance between search depth and breadth at different budget levels. We validate our method empirically on three combinatorial optimization problems, demonstrating consistent superiority of our graph-based search over full-algorithm search at equal token budget. Finally, our experiments suggest that rich contexts help only when the LLM's prior knowledge is shallow, and can hinder performance otherwise.
Maxime Bouscary, Manxi Wu, Saurabh Amin
Operations Research Center Massachusetts Institute of Technology · Department of Civil and Environmental Engineering University of California, Berkeley · Laboratory for Information & Decision Systems Massachusetts Institute of Technology