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

1 Introduction

• Inputs mapped to the same representation may still require different task outputs, so operator-induced indistinguishability need not match task requirements.When the targets agree, ignoring the input differences is appropriate; the mismatch arises when the task requires distinctions the mapping removes.Source: §1 · p. 1
• For a fixed linear operator, its null space exactly characterizes invisible input variations; with input-dependent groups or weights, the characterization is conditional on the current forward pass.Graph aggregation and weighted token merging are examples of this setting [Kipf and Welling 2016, Bolya et al. 2023].Source: §1 · pp. 1–2
• NSR extracts null-space components from pre-mapping representations and uses task-supervised encoding, member-wise gating, and application-specific integration while preserving the original aggregation or merging rule.The paper frames this as a pathway for exploiting distinctions invisible in the original operator’s output.Source: §1 · pp. 2–3
• NSR improves mIoU over corresponding compressed baselines in 34 of 36 token-merging configurations and reaches 100% Tree-NeighborsMatch training accuracy at depths d=2–6 across three backbones.The reported evidence also includes gains on heterophilic node classification and molecular graph regression.Source: §1 · p. 3

Representation invariance and null-space methods

• NSR retains a non-injective mapping rather than making it invertible, extracting candidate complementary signals from accessible pre-mapping representations for a separate task-supervised branch.This differs from invertibility-oriented approaches such as i-RevNet [Jacobsen et al., 2018b] and LiftPool [Zhao and Snoek, 2021], and from null-space networks for inverse problems [Schwab et al., 2019].Source: §2 · p. 3

Graph aggregation and residual connections

• Unlike aggregation and cross-layer residual approaches, NSR uses the current local aggregation operator’s null space to extract operator-invisible member residuals for node updates.The related work contrasts this with GCN, GraphSAGE, and GIN aggregation [Kipf and Welling, 2016; Hamilton et al., 2017], and with Jumping Knowledge [Xu et al., 2018] and GCNII [Chen et al., 2020].Source: §2 · p. 3

Token merging in vision transformers

• Copy-based unmerging restores token count and spatial arrangement but not member feature differences; NSR targets those differences while preserving token-selection, matching, and weight-computation rules.The related-work passage describes ToMe [Bolya et al., 2023], PiToMe [Tran et al., 2024], ALGM [Norouzi et al., 2024], DTEM [Lee and Hong, 2024], and MPM [Ravé et al., 2026].Source: §2 · p. 3

3.1 Operator-Induced Indistinguishability and Task Relevance

• Inputs with the same mapped representation are indistinguishable to later computations using only that representation, which matters when their required task outputs differ.The section focuses on linear mappings and operations that become linear once current groups and weights are fixed.Source: §3.1 · p. 4

3.2 Null-Space Complementarity

• With a lift U satisfying AUA = A, NSR defines Z = (I_n − UA)X, whose features lie in ker(A) and which together with Y = AX determines X.This exposes operator-invisible member differences; for input-dependent groups or weights, the null-space statements apply to the operator realized in the current forward pass.Source: §3.2 · p. 4, §3.1 · p. 4

3.3 Task-Supervised Complementary Pathway

• NSR encodes each member residual and applies a learnable member-dependent gate before application-specific aggregation or spatial routing under the downstream task loss.Shared linear processing alone preserves cancellation under the original operator, whereas member-dependent gating can change relative contributions.Source: §3.3 · p. 4

3.4 NSR for Graph Aggregation

• For graph aggregation, NSR extracts message variations invisible to the backbone’s current local aggregation and transforms gated residuals into node updates.The member set and coefficients follow the backbone’s aggregation rule; the output transformation and neighborhood-dependent scaling produce the residual update.Source: §3.4 · pp. 4–5

3.5 NSR for Token Merging

• For token merging, the feature path aggregates member codes with the original merge weights and decodes a correction into the merged token for subsequent backbone computation.The decoder maps the group code into token features, allowing within-group variations to affect later transformations.Source: §3.5 · p. 5
• The spatial path retains member codes and correspondences, routes codes to original patch positions, and decodes position-specific updates without adding a Transformer token sequence.Both token paths preserve the original selection, matching, weight-computation rules, and predefined merge schedule.Source: §3.5 · p. 5

