🤖 machine learning

K-Inverse-RFM: A Modified RFM that Bridges the Gap to Neural Networks for Data-Corrupted Mathematical Tasks

This paper introduces K-Inverse-RFM, a modified Recursive Feature Machine that employs a novel label transformation to overcome performance limitations in data-corrupted mathematical tasks, enabling it to match or even surpass Feedforward Neural Networks.

Original authors: Gil Pasternak

Published 2026-07-02

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Gil Pasternak

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: Two Ways to Learn Math

Imagine you are trying to teach a computer to solve math problems, specifically things like modular arithmetic (think of a clock where numbers wrap around, like 14 o'clock being 2 o'clock).

There are two main "students" in this story:

The Neural Network (The Intuitive Artist): This is the modern, powerful AI everyone talks about. It learns by adjusting millions of tiny internal knobs. It is great at figuring out patterns, even when the data is messy, noisy, or unbalanced.
The RFM (The Rule-Follower): This is a newer, simpler model called a Recursive Feature Machine. It tries to mimic the Neural Network but uses a different, more mathematical approach. It's like a student who tries to learn by looking at the "average slope" of the data to figure out what's important.

The Problem: In perfect, clean math problems, both students get an A+. But as soon as you introduce real-world messiness—like noise (wrong answers in the textbook), imbalance (too many examples of one type and too few of another), or weird encoding (writing numbers in a secret code)—the Rule-Follower (RFM) starts to fail miserably. The Intuitive Artist (Neural Network) keeps performing well.

The author of this paper asked: Why does the Rule-Follower struggle with messy data, and can we fix it without turning it into a complex Neural Network?

The Investigation: Why Did the Rule-Follower Fail?

The author ran three main experiments to see where the RFM broke down:

1. The "Noisy Textbook" Test (Label Noise)

The Scenario: Imagine a textbook where 30% of the answers are randomly wrong.
The Result: The Neural Network ignored the wrong answers and learned the right pattern. The RFM got confused by the noise and its performance crashed.
The Discovery: The author found that the RFM wasn't failing because it couldn't predict the answer; it was failing because it couldn't learn the right features (the right way to look at the data) when the data was noisy. It was like a student trying to learn algebra but getting distracted by scribbles on the page.

2. The "Unbalanced Class" Test (Imbalanced Data)

The Scenario: Imagine a dataset where 90% of the examples are "Apples" and only 10% are "Oranges."
The Result: The Neural Network learned to recognize both. The RFM got obsessed with "Apples" and completely forgot how to handle "Oranges." It overfitted to the majority group.
The Discovery: The RFM struggled to share what it learned about one group with another. It treated every class as a separate island.

3. The "Secret Code" Test (Complex Representation)

The Scenario: Instead of giving the model the number "5," you give it a code like "5 mod 3, 5 mod 5, 5 mod 7." This is a more efficient way to store numbers (Chinese Remainder Theorem), but it's harder to decode.
The Result: The Neural Network eventually figured out the code. The RFM struggled to decode the message and solve the math.
The Discovery: The RFM couldn't figure out how to translate this complex code into a useful feature on its own.

The Solution: The "K-Inverse-RFM"

The author realized the RFM's main weakness was how it handled the labels (the answers) and how it learned features. The standard RFM was too rigid.

To fix this, the author created a new version called the K-Inverse-RFM. Here is the analogy for how it works:

The Old Way (Standard RFM): Imagine the student is trying to memorize the textbook page by page. If the page is torn or has typos, they get stuck. They treat every question as totally separate.
The New Way (K-Inverse-RFM): The author gave the student a new strategy: "Look at the answers to figure out the questions."
- Instead of just looking at the input (the question) and guessing the output, the K-Inverse-RFM projects the answers back onto the features. It asks, "If I want to get this answer, what combination of features do I need?"
- It also uses a "moving average" to smooth out the learning process, so one bad example doesn't ruin the whole lesson.
- Crucially, it allows the model to share information between different classes (like Apples and Oranges) more effectively.

