PaperlayerView exact revision on arXiv

Source-linked AI summary

Network World Models as Environments for Algorithm Design on Complex Systems

Rishab Alagharu, Hongji Pu, Zeeshan Memon, Xinyuan Song, Yuntong Hu, Liang Zhao

arXiv:2610.01048v1cs.AI

TL;DR

Evaluating candidate actions in complex networks relies on costly simulation, while learned evaluators are often task-specific. The paper combines an action-conditioned Network World Model with an LLM-based algorithm-design loop, and its designed algorithms match or exceed the strongest reported baseline in most evaluated settings.

  • Problem

    Selecting network interventions requires evaluating outcomes over time, but simulation makes candidate scoring costly and learned evaluators are typically specialized to a task and objective.

    Source: §1 · p. 2

  • Method

    An action-conditioned Network World Model applies interventions and predicts subsequent diffusion, providing fast rollouts and targeted feedback for a coding agent that designs executable algorithms.

    Source: §1 · p. 2, §3.2 · p. 4, §3.3.1 · p. 5

  • Results

    Across eight tasks and five diffusion models, designed algorithms match or exceed the strongest reported baseline in 138 of 141 settings.

    Source: §5 · p. 9

  • Takeaways & Limitations

    The results support using learned network dynamics for algorithm selection and iterative algorithm design across a range of complex-network tasks.

    Source: §5 · p. 9

    The model must generalize across task instances that share the same dynamics, and finite search rounds may leave the returned algorithm suboptimal under the learned evaluator.

    Source: §3.1 · p. 4, §3.4 · p. 6

Abstract

from arXiv · show

World models, which simulate an environment and predict how it changes under actions, are increasingly used in real-world applications such as robotics. Complex systems call for the same tool because the effect of an action is not immediate. Seeding nodes for a campaign, or immunizing nodes against an epidemic, changes little on its own; what matters is the outcome that unfolds over the steps that follow. Designing an algorithm that selects such actions to maximize expected performance on a task is inherently iterative, and every candidate must be scored by the outcome it produces. Obtaining that outcome has relied on simulation, whose cost becomes a bottleneck when candidates are evaluated over many sampled trajectories. We propose an action-conditioned Network World Model that learns a network's diffusion dynamics under interventions over time, applies each action to the network, and predicts the outcome that follows. It serves as a fast evaluator inside an algorithm design loop in which a coding agent designs and refines executable algorithms using feedback from full rollouts, action-level credit, and counterfactual probes over alternative interventions. Across eight network tasks and five diffusion models, the designed algorithms match or exceed the strongest reported baseline in 138 of 141 settings while enabling up to 14.5 times faster rollouts than Monte Carlo simulation. Code will be released upon acceptance.

1 INTRODUCTION

Evaluating action sequences in complex networks is costly, while existing learned evaluators are typically specialized to a task or objective. The paper proposes an action-conditioned network world model and algorithm-design framework to make this evaluation faster and more informative.

1 INTRODUCTION

  • Action selection is combinatorial, and simulation-based evaluation is costly because expected outcomes must be estimated for each candidate.Learned mappings can be inexpensive but are generally fit to a particular task and objective.Source: §1 · p. 2
  • Network world modeling must capture interventions that alter states, edges, or contact weights and preserve candidate rankings over long rollouts despite transition error.Aggregate scores offer limited guidance for revisions, while evaluating alternative interventions with simulation adds cost.Source: §1 · p. 2
  • Across eight tasks and five diffusion models, designed algorithms match or exceed the strongest reported baseline in 138 of 141 settings, with rollouts up to 14.5× faster than Monte Carlo simulation.The coding-agent search uses model rollouts and targeted feedback to refine executable algorithms.Source: §1 · p. 2
  • The proposed model applies interventions exactly, predicts subsequent diffusion, and supplies rollout scores, action-level credit, and counterfactual probes to an algorithm-design loop.The paper also analyzes algorithm-selection regret in terms of transition error, rollout horizon, and search suboptimality.Source: §1 · p. 2

2 RELATED WORK

Prior work offers methods for network diffusion, world modeling, and language-model-driven algorithm discovery, but their capabilities leave gaps for action-conditioned network algorithm design. This paper supplies an evaluator that returns diagnostics and counterfactual answers for the discovery loop.