4.1 Experimental Setup

• Segmentation compares ToMe, PiToMe, and MPM with NSR-augmented counterparts on Pascal VOC 2012, Cityscapes, and ADE20K using mIoU.Models use ImageNet-pretrained DeiT-Tiny/16 with a linear segmentation head.Source: §4.1 · p. 5
• Original–NSR comparisons use the same backbone, optimization settings, and training budget; segmentation pairs also share initialization, data ordering, and compression controls.The computation-reduction operating point compares Full-ViT GFLOPs with those of the original compressed baseline.Source: §4.1 · p. 6

4.2.2 Graph Aggregation

• The controlled graph task constructs a local mismatch by swapping distinct values between equal-coefficient sibling leaves: the parent aggregate stays unchanged while the correct answer changes.The graph experiments complement this controlled test with real-data heterophilic classification and graph-level regression.Source: §4.2.2 · pp. 6, 9
• All three NSR variants reach 100% training accuracy on Tree-NeighborsMatch at depths d = 2–6, and substantially outperform their original counterparts at d = 7, 8.The task tests whether GNNs fit long-range key–value associations; each plotted point is the highest training accuracy in a run.Source: §4.2.2 · p. 6, Figure 3 · p. 8
• NSR raises the reported metric in 13 of 15 heterophilic node-classification backbone–dataset combinations, with the largest gains on Roman-empire.Roman-empire accuracy gains are 10.85, 6.12, and 8.25 percentage points for GCN, GraphSAGE, and GIN, respectively.Source: §4.2.2 · p. 6, Table 2 · p. 7

4.2.1 Token Merging

• 34 of 36 configurations show higher mIoU with NSR than the corresponding compressed baseline, with gains generally larger under stronger compression.ToMe's maximum gains are 31.51 mIoU points on Pascal VOC and 20.83 on Cityscapes; on ADE20K, ToMe+NSR reaches 34.11 mIoU at 3.443 GFLOPs versus 31.44 at 4.202 GFLOPs for original ToMe.Source: §4.2.1 · p. 6, Table 1 · p. 7

4.2.2 Graph Aggregation

• A label-based null-space diagnostic is computed after training and is not used for training, hyperparameter selection, or model selection.Figure 4 bins test nodes by diagnostic score; mean accuracy generally declines across higher bins for original backbones, while NSR accuracy remains relatively stable and the gap widens.Source: §4.2.2 · pp. 7–8, Figure 4 · p. 8
• NSR lowers test MAE on ZINC for all three backbones, with absolute reductions of 0.1785, 0.0360, and 0.0542 for GCN, GIN, and GraphSAGE.This extends the graph evaluation to molecular graph-level regression.Source: §4.2.2 · p. 8, Table 3 · p. 9

5 Conclusion

• NSR combines null-space residual extraction, member-level encoding and gating, and application-specific integration in a task-supervised pathway that preserves original aggregation or merging rules.The null space of the realized linear operator supplies candidate information, and downstream supervision guides its use.Source: §5 · p. 9
• Experiments across graph aggregation and token merging demonstrate improvements across multiple models and configurations.The conclusion frames access to operator-invisible variations as a practical design principle for many-to-one neural computation.Source: §5 · p. 9

A Implementation and Experimental Details

• In both applications, NSR constructs member residuals using the current aggregation members and weights, then transforms them into task-adaptive updates through a learnable branch.Source: A Implementation and Experimental… · p. 11

A.1 Datasets, Baselines, and Experimental Protocols

• The protocols use official segmentation splits for Pascal VOC 2012, Cityscapes, and ADE20K, and compare ToMe, PiToMe, and MPM with NSR counterparts under a shared DeiT-Tiny/16 architecture.Models share initialization, data ordering, and compression-control configurations; the segmentation head and NSR parameters are trained jointly under segmentation supervision.Source: §A.1 · p. 11
• Graph evaluation covers five heterophilic node-classification datasets, Tree-NeighborsMatch on binary trees of depths 2–8, and the 12,000-graph ZINC subset.Node classification uses ten official splits; Tree-NeighborsMatch reports the highest training accuracy from a single run per depth, while ZINC test MAE is averaged over ten seeds.Source: §A.1 · pp. 12–13
• Token-merging operating points range from mild to aggressive compression, and each method adjusts its native controls while retaining its matching and merging rules.Original–NSR pairs use the same compression-control configuration; NSR's additional computation is reported separately.Source: §A.1 · p. 13

