acceptodds
Under review as a conference paper at ICLR 2027

Task-Relevant Null-Space Residuals for Non-Injective Neural Mappings

Abstract

Non-injective mappings in neural networks map distinct inputs to the same representation, thereby implicitly inducing equivalence relations in the input space. However, the input differences eliminated by these mappings may still be required by downstream tasks, creating a mismatch between operator-induced indistinguishability and task-required distinctions. For non-injective linear operators realized in the current forward pass, their null spaces exactly characterize these invisible input variations. We propose Task-Relevant Null-Space Residuals (NSR), a general residual framework for non-injective linear mappings. NSR combines null-space component extraction from pre-mapping representations, member-level encoding and gating, and application-specific integration to exploit potentially task-relevant information under downstream supervision while preserving the original aggregation or merging rules. We evaluate NSR in two structurally different settings: token merging and graph aggregation. In token merging, NSR achieves higher semantic segmentation performance than the corresponding compressed baselines in 34 out of 36 evaluated configurations, with a maximum observed gain of 31.51 mIoU points under strong compression. In graph aggregation, NSR achieves 100% training accuracy on Tree-NeighborsMatch at depths \(d=2–6\) across three backbones, alongside gains on heterophilic node classification and molecular graph regression. Together, these results support null-space residuals as a practical complement to non-injective linear mappings, enabling downstream models to learn from input distinctions invisible in the original operator's output.

Primary area:
other topics in machine learning (i.e., none of the above)
Keywords:
non-injective mappings, null-space residuals, task-relevant information, token merging, graph aggregation

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_AacgOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper investigates the information discarded during non-injective aggregation processes. By constructing null-space residuals and learnable complementary branches, the authors incorporate member-level information into graph message passing and visual token merging. The study includes experiments on graph classification, node classification, tree-neighborhood memory, and semantic segmentation, while providing comparisons involving raw member inputs and post-aggregation processing. Although the construction of linear residuals is well-grounded, their individual contribution, actual computational cost, and robustness across different settings remain to be fully substantiated.

Critical strengths

Addressing the issue of information loss during the neural network aggregation process from the perspective of null space offers a clear theoretical motivation and a versatile methodology. It yields significant performance improvements in both computer vision and graph learning tasks, with particularly notable results in high-compression scenarios.

Critical weaknesses
  1. In Table 14, the mIoU for the 3.4× compression setting (using ToMe) improves from a baseline of 18.31 to 49.12 with "RawSource," and further to 49.82 with "NSR." Most of this gain stems from the full complementary branch, rather than being attributable solely to null-space projection.
  2. The gating mechanism described in Section 3 takes the residual, member, and aggregated representations as inputs. Existing ablation studies do not disentangle the effects of the adaptive gating from those of the residual encoding; thus, it remains unclear at which stage task-relevant information is actually filtered.
  3. Experiments involving token compression are compared under identical compression ratios; however, NSR introduces additional parameters and computational operations. Consequently, these comparisons reflect the benefits of the added branch rather than an accuracy advantage under a fixed total computational budget.
  4. The computational complexity analysis in Appendix B excludes overheads such as indexing and padding, while the spatial branch retains original positional encodings. In the absence of empirical latency and peak VRAM usage measurements, the link between reduced computational complexity and actual resource efficiency remains unverified.
  5. Semantic segmentation experiments rely exclusively on Tiny-DeiT/16 paired with a linear decoding head. This is insufficient to demonstrate the generalizability of the proposed mechanism across backbones of varying scales or decoders capable of spatial reconstruction.
  6. In Appendix A, segmentation results are defined based on the final checkpoint from a single training run. In Table 14, the observed advantage of using residual inputs is only 0.20–0.24 mIoU points—a margin too small to be reliably distinguished from random fluctuations.
  7. In the tree-neighborhood memory experiments, NSR incorporates non-linear processing at the member level prior to aggregation. The study lacks a control condition with equivalent-capacity member processing, making it impossible to isolate whether the performance gains are truly attributable to the null-space construction.
  8. The ZINC experiments in Section 4 do not utilize edge (bond) types, while the graph-branch ablation in Appendix G is limited to the "Roman-empire" dataset. There is no direct evidence to substantiate the claims regarding the contributions to molecular tasks or the effective utilization of chemical relational information.
  9. The diagnostic quantity in Appendix E is constructed using ground-truth labels rather than learned latent features; while it can characterize the degree of label mixing, it cannot directly verify whether the model has truly recovered the task-relevant features that were discarded during aggregation.
Questions for authors
  1. Table 14 shows that RawSource accounts for most of the performance gain. How can the authors isolate the specific contribution of null-space projection from the auxiliary branch and adaptive gating?
  2. Since NSR introduces additional parameters and computation, how does it compare with baselines under matched total computational budgets? Can actual inference latency and peak memory usage be clarified?
  3. How stable are the reported improvements across random seeds, particularly the small gains over RawSource? Would the conclusions hold with larger backbones or more capable decoders?
  4. Can the authors provide stronger evidence that NSR recovers task-relevant information rather than benefiting from additional member-wise processing? How well do the label-based diagnostics support this mechanism?
6 comments

We sincerely thank you for your careful review and insightful comments. We especially appreciate your detailed analysis of the specific contribution of null-space projection, the roles of the auxiliary pathway and adaptive gating, computational fairness, and evidence for task-relevant information.

NSR uses the null space of the currently realized non-injective operator to address a potential mismatch between operator-induced input indistinguishability and distinctions required by downstream tasks. It is a complete framework combining null-space residual extraction, member-wise encoding and adaptive gating, and task-relevant information integration.

Regarding your observation that RawSource already accounts for most of the performance improvement, we would particularly like to clarify its relationship to Full NSR. RawSource uses original member representations, which already contain null-space components. Thus, their comparison does not test whether null-space information exists; it evaluates the additional value of explicitly separating operator-invisible components and processing them within the same compensation architecture. On ADE20K, Full NSR exceeds RawSource by 2.04 and 3.29 mIoU points at 3.4× and 3.8× compression, respectively.

In response to your questions, we added Member-wise MLP controls, ADE20K input-source ablations, comparisons at nearly matched total GFLOPs, a larger visual model, and measured inference-efficiency results. Complete results are consolidated in the shared Official Comment. We address your questions individually below.


Q1. Separating the Contributions of Projection, the Auxiliary Pathway, and Adaptive Gating

We examine these factors using three controls. Post-aggregation-only processes only the aggregated representation; Member-wise MLP applies a pre-aggregation Linear–GELU–Linear transformation without null-space projection or NSR gating; and RawSource retains NSR's full encoding, gating, and integration architecture, replacing only the null-space residuals with original member representations.

For the currently realized linear operator, X=UY+ZX=UY+Z and AZ=0AZ=0. Therefore, the original representations used by RawSource already contain null-space information. RawSource's improvement reflects the value of the complete member-wise compensation pathway, while its comparison with Full NSR isolates the additional value of explicitly separating operator-invisible components within the same architecture. On Roman-empire, Full NSR exceeds RawSource by 3.69, 2.14, and 1.56 percentage points for GCN, GraphSAGE, and GIN, respectively; it also exceeds nearly parameter-matched MLP controls by 7.53, 4.36, and 4.83 points, with only 260 parameters difference per pair (Table C1; Table 15 in the paper). On ADE20K at ToMe 3.4×/3.8×, Full NSR exceeds RawSource by 2.04/3.29 mIoU points and MLP by 3.52/4.34 points (Table C4).