Algorithms for complex network dynamics

  • Classical network methods use repeated simulation or task-specific structural objectives, while learned alternatives often specialize to a task, objective, or intervention form.These alternatives approximate forward processes, predict solutions, or learn generative priors over diffusion trajectories.Source: §2 · pp. 2–3

World models

  • Most world models handle video or low-dimensional control, while existing graph methods separately model state transitions, action effects, or task-level outputs rather than both network structure and structural interventions.The paper identifies the need for graph-structured representations and dynamics responsive to actions that change the network structure.Source: §2 · p. 3

Algorithm discovery with language models

  • Language-model algorithm discovery typically evolves candidate programs or heuristics, but assumes evaluation is cheap; graph diffusion instead requires thousands of simulations per candidate.The paper supplies an evaluator that returns diagnostics and counterfactual answers.Source: §2 · p. 3

3 METHODOLOGY

The methodology learns action-conditioned network dynamics and uses the learned model to evaluate and refine executable algorithms. It combines exact intervention handling, targeted rollout feedback, paired candidate comparisons, and a regret analysis for selection under model error.

3.1 PROBLEM FORMULATION

  • A task instance specifies a network, transition process, constraints, horizon, and initial state; algorithms produce action plans scored by outcomes after the horizon.Expected outcomes can be expensive to compute because expected spread is #P-hard under IC and candidate scores require sampled trajectories.Source: §3.1 · p. 3
  • The objective is to find an algorithm that satisfies task constraints and maximizes expected horizon score, requiring both a learned dynamics model and search against that model.The model is trained on observed network transitions and must capture action effects, remain accurate over the horizon, and generalize across instances sharing the same dynamics.Source: §3.1 · pp. 3–4

3.2 NETWORK WORLD MODEL OF COMPLEX NETWORKS

  • The world model applies each intervention exactly to the network, state, or parameters, then learns the subsequent diffusion transition and uses process-specific features and readouts.Exact intervention handling removes intervention-semantics error from the rollout bound and tightens the downstream selection guarantee.Source: §3.2 · p. 4

3.3.1 ALGORITHM DESIGN LOOP

  • In each search round, a coding agent generates an executable candidate, which the model scores alongside the current best on shared sampled trajectories before feedback informs the next candidate.Candidates may reuse, combine, or extend classical algorithms and are validated against task constraints before evaluation.Source: §3.3.1 · p. 5

3.3.2 ROLLOUT FEEDBACK FROM THE NETWORK WORLD MODEL

  • The model returns rollout diagnostics, action-level credit from action-omission comparisons, and counterfactual evaluations of actions outside the current plan.Rollout diagnostics and credit are computed from evaluation rollouts; credit for k actions requires k + 1 plan evaluations.Source: §3.3.2 · pp. 5–6

3.3.3 SEARCH AND CANDIDATE SELECTION

  • Candidate and current-best algorithms are evaluated on the same fresh trajectories, and a candidate replaces the best only when its estimated gain exceeds the variability of paired differences.The current best is re-evaluated under each fresh seed to avoid carrying forward a favorable rollout realization.Source: §3.3.3 · p. 6

3.4 RELIABILITY OF WORLD-MODEL-BASED ALGORITHM SELECTION

  • Selection regret is bounded under assumptions on one-step transition error over reachable state-action support, score range, horizon, and search suboptimality; exact rollout reproduction is not required for reliable selection.The regret bound depends on accumulated transition error and search error.Source: §3.4 · pp. 6–7

4 EXPERIMENTS

The experiments evaluate designed algorithms across network tasks and assess the Network World Model’s prediction, selection, and rollout efficiency. Designed algorithms generally match or outperform baselines, transfer across networks, and can be evaluated faster than with Monte Carlo simulation.

4.1 SETUP

  • The evaluation covers eight tasks, networks from 10^3 to over 10^5 nodes, five diffusion models, and task-specific baselines.The design loop uses 10 rounds, 200 sampled rollouts per evaluation, a horizon of 10, and six probes per round; final algorithm scores are independently evaluated with 200 trusted Monte Carlo samples.Source: §4.1 · pp. 7–8