The Results: Did It Work?

Yes, and in some cases, it was even better than the Neural Network.

With Noisy Data: The K-Inverse-RFM bridged about 64% of the gap between the old RFM and the Neural Network. It became much more robust against wrong answers.
With Imbalanced Data: It stopped obsessing over the majority group. It learned to handle rare examples much better than the old RFM.
With Secret Codes (CRT): This was the surprise winner. In tasks where the data was encoded in the complex "Chinese Remainder Theorem" style, the K-Inverse-RFM actually beat the Neural Network. It learned the features so well that it solved the problem faster and more accurately.

The "Secret Sauce" Finding

One of the most interesting side discoveries in the paper is that the Neural Network's first layer of learning is actually the most important part.

The author took the features learned by the first layer of a Neural Network and fed them into a simple kernel (a mathematical tool). This simple tool performed better than the full, complex Neural Network.

Analogy: It's like taking the "rough draft" notes a genius student made in the first 10 minutes of class, and realizing those notes were actually better than the final essay the student wrote after 3 hours of overthinking.

Summary

The paper shows that the "Rule-Follower" (RFM) was failing not because it was stupid, but because it was too rigid when data got messy. By tweaking how it maps answers back to features (the K-Inverse method), the author created a model that is:

Smarter with messy data (noise and imbalance).
More efficient (it needs fewer unique examples to learn).
Sometimes stronger than the complex Neural Network, especially when dealing with complex data encodings.

The paper concludes that while the K-Inverse-RFM isn't perfect yet, it closes the gap significantly and proves that we don't always need massive, complex Neural Networks to solve difficult math problems; sometimes, a smarter, simpler approach works best.

Technical Summary: K-Inverse-RFM

Problem Statement

Recursive Feature Machines (RFMs) are a class of kernel-based models that utilize the Average Gradient Outer Product (AGOP) to learn features, theoretically bridging the gap between classical kernel methods and Feedforward Neural Networks (FNNs). While RFMs have demonstrated the ability to replicate neural network dynamics and achieve state-of-the-art performance on clean tabular data and specific mathematical tasks (such as modular arithmetic), this thesis identifies a significant performance gap between RFMs and FNNs when data is corrupted.

Specifically, the author observes that RFMs degrade significantly compared to FNNs in three distinct scenarios:

Label Noise: RFMs fail to scale robustly as training label noise increases, whereas FNNs maintain high accuracy.
Imbalanced Data: RFMs suffer from overfitting when input or output distributions are skewed (e.g., via resampling or systematic exclusion of specific data subsets), while FNNs remain relatively stable.
Complex Representations: When inputs are encoded using complex schemes like the Chinese Remainder Theorem (CRT), RFMs struggle to decode the structure, often underperforming FNNs.

The core hypothesis is that while FNNs possess superior feature learning capabilities in these noisy or complex regimes, standard RFMs fail to learn the necessary feature structures (specifically the block-circulant features required for modular arithmetic) under these conditions.

Methodology: The K-Inverse-RFM

To address these limitations, the author proposes the K-Inverse-RFM, a modification of the standard RFM framework. The method introduces three primary algorithmic changes to the standard RFM training loop (which iterates between predictor training and AGOP-based feature learning):

Label Projection (K-Inverse): Instead of solving the standard kernel ridge regression equation, the method solves a modified equation where labels are projected onto the kernelized feature space. Specifically, the weight vector $\alpha$ is solved via:
$\alpha (K(X, X; M_t) + \lambda I) = K(X, X; M_t) d y$
Here, $d$ is a power parameter (typically set to $-1$, hence "K-Inverse"). This formulation maps labels to the space of kernelized features, effectively representing outputs as combinations of data points. This encourages the sharing of multiclass structure and allows features learned from one class to inform others, mitigating issues with class imbalance and noise.
Moving Average AGOP: To address instability and large gradient changes in the AGOP matrix (particularly in high-dimensional feature spaces), the feature learning step ( $M_{t+1}$ ) is reformulated as a moving average of the AGOP matrices over a window of $k$ steps. This average is weighted by the inverse of the training loss ( $1/l_i$ ), reducing the impact of poor updates.
Ridge Regularization: The kernel regression is reformulated as kernelized ridge regression with a high ridge term ( $\lambda$ ) to constrain update sizes and ensure training stability.