These comparisons distinguish the benefit of the complete framework over ordinary member-wise processing from the additional contribution of explicit null-space separation. Projection defines the complementary information source; encoding and gating learn how to process it; and task-relevant integration enables it to affect downstream predictions.


Q2. Matched Computational Budgets and Actual Costs

Thank you for your careful attention to computational fairness. We added nearly parameter-matched controls, comparisons at similar total GFLOPs, and measurements of inference latency, throughput, and peak memory. The Member-wise MLP parameter comparisons appear in Table C1. At nearly identical total GFLOPs on ADE20K, ToMe-NSR-3.8× achieves 33.74 mIoU at 3.082 GFLOPs, compared with 17.67 mIoU at 3.085 GFLOPs for original ToMe-3.4×, a gain of 16.07 points. The corresponding PiToMe comparison is 34.17 versus 31.39 mIoU, a gain of 2.78 points (Table C9). Moreover, ToMe-NSR-3.4× reaches 34.11 mIoU at 3.443 GFLOPs, surpassing original ToMe-2.5× at 31.44 mIoU and 4.202 GFLOPs.

Measured inference results are given in Table C6. With DeiT-Base + FCN on VOC, adding NSR to ToMe 3.4× improves mIoU from 31.18 to 51.39, while inference latency rises from 36.86 to 41.06 ms/batch and peak memory from 1339.94 to 1346.35 MiB. These results directly show the predictive advantage at comparable theoretical compute budgets alongside the associated measured resource costs.


Q3. Experimental Stability and Stronger Visual Models

Regarding the evaluation protocol, the paper reports semantic-segmentation validation mIoU from the final checkpoint of a single training run; heterophilic node classification uses ten official splits, and ZINC uses ten random seeds. To further examine the Full NSR–RawSource differences, we extended the input-source ablations to ADE20K. Full NSR exceeds RawSource by 1.42, 2.04, and 3.29 mIoU points at ToMe 2.5×, 3.4×, and 3.8×, respectively (Table C4). Full NSR outperforms RawSource at all four ADE20K compression settings, showing consistent positive improvements across the evaluated compression strengths and providing further evidence for the stability of this residual-source benefit.

We also evaluated a larger DeiT-Base/16 backbone with an FCN segmentation head on VOC. NSR improves mIoU in all 12 compression configurations across ToMe, PiToMe, and MPM, including an increase from 31.18 to 51.39 for ToMe 3.4× and from 28.43 to 48.67 at 3.8× (Table C5). These results further demonstrate the value of explicit null-space residuals across ADE20K compression settings and the effectiveness of the complete NSR framework with a larger backbone and stronger segmentation head.


Q4. Evidence for Task-Relevant Information and the Label-Based Diagnostic

Your question concerns a central motivation of NSR: whether member differences invisible to the current aggregation operator remain relevant to downstream tasks. We examine this from three complementary perspectives: a controlled task with explicit semantic requirements, a label-based null-space diagnostic, and input-source ablations.

First, Tree-NeighborsMatch: the sibling-swap construction demonstrates that, under identical local aggregation weights, swapping values associated with different keys can leave the aggregated output unchanged while changing the correct answer. This gives a concrete example of a conflict between aggregation-induced indistinguishability and the key–value associations required by the task. Second, the label-based diagnostic in Appendix E: it measures the projection of task-label differences onto the current aggregation null space. Figures 4 and 6 show that, as diagnostic scores increase, original GNN accuracy generally decreases while NSR remains relatively stable, widening the accuracy gap. The diagnostic is used only for post-training analysis, not for training or model selection. Third, RawSource versus Full NSR: comparing predictive performance within the same compensation architecture shows the additional value of explicit null-space separation, with consistent improvements on Roman-empire and ADE20K (Table C4; Tables 14–15 in the paper).

Taken together, Tree-NeighborsMatch provides a concrete example of task-relevant local indistinguishability; the label diagnostic reveals the relationship between task-label structure and model performance; and RawSource ablations demonstrate the additional value of explicitly processing null-space information in actual prediction tasks. These complementary findings support NSR's central motivation: non-injective aggregation may eliminate member differences still required by downstream tasks, and explicitly extracting and using these differences under task supervision can improve predictive performance.


Additional Clarifications on Weaknesses

(1) Member-wise Encoding and Adaptive Gating

Null-space projection constructs Z=(I−UA)XZ=(I-UA)X from the current operator. The encoder transforms the residuals into learnable representations, and member-wise gating produces ci=gi⊙E(zi)c_i=g_i\odot E(z_i) based on each member and its context, adaptively modulating their contributions. For residuals satisfying ∑itizi=0\sum_i t_i z_i=0, a shared linear transformation BB still cancels under the original weights:

∑itiBzi=B∑itizi=0.\sum_i t_i Bz_i=B\sum_i t_i z_i=0.

In the visual implementation, member-wise RMSNorm and context-dependent sigmoid gates make the processed codes different from a single shared linear transformation, enabling effective complementary information. The RawSource and Member-wise MLP ablations further demonstrate the value of information-source choice and the complete member-wise processing mechanism. Projection, encoding, and gating have distinct but interconnected roles: projection defines the information source, encoding transforms its representation, and gating learns how to use it according to member context.

(2) Tree-NeighborsMatch Member-Level Controls

Following your suggestion, we added RawSource and Post-aggregation-only controls on Tree-NeighborsMatch under the task construction and training-fit evaluation settings of the original Alon & Yahav (ICLR 2021) paper. At d=6d=6, RawSource achieves 89%, 78%, and 85% maximum training accuracy for GCN, GIN, and GraphSAGE, respectively, whereas Full NSR reaches 100% for all three (Table C7). These results further distinguish post-aggregation processing, processing of original member representations, and explicit null-space residual processing in long-range matching.

(3) ZINC Inputs and Cross-Task Validation

Our three graph settings—heterophilic node classification, Tree-NeighborsMatch, and ZINC regression—all use GCN, GraphSAGE, and GIN as graph-aggregation backbones. To maintain consistent aggregation mechanisms and model designs across graph tasks, the ZINC experiments use GNNs based on node features and graph connectivity without introducing additional bond-type-specific message passing. Specifically, ZINC uses atom types and molecular connectivity to examine whether the same NSR aggregation-compensation mechanism extends from node classification and controlled matching to graph-level continuous regression. Table 3 in the paper reports test MAE over ten random seeds, with improvements from NSR for all three backbones, further demonstrating the applicability of the same compensation mechanism across graph prediction tasks.

In response to your questions, we will consolidate the Member-wise MLP controls and ADE20K input-source and integration-pathway ablations in the revised appendix.

We sincerely thank you again for your insightful comments on our methodology, experimental design, and computational fairness. Your emphasis on experimental stability was especially valuable: it prompted us to extend the input-source ablations to ADE20K, where we observed consistent improvements across compression settings, allowing us to examine the value of explicit null-space residuals more thoroughly. Your careful analysis has helped us clarify the contribution of the complete NSR framework and better connect its theoretical motivation with the experimental results.

