Quadratic Training Data Scaling via Relational Comparisons

You are reading version 1 of this direction, frozen 2026-10-04. The latest version is version 2.

Version 1 of 298 papers143 conceptsfrozen 2026-10-04

In traditional supervised learning, the relationship between data and signal is linear: to get more information, you need more labeled examples. If you have 100 signatures, you have 100 data points to learn from. However, a growing body of research suggests that we can break this linear bottleneck by shifting our focus from individual samples to the relationships between samples.

By reframing tasks as pairwise comparisons or set-based interactions, researchers are achieving "combinatorial expansion"—turning a small pool of $N$ samples into a massive training set of $O(N^2)$ or even $O(2^N)$ instances. This approach is proving essential in fields where high-quality data is chronically scarce, from forensic document analysis to the alignment of large language models.

The Combinatorial Explosion of Training Signal

The core intuition behind this direction is simple: while an individual data point tells you what a class is, a pair of data points tells you how classes differ.

In Dissimilarity Representation for Handwritten Signature Verification, George S. Eskander and colleagues demonstrate that by modeling the "distance" between a questioned signature and a template, they can generate a quadratic number of training instances from a tiny set of references. This mimics forensic experts who don't just look at a signature in isolation, but constantly weigh it against known variations.

This quadratic scaling is a recurring theme. In the realm of Large Language Models, Hritik Bansal and Aditya Grover introduced Joint Preference Optimization (JPO). While standard alignment methods only compare two responses to the same prompt, JPO allows for comparisons across different prompts. This "comparing apples to oranges" approach allows existing datasets to be recycled into a much larger pool of preference signals without generating a single new model response.

From Absolute Scores to Relative Distances

Why is a relative comparison often more powerful than an absolute label? Humans are notoriously bad at assigning consistent numerical scores (like a "7.4" for a dive) but excellent at ranking (deciding "Dive A was better than Dive B").

This insight is central to Action Quality Assessment using Siamese Network-Based Deep Metric Learning. Instead of asking a model to regress a single score for a video, Hiteshi Jain and team use a Siamese network to compare a student's performance against an expert reference. By training on pairs, the model learns the features of improvement rather than just memorizing what a "good" video looks like.

Similarly, in speech enhancement, Jiahe Wang developed URGENT-PK, which uses a "Comparing Module" to determine which of two audio samples is perceptually superior. This pairwise approach achieves better generalization across unseen languages because it learns the fundamental characteristics of quality rather than the specific biases of a human-assigned Mean Opinion Score (MOS).

Regularization through Contextual Mixing

Relational learning does more than just increase the volume of data; it acts as a powerful form of implicit regularization. By forcing a model to look at two things at once, we prevent it from "cheating" by memorizing superficial patterns.

In 3D computer vision, Alexey Nekrasov 0001 and Francis Engelmann proposed Mix3D, which concatenates random pairs of 3D scenes. This creates "out-of-context" training samples that force the model to ignore global priors (like "chairs are usually in offices") and focus on local geometric structures. The combinatorial expansion of possible scene mixtures provides a variety of training scenarios that a linear dataset could never capture.

A similar logic applies to Mixing and Disentangling (MD). Chao Sun and colleagues train models to separate two mixed point clouds. This self-supervised task creates an $O(M^2)$ training pool and forces the encoder to capture deep geometric priors necessary to "unscramble" the shapes.

Scaling Beyond Pairs: Triplets and Sets

While pairwise comparisons provide a quadratic boost, the research is moving toward even higher-order interactions.

  • Triplets: Jianbing Shen and Xingping Dong use Triplet Loss in Siamese Networks for object tracking, pairing every positive instance with every negative instance in a batch to maximize the supervision signal.
  • Sets: Chongyang Tao and colleagues introduced SetAD, which treats anomaly detection as a set-level learning problem. By sampling data points into various combinations, they expose the model to the same anomaly in many different contextual configurations, achieving high performance with very few labeled examples.
  • Power Sets: In audio source separation, Luca A Lanzendörfer uses power set data augmentation to train on every possible combination of voices in a recording, exponentially increasing the effective size of the dataset.

Why It Works: The Relational Prior

The success of these methods suggests that the "structure" of a dataset—the web of similarities, differences, and rankings between points—is often more informative than the points themselves.

Whether it is Natasa Tagasovska using neighbor matching to learn property gradients in PropEn, or Tengfei Ma pairing slow and fast code solutions to optimize algorithms, the underlying mechanism is the same. By shifting from "what is this?" to "how does this relate to that?", we unlock a combinatorial wealth of training data hidden within even the smallest datasets.

Papers in this version

Showing 60 of 98 papers.

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 51 papers
  2. Version 1 · 2026-10-04 · 98 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_combinatorial_data_augmentation_0872c10c,
  title = {combinatorial data augmentation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/combinatorial-data-augmentation/rdr_0872c10ca6914bc09abf5a7527be5e68},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_quadratic_training_data_scaling_via_rela_0872c10c_v1,
  title = {Quadratic Training Data Scaling via Relational Comparisons},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/quadratic-training-data-scaling-via-relational-comparisons/rdr_0872c10ca6914bc09abf5a7527be5e68/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}