4.2 PERFORMANCE OF DESIGNED ALGORITHMS

  • Across eight tasks, designed algorithms improve on the strongest existing method in all eight and trail it in only 3 of 141 settings.They beat or tie the strongest listed baseline in 63 of 64 Table 1 configurations.Source: §4.2 · p. 8
  • Across budgets, GPT-5.6 Sol, Terra, and Luna finish within 0.1 points on Network Science and 0.3 points on Power Grid, and each beats the strongest baseline.Figure 2 reports returned-algorithm task scores under the three coding models, averaged over budgets.Source: Figure 2 · p. 8, §4.2 · p. 8

4.3 CROSS-NETWORK GENERALIZATION AND SCALING

  • Transferred algorithms beat target-network baselines, while influence maximization stays ahead from Network Science through Digg as network size increases.Transfer gains are 4.0–11.7% for critical node detection; on Digg, influence maximization improves by 7–12%, versus 1–4% on Network Science.Source: §4.3 · p. 8, Figure 3 · p. 9

4.4 NETWORK WORLD MODEL ACCURACY AND EFFICIENCY

  • One-step ∆F1 ranges from 0.87 to 0.99 for IC, LT, and CLT and from 0.85 to 0.86 for SIR and SIS, with Brier scores ≤0.0006.Free-running rollouts stay within 2.2% of the trusted simulator at the horizon except under LT, where the model undercounts by 6.0%.Source: §4.4 · p. 8, Table 2 · p. 9
  • On held-out SBM and BA networks, candidate-pair agreement is 90.2% and 86.1%, with selection regret of 0.11% and 0.13%; on Watts-Strogatz, regret is 1.18%.On Watts-Strogatz, preference accuracy is 86.0%; Table 3 reports decision value on 20 held-out graphs per family.Source: §4.4 · pp. 8–9, Table 3 · p. 9
  • One world-model rollout is 4.0 times faster on Power Grid and 14.5 times faster on Digg than direct simulation.Training costs 38,800 simulator episodes once, while simulator-based search uses 7,800 episodes per new search, yielding a break-even point of about five searches.Source: Figure 4 · p. 9, §4.4 · p. 9

5 CONCLUSION

The paper presents a Network World Model and LLM-based search framework for designing executable algorithms on complex networks. It reports broad performance, transfer, and evaluation-speed results, while noting that interventions are evaluated only in simulation.

5 CONCLUSION

  • The framework uses model rollouts and targeted feedback to refine executable algorithms, and designed algorithms match or exceed the strongest reported baseline in 138 of 141 settings.The reported results also include transfer across networks with little performance loss and faster evaluation than Monte Carlo simulation.Source: §5 · p. 9
  • Generative AI tools assisted with editing and the coding agent, and the authors reviewed the work and accepted or rejected suggested edits by hand.The authors state that no edit changed the paper’s technical content, claims, or results.Source: AI USE STATEMENT · p. 10
  • The authors report no new data collection or human subjects, and state that interventions are evaluated in simulation rather than deployed on real platforms or populations.The evaluated networks and cascade corpora are public.Source: ETHICS STATEMENT · p. 10
  • The appendix documents datasets, tasks, baselines, evaluators, experimental protocol, world-model setup, design loop, and prompts; example algorithms are also provided.The coding agent uses closed-source LLMs accessed through an API.Source: REPRODUCIBILITY STATEMENT · p. 10

A.1 PROOF OF THEOREM 1: ALGORITHM-SELECTION REGRET

The appendix bounds algorithm-selection regret under transition-accuracy and search assumptions, then shows how intervention factorization tightens that guarantee. It also details the coding-agent loop, its probes and context, and its exploration-to-exploitation operators.

A.1 PROOF OF THEOREM 1: ALGORITHM-SELECTION REGRET

  • Theorem 1 bounds algorithm-selection regret using transition error on the search support, bounded task reward, and learned-evaluator search suboptimality.The model’s approximation quality is characterized by one-step transition error over state-action pairs reachable during algorithm search.Source: §A.1 · p. 18