A.2 Token-Merging Implementation

• For each token merge group, NSR extracts each member's residual relative to the weighted merged representation; singleton groups produce no residual update.A shared branch architecture encodes and gates member residuals; feature updates are added to merged tokens, while spatial codes are accumulated and decoded into position-specific updates.Source: §A.2 · pp. 13–14
• Token feature and spatial decoders are zero-initialized, so with identical shared parameters the augmented model initially preserves its corresponding merging baseline.The original token selection, matching, weighting, and predefined compression configurations remain unchanged.Source: §A.2 · p. 14

A.3 Graph-Aggregation Implementation

• Each graph message-passing layer has a separate NSR branch that projects member messages onto the null space of the current aggregation operator.The member set and coefficients follow the backbone; gated residuals are summed by destination node, decoded into a correction, and added to the baseline layer update.Source: §A.3 · pp. 14–15

B Supplementary Derivations for NSR

• For each computation event, input-dependent groups or weights are held fixed so the construction applies to the realized linear operator.Source: B Supplementary Derivations for NSR · p. 15

B.1 Null-Space Projection Properties

• P = I_n − UA is a projection onto ker(A), but it is not necessarily an orthogonal projection.Source: §B.1 · p. 15

B.2 Specialization to Graph Aggregation and Token Merging

• Graph aggregation lifts along the aggregation coefficient vector, and the resulting lift satisfies the condition for the null-space projection.Source: §B.2 · pp. 15–16
• Figure 5 plots relative residual magnitude across compression settings, with means across merging blocks and shaded regions showing ±1 standard deviation.Source: Figure 5 · p. 16
• Token merging uses a copy-based lift; its residual is the difference between member representations and the copied merged representation, even with nonuniform normalized weights.Source: §B.2 · p. 16

• For each realized token-merging operation, the check compares AZ against zero for the residual Z and measures residual magnitude relative to input representations X.Source: C Numerical Verification of NSR for… · p. 16
• Relative residual magnitude generally rises with stronger compression for ToMe and PiToMe, while MPM varies more mildly and is occasionally non-monotonic.Source: C Numerical Verification of NSR for… · p. 16
• 1.76 × 10^-6 is the overall maximum observed null-space violation; across methods and datasets, violations are on the order of 10^-6 or below.Source: C Numerical Verification of NSR for… · p. 16, Table 7 · p. 17

• NSR parameter increases range from 3.56%–10.23% on PASCAL VOC, 1.78%–9.61% on Cityscapes, and 4.25%–9.90% on ADE20K.Source: D Additional Performance and Parameter… · p. 17
• 35 of 36 evaluated settings show higher Pixel Acc. with NSR than with the corresponding compressed baseline, with larger observed recovery under stronger compression.Source: D Additional Performance and Parameter… · p. 17
• At 3.4× on PASCAL VOC, ToMe gains 31.51 mIoU points and closes 67.7% of the Full-ViT gap; at 1.8× on ADE20K, PiToMe reaches 127.1% Gap Closure.Source: D Additional Performance and Parameter… · p. 17
• Gap Closure is sensitive to small Full-ViT–baseline gaps, so it should be interpreted alongside absolute mIoU values and gains.Source: D Additional Performance and Parameter… · p. 17

E Label-Based Null-Space Diagnostic: Definition and Supplementary Analysis

• The local score measures the normalized projection energy of member-label encodings in the null space of the realized aggregation operator.It diagnoses label encodings, not task-relevant information loss in hidden features.Source: E Label-Based Null-Space Diagnostic:… · pp. 17–18
• Node scores are weighted averages of local event scores in the unfolded computation tree, computed after training and excluded from training or model selection.Source: E Label-Based Null-Space Diagnostic:… · pp. 18–19
• Mean NSR accuracy gain shows an overall increase with diagnostic-score bin for all three backbones, despite local fluctuations.Figure 6 averages gains over ten official splits.Source: E Label-Based Null-Space Diagnostic:… · p. 19, Figure 6 · p. 19