Reviewer_37bfOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper studies the mismatch between the equivalence classes induced by a non-injective linear operator (e.g., weighted neighbourhood aggregation in GNNs, weighted token merging in ViTs) and the distinctions a downstream task may require. Task-Relevant Null-Space Residuals (NSR) keeps the original operator untouched and adds a learnable side branch that (i) extracts per-member residuals, (ii) encodes and gates them, and (iii) integrates them in an application-specific way.

Critical strengths
  1. Clean, operator-agnostic formulation with a non-trivial engineering instantiation, and the baseline is provably preserved. The AUA=AAUA=A lift covers both the orthogonal (graph, U=t/t⊤tU=t/t^\top t) and oblique (token, U=1KU=\mathbf 1_K) cases, matches copy-based unmerging exactly, and the zero-initialised vision decoders guarantee the augmented model starts at the baseline. This makes NSR a drop-in addition that does not alter the compression schedule, matching rule, or FLOP target of the host method — a practically attractive property that is consequential for adoption.
  2. Breadth and honesty of the empirical study. Two structurally different domains, three operators × three datasets × four operating points in vision, three backbones × seven tasks in graphs, 10-split/10-seed reporting for the heterophilic and ZINC experiments, and — crucially — ablations that isolate (i) access to pre-merge information (post-merge-only control), (ii) the integration path (feature vs. spatial), and (iii) the input source (RawSource vs. null-space residual) in both domains. The authors report the cases where NSR hurts (ToMe 1.8× Cityscapes, MPM 1.8× ADE20K, GCN/Tolokers, SAGE/Minesweeper) and where feature-only is harmful. This transparency strongly supports the credibility of the reported numbers.
Critical weaknesses
  1. The paper's central claim — that the null-space construction is what matters — is only weakly supported by the paper's own ablations; the dominant effect is a generic member-level bypass.

    • All evaluated operators have k=1k=1 (a single weighted sum), so ker⁡(A)\ker(A) is (n−1)(n{-}1)-dimensional and ZZ is simply XX with one rank-one direction removed. The "null-space residual" is therefore nearly the full pre-merge input.
    • Consistently, RawSource (encode xix_i instead of ziz_i, everything else identical) recovers almost all of the gain on VOC: ToMe 3.4× gives Base 18.31 → RawSource 49.12 → Full NSR 49.82, i.e. the projection accounts for ≈0.7 of the headline +31.5 points; across Table 14 the projection adds only 0.20–3.68 points, and RawSource is itself above Base in 11/12 cases. On Roman-empire (Table 15) the projection contributes 1.6–3.7 of the 6–11-point gain.
    • NSR-Feature alone is often below baseline (ToMe 2.5×/3.4×/3.8×, PiToMe 1.8×/3.4×, MPM 1.8×/2.4×/3.0×). In the collapsed ToMe regimes (2.5–3.8×) that produce the headline numbers, NSR-Spatial alone recovers 95–102% of Full NSR's gain; for PiToMe and MPM the spatial path accounts for roughly 57–87% and the feature path contributes the remainder (MPM 2.4× is the one case where neither path alone beats the baseline). The spatial path is a learned skip connection carrying predominantly early-layer (where most merging occurs), full-resolution token information around the merge — a well-known benefit for dense prediction with a linear head. The VOC ablations suggest the same mechanism may explain why PiToMe 1.8× on ADE20K surpasses Full-ViT, which has no such skip; the decomposition on ADE20K would be needed to confirm this.
    • There is also a design-level reason for the weak feature path. The encoder is RMSNorm followed by a bias-free linear map BB (App. A.2). The linear part cancels exactly under re-aggregation with the original weights, ∑iti ziB=(AZ)B=0\sum_i t_i\, z_i B = (AZ)B = 0 — a point §3.3 itself makes for a shared linear transform. In the actual implementation the only non-linearities that can prevent this cancellation are the per-member scalar rescaling 1/rms(zi)1/\mathrm{rms}(z_i) from RMSNorm and the sigmoid gates, so the feature path has to carry all of its information through two rather restricted channels. The paper does not connect this observation to the fact that NSR-Feature often underperforms the baseline in Table 13. Together these results suggest the paper's title, abstract and conclusion over-attribute the gains to the null-space idea. This is consequential because the framing is the main conceptual contribution; the empirical contribution reduces to "add a gated, member-wise skip around non-injective merges/aggregations," which is useful but much less novel.
  2. Missing simple, strong comparison points, heterophilic baselines below published numbers, and a weak Tree-NeighborsMatch protocol.

    • The gate network (inputs: source, destination, member) followed by a sum is essentially gated/attentional message passing (GAT, GatedGCN, PNA-style). On Roman-empire, Platonov et al. (2023a) report GAT 80.87 → GAT-sep 88.75 and GT-sep 87.32, and GraphSAGE (which separates the root path) at 85.74 vs. GCN 73.69; NSR+GraphSAGE (87.71) sits in that range. None of these baselines are compared. Moreover, the paper's own baselines are below the published ones (GCN 72.05 vs. 73.69; GraphSAGE 81.59 vs. 85.74). The configurations differ (hidden 128 / 4 layers here vs. hidden 512 / tuned depth in Platonov et al.), so the numbers are not directly comparable, but against a tuned SAGE the NSR margin would be ≈2 points rather than 6. Graph parameter/FLOP overhead of NSR is not reported (only one parameter-matched control, on one dataset).
    • Tree-NeighborsMatch (§4.2.2, Fig. 3). The sibling-swap argument correctly shows that the first local aggregation cannot distinguish swapped values under equal coefficients. However, the backbones use d+1d{+}1 message-passing layers with self-loops (App. A.1), so a leaf's representation after layer 1 is already a non-linear function of its (key, value) input (GELU/LN or the GIN MLP, App. A.3); at layer 2 the parent therefore sums non-linearly transformed members, which can in principle preserve the pairing (cf. Xu et al. 2019, Lemma 5). The argument thus establishes local indistinguishability at one layer but not a failure of the backbone as a whole, and it does not by itself explain depth-dependent degradation — the pattern Alon & Yahav attribute to over-squashing. The text does not state at which depth the original backbones first fail (Fig. 3 is not tabulated). The Post-aggregation-only and RawSource controls (App. G.4) are run only on Roman-empire; running them on this task would separate "null-space information" from "an additional normalised residual path with extra capacity." The protocol also limits the claim: each model is trained once with a single seed (seed 11, following the reference implementation) and the reported number is the maximum training accuracy observed during the run (App. A.1); differences at d=7,8d=7,8 between single runs are fragile. Parameter counts are not reported; from App. A.3 the NSR branch adds ≈7d27d^2 parameters per layer (message linear d2d^2, gate 4d24d^2, output MLP 2d22d^2), i.e., roughly 7× a GCN layer and 3–3.5× a SAGE/GIN layer at hidden size 32, with no width- or depth-matched baseline. Statements such as "100% training accuracy at d=2d=2–66" should be qualified accordingly.
    • In vision, segmentation-oriented merging methods (ALGM, cited in related work) are not compared, and results are single-run/final-checkpoint only. The largest gains (e.g., +31.51 on VOC ToMe 3.4×) occur where the baseline has collapsed: with 196 tokens and r=29r=29, and ToMe capping merges at half the remaining tokens, roughly 25 tokens remain by block 5 and ≲10 in the last four blocks. The VOC ablations (Tables 13–14) show that in this regime almost all of the gain comes from the spatial write-back of member codes, and that replacing null-space residuals with raw member features recovers all but 0.2–3.7 mIoU. The abstract should attribute the headline number accordingly, and a per-layer token-count table would help readers interpret the strong-compression results.