A.2 PAIRWISE RANKING PRESERVATION

  • Algorithms separated by more than world-model distortion preserve their true ordering, and a unique best algorithm is recovered when its selection margin exceeds that distortion and search is exact.The ranking guarantee extends to closer algorithm pairs as training reduces transition error.Source: §A.2 · p. 19, §A.3 · p. 19

A.4 EXACT INTERVENTION FACTORIZATION

  • Exact intervention factorization leaves rollout error dependent on endogenous-dynamics error, while a generic intervention surrogate can add LT ϵexo before rollout.The exact intervention operator is applied directly; the surrogate must additionally infer how the action modifies the network.Source: §A.4 · pp. 19–20

A.5 TIGHTER SELECTION REGRET UNDER EXACT INTERVENTION

  • Exact intervention removes the intervention-semantics term from the selection-regret bound, making the upper bound tighter when LT ϵexo > 0 under the stated nondegenerate conditions.The transition-error term falls from ϵdyn + LT ϵexo to ϵdyn.Source: §A.5 · pp. 20–21

B NETWORK ALGORITHM DESIGN AGENT: DETAILS

  • Each design round probes the incumbent, writes and validates a candidate, scores candidate and incumbent on shared sampled trajectories, and feeds rollout diagnostics and action-level credit back to the agent.The search begins from the strongest classical anchors scored on the instance.Source: B NETWORK ALGORITHM DESIGN AGENT:… · p. 21

B.1 ALL PROBES

  • For seeding, a mean-field gradient probe ranks promising unselected nodes and low-value selected nodes, providing local headroom rather than an optimum.A backward pass through the rollout yields marginal seed values; the probe is available only on forward-model evaluators.Source: §B.1 · p. 22

B.2 AGENT CONTEXT

  • The agent receives a one-time static prompt and rebuilt round-specific context, including attempts, paired diagnostics, anchor comparisons, and losing counterexample realizations.Counterexamples inform later edits but do not determine acceptance, which uses a fresh realization.Source: §B.2 · pp. 22–23

B.3 OPERATORS

  • Operators shift from exploration to exploitation, restore exploration after stalls, and edit the current best using paired comparisons rather than raw rewards.Crossover and synthesis are withheld until the population has at least two members.Source: §B.3 · pp. 24–25

B.4 IMPLEMENTATION DETAILS

Implementation details specify experimental settings, candidate validation and sandbox constraints, the coding prompts, and the rollout evaluators used to score algorithms.

B.4 IMPLEMENTATION DETAILS

  • Experiments use 200 episodes or rollouts, base seed 42, and an NVIDIA RTX A6000; budgets vary by task, and generated programs face 900- or 1800-second limits.The longer limit applies on larger networks.Source: §B.4 · p. 25
  • Candidates must pass an AST check and sandbox execution, then return feasible plans within budget; validation errors trigger a repair turn.The check rejects dynamic execution, file primitives, and imports outside the allowed set.Source: §B.4 · pp. 25–26, C CALLABLE LIBRARY AND NETWORK… · p. 26

C CALLABLE LIBRARY AND NETWORK PRIMITIVES

  • The sandbox exposes network primitives and task-family libraries, but generated programs cannot use library members that select by running their own Monte Carlo simulations.The two simulation primitives remain callable and count against the per-call wall-clock cap.Source: C CALLABLE LIBRARY AND NETWORK… · p. 26

D PROMPTS OF THE DESIGN AGENT

  • The coding prompts specify a one-shot plan contract and provide the task, evaluator, budget, horizon, graph profile, library API, and reference scores.The agent’s instructions distinguish targeted refinement, simplification, crossover, synthesis, and new strategies from scratch.Source: D PROMPTS OF THE DESIGN AGENT · pp. 29–30

E.1 ROLLOUT EVALUATORS

  • Monte Carlo uses n independent NDlib episodes, the oracle reproduces the trusted process, and the Network World Model scores batched learned forward passes over sampled states.Monte Carlo cost grows with n times the number of candidates; the world model’s online cost is a batched forward pass per timestep.Source: §E.1 · p. 31

E.2 TASKS

The eight tasks cover intervention design, source and cascade recovery, and cascade forecasting, with each task defining its own program contract and reward.

