CS Paper Radar

Beyond Reachability: When Edit Order Preserves Couplings in Graph Flow Matching

Zilin Li, Zixing Song

cs.IT cs.LG ·submitted 2026-10-28 08:58 UTC · v1

Abstract

Shortest-path optimality does not guarantee that a memoryless graph generator preserves a prescribed source-target correspondence. We study whether reordering legal shortest edits can retain this correspondence without changing the pairing, mandatory edits, or sampling budget. Under a common Poisson clock, we establish an exact criterion for endpoint coupling recoverability: the source-blind Markov projection attains the unavoidable clock-error floor if and only if routes to distinct targets do not share graph states. Routes to the same target may merge without sacrificing endpoint fidelity. This characterization leads to an exact finite-state routing formulation and a legality-preserving scheduling procedure with recovery certificates. A marker-free construction demonstrates how shared edge structure can retain source distinctions, while a capacity-constrained family exhibits a sharp separation in paired error between edit orders with identical marginal error. Finally, a target-conditioned aliasing bound connects structural route design to the terminal fidelity of a learned graph-only generator. These results characterize when legal edit ordering can preserve a prescribed coupling under fixed operational costs.

Comment
14 pages. Theoretical preprint

Closest papers

Nearest neighbours by meaning across the whole index.

State-Aware Activation Recomputation with Replay Contracts and Selective Preservation

cs.AI ·2026-10-31 ·Annan Zhang, Shengjie Song, Wenshuai Yao, Lihao Zhang, Tianmiao
similarity 0.61
Abstract

Activation recomputation saves accelerator memory by replaying forward segments during the backward pass, but replay is only correct if it sees the state the original forward pass saw. Mutable buffers, aliased bytes and random-generator state can change in between, so re-executing unchanged code can differentiate a different computation. We make this state explicit. A versioned replay contract specifies what replay must restore, and a joint planner chooses, per segment, between activation retention, whole-buffer snapshots and selective-region preservation, charging each option its measured memory and recovery cost. Independent derivative and byte-level checks validate the contract, and a Torch/JAX cohort retains all 5,900 execution records, including matches, rejections and divergences. On frozen sparse-write H100 workloads, each measured over fifty fresh processes, joint planning reduces paired step time by 18.16% against a correctly costed eager/whole planner at a 44 GiB budget (approximate 97.5% ratio interval $[.8172,.8195]$). At 32 GiB, where the eager/whole planner has no feasible static policy, joint planning is 4.98% faster than fixed regions at 29.94 rather than 26.20 GiB. A complete CIFAR-100 dense-queue application runs seven methods for 100 encoder and 25 probe epochs at six training seeds, with byte-identical test scores within each seed. There, joint planning uses 22.41% more allocated memory than whole snapshots, with a process-time geometric-mean ratio of 1.0080 (seed range $[.9845,1.0191]$). Together, the results map where selective preservation pays off: sparse writes with large activations benefit, while in the dense-queue workload whole snapshots use less allocated memory.

0.26

Preserving Geometric Integrity in Graph Prompting via Measure-Constrained Optimal Transport

cs.LG ·2026-09-20 ·Xiangyu Wang, Shuo Wang, Ruiyi Fang, Zhao Kang
code/data similarity 0.58
Abstract · 28 pages, 4 figures

Graph prompt learning enables parameter-efficient adaptation of frozen Graph Neural Networks to downstream tasks through lightweight prompt parameters. As routing becomes increasingly node-adaptive, however, independently optimized local decisions can collectively concentrate assignment mass on a small subset of a finite shared prompt bank, even when individual node--prompt matches remain locally meaningful. We propose MINT (Measure-INtegrity Transport), an entropically regularized optimal transport framework that formulates node-to-prompt adaptation as a globally coupled allocation problem. The transport cost favors local geometric compatibility, while a prescribed prompt-side marginal explicitly controls graph-wide prompt utilization. We further derive an exact variance decomposition that separates prompt-side geometric variance into retained prompt-update variation and within-node barycentric dispersion, together with a conditional stability bound for the frozen-encoder forward map. Across standard citation networks and additional heterophilic graphs, MINT remains competitive in few-shot adaptation. Controlled and end-to-end experiments further distinguish the roles of routing and topology: fixed-marginal routing controls graph-wide prompt utilization and has measurable end-to-end effects on citation networks, while topology augmentation provides a complementary, graph-dependent mechanism for addressing structural mismatch. Code is available at https://github.com/Ga1axy0051/MINT.

0.32

From Reasoning Strings to Partial Orders: Verifier-Certified Rule Transport through Quotient Policy Optimization