Questions for authors

Clarifications (could change my assessment):

  1. Please add, in both domains, a baseline that applies a non-linear per-member transform before the original aggregation/merge (no null space, no gating), and in graphs GAT / GatedGCN / "-sep" variants at matched parameter counts. Does Full NSR still provide a meaningful margin? Please also report graph-model parameter counts and training/inference time for Original vs. +NSR, and — since the GCN/GraphSAGE baselines are below the numbers in Platonov et al. (2023a) — the Original–NSR comparison under their configuration (hidden 512, tuned depth).
  2. Given Table 13, what is the paper's position on the feature path? Since the encoder's linear projection cancels under the merge weights and only RMSNorm's per-member scalar and the gates break the cancellation, is this restricted capacity the reason the feature path often hurts? Would a second-order statistic (e.g. ∑iti zi⊙zi\sum_i t_i\, z_i\odot z_i) or a genuinely non-linear EE (e.g. an MLP) be a better-motivated feature path?
  3. For segmentation, how does Full-ViT + a comparable early-layer skip connection (same 64-d codes written to patch positions, no merging) perform? This is needed to separate "compensating for merging" from "adding a skip that also helps the uncompressed model" (cf. PiToMe 1.8× ADE20K exceeding Full-ViT). Please also report the Table 13/14 decomposition on at least one dataset other than VOC.
  4. Tree-NeighborsMatch: please tabulate Fig. 3, report multiple seeds, final (not maximum) training accuracy, a width-matched baseline, and the Post-aggregation-only / RawSource controls on this task. At which depth do the original backbones first fail, and does NSR still reach 100% at d=5,6d=5,6 under this protocol?
  5. The graph branch sums gated residuals unweighted (∑igi⊙zi\sum_i g_i\odot z_i) while the null-space constraint is w.r.t. tvt_v. For GraphSAGE (uniform tvt_v) and GIN with ϵ=0\epsilon=0 (App. A.3; tv=1t_v=\mathbf 1) this sum is identically zero whenever the gates are constant across members, so for these two backbones all signal must come from member-dependent gating, whose inputs (source, destination, residual) make it an attention mechanism; only for GCN (tvt_v non-uniform) does the residual itself survive the sum. Can the authors comment on this, and does it explain why GCN benefits most on Roman-empire?
  6. Appendix F: for ToMe at r=29r{=}29/33 on 196-token VOC inputs, how many tokens remain after each block? Please state explicitly how degenerate the 3.4×/3.8× baselines are so readers can calibrate the +31.5 claim.
  7. Is code released? Several details (scatter-based projection, spatial write-back, MPM calibration search, graph-branch initialisation) are hard to reproduce from text alone.

Suggestions (not affecting the score):

  • Evaluate at least one operator with k>1k>1 (e.g. 2×2 average pooling, strided projection) to substantiate the "general framework" claim.
  • Add ImageNet classification or a larger backbone to show the vision results are not specific to DeiT-Tiny + linear head.
  • Appendix C's ∥AZ∥∞≤1.8×10−6\|AZ\|_\infty\le 1.8\times10^{-6} check only verifies a linear identity in floating point; consider replacing it with something informative (e.g. how much task-relevant information ZZ carries, probing accuracy from ZZ alone).
  • Temper the abstract/conclusion to reflect that most of the gain comes from member-level access, with the null-space projection providing a consistent but modest additional benefit.
5 comments

We sincerely thank you for your careful review and insightful comments. We particularly appreciate your in-depth analysis of linear cancellation in Feature Integration, the roles of the two information-integration pathways, and the relationship between RawSource and null-space residuals. NSR is not a stand-alone null-space projection; it is a complete framework combining operator-defined null-space residual extraction, member-wise encoding and adaptive gating, and task-relevant information integration.

To assess the value of the complete framework, we followed your suggestion and added Member-wise MLP controls in both graph aggregation and Token Merging. With nearly identical parameter counts, NSR clearly outperforms ordinary member-wise nonlinear processing across four graph backbones. On ADE20K, Full NSR also outperforms direct MLP-based member compensation at all four compression settings.

Another key distinction concerns RawSource versus Full NSR. RawSource uses original member representations, which already contain null-space components. Thus, this comparison does not test whether null-space information exists; it tests the additional value of explicitly separating operator-invisible components and processing them within the same compensation architecture. On ADE20K at 3.4× and 3.8×, Full NSR exceeds RawSource by 2.04 and 3.29 mIoU points, respectively. The additional ADE20K experiments also clarify the complementarity between Feature Integration and Spatial Routing. Complete experimental results are consolidated in the shared Official Comment. We respond to your questions individually below.


Q1. Member-wise MLP, Stronger GNN Baselines, and Computational Costs

Following your suggestion, we added pre-aggregation Member-wise MLP controls using Linear–GELU–Linear and extended NSR to four-head GAT. On Roman-empire, Full NSR exceeds the nearly parameter-matched MLP controls by 7.53, 4.36, 4.83, and 4.12 percentage points for GCN, GraphSAGE, GIN, and GAT, respectively, with only 260 parameters difference per pair (Table C1). For GAT, NSR preserves the native attention-weight computation and constructs null-space residuals from the aggregation weights actually used by each head. For stronger baselines, we further tested GNNs with h=512h=512: GCN improves from 75.05% to 84.95%, and GraphSAGE from 84.90% to 89.79% (Table C2). Parameter counts, training and inference times for original GNNs, MLPs, and NSR are reported in Table C1; visual-model computation and measured efficiency are given in Tables C5–C6.

We also extended the paper's null-space label diagnostic to GAT (Table C3). As diagnostic scores increase, original GAT accuracy generally declines while NSR-GAT remains relatively stable; gains in the lowest and highest bins are 2.38 and 10.97 percentage points, respectively, consistent with the trends for the other GNNs in the paper.


Q2. Linear Cancellation in Feature Integration and Second-Order Augmentation

We agree that, for a shared linear transformation BB,

∑itiBzi=B∑itizi=0.\sum_i t_i Bz_i = B\sum_i t_i z_i = 0.

The residual encoder includes RMSNorm and a linear mapping, while the gating network generates channel-wise sigmoid weights from the member residual, member representation, and group context. RMSNorm introduces member-dependent normalization scales, and contextual gating modulates individual members. Consequently, the processed residual codes are no longer equivalent to applying a single shared linear transformation to every member and generally need not cancel under the original merging weights. Furthermore, Feature Integration is not NSR's only means of using complementary information. Feature Integration updates the merged group representation so that member differences can influence subsequent Transformer feature computation. Spatial Routing retains the correspondence between member codes and their original patch positions, providing position-specific compensation during spatial reconstruction. The two paths operate at different stages, and their synergy is central to Full NSR.