E.2 TASKS

  • Influence maximization selects k seeds for a horizon-length plan and maximizes final spread; its adaptive counterpart chooses batches at round boundaries using the diffusion state and feedback model.The registry pairs adaptive and static arms to compute their spread ratio at matched budgets.Source: §E.2 · p. 31
  • Critical node detection removes nodes around a seeded outbreak to minimize final infections, while influence blocking uses counter-seeds or network blocks to minimize rumor size.Critical-node plans cannot remove outbreak sources, and the budget must remain below the outbreak’s one-hop ring size.Source: §E.2 · pp. 31–32
  • Epidemic control applies vaccination, quarantine, arc cuts, or contact reduction to minimize attack rate under SIR or SIS dynamics.Prevalence curves and spectral eigendrop are also reported as context.Source: §E.2 · p. 32
  • Source localization names likely cascade sources from an observed state, whereas cascade reconstruction returns an inferred infection history from partial observations.Their rewards are label-free; source and history metrics are computed against stored ground truth after search.Source: §E.2 · pp. 31–32
  • Cascade prediction replays real-corpus transitions and forecasts popularity at a target time, minimizing mean squared log error; declines are counted but not scored.The default split is chronological.Source: §E.2 · p. 32

E.3 DATASETS

The appendix identifies the dataset table’s scope and catalogs the baselines used for comparisons across tasks.

E.3 DATASETS

  • The dataset table orders datasets by node count; for three cascade-prediction corpora, counts refer to the full network while runs replay an active-participant subsample.The supplied passage identifies the table’s scope but does not provide its dataset entries.Source: Table 9 · p. 33

E.4 BASELINES

  • The baseline comparison uses five methods per task, or four for adaptive influence maximization, with all methods scored on the shared referee under matched networks, budgets, and outbreak or rumor conditions.The table distinguishes implementations of published algorithms from authors’ released code.Source: §E.4 · p. 33, Table 10 · p. 33
  • Baseline examples span centrality, sampling, and greedy methods, including DegreeDiscount for influence maximization and EPIC for adaptive influence maximization.The listed anchors include DegreeDiscount and EPIC, respectively.Source: §E.4 · p. 34

F CHOICE OF CODING MODEL

Across GPT-5.6 Sol, Terra, and Luna, the design loop returns similar performance, and each outperforms the strongest classical baseline.

F CHOICE OF CODING MODEL

G COMPARISON WITH LLM ALGORITHM DISCOVERY SYSTEMS

The design loop outperforms four published algorithm-discovery systems on influence maximization and critical node detection, while those systems do not reach the strongest classical baseline on Network Science.

G COMPARISON WITH LLM ALGORITHM DISCOVERY SYSTEMS

  • The four comparison systems run their own search loops and defaults, using the same task, exact-simulator fitness function, and coding model, but not the Network World Model.The shared coding model is GPT-5.6 Sol.Source: G COMPARISON WITH LLM ALGORITHM… · p. 35
  • At every budget, the design loop performs best on influence maximization and critical node detection.None of the four discovery systems reaches the strongest classical baseline on Network Science at any budget.Source: G COMPARISON WITH LLM ALGORITHM… · p. 36, Table 12 · p. 36
  • EoH and LLaMEA both converge to reverse-reachable-set sampling, the mechanism behind IMM, without reaching IMM’s baseline performance.The authors conclude that both the design loop and Network World Model are necessary for considerable gains over baselines.Source: G COMPARISON WITH LLM ALGORITHM… · p. 36

H FULL RESULTS

The supplied results cover designed algorithms across tasks and networks, their transfer between networks, and world-model evaluation across training setups, scale, topology, and transition-head choices. They report close cross-network agreement, model transfer with long-horizon calibration degradation, and improved long-horizon and action-effect metrics with the structured transition head.

H FULL RESULTS

  • Table 13 reports designed-algorithm results for all eight tasks and every dataset, with diffusion-model pairs by task; Figure 5 plots performance across intervention budgets for four IC tasks.A dash denotes an out-of-memory error or a timeout exceeding 1,800 seconds.Source: Figure 5 · p. 36, H FULL RESULTS · p. 36, Table 13 · pp. 37–38