F Operating-Point Construction

• Token-merging operating points target the Full-ViT-to-compressed-baseline GFLOPs ratio while keeping each method’s native compression controls and matching rules unchanged.Baseline and NSR counterparts share compression-control configurations; NSR does not compensate for its overhead by searching for more aggressive compression.Source: F Operating-Point Construction · pp. 19–20

F.1 ToMe Compression Configurations

• ToMe operating points search the planned per-layer merge count r, while actual merges follow native rules and can be capped by the remaining token count.Source: F Operating-Point Construction · pp. 19–20, §F.1 · p. 20, Table 9 · p. 20

F.2 PiToMe Compression Configurations

• PiToMe operating points search retention ratio q while preserving its energy-based token selection and preset margin and matching-mode schedules.Source: F Operating-Point Construction · p. 20, §F.2 · pp. 20–21, Table 10 · p. 21

F.3 MPM Compression Configurations

• At the strongest MPM targets, all 12 blocks serve as insertion points, so achieved compression is reported rather than treating the original targets as exact matches.On ADE20K, the 2.5× target yields 2.507× during calibration and 2.355× in final validation.Source: §F.3 · p. 21

F.4 Layer-wise Token Merging Distributions

• Stronger target compression shifts more token reduction to early layers for both ToMe and PiToMe, but their layer-wise merging patterns differ across the three datasets.ToMe’s initial merge counts are relatively stable before token limits tighten; PiToMe’s counts progressively decrease as the sequence shortens.Source: Figure 7 · p. 22, §F.4 · p. 22

G.1 Comparison with Post-Merge-Only Refinement

• Full NSR outperforms both the baseline and post-merge-only control in every reported setting, including 0.4982 mIoU versus 0.1831 for the 3.4× ToMe baseline.The post-merge-only control varies across settings, sometimes improving and sometimes reducing baseline performance.Source: Table 12 · p. 23, §G.1 · p. 23

G.2 Ablation of information-integration pathways within NSR

• Full NSR achieves the highest mIoU in 10 of 12 pathway settings; at MPM 2.4×, neither pathway alone exceeds the 0.5887 baseline, while Full NSR reaches 0.5974.At PiToMe 3.4× and 3.8×, joint integration raises mIoU from 0.5008 and 0.4810 with the spatial path alone to 0.5402 and 0.5066.Source: §G.2 · p. 23, Table 13 · p. 24

G.3 Ablation of the Input Source within NSR

• Full NSR exceeds RawSource in all 12 configurations, with gains ranging from 0.20 to 3.68 mIoU points; RawSource itself improves over baseline in 11.At PiToMe 3.4×, Full NSR achieves 0.5402 mIoU versus 0.5034 for RawSource.Source: Table 14 · p. 24, §G.3 · p. 24

G.4 Complementary Pathway and Input-Source Ablation for Graph Aggregation

• The controls share data splits, backbone settings, optimization, training budget, and validation-based selection; Post-aggregation-only lacks member inputs, while RawSource uses unprojected messages.Source: §G.4 · p. 25
• Across all three backbones, mean performance orders Base < Post-aggregation-only < RawSource < Full NSR; Full NSR exceeds the two controls by the reported margins.Its margins over Post-aggregation-only are 7.60, 3.71, and 6.24 percentage points for GCN, GraphSAGE, and GIN; over RawSource they are 3.69, 2.14, and 1.56 points, respectively.Source: Table 15 · p. 25, §G.4 · p. 25
• The graph branch has no spatial memory or write-back path, complementing the token-merging evidence for the same residual-processing design principle.Source: §G.4 · p. 25

H Heterophilic Dataset Statistics

• The five benchmark statistics cover graph structure, node attributes, and label-related metrics, with values taken from Platonov et al. [2023a].Source: Table 16 · p. 25, H Heterophilic Dataset Statistics · p. 25
• Roman-empire has relatively high Label Informativeness (LI), and NSR shows more pronounced performance gains on that dataset.Source: H Heterophilic Dataset Statistics · p. 25
• The Roman-empire observation is consistent with the paper’s discussion that task-relevant information may influence NSR’s performance benefits.Source: H Heterophilic Dataset Statistics · p. 25