In response to your suggestions on second-order statistics and nonlinear MLPs, we added Feature-2nd, NSR-2nd, and ToMe-MLP experiments on ADE20K (Table C4). Feature-2nd improves on Feature-only at all four operating points, but its dual-path variant NSR-2nd does not outperform Full NSR, highlighting the more effective synergy of the two pathways in the current framework. Under strong 3.4×/3.8× compression, Full NSR exceeds ToMe-MLP by 3.52/4.34 mIoU points and Spatial-only by 4.23/4.80 points, respectively. Thus, the value of Feature Integration lies not only in its individual feature updates but also in its complementary interaction with Spatial Routing.


Q3. Full-ViT+Skip and ADE20K Ablations

Following your suggestion, we introduced a Full-ViT+Skip control on ADE20K and extended the pathway and input-source ablations from VOC to ADE20K. Full-ViT+Skip performs no Token Merging; it adds an early feature pathway analogous to Spatial Routing to the uncompressed model, isolating the effect of an ordinary skip connection. Full-ViT achieves 37.60 mIoU and Full-ViT+Skip reaches 37.64, a gain of just 0.04.

By comparison, for ToMe at 3.4×, Original, RawSource, Spatial-only, and Full NSR achieve 17.67, 32.07, 29.88, and 34.11 mIoU, respectively; at 3.8×, the corresponding values are 12.44, 30.45, 28.94, and 33.74 (Table C4). Since the original member representations satisfy X=UY+ZX=UY+Z, RawSource already contains null-space information. Full NSR retains the same encoding, gating, and integration architecture but explicitly extracts the null-space components, so the comparison isolates the additional value of the information-source choice. Full NSR exceeds RawSource by 2.04/3.29 points at 3.4×/3.8×. Together with the Full-ViT+Skip results, these findings highlight NSR's role in compensating for member differences eliminated by Token Merging.


Q4. Tree-NeighborsMatch Protocol and Additional Controls

Thank you very much for your in-depth analysis of the relationship between local indistinguishability and the representational capacity of multilayer GNNs. The sibling-swap construction in the paper illustrates that a single realized local linear aggregation can map distinct member configurations to the same representation even when the downstream task requires distinguishing them. Subsequent nonlinear mappings may produce different representations, but they may also fail to adequately preserve or exploit member differences eliminated by an earlier aggregation. NSR operates directly at the current local aggregation, extracting the member differences invisible to that operator and providing them to subsequent computation through a learnable compensation pathway.

We follow the Tree-NeighborsMatch task and training-fit evaluation settings of the original Alon & Yahav (ICLR 2021) paper, using d+1d+1 message-passing layers, hidden dimension 32, and seed 11, and report the highest training accuracy observed during training, consistent with best_train_acc in the original paper. In Figure 3 of the paper, the original GNNs begin exhibiting varying degrees of fitting degradation at d=4d=4, whereas Full NSR achieves 100% at d=2d=2–66. The new Tree RawSource and Post-only controls (Table C7) further distinguish access to post-aggregation information from member-level information. At d=6d=6, RawSource reaches 89%, 78%, and 85% for GCN, GIN, and GraphSAGE, whereas Full NSR reaches 100% for all three. These results connect the local indistinguishability analysis to fitting behavior in a long-range matching task and further demonstrate the value of explicit null-space residuals in the complete compensation architecture.


Q5. Gated Residual Aggregation and the Null-Space Constraint

Thank you for your accurate observation about this key mechanism. The distinction is that extracted NSR residuals satisfy the weighted null-space constraint of the original aggregation operator, whereas NSR forms node corrections by summing member-wise gated residuals:

∑itizi=0,Δv=Fout,v(∑igi⊙zi).\sum_i t_i z_i = 0, \qquad \Delta_v=F_{\mathrm{out},v}\left(\sum_i g_i\odot z_i\right).

These two operations do not employ the same aggregation weights, so the original weighted null-space constraint does not imply that the NSR correction must vanish. For GraphSAGE with uniform neighborhood aggregation and the evaluated GIN with ϵ=0\epsilon=0, all participating members have the same aggregation coefficient, hence ∑izi=0\sum_i z_i=0. If gates are constant across members, gi=gg_i=g, then

∑ig⊙zi=g⊙∑izi=0.\sum_i g\odot z_i=g\odot\sum_i z_i=0.

Thus, these two backbones rely on member-dependent adaptive gating to change the relative contributions of residuals that would otherwise cancel, allowing them to participate in node updates. For GCN, degree-normalized aggregation coefficients are generally nonuniform; consequently, ∑itizi=0\sum_i t_i z_i=0 does not imply ∑izi=0\sum_i z_i=0. Even a constant gate can therefore yield a nonzero unweighted residual sum, while adaptive gating further modulates member contributions. Accordingly, null-space projection extracts information invisible to the currently realized original aggregator, and member-level gating learns how to utilize it. The new four-head GAT experiment further illustrates this mechanism's complementarity with adaptive attention aggregation: original GAT achieves 77.32%, compared with 84.41% after adding NSR (Table C1).


Q6. Layer-Wise Token Counts for ToMe 3.4× and 3.8×

For a VOC input with 196 patch tokens and one CLS token, ToMe at 3.4× (r=29r=29) retains 168 and 27 tokens after blocks 0 and 5, respectively; at 3.8× (r=33r=33), it retains 164 and 17. The complete 12-block trajectories appear in Table C8. The two configurations differ from the early blocks onward; approximately 25 remaining tokens does not describe the state after the first block.


Q7. Code and Reproducibility

Appendix A of the paper specifies scatter-based null-space projection, member-wise encoding and gating, spatial write-back, and initialization. Appendix F gives the compression configurations and their construction, and Appendix C presents numerical checks. The associated experimental code has also been submitted as supplementary material to facilitate verification of the implementation and results.


Responses to Additional Suggestions

S1. Multi-Output Non-Injective Operators

MPM provides a multi-output non-injective mapping example. For kk disjoint token pairs, the overall merging operator can be written as A∈Rk×2kA\in\mathbb{R}^{k\times 2k}. Each pair uses mean merging with weights (1/2,1/2)(1/2,1/2), and the overall operator has a block-diagonal structure. With a lift UU consistent with copy-based restoration, P=I−UAP=I-UA is also block-diagonal; the global null-space projection is therefore equivalent to the local projections for individual pairs. The overall operator has rank kk and null-space dimension kk. For each pair, the null-space dimension is one, which is half of that pair's original member-space dimension. Thus, MPM illustrates that null-space residuals are not always almost identical to the complete original member representation, and shows NSR's applicability to multi-output non-injective mappings formed by independent local aggregations.


S2. Larger Visual Backbone

We evaluate DeiT-Base/16 + FCN. NSR improves mIoU in all 12 compression configurations across ToMe, PiToMe, and MPM; for instance, ToMe improves from 31.18 to 51.39 at 3.4× and from 28.43 to 48.67 at 3.8× (Table C5).


S3. Numerical Verification and Task-Relevant Information