The power parameter $d$ is treated as a hyperparameter; while $d=-1$ is used for standard cases, the author notes that for denser feature spaces (like CRT encodings), smaller or positive powers (e.g., $d=0.4$ or $0.6$) can improve performance and stability.

Key Contributions

Empirical Investigation of RFM Limitations: The thesis provides a comprehensive analysis of where RFMs diverge from FNNs, specifically isolating label noise, data imbalance, and complex input representations as the primary causes of performance gaps in mathematical tasks.
Feature Learning Diagnosis: Through experiments using Laplace kernels trained on FNN first-layer features, the author demonstrates that the performance gap in noisy and imbalanced settings is primarily due to the RFM's inability to learn robust features (the AGOP mechanism), rather than the predictive head (kernel regression).
The K-Inverse-RFM Algorithm: The introduction of a modified RFM that incorporates label projection and stabilized feature averaging. This method successfully bridges the performance gap between RFMs and FNNs in corrupted data scenarios.
Sample Efficiency Analysis: The work reveals that RFM performance scales almost linearly with the number of unique training points rather than the total number of samples. The K-Inverse-RFM exhibits superior sample efficiency, achieving higher performance gains per unique sample due to its ability to share information across classes.

Results

The K-Inverse-RFM was evaluated against standard RFMs and FNNs across modular addition, multiplication, subtraction, division, and GCD tasks under various data conditions:

Label Noise: The K-Inverse-RFM bridges an average of 64% of the performance gap between standard RFMs and FNNs. It significantly outperforms standard RFMs (up to 39.3% higher test accuracy) and remains comparable to FNNs up to 14% label noise.
Imbalanced Data: In scenarios with skewed input weights (e.g., divisible-by-3 pairs), the K-Inverse-RFM shows a 53% improvement in test accuracy over standard RFMs. The results indicate that the K-Inverse-RFM is less sensitive to data distribution imbalances and more dependent on the sheer number of unique samples.
Systematic Exclusion: The K-Inverse-RFM outperforms standard RFMs across all tested exclusion types (e.g., excluding operands $>50$ or $<10$ ).
Complex Representations (CRT): In tasks using Chinese Remainder Theorem encodings, the K-Inverse-RFM not only closes the gap with FNNs but, in 5 out of 6 encoding-task pairs, surpasses both the standard RFM and the neural network. This suggests that with the correct feature learning mechanism, kernel-based models can outperform deep networks on specific structured tasks.

Significance and Claims

The paper claims that the K-Inverse-RFM represents a significant step toward unifying the efficiency of kernel methods with the robustness of neural networks. By modifying the RFM to better handle multiclass feature learning and stabilize AGOP updates, the model achieves:

Robustness: It performs reliably on noisy, imbalanced, and complexly represented data where standard RFMs fail.
Efficiency: It retains the computational efficiency of RFMs, capable of being trained on a CPU, unlike the GPU-heavy training of deep FNNs.
Superiority in Specific Regimes: In certain structured tasks (specifically CRT-encoded modular arithmetic), the K-Inverse-RFM can outperform deep neural networks, suggesting that the "gap" between kernel methods and neural networks is not inherent but rather a result of suboptimal feature learning mechanisms in the former.

The author modestly concludes that while the K-Inverse-RFM narrows the gap significantly, it does not eliminate it entirely in all scenarios. Future work is suggested to explore extending these findings to non-mathematical domains (NLP, Computer Vision) and investigating the behavior of Transformers, as the current study is limited to Feedforward Neural Networks.