cs.LG ·2026-08-20 ·Bang Xie, Hao Liu, Zhiyuan Peng, Xin Yin, Chenhao Ying +3 more
similarity 0.58
Abstract · 9 pages, 2 figures, 4 tables

Many computations admit several valid execution orders because independent subgoals or disjoint state updates can commute. Reinforcement learning with verifiable rewards usually treats each successful trace as a separate token sequence, so serialization choices can be mistaken for logical dependencies. We introduce Verifier-Certified Rule Transport (VCRT), which replays adjacent operation pairs with native verifiers. Pairs whose two orders are accepted and reach the same canonical state provide commutation certificates; rejected or state-changing reversals provide anti-diamonds. VCRT uses anti-diamonds to preserve genuine prerequisites and assigns policy credit to the total probability mass of each certified orbit. It also constrains post-swap consistency, source retention, and policy drift. We evaluate leave-one-environment-out transfer across ProofWriter, CLRS, and Lean through a shared anonymized relation-graph interface. All training and checkpoint decisions are frozen before held-out evaluation, which uses one greedy trajectory per item without search or verifier feedback. VCRT obtains a 77.60% macro pass rate versus 64.53% for the strongest matched baseline, a paired gain of 13.06 points (95% bootstrap CI [12.58, 13.54]). Lean accounts for most of this gain at 33.49 points, while ProofWriter and CLRS improve by 2.85 points on average. Mechanism tests consistently favor anti-diamond supervision, whereas No-Orbit is statistically indistinguishable from full VCRT. The evidence does not establish a general benefit from exact orbit aggregation.

0.33

Energy-optimal scheduling for clocked reversible computing

cs.CC cond-mat.stat-mechcs.ET ·2026-10-17 ·Michael C. Thumann, David Soloveichik
theory similarity 0.58
Abstract · 12 pages, 5 figures

Computational dissipation may arise from both information erasure and finite-time operation, although both contributions can in principle be avoided in the absence of space and time constraints. Logically reversible computation can replace erasure with ancilla cleanup, and slow adiabatic protocols can eliminate any excess finite-time dissipation. Under limited memory and in finite time, however, choosing reversible cleanup over erasure requires additional dissipative operations, creating a semi-reversible energy--memory--time tradeoff. We formulate this tradeoff at a fixed operating point of an externally clocked thermally coupled computer, where reversible checkpoint moves and local irreversible erasures have specified effective prices $ε_R$ and $ε_I$. Their ratio $λ=ε_I/ε_R$ selects an energy-optimal semi-reversible schedule under a checkpoint-memory bound by trading reversible moves against erasures. For a sequential computation whose dependency graph is a line, we derive an exact separator recurrence and prove that an asymptotically optimal schedule repeats a strictly reversible block followed by one local erasure. Coupling this scheduling theorem to a stochastic-thermodynamic constitutive model shows how temperature, primitive duration, memory, and device-dependent operation costs determine whether the optimal schedule uses reversible cleanup, elective erasures, or erasure at every disposal.

0.23

Feasible Flow Matching for Graph Reconstruction via Within-Sampling Primal-Dual Guidance

cs.LG ·2026-09-26 ·Haoming Chen, Nicolas Zilberstein, Santiago Paternain, Santiago Segarra
theory similarity 0.57
Abstract

Graph reconstruction from partial observations often comes with structural side information, such as degree bounds, triangle counts, or an edge-density band. Prior-Informed Flow Matching (PIFM) reconstructs graphs by transporting a local prior toward the graph distribution, but it provides no mechanism to incorporate this side information. We put forth Constrained Primal-Dual PIFM (CPD-PIFM), which augments the sampler with Lagrange multipliers that evolve along each trajectory. The multipliers respond to constraint violations at a predicted endpoint and guide subsequent sampling steps without retraining. We prove that the sampler inherits PIFM's permutation equivariance and bound its expected terminal slack by a term that decays as the inverse square root of the number of steps, plus two approximation terms. On three link-prediction benchmarks and nine combinations of datasets and constraints, CPD-PIFM raises feasibility by 11-26 percentage points and remains competitive with fixed guidance without selecting a separate multiplier for each constraint.

0.35

Trajectory Matching: Discrete Flow Matching with Structured Actions

cs.LG ·2026-10-23 ·Niklas Kemper, Marten Lienen, David Lüdke, Stephan Günnemann
theory similarity 0.56
Abstract