Appendix C of the paper verifies the null-space constraint with ϵnull=∥AZ∥∞\epsilon_{\mathrm{null}}=\lVert AZ\rVert_\infty and analyzes residual magnitude using ρZ=∥Z∥F/∥X∥F\rho_Z=\lVert Z\rVert_F/\lVert X\rVert_F. Appendix E additionally constructs a diagnostic score by projecting task labels onto the current aggregation null space. The diagnostic is computed after training and does not affect model training or selection. In the new GAT analysis, the lowest and highest diagnostic bins show gains of 2.38 and 10.97 percentage points (Table C3), consistent with the trends for other GNNs in the paper. Thus, Appendix C's numerical checks and Appendix E's label-based diagnostic provide complementary views: the former verifies the residual's mathematical properties and nonzero magnitude, while the latter examines how operator-invisible differences relate to downstream task-label structure. The added GAT analysis further extends this evidence to different graph aggregation mechanisms.


S4. Positioning the Contribution in the Abstract and Conclusion

NSR's core contribution is to use the current non-injective operator's null space to address a potential mismatch between operator-induced input indistinguishability and downstream task requirements, rather than to introduce a stand-alone projection operation. The complete framework combines null-space residual extraction, member-wise encoding and gating, and task-relevant information integration. Member-wise MLP, RawSource, and the dual-pathway ablations respectively demonstrate the roles of the complete framework, the explicit information source, and the complementarity of the two information-utilization pathways. In response to your suggestions, we will consolidate the Member-wise MLP controls and ADE20K pathway and input-source ablations in the revised appendix.

We sincerely thank you again for your in-depth and constructive comments, especially your precise analysis of the linear cancellation property of Feature Integration. Your suggestion of Member-wise MLP controls was particularly valuable—an important experimental perspective we had not previously considered. It helped us gain a deeper understanding of NSR's contribution and demonstrate the complete framework's value over ordinary member-wise processing more effectively. We greatly appreciate your insightful guidance on our methodological mechanisms and experimental design.

Reviewer_kKJROpenReview ↗
Rating
2
Confidence
2
Informativeness
1
Presentation
2
Soundness
1
Read review
Paper summary

This paper proposes Task-Relevant Null-Space Residuals (NSR), a framework for recovering task-relevant information discarded by non-injective neural mappings. The method extracts null-space components from pre-aggregation representations and processes them through a learnable residual pathway with member-wise encoding and gating. The authors instantiate NSR in graph neighborhood aggregation and visual token merging, demonstrating improvements in semantic segmentation, heterophilic node classification, and molecular graph regression.

Critical strengths
  1. The null-space perspective provides a coherent interpretation of this information loss. The motivation is clear
  2. The experiment setting and task choice are reasonable
  3. The method improves semantic segmentation performance
Critical weaknesses
  1. The main theoretical result, namely the decomposition (X=UY+Z) with (AZ=0), follows directly from standard null-space projection properties. The method is easy to follow novelity is limited
  2. The computational efficiency analysis is incomplete. Could the author provide systematic measurements of end-to-end inference latency, throughput, or peak memory.
  3. i am not familar with the importance of this reasearch problem, especially the impact. But, from graph or GNN perspective, the proposed method is more like residual GNN+ some MOE design. I am not surprised by the experiment, but i should say the contribution to graph/GNN community is so limited. If this problem has strong and realistic application, i would change my mind. But for now, i do not see any novelty in graph task and guidance for GNN.
Questions for authors

See weakness

6 comments

Thank you for recognizing the motivation, choice of tasks, and semantic segmentation results of our work. The new numerical results are consolidated in the shared Official Comment. We respond to your questions individually below.


Q1. Theoretical Novelty and the Contribution of Null-Space Decomposition

We agree that Z=(I−UA)XZ=(I-UA)X, AZ=0AZ=0, and X=UY+ZX=UY+Z follow directly from standard linear algebra. We do not present these projection identities as new theoretical theorems. Instead, NSR addresses a specific operator–task mismatch: two sets of member messages may produce the same realized aggregation output while retaining differences useful for the downstream task.

Our GCN, GraphSAGE, and GIN baselines already include inter-layer residual connections. Building on these residual backbones, NSR constructs complementary information specifically from member differences eliminated by the current neighborhood aggregation. A conventional inter-layer residual connection passes the central node's representation across layers but does not necessarily expose differences among members eliminated by the current aggregation. NSR constructs an operator-specific complementary information source, and member-wise encoding and gating enable its use under downstream supervision without replacing the backbone's native aggregation. Although the gating mechanism resembles adaptive message passing, NSR does not contain a mixture of independent experts or an expert router.

To assess the complete framework, we added nearly parameter-matched Member-wise MLP controls. On Roman-empire, NSR exceeds MLP by 7.53, 4.36, and 4.83 percentage points for GCN, GraphSAGE, and GIN, respectively, with only 260 parameters difference in each pair (Table C1). In addition, RawSource retains the complete NSR compensation architecture but replaces null-space residuals with original member representations. Within the same architecture, Full NSR exceeds RawSource by 3.69, 2.14, and 1.56 percentage points on Roman-empire, and by 2.04/3.29 mIoU points on ADE20K with ToMe at 3.4×/3.8× (Table C4; Table 15 in the paper). These results distinguish the value of the complete NSR framework over ordinary member-wise nonlinear processing from the additional benefit of explicit null-space separation within the same architecture.


Q2. Inference Latency, Throughput, and Peak Memory

Following your suggestion, we measured actual inference latency, throughput, peak memory, and graph-model training and inference times. Complete results appear in shared Tables C1, C5, and C6.

(1) Visual Token Merging

With DeiT-Base/16 + FCN, NSR improves mIoU in all 12 compression configurations of ToMe, PiToMe, and MPM. For example, with ToMe at 3.4×, mIoU rises from 31.18 to 51.39 (+20.21), while inference latency increases from 36.86 to 41.06 ms/batch (+11.4%) and peak memory from 1339.94 to 1346.35 MiB (+0.48%). With ToMe at 1.8×, NSR reaches 72.81 mIoU, approaching the uncompressed Full-ViT's 74.58, while its latency is 57.36 ms/batch versus 79.23 ms/batch for Full-ViT.

(2) Graph Aggregation

For GraphSAGE, NSR improves accuracy from 81.59% to 87.71%, with inference time increasing from 0.002065 s to 0.007562 s. In the nearly parameter-matched comparison, MLP-GraphSAGE achieves 83.35%, whereas NSR-GraphSAGE achieves 87.71% (Table C1). These results document the actual computational performance of NSR in vision and graph learning, while further demonstrating the advantage of the complete framework over ordinary member-wise processing.


Q3. Research Significance and Guidance for Graph Learning

We appreciate your concern regarding the significance of this problem. NSR offers a concrete design principle: preserve the original aggregation rule, explicitly extract member differences invisible to the currently realized operator, and learn to use this complementary information under downstream task supervision.

(1) Tree-NeighborsMatch: A Controlled Task with Explicit Task Requirements

