When 95–99% of a multi-way array is missing, classical low-rank solvers often fail in ways that are hard to fix. These are methods that rebuild the array from a few small factors, such as a tensor train, which writes a high-order array as a chain of small three-way blocks. Under that much missingness they settle into poor local minima, they are sensitive to the chosen rank, and they leave whole regions, such as a missing row or a sparsely observed slice, reconstructed as noise. The usual responses are random restarts, careful rank tuning, or giving up on the classical solver and training a neural network to fill in values directly. This proposal takes a different route, borrowed from neural solvers for vehicle routing. A small learned policy looks at the current factorization and decides which parts of it to throw away and re-solve. A deterministic low-rank solver then does the actual re-solving. The policy only reads local, size-normalized statistics, such as how many entries a slice has observed and how badly it predicts held-out entries. It can therefore be trained on 32×32×32 tensors and run unchanged on tensors a thousand times larger.
The reason to split the work this way is a tension the two literatures expose. Methods that generalize across scale depend on locality: a decision depends only on a neighborhood, so it looks the same at size 50 or 5,000. Recovery under extreme sparsity depends on global low-rank structure: Bengua et al. argue that only ranks linking all modes at once can recover 95%-missing images and video. Our design keeps the global part non-learned (the low-rank solver) and makes the learned part local (where to restart). Each half then does the job it is good at. In two sentences: we learn a scale-free policy that tells a standard tensor-completion solver which blocks of its own solution to discard and recompute. Because that policy never predicts tensor values, it can be trained on small tensors and transferred zero-shot to large ones.
Core Claim
Under 95–99% missingness, most of the error left by a well-tuned low-rank solver sits in a small, identifiable set of badly fit index slices. Examples are the rows of a mode's factor that correspond to a sparsely observed pixel row, spectral band, or video frame. Which slices are badly fit can be predicted from features whose distribution does not change with tensor size. A policy trained to pick those slices for re-initialization and local re-solving, inside an annealing-style accept/reject loop, should beat two alternatives on large tensors at equal wall-clock time: running the same solver longer, and re-solving randomly chosen slices.
The claim is deliberately narrow. We do not claim a neural network reconstructs tensors better than low-rank models. We claim a learned search controller makes low-rank models more reliable, and that this controller transfers across scale.
Relation to Prior Work
The method is supplied by Neural Deconstruction Search. NDS trains a Transformer to choose which customers to remove from a vehicle-routing solution and lets a fixed greedy insertion heuristic rebuild the routes. Wrapped in simulated annealing, it generalizes from 500-node training instances to 2,000-node tests. We reuse that division of labor exactly. What we change is the object being ruined: continuous factor slices of a low-rank model instead of discrete route segments, with a least-squares re-solve in place of greedy insertion. BQ-NCO motivates the scale-invariance argument. It redefines the state as the remaining subproblem so that large instances shrink into the training distribution. We considered a quotiented "remaining unfilled region" formulation for completion and rejected it. Low-rank completion has no natural order in which the problem shrinks, because every observation constrains every factor at once. The ruin-and-recreate view avoids needing one.
Three lines of completion work constrain the design. Tensor-train methods (Bengua et al., Yuan et al., and STTO) and tensor-ring completion lift images into high-order tensors and optimize factors using only observed entries. STTO and the tensor-ring work also report sensitivity to rank and initialization near 99% missingness. They supply our "recreate" step and the failure mode we target. ATNN learns a column-orthogonal transform for one 3-mode tensor, with recovery guarantees. It is our strongest per-instance competitor on hyperspectral data. It must be re-optimized whenever the mode size changes, which is fine for a per-instance method, so we compare at matched compute rather than claim it cannot scale.
NTAN is the closest existing work. It applies attention along each tensor mode, so it is indifferent to mode length, meta-learns across heterogeneous tensors, and fits a closed-form linear head per target. It predicts values directly and was evaluated for cross-domain transfer, not for training small and testing large. Our policy predicts no values. If NTAN already transfers across scale, the case for our controller weakens, so we test NTAN zero-shot on the same scale ladder. We also reuse its mode-wise attention as the policy's backbone, because that is what makes the policy size-independent.
Research Program
The base solver is an alternating least-squares tensor-ring or tensor-train completion. Images and video are lifted by ket augmentation as in Bengua et al., and 3-mode tensors are left in native form. For mode $k$ and index $i$, the "slice" $G_k[:, i, :]$ is the part of the $k$-th factor that serves index $i$. Holding all other factors fixed, re-solving one slice is a small least-squares problem over the observed entries that touch index $i$. This makes slices the natural unit to ruin.
We split the observed entries into a fitting set $\Omega$ and a small held-out set $\Omega_h$. One step of the loop has three parts. The policy selects a set $S$ of slices across modes. Those slices are reset to random values and re-solved by least squares on $\Omega$. A few global sweeps follow. The candidate is then accepted or rejected by simulated annealing on the held-out error $$ E_h = \frac{\|P_{\Omega_h}(\hat{\mathcal{X}} - \mathcal{X})\|_F}{\|P_{\Omega_h}(\mathcal{X})\|_F}, $$ where $\hat{\mathcal{X}}$ is the current reconstruction, $\mathcal{X}$ the true tensor, and $P_{\Omega_h}$ zeroes every entry outside $\Omega_h$. Scoring on held-out entries matters at 1% observation: a fit judged on $\Omega$ alone would reward overfitting. The ruin action set may optionally include "raise the rank of the ring bond adjacent to mode $k$ by one." This addresses the rank-tuning open problem raised by ATNN and STTO, and we ablate it separately.
Each slice becomes one token with scale-free features. These are the fraction of its entries observed, its normalized residuals on $\Omega$ and $\Omega_h$, its factor norm relative to the mode median, the change in those quantities since the last ruin, and residual agreement with neighboring indices along the same mode. The policy applies mode-wise attention over these tokens, using linear attention or a $k$-nearest-neighbor restriction along each mode so that cost stays linear in mode size. It is trained with REINFORCE on the reduction in $E_h$ per unit of compute, as in NDS. Training uses small tensors: synthetic low-rank tensors of mode size 16–48 with random, row-structured, fiber-structured, and slice-structured missingness, plus small crops of training images and videos. A conceptual check runs before the main experiments. On small tensors where the true factors are known, we measure whether the slices the policy picks are the ones whose error is largest. If they are not, the method is a lucky perturbation scheme and should be reported as such.
Baselines
The naive reference point is the base solver alone: tensor-ring or tensor-train alternating least squares, given the full wall-clock budget, with rank chosen by held-out error from a small grid. A second, weaker reference is zero-filling followed by a dense method. Deep-Union Completion already shows zero-filling biases recovery, so it is reported only for orientation.
The strongest per-instance competitors are TMac-TT and ATNN. On the NYC video at 95% missing, Bengua et al. report an RSE of 0.072 for TMac-TT, against 0.185 for standard TMac. On WDC hyperspectral data at 95% missing, ATNN reports a PSNR of 38.06 dB, against 30.01 dB for fixed-transform TNN. For structured row-missingness on Lena, STTO reports 24.00 dB PSNR, with competitors around 10.5. STTO gives no PSNR at 99% random missingness, and the file has no reported result found on Lacuna for that setting. We rerun all three under our protocol: the same observed masks, the same held-out entries for rank and hyperparameter selection, the same per-instance tuning budget, and the same wall-clock limit on the same GPU. Beating them means lower RSE or higher PSNR at equal time on the large test tensors. It does not mean beating their published numbers under different masks.
The strongest learned competitor is NTAN, trained on the same small tensors and applied to large ones with its closed-form head refit per target. On Enose at 1% observed, NTAN reports an RMSE of 0.068 against 0.909 for CP decomposition (NTAN). The file has no reported result found on Lacuna for NTAN under scale transfer.
The ablations that isolate the key ingredient are random ruin and greedy-by-residual ruin. Random ruin re-solves uniformly chosen slices with the same count, recreate step, and annealing schedule. Greedy-by-residual ruin always picks the slices with the largest held-out residual. The learned policy must beat both at matched compute on the large tensors to justify being learned.
Why not just…?
Why not just run TMac-TT or ATNN longer, or with more restarts? This is the most serious threat. Per-instance solvers already work at any size, so cross-scale transfer only matters if the controller adds something. The reported sensitivity to rank and initialization in STTO and tensor-ring completion suggests restarts waste effort: they redo the well-fit majority of the factors to fix a few bad slices. That is a hypothesis, not evidence. We settle it with equal-compute curves of error against wall-clock time, comparing best-of-$R$ restarts to our loop. If restarts match us, we report that and drop the claim.
Why not just ruin random slices, or the highest-residual ones? If either matches the learned policy, the honest conclusion is "ruin-and-recreate helps tensor completion" without the learning. That is still useful but a smaller claim. The greedy heuristic is the dangerous one. We expect it to fail under structured missingness, where the residual is uninformative precisely in the unobserved rows and the useful signal is the observation pattern together with neighbor disagreement. We test this directly on row- and fiber-missing masks.
Why not just use NTAN, which is already indifferent to mode size? NTAN regresses values, so its errors at scale are errors in its learned prior. Our policy can be wrong about where to look without corrupting the low-rank fit, because annealing rejects bad moves. If NTAN zero-shot matches our accuracy on the large tensors, the local-controller argument loses its main motivation. We would then test whether NTAN's predictions make a better initialization for our loop.
Why not just tile the large tensor and complete small tiles? Tiling discards exactly the long-range fiber intersections that Bengua et al. argue are needed at 95% missingness. We include tiled TMac-TT as a baseline to show this cost concretely.
Proposed Experiments
The scale ladder trains at mode size 32 and tests at 64, 128, 256, 512, and 1,024 on synthetic tensor-ring tensors at 95% and 99% missingness, under four mask types. We report RSE, the gap to an oracle (best of 50 restarts with the true rank), and success rate over seeds. Real-data transfer uses the NYC video (RSE at 95% missing), WDC and paviaU hyperspectral cubes (PSNR at 95% missing), Lena under row-missing and 99% random masks, and Enose at 1% observed, with the policy trained only on small synthetic tensors and crops. Across all of these we also report wall-clock time and how often a tuned rank had to be supplied.
The decisive check is the comparison of learned ruin against random and greedy ruin on the 1,024-size tensors and the full real datasets, at equal compute. The idea survives if the learned policy shows a consistent margin there, and if that margin holds or grows from training size to test size rather than shrinking. A second decisive check is whether the policy's chosen slices concentrate on the truly worst-fit slices on synthetic tensors with known factors. A third is whether the rank-increase action removes the need for rank tuning without losing accuracy against held-out-tuned TMac-TT.
References
- Efficient Tensor Completion for Color Image and Video Recovery: Low-Rank Tensor Train
- Neural Deconstruction Search for Vehicle Routing Problems
- BQ-NCO: Bisimulation Quotienting for Efficient Neural Combinatorial Optimization
- Completion of High Order Tensor Data with Missing Entries via Tensor-train Decomposition
- High-Order Tensor Completion for Data Recovery via Sparse Tensor-Train Optimization
- Provable tensor ring completion
- Fast Guaranteed Tensor Recovery with Adaptive Tensor Nuclear Norm
- Meta-learning from Heterogeneous Tensors for Few-shot Tensor Completion
- Deep-Union Completion