H.1 CROSS-NETWORK TRANSFER

  • Table 14 reports that transferred algorithms agree with target-designed algorithms within 0.1 percentage points in every completed cell; the NetHEPT adaptive algorithm exceeds the per-call limit on Digg.The failed transfer is attributed to runtime cost, not a failure of the decision rule.Source: §H.1 · pp. 38–39, Table 14 · p. 38

I.1 WORLD MODEL SETUP

  • Training uses network-disjoint IC suites BA-24 and SBM-24, with LT trained on BA-24; evaluation includes held-out decision-value, topology-shift, size-transfer, probabilistic, and counterfactual tests.The suites contain 24 BA networks of N = 100 and 24 SBM networks of N = 120.Source: §I.1 · p. 39

I.1.1 SCALE AND TOPOLOGY TRANSFER

  • Freezing the checkpoint transfers it to networks up to 10× larger and to WS, ER, and SBM topologies, with one-step KL between 0.0036 and 0.0063; long-horizon spread calibration degrades.The transfer runs keep edge weights visible to the model.Source: §I.1.1 · p. 39, Table 15 · p. 39

I.1.2 TRANSITION HEAD AND ACTION CONDITIONING

  • The structured transition head changes spread bias at H = 10 from +1.7% to +8.7% and normalized action-effect error from 0.0105 to 0.0398 with a linear head, while one-step KL is nearly unchanged.One-step KL is 0.0061 with the linear head against 0.0059 with the structured head.Source: §I.1.2 · pp. 39–40

I.2 WORLD MODEL ENCODER ABLATION

The encoder comparison finds similar one-step and rollout performance across backbones, with the structured transition head carrying the result. The rollout figure also shows that count bias settles early rather than accumulating with horizon.

I.2 WORLD MODEL ENCODER ABLATION

  • The four encoders are within 0.002 ∆F1 of one another, and each rollout’s final count bias stays within 3%.The authors conclude that the structured head, rather than the encoder, carries the result.Source: §I.2 · p. 40, Table 16 · p. 40
  • Across every backbone, relative count bias settles within the first five steps and does not grow with the rollout horizon.Figure 6 compares mean infected count with the simulator and plots relative count bias by step.Source: Figure 6 · p. 40

I.3 ERROR AGAINST HORIZON

The section reports rollout-bias behavior over time and presents four designed algorithms for critical node detection, influence maximization, source localization, and influence blocking.

I.3 ERROR AGAINST HORIZON

  • Power Grid’s rollout overcounts by about 3%, while bias on both networks settles within the first two to five steps and does not grow.The search tolerates the Power Grid offset because it shifts every candidate’s score equally.Source: §I.3 · pp. 40–41, Table 17 · p. 41, Figure 7 · p. 41

J.1 CRITICAL NODE DETECTION: ENSEMBLE CAVITY-GRADIENT REMOVAL

  • 16.5% of nodes remain infected at the 10% PGP budget, versus 20.2% for Frontier.The method ranks nodes using outbreak-conditioned cavity gradients across actual and probability-capped models, then discounts neighbors between batches of removals.Source: §J.1 · pp. 41–42

J.2 INFLUENCE MAXIMIZATION: STRATIFIED HORIZON-LIMITED COVERAGE WITH EXCHANGE SWEEPS

  • 56.5% of Digg’s nodes activate at the 10% budget, versus 51.8% for OPIM and SubSIM.The method uses horizon-limited reverse-reachable sets with stratified roots, then applies exchange sweeps to replace weak seeds.Source: §J.2 · p. 43

J.3 SOURCE LOCALIZATION: CAVITY CONSISTENCY OPTIMIZATION WITH COMPONENT REPAIR

  • −0.080 consistency is reached on Power Grid, versus −0.106 for LPSI.The method fits source probabilities to observed infections with a differentiable cavity model, then uses exchange search and component repair.Source: §J.3 · pp. 44–45

J.4 INFLUENCE BLOCKING: DIFFERENTIABLE COMPETITIVE-CAVITY BLOCKING

  • 1,113.6 nodes receive the rumor on Gnutella24 with 30 counter-seeds, versus 1,151.5 for RPS.The method jointly optimizes counter-seeds by differentiating a competitive mean-field recursion in which the counter cascade wins same-step ties.Source: §J.4 · pp. 45–46
Loading 2610.01048v1…