The root must retrieve the value associated with a query key. The sibling-swap construction in the paper shows that exchanging values associated with different keys can leave a local aggregation output unchanged while changing the correct prediction. This directly illustrates a conflict between local aggregation-induced indistinguishability and task requirements. In Figure 3 of the paper, Full NSR reaches 100% maximum training accuracy for all three GNN backbones at depths d=2d=2–66. The additional RawSource and Post-only controls further examine member-level information processing: at d=6d=6, RawSource achieves 89%, 78%, and 85% for GCN, GIN, and GraphSAGE, respectively, whereas Full NSR reaches 100% for all three (Table C7).

(2) Roman-empire: Real Graph Tasks and Attention Aggregation

On Roman-empire, NSR improves GCN, GraphSAGE, and GIN, which already contain inter-layer residual connections, by 10.85, 6.12, and 8.25 percentage points, respectively. We also extend NSR to four-head GAT, improving accuracy from 77.32% to 84.41% while preserving its native attention computation. The null-space label diagnostic shows a consistent pattern: as diagnostic scores rise, original GNN accuracy generally decreases while NSR remains relatively stable. The additional GAT diagnostic yields gains of 2.38 and 10.97 percentage points in the lowest and highest bins (Table C3).

(3) Specific Implications for GNN Design

The experiments demonstrate a design alternative to modifying aggregation functions or increasing model capacity: construct null-space complementary information from the currently realized operator and use member-wise encoding and adaptive gating to form node updates. This approach preserves the native aggregation rules of GCN, GraphSAGE, GIN, and GAT, and also applies to visual Token Merging. For example, on ADE20K, ToMe-NSR-3.8× exceeds original ToMe-3.4× by 16.07 mIoU points at nearly identical total GFLOPs (Table C9). Together, these two structurally different applications show the value of exploiting operator-invisible member differences and provide an integrable information-compensation mechanism for non-injective aggregation.

In response to your suggestions, we will consolidate the Member-wise MLP controls and ADE20K input-source and dual-pathway ablations in the revised appendix.

Thank you again for your detailed comments on the theoretical contribution, computational efficiency, and significance for graph learning. Your suggestions have helped us clarify the distinction between NSR and conventional residual connections and better demonstrate the practical value of the complete framework.

Thank you for the additional experiments. The results show that NSR improves GCN, GraphSAGE, and GIN, but I still have a concrete question: when would I choose NSR over an existing GNN aggregator, and why? The rebuttal reports gains over the original backbones. I would find it more useful to see what NSR does differently from methods such as PNA or MM-GNN, which already use information that mean aggregation discards.

For example, the neighborhoods {1,3}\{1,3\} and {2,2}\{2,2\} have the same mean. NSR can distinguish them, and so can a GNN that uses standard deviation. Could the authors give a concrete example where the particular residual used by NSR makes a difference, and explain whether that situation occurs in the datasets they study?

Comments on the paper

3 comments

Consolidated Additional Experiments and Clarifications

We sincerely thank all three reviewers for their careful assessments, in-depth analyses, and constructive suggestions. In response to their questions on NSR's novelty, component roles, experimental controls, computational efficiency, and applicability across models, we have conducted additional experiments and consolidate the shared results here for the reviewers and Area Chair. Reviewer-specific questions are addressed individually in the corresponding responses.


A. NSR Framework and Experimental Controls

The core contribution of NSR is to use the null space of the currently realized non-injective operator to identify and address a specific problem: the input indistinguishability induced by the original operator may not align with the distinctions required by downstream tasks.

NSR is a complete framework consisting of operator-defined null-space residual extraction, member-wise encoding and adaptive gating, and task-relevant information integration.

We use three controls to examine the complete framework and its information sources. Post-aggregation-only generates an additional correction using only the aggregated representation. Member-wise MLP applies Linear–GELU–Linear to members before native aggregation, without null-space projection or NSR's adaptive gating. RawSource retains NSR's full encoding, gating, and integration architecture, replacing only the null-space residuals with original member representations.

Post-aggregation-only and Member-wise MLP compare ordinary extra processing against Full NSR; RawSource versus Full NSR isolates the additional value of explicit null-space separation within the same compensation architecture.


B. Graph Aggregation Experiments

Table C1. Roman-empire: Member-wise MLP, GAT, and Computational Costs

All results use ten official splits. We report test accuracy, parameter counts, training time per epoch, and inference time.

BackboneVariantAcc. (%)ParamsTrain/epoch (s)Inference (s)
GCNOriginal72.05 ± 0.64107,9220.0072320.002906
MLP75.37 ± 0.47569,4860.0192070.007393
+NSR82.90 ± 0.71569,7460.0251940.009630
GraphSAGEOriginal81.59 ± 0.55173,4580.0064430.002065
MLP83.35 ± 0.57635,0220.0169030.005541
+NSR87.71 ± 0.61635,2820.0207640.007562
GINOriginal74.00 ± 0.79174,9940.0063740.002177
MLP77.42 ± 0.50636,5580.0168930.005544
+NSR82.25 ± 0.65636,8180.0247230.008356
GATOriginal77.32 ± 0.79174,9940.0144760.005817
MLP80.29 ± 0.61636,5580.0266710.009735
+NSR84.41 ± 0.41636,8180.0336420.011603

Full NSR differs from the corresponding MLP by only 260 parameters for each of the four backbones, yet achieves accuracy improvements of 7.53, 4.36, 4.83, and 4.12 percentage points. For four-head GAT, NSR constructs null-space residuals using the aggregation weights realized by each attention head while preserving the native attention-weight computation.

Table C2. Stronger GNN Configurations (h=512)

Backbone (h=512h=512)Original Acc. (%)+NSR Acc. (%)
GCN75.05 ± 0.3684.95 ± 0.65
GraphSAGE84.90 ± 0.4489.79 ± 0.30

NSR still improves the stronger GraphSAGE baseline by 4.89 percentage points.

Table C3. GAT Null-Space Label Diagnostic

We extend the label-based null-space diagnostic in Appendix E to GAT and divide test nodes into ten quantile bins by diagnostic score.

BinOriginal GAT (%)+NSR (%)Gain (pp)
178.96 ± 1.6081.34 ± 1.642.38 ± 1.46
279.79 ± 1.9584.01 ± 2.084.22 ± 1.80
380.86 ± 1.7585.15 ± 0.974.29 ± 2.09
478.18 ± 1.8484.91 ± 1.306.73 ± 1.36
579.94 ± 1.8586.20 ± 0.586.26 ± 2.14
678.43 ± 1.7486.06 ± 1.377.63 ± 1.78
775.35 ± 1.7484.75 ± 1.069.40 ± 1.52
876.52 ± 1.7484.36 ± 1.827.85 ± 1.65
972.60 ± 1.4483.83 ± 1.3611.23 ± 1.19
1072.56 ± 1.8783.53 ± 1.1310.97 ± 1.45

As the diagnostic score increases, the original GAT's accuracy generally decreases while NSR-GAT remains relatively stable. Gains are 2.38 and 10.97 percentage points in the lowest and highest bins, respectively, consistent with the diagnostic trends for the other GNNs in the paper.


C. ADE20K: Input-Source and Integration-Pathway Ablations

Table C4. ToMe Ablations on ADE20K (mIoU)

Feature-2nd augments Feature-only with second-order statistics; NSR-2nd combines this enhanced feature pathway with Spatial Routing. MLP uses ordinary member-wise nonlinear compensation.

