- Rating
- 3
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
SepBench tests whether a neural graph-algorithm model keeps its predictions on a base graph after attaching a connected subgraph via one bridge edge. For MST edge labels and SSSP distances, this attachment provably leaves every original answer alone (Proposition 1), so any flip is a violation. A paired control attaches the subgraph through two edges, where an oracle confirms that at least one old label flips, to measure responsiveness.
For a reproduced 16-layer graph transformer trained on 16-node graphs (Stoll et al., 2025), 53.3–65.9% of exactly solved 64-node bases get a protected label flipped after a 64-node graft (three seeds). A second transformer and a message-passing network also violate the contract. Rates are far lower when the composite is no larger than a training graph (0.26–0.45% for the primary model, 6.06% for the MPNN at n=16).
Frozen-weight ablations has mixed results. Cutting CLS has no consistent direction, within-block attention masks remove most violations at n=64, and all masks together still leave 5.7–8.9%. The authors attribute the remainder to articulation vertices shared by two blocks. Executing each biconnected block separately, with private articulation copies, gives zero observed all-pair violations in both transformers with base F1 shifting by at most 0.0002.
In a matched training comparison at n=16, augmentation plus a consistency penalty cut the all-pair defect from 2.91% to 0.56%, while response to answer-altering edits fell from 97.6% to 68.9%, mostly from augmentation alone. An SSSP experiment with separately trained global and blockwise models shows the same pattern. A widest-path experiment was uninformative.
Critical strengths
-
Proposition 1 defines a violation with no tolerance and no distributional assumption. The oracle-certified answer-altering set lets the authors separate “invariant” from “ignores the graft”, which makes the training result readable. As far as I know, most stress tests lack ground truth for “this edit should not matter”, so the design transfers to any task with a decomposition.
-
The controls include composites at or below the training size, a model trained at 64 nodes, an fp32 rerun, a disjoint-union control for the MPNN, and a decision rule fixed before training. Mixed results are reported too (CLS removal, the mask worsening the defect at the training size). This makes it believable for me that the violations are real and not a bf16 or size artifact.
Critical weaknesses
-
If I understood correctly, the headline rates and the repair mostly reflect size extrapolation and a by-construction guarantee. The 53-66% is measured at eight times the training size, over a minority of bases that are solved exactly (794-1,522 per seed). Within the training size the primary model’s rate is 0.26–0.45%, and at twice the training size it is 16.08%. Section 3 concedes the size effect, but no control separates separator-specific interference from generic out-of-distribution instability. Zero violations under blockwise execution are guaranteed in exact arithmetic, because each old block receives identical inputs. That makes the result a check of the implementation and a statement about the wrapper. The wrapper also runs a classical Tarjan decomposition and sets bridge labels symbolically, so the network never sees the graft. It covers only undirected graphs, positive distinct weights, and single bridges.
-
I also think the mechanism and the trade-off are not isolated cleanly. Partitioning changes several things at once: it removes shared articulation state, recomputes positional encodings per block, and shrinks inputs toward the training size. Zero violations afterward do not pinpoint the shared articulation token, and the mask evidence is mixed. For Table 2, the augmentation arm trains on grafted copies, so the response drop at λ=0 may partly reflect a shift in input size and not lost sensitivity. The response metric counts a hit when any affected edge flips. It covers one architecture at n=16, and the control pairs use different base graphs and portal-edge construction from the answer-preserving pairs, so invariance and sensitivity are measured on different graph distributions. “Reduced responsiveness” is plausible but not separated from “learned to ignore the graft side”.
Questions for authors
- For the released transformer at 64+64, what is the violation rate for a disjoint union with no connecting edge, and for the same graft attached to a base of training size? If these are in a supplementary table, please point me to them. I want to know how much of the 53-66% is size extrapolation and how much is separator structure.
- Can you run single-factor ablations of the articulation explanation? For example, duplicate only the articulation token while keeping positional encodings computed on the whole composite, and separately recompute positional encodings per block while keeping the token shared. How does the flip rate depend on the distance between the flipped edge and the attachment vertex?
- How are the answer-altering controls matched to the answer-preserving pairs (degree and weight distributions, base graphs)? What is the response rate when control bases equal the keep bases, and how sensitive is it to the “cheap portal edge” choice?
- What are the block-count and block-size distributions, and how do base F1 and violations behave on graphs where one block holds most vertices, so partitioning does little?