The natural units of structured discrete generation are often not independent single-component edits but richer actions: attaching a fragment to a molecule, inserting a node together with an incident edge, or growing a hierarchy by adding a child. Yet most existing discrete flow matching methods (DFM) are restricted to independent component-wise edits over fixed-size states. This restriction stems from endpoint conditioning: endpoints fix the source and target during training but not the action sequence between them, making tractable conditional rates hard to define for complex actions that cannot be factorized component-wise. We propose trajectory matching, which conditions the flow on a full sequence of actions connecting the endpoints. This yields principled, simulation-free training targets for user-defined action spaces, including actions that change state size, modify multiple components, or depend on earlier actions. We prove that the resulting objective recovers the marginal flow and that trajectory matching strictly subsumes factorized DFM, while additionally capturing actions with prerequisite structure such as hierarchy growth or fragment-based molecule generation. Empirically, on tree and molecular graph generation, trajectory matching with domain-aligned actions matches or surpasses factorized DFM baselines (lifting MOSES validity from 92.8% to 99.2%) and transfers without retraining to substructure extension and linking. Trajectory matching enlarges the design space of discrete flow matching by turning the action vocabulary into a modeling choice. An interactive explanation of trajectory matching is available at https://niklaskemper.com/blog/trajectory-matching/.

0.45

Distributed LTL Synthesis under Arbitrary Message Adversaries

cs.DC cs.FLcs.LOeess.SY ·2026-11-03 ·Benedikt Bollig, Patricia Bouyer-Decitre, Matthias Függer, Dhrubajyoti Ghosh, Thomas Nowak +1 more
similarity 0.56
Abstract

Reactive synthesis is the problem of generating a program that produces outputs satisfying a logical specification for every input stream. We study distributed synthesis for two processes communicating in rounds over unreliable links, with at least one message delivered in every round. Despite this delivery guarantee, we show that synthesis from linear temporal logic specifications is undecidable, even when messages carry the processes' complete causal histories. More generally, we give a complete characterization of the communication restrictions that make synthesis decidable. Restrictions are described by a message adversary $A$, a set of allowed infinite graph histories: sequences of communication graphs, each specifying which messages are delivered in a round. Iterated chromatic subdivision associates these histories with points in the unit interval, yielding an image $π(A) \subseteq [0,1]$. For every $ω$-regular message adversary $A$, synthesis is decidable if and only if $π(A)$ is nowhere dense. In the decidable cases, our procedure takes a deterministic parity automaton for $A$ and a specification, decides realizability, and constructs a realizing distributed algorithm whenever one exists. Further, our topological arguments shed new light on the fundamental requirements of synthesis. They show that, for $ω$-regular message adversaries, synthesis is decidable if and only if consensus is repeatedly solvable in bounded time. This links two previously unrelated problems from formal verification and distributed computing through the processes' uncertainty about communication.

0.22

Recompute or Restore? Host-Tier KV for Multi-Model Agent Workflows on a Static-Graph NPU Serving Stack

cs.DC cs.LGcs.PF ·2026-11-11 ·Sungwon Woo, Seyeon Kim
similarity 0.56
Abstract · 14 pages, 6 figures, 5 tables

Agent workflows issue dependent model calls that share long context prefixes, so serving them efficiently depends on reusing the key-value (KV) cache of those prefixes. On accelerators that compile model graphs ahead of time, however, the device KV budget is fixed, and prefixes evicted under load must be recomputed. Restoring them from host memory avoids this recomputation, but the transfer occupies the same engine thread as prefill and decode, so its benefit is not guaranteed. In this paper, we study when restoring beats recomputing on a commercial static-graph neural processing unit (NPU) stack (Rebellions ATOM+, vllm-rbln 0.10.2) that serves a Qwen3-8B planner on two cards and a Qwen3-0.6B executor on one. We first show that repeated prefill dominates planner work when default serving collapses: 89.5% of the executed planner prompt tokens had been materialized before. We then build a synchronous host-DRAM tier on the runtime's public KV copy calls, together with a scheduler-aware event model whose predictions are frozen before each test cohort. Experimental results show that the host tier raises workflow service-level objective (SLO) attainment from 22.8% to 100% and from 9.4% to 99.8% in the two tested overload conditions, and endpoint confirmation on two new seeds supports conservative load gains of 11.8% (chain) and 18.2% (fork), while mixed and bursty workloads remain seed-sensitive. The frozen model predicts median and 99th-percentile (P99) latency within its 15% tolerance in all 24 common-load conditions, including the 16-18% P99 increase that the tier causes for fork workflows, but it misorders three policy contrasts and overestimates the benefit of a cheaper store path (11% predicted against 3.1% measured). The trade-off therefore depends on runtime scheduling and transfer cost as well as cache capacity.

0.25