Variant1.8×2.5×3.4×3.8×
Original36.6031.4417.6712.44
MLP36.9835.4730.5929.40
Feature-only36.7733.1520.5316.82
Feature-2nd36.8134.0620.6417.33
Spatial-only37.1135.3229.8828.94
RawSource37.3335.6532.0730.45
NSR-2nd37.2236.8133.9733.10
Full NSR37.4137.0734.1133.74

At 3.4×/3.8× compression, Full NSR exceeds RawSource by 2.04/3.29 mIoU points, MLP by 3.52/4.34 points, and Spatial-only by 4.23/4.80 points. Feature-2nd outperforms Feature-only at all four operating points, yet NSR-2nd does not outperform Full NSR, further illustrating the more effective synergy between the two information-integration pathways in the current Full NSR framework.

We also add a Full-ViT+Skip control on ADE20K. Without Token Merging, this control introduces an early-feature skip similar to Spatial Routing and forwards early token information to downstream prediction, testing the effect of an ordinary early skip alone. Full-ViT achieves 37.60 mIoU and Full-ViT+Skip 37.64, an increase of just 0.04. In contrast, NSR delivers larger improvements under strong compression, highlighting its value in compensating for member differences eliminated by Token Merging.


D. Larger Visual Backbone

Table C5. DeiT-Base/16 + FCN Results on PASCAL VOC

Compared with the DeiT-Tiny/16 backbone and linear head in the paper, this configuration increases both backbone and segmentation-head capacity.

MethodWPOriginal mIoU (%)+NSR mIoU (%)Original Params+NSR ParamsOriginal GFLOPs+NSR GFLOPs
Full-ViT1.0×74.58–90,525,717–18.489–
ToMe1.8×70.6572.8190,525,71792,711,06110.21310.377
2.5×53.9164.6490,525,71792,711,0617.4527.583
3.4×31.1851.3990,525,71792,355,0295.4135.518
3.8×28.4348.6790,525,71792,355,0294.9175.015
PiToMe1.8×70.1672.9190,525,71792,711,06110.26410.386
2.5×63.6367.3590,525,71792,711,0617.4117.522
3.4×49.9757.4190,525,71792,711,0615.4045.502
3.8×42.9751.8690,525,71792,711,0614.8724.964
MPM1.8×70.8572.9790,525,71791,464,94910.53710.557
2.4×64.1969.0690,525,71791,820,9817.7757.823
2.8×60.7963.3390,525,71792,355,0296.5806.660
3.0×58.2161.3090,525,71792,711,0616.2876.343

NSR improves mIoU in all 12 configurations. For example, ToMe at 3.4× improves from 31.18 to 51.39 mIoU, while GFLOPs increase from 5.413 to 5.518.


E. Measured Inference Efficiency

Table C6. DeiT-Base/16 + FCN: Latency, Throughput, and Peak Memory

Each pair is reported as Original / +NSR.

MethodWPLatency (ms/batch)Throughput (img/s)Peak Memory (MiB)
Full-ViT1.0×79.23 / –403.91 / –1339.57 / –
ToMe1.8×52.17 / 57.36613.38 / 557.881341.91 / 1349.42
2.5×43.41 / 48.24737.16 / 663.351340.10 / 1347.81
3.4×36.86 / 41.06868.15 / 779.351339.94 / 1346.35
3.8×34.18 / 37.24936.22 / 859.291339.92 / 1345.76
PiToMe1.8×52.42 / 57.67610.45 / 554.881344.91 / 1352.61
2.5×42.79 / 47.42747.84 / 674.821342.00 / 1350.38
3.4×36.73 / 40.27871.22 / 794.641340.56 / 1348.27
3.8×34.02 / 37.11940.62 / 862.301340.34 / 1347.52
MPM1.8×55.93 / 60.87572.14 / 525.711359.07 / 1366.91
2.4×47.86 / 52.31668.62 / 611.741358.23 / 1365.67
2.8×42.94 / 46.83745.23 / 683.321358.28 / 1365.12
3.0×39.19 / 43.62816.53 / 733.611358.31 / 1364.93

At ToMe 3.4×, NSR improves mIoU from 31.18 to 51.39; latency increases from 36.86 to 41.06 ms/batch, and peak memory from 1339.94 to 1346.35 MiB. Corresponding graph runtime measurements appear in Table C1.


F. Additional Tree-NeighborsMatch Controls

Following the original Alon & Yahav (ICLR 2021) task and training-fit evaluation settings, depth d uses d+1 message-passing layers, hidden dimension 32, and random seed 11. We report the highest training accuracy observed during training.

Table C7. Tree-NeighborsMatch: RawSource and Post-only

BackboneVariantd=2d=3d=4d=5d=6d=7d=8
GCNRawSource1.001.001.001.000.890.580.39
Post-only1.001.000.810.420.290.180.12
GINRawSource1.001.001.001.000.780.430.33
Post-only1.001.000.840.480.330.130.11
GraphSAGERawSource1.001.001.001.000.850.510.36
Post-only1.001.001.000.550.360.240.13

In Figure 3 of the paper, Full NSR achieves 100% maximum training accuracy for all three backbones at depths d=2–6. At d=6, RawSource reaches 89%, 78%, and 85% for GCN, GIN, and GraphSAGE, respectively.


G. Token Compression Trajectories and Nearly Matched Compute Budgets

Table C8. Layer-Wise Remaining Tokens for ToMe on VOC (including CLS)

The initial sequence contains 196 patch tokens and one CLS token, or 197 tokens in total.

Setting / Block01234567891011
3.4× (r=29r=29)1681391108152271485322
3.8× (r=33r=33)16413198653317953222

The two configurations follow different compression trajectories from early blocks onward; the roughly 25-token state does not occur immediately after block 0.

Table C9. ADE20K: Nearly Matched Total GFLOPs

ModelTotal GFLOPsVal mIoU (%)
ToMe-3.4×3.08517.67
ToMe-NSR-3.8×3.08233.74
PiToMe-3.4×3.07631.39
PiToMe-NSR-3.8×3.07134.17
ToMe-2.5×4.20231.44
ToMe-NSR-3.4×3.44334.11

At nearly equal total GFLOPs, ToMe-NSR and PiToMe-NSR improve over their corresponding original variants by 16.07 and 2.78 mIoU points. ToMe-NSR-3.4× also outperforms the original ToMe-2.5× at lower computational cost.


H. Summary of Revisions

In response to the reviewers' suggestions, we will consolidate two key groups of additional experiments in the revised appendix.

Group 1: Member-wise MLP controls. We add pre-aggregation MLP controls for GCN, GraphSAGE, and GIN, and a ToMe-MLP control on ADE20K, comparing ordinary member-wise nonlinear processing with the complete NSR framework.

Group 2: ADE20K input-source and integration-pathway ablations. We add comparisons among RawSource, Feature-only, Spatial-only, Full-ViT+Skip, and Full NSR to examine the additional value of explicit null-space separation and the complementarity of the two integration pathways.

We sincerely thank all reviewers again for their insightful analyses and constructive suggestions, which have helped us strengthen the experimental controls and more clearly present the contribution of the complete NSR framework.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.