CAVA: Complementary-Label-Aware Data Valuation

Tan-Ha Mai; Hsuan-Tien Lin; Vu Nguyen

cs.LGOct 19, 2026

CAVA: Complementary-Label-Aware Data Valuation

Authors: Tan-Ha Mai, Hsuan-Tien Lin, Vu Nguyen

Organizations: National Taiwan University · Amazon

Abstract

Complementary-label learning (CLL) trains a classifier from labels that name a class an instance does not belong to. Such labels are cheap to collect from crowdworkers or vision-language models (VLMs), making them attractive for large-scale annotation. However, both sources can mistakenly assign the true class as the complementary label. Such annotation errors are particularly harmful in CLL because the model is explicitly trained to suppress the correct answer. Optimal transport (OT) data valuation identifies harmful samples by comparing training data with a clean validation set, but transferring it directly to CLL creates a semantic mismatch: label $c$ means not class $c$ in the training but class $c$ in the validation. We show that this makes the OT label groups noisy mixtures whose behavior depends on the noise rate. The transferred score is informative only at sufficiently high noise, becomes uninformative at the crossover rate $1/M$ for $M$ classes, and reverses below it, where practical CLL annotation typically operates. We propose CAVA, which introduces a complementary label cost and a label margin that isolates the contribution of each complementary label to the transport potential. The margin keeps a consistent direction across noise rates, detects diagonal noise with a parameter-free threshold of closed-form precision, and allows detected samples to be recycled as ordinary-label supervision. On synthetic and human-annotated benchmarks, CAVA separates diagonal noise almost perfectly where directly transferred OT valuation performs worse than random. With only a fraction of the clean validation data, it also improves every CLL objective we evaluate, showing that OT-based valuation becomes reliable once the semantics of complementary supervision are modeled explicitly.

Figures & tables

Figure 1: Overview of CAVA. The pool is split into tasks, and each task is matched to a clean validation set by entropic OT with the complementary label cost. Each sample is scored by its label margin; samples with a negative margin are flagged as diagonal noise and then removed or recycled.

Figure 2: From TW-LAVA to CAVA. Left : TW-LAVA compares noisy label groups with clean classes, so its label weight

\lambda_{y}\alpha(\eta)

changes sign at

\eta=1/M

and the noise switches sides (Theorem 1 ). Right : CAVA compares clean classes only, so the sign of its margin is fixed: negative exactly when the given label is the most likely class under the transport posterior (Theorem 2 ). Scores are measured on CIFAR-10 (

\eta=25\%

, top) and CLCIFAR-10 (bottom).

Figure 3: The label margin. The image looks like class A, so it is cheap to transport under label A and costly under B or C. The bars show

f_{i}(c)

, and the margin

s_{i}

compares the given label (solid bar) with the cheapest other label. Given A,

s_{i}<0

and the sample is flagged as diagonal noise; given B,

s_{i}>0

and the label is valid.

		Synthetic ( $\eta=25\%$ )			Real-world
Method	Selection	MNIST	CIFAR-10	CIFAR-20	CLCIFAR-10	CLCIFAR-20	CLMIN-10	CLMIN-20
(a) Selection only: SCL-NL on the retained pool, Eq. ( 3.13 )
No pruning	–	0.14 $\pm$ 0.09	1.19 $\pm$ 0.02	0.49 $\pm$ 0.10	42.36 $\pm$ 0.91	7.71 $\pm$ 0.08	14.89 $\pm$ 1.02	4.55 $\pm$ 1.18
TW-LAVA	Fixed $p$	98.21 $\pm$ 0.29	76.04 $\pm$ 0.25	14.43 $\pm$ 1.00	47.46 $\pm$ 0.17	6.90 $\pm$ 0.11	12.56 $\pm$ 0.84	4.28 $\pm$ 0.35
CAVA (ours)	Fixed $p$	99.20 $\pm$ 0.10	79.26 $\pm$ 0.25	17.70 $\pm$ 1.38	79.63 $\pm$ 0.33	10.78 $\pm$ 1.25	27.44 $\pm$ 2.69	10.39 $\pm$ 0.67
CAVA (ours)	Adaptive cut	99.47 $\pm$ 0.04	79.12 $\pm$ 0.13	12.54 $\pm$ 2.68	80.00 $\pm$ 0.59	10.27 $\pm$ 1.15	27.44 $\pm$ 1.84	9.56 $\pm$ 1.13

Table 1: Main results: test accuracy (%) with AutoAugment. All methods score the pool against the same

2{,}000

validation images (

20

per class on CLMIN), and accuracy is measured after the final epoch on the remaining test images. The fixed cut removes

p=25\%

of each task on the synthetic datasets and

5\%

(

3\%

on CLCIFAR-20) on the human-labeled ones; the adaptive cut removes every sample with

s_{i}\leq 0

and needs no ratio. Mean

\pm

std over three seeds; best per column and block in bold .

Method	Valuation scope	Label cost	Score
LAVA [ 16 ]	full set ( $\leq$ 20K)	noisy-group	calibrated
TW-LAVA	task-wise, all data	noisy-group	calibrated
CAVA (ours)	task-wise, all data	complementary	label margin

Table 2: The three OT valuation methods compared in this paper. TW-LAVA differs from LAVA only in the task-wise decomposition; CAVA differs from TW-LAVA only in the label cost and the score.

Figure 4: Real-world complementary labels. (a) Score distributions: under TW-LAVA (top), annotation errors overlap with valid labels and sit on the wrong side; under CAVA (bottom), they separate on the low side. (b) Test accuracy of TW-LAVA and CAVA at the fixed cut of Table 1 (

5\%

on CLCIFAR-10,

3\%

on CLCIFAR-20) and of CAVA with the adaptive cut, mean of three seeds; all use the same

2{,}000

validation images.

Figure 5: Scale and the value of clean labels. (a) CIFAR-10-1M (

\eta=25\%

, SCL-NL): test accuracy after every epoch against time (valuation plus training, measured on one dedicated GPU), each method at its best cut (CAVA

p=25\%

, TW-LAVA

p=35\%

), for the 20-epoch and the 200-epoch schedule. Shaded: the valuation of TW-LAVA, so its training starts only after

2.5

hours (dashed line); CAVA needs about 4 minutes. All cuts are in Table 23 . (b) Supervised CE trained from scratch on

n

clean labels (three seeds) against CAVA, which uses

2{,}000

clean labels only as its validation set (

\eta=25\%

); CAVA uses the supervised embedder of the main tables, and results on other fixed representations are in Table 21 .

Figure 6: Small noise ratios. Final-epoch test accuracy (held-out test images) of SCL-NL on the retained pool against the pruning ratio

p

, on CIFAR-10 with small diagonal-noise ratios

\eta

; CAVA, TW-LAVA, and no pruning are means over three seeds, the other baselines single runs (seed 1126); same validation set for all methods; TW-LAVA keeps its original OT settings here (Appendix C.2 ). Each baseline is used as published, keeping its highest-valued or lowest-loss samples. The dashed line trains on the full pool.

Figure 7: Beyond CIFAR. Test accuracy with recycling (CE+SCL-NL) on FOOD15 (Food-101 [ 1 ] ), RESISC45-20 (NWPU-RESISC45 [ 2 ] ), and Places365-10 (Places365 [ 41 ] ) with synthetic diagonal noise; protocol of Table 1 , fixed cut

p=\eta

, seed 1126. All rows, including selection only, are in Table 18 .

Appendix figures & tables34 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 8: Complementary-label noise in CLL. When the complementary label coincides with the true label, i.e., $\bar{y}_{i}=y_{i}$ , the empirical transition matrix contains diagonal mass, creating contradictory exclusion constraints.

Symbol	Meaning
$\mathcal{X},\ \mathcal{Y}=\{1,\ldots,M\}$	Input space and label space of $M$ classes
$\bar{\mathcal{D}}=\{(\mathbf{x}_{i},\bar{y}_{i})\}_{i=1}^{N}$ , $y_{i}$	Pool with given labels, and the unobserved true labels
$\mathcal{N}=\{i:\bar{y}_{i}=y_{i}\}$ , $\eta=\mathbb{P}(\bar{y}=y)$	Diagonal-noise set and noise rate
$\mathcal{D}_{v}=\{(\mathbf{x}^{v}_{j},y^{v}_{j})\}_{j=1}^{N_{v}}$	Clean validation set with ordinary labels
$I_{t}$ , $T$	Task $t$ (a subset of the pool) and the number of tasks
$\phi$ , $C_{\mathrm{feat}}$	Fixed feature extractor and feature cost (Eq. ( 3.2 ))

Appendix

Table 3: Notation.

Figure 9: The direction flip, measured. Detector AUC against

\eta

on CIFAR-10; both scores use the same features,

\varepsilon_{\mathrm{OT}}=0.01

\lambda_{y}=1

, and the same

N_{v}=2{,}000

validation images. An AUC of

0.5

is chance. The noisy-group label cost is at chance exactly at the blind spot

\eta=1/M

(orange) predicted by Theorem 1 , and below chance for smaller

\eta

, where it ranks the noise in the wrong direction. The complementary label cost stays at the top for every

\eta

. Stars: human-labeled CLCIFAR-10 (

3.98\%

errors).

Metric	Definition	What it measures
CE Precision	$\|I^{\mathrm{rec}}\cap I^{\mathrm{noise}}\|\,/\,\|I^{\mathrm{rec}}\|$	recycled labels that are correct ordinary labels
CE Recall	$\|I^{\mathrm{rec}}\cap I^{\mathrm{noise}}\|\,/\,\|I^{\mathrm{noise}}\|$	diagonal noise recovered into the CE branch
F1	harmonic mean of the two	balance between precision and recall
CE Contam.	$1-\text{CE Precision}$	wrong ordinary labels in the CE branch
CLL Contam.	$\|I^{\mathrm{keep}}\cap I^{\mathrm{noise}}\|\,/\,\|I^{\mathrm{keep}}\|$	diagonal noise left in the complementary-label branch

Appendix

Table 4: Branch-quality metrics. Higher is better for precision, recall, and F1; lower is better for the two contamination rates.

Figure 10: Detection of diagonal noise. Detection AUC of each score in its natural direction; the synthetic datasets are shown at

\eta=5\%

and

15\%

, around the crossover

1/M

(

10\%

for CIFAR-10,

5\%

for CIFAR-20). The gray dashed line marks chance (

0.5

): a bar below it ranks the noise above valid data, and bars with an AUC near

0

show their value.

	CIFAR-10			CIFAR-20			CLCIFAR-10	CLCIFAR-20
Noise rate $\eta$	$25\%$	$15\%$	$5\%$	$25\%$	$15\%$	$5\%$	$3.98\%$	$2.32\%$
KNN-Shapley	0.000	0.000	0.000	0.002	0.003	0.005	0.000	0.004
Data-OOB	0.000	0.001	1.000	0.002	0.006	0.506	0.965	0.869
Small-loss	0.217	0.338	0.614	0.313	0.354	0.509	0.787	0.603
TW-LAVA	0.995	0.906	0.041	0.940	0.852	0.447	0.072	0.156
CAVA (ours)	1.000	1.000	1.000	0.997	0.998	0.999	1.000	0.999

Appendix

Table 5: Detection AUC of diagonal noise in the natural direction of each score (valid samples high;

0.5

is chance, values near

0

rank the noise as the most valuable data). Same pool and tasks for every method (seed

1126

		CAVA (ours)
Features	Dataset	AUC	adaptive cut P / R	$w=0$	TW-LAVA
CLIP	MNIST	0.990	96.7 / 88.5	–	0.771
	CIFAR-10	0.994	96.6 / 88.1	0.992	0.773
	CIFAR-20	0.971	94.5 / 66.3	0.969	0.711
	CLCIFAR-10	0.996	87.1 / 86.4	0.995	0.758
	CLCIFAR-20	0.981	75.4 / 59.6	0.976	0.621

Appendix

Table 6: Detection of diagonal noise on two representations that have never seen a label of the pool (seed

1126

, all five tasks). AUC treats valid samples as positive; “adaptive cut” gives the precision and recall of

\{s_{i}\leq 0\}

, and “

w=0

” is the CAVA margin without the validation potential. The supervised embedder of the main tables is shown for reference; “–”: not run.

		Noisy-group cost		Complementary cost
Dataset	$\eta$	calibrated (TW-LAVA)	margin	calibrated	margin (CAVA)
CIFAR-10	2%	0.342	0.041	0.983	0.995
	5%	0.400	0.063	0.981	0.995
	10%	0.503	0.508	0.979	0.994
	15%	0.610	0.952	0.977	0.994
	25%	0.773	0.982	0.974	0.994

Appendix

Table 7: Detection AUC of the four combinations of label cost and score on CLIP features (seed

1126

N_{v}=2{,}000

) against the noise rate; the crossover is

\eta=1/M

. The supervised embedder gives the same pattern (Figure 9 ).

Dataset	$\hat{e}$	$\hat{\eta}$	$\eta$	$\hat{\pi}$ (%)	measured (%)	recall (%)
MNIST	0.093	0.244	0.250	96.6	96.7	88.5
CIFAR-10	0.107	0.245	0.250	96.1	96.6	88.1
CIFAR-20	0.304	0.234	0.250	93.0	94.5	66.3
CLCIFAR-10	0.104	0.032	0.040	71.7	87.1	86.4
CLCIFAR-20	0.285	0.005	0.023	18.6	75.4	59.6
CLMIN-10	0.248	0.026	0.048	42.4	73.0	70.8

Appendix

Table 8: Estimating the precision of the adaptive cut without true labels (CLIP features, seed

1126

): leave-one-out error

\hat{e}

of the posterior classifier, estimated noise rate

\hat{\eta}

, and estimated precision

\hat{\pi}

(Eq. ( 3.15 )), next to the measured precision and recall.

			MNIST	CIFAR-10	CIFAR-20	CLCIFAR-10	CLCIFAR-20	CLMIN-10	CLMIN-20
(a) Selection only: SCL-NL on the retained pool
CLIP	TW-LAVA	Fixed $p$	26.25 $\pm$ 1.31	8.41 $\pm$ 1.86	3.10 $\pm$ 0.31	42.79 $\pm$ 1.79	7.69 $\pm$ 0.08	15.22 $\pm$ 2.17	4.50 $\pm$ 0.17
CLIP	CAVA (ours)	Fixed $p$	90.59 $\pm$ 0.21	74.11 $\pm$ 0.32	12.05 $\pm$ 1.05	79.06 $\pm$ 0.67	10.64 $\pm$ 0.89	27.11 $\pm$ 1.90	10.66 $\pm$ 0.76
CLIP	CAVA (ours)	Adaptive cut	84.58 $\pm$ 0.35	64.19 $\pm$ 3.36	7.01 $\pm$ 1.74	77.94 $\pm$ 0.43	8.48 $\pm$ 0.11	25.11 $\pm$ 4.43	7.83 $\pm$ 2.92
validation only	TW-LAVA	Fixed $p$	97.91 $\pm$ 0.10	29.90 $\pm$ 2.29	2.71 $\pm$ 0.12	43.43 $\pm$ 0.72	7.68 $\pm$ 0.15	16.22 $\pm$ 3.02	4.39 $\pm$ 0.59
validation only	CAVA (ours)	Fixed $p$	98.83 $\pm$ 0.06	66.25 $\pm$ 0.31	18.57 $\pm$ 1.40	73.33 $\pm$ 0.08	10.41 $\pm$ 1.77	21.56 $\pm$ 2.52	12.83 $\pm$ 0.67

Appendix

Table 9: Test accuracy (%) of Table 1 on CLIP features and on the validation-only features (mean

\pm

std over seeds 1126, 42, 2023). Best per column, block and representation in bold .

Selection		CIFAR-10	CIFAR-20	CLCIFAR-10	CLCIFAR-20	CLMIN-10
(a) Selection only: SCL-NL on the retained pool
TW-LAVA	Fixed $p$	8.41 $\pm$ 1.86	3.10 $\pm$ 0.31	42.79 $\pm$ 1.79	7.69 $\pm$ 0.08	15.22 $\pm$ 2.17
CAVA (ours)	Fixed $p$	74.11 $\pm$ 0.32	12.05 $\pm$ 1.05	79.06 $\pm$ 0.67	10.64 $\pm$ 0.89	27.11 $\pm$ 1.90
CAVA (ours)	Adaptive cut	64.19 $\pm$ 3.36	7.01 $\pm$ 1.74	77.94 $\pm$ 0.43	8.48 $\pm$ 0.11	25.11 $\pm$ 4.43
CAVA, $w=0$	Fixed $p$	73.20 $\pm$ 0.06	13.98 $\pm$ 0.81	78.27 $\pm$ 0.37	8.75 $\pm$ 0.16	25.44 $\pm$ 2.14
CAVA, $w=0$	Adaptive cut	64.29 $\pm$ 0.65	8.77 $\pm$ 0.51	76.96 $\pm$ 0.88	9.39 $\pm$ 1.01	29.00 $\pm$ 1.76

Appendix

Table 10: Training on the selections of Table 6 with CLIP features (cuts of Table 1 ; mean

\pm

std over three seeds). “

w=0

” is the CAVA margin without the validation potential. Best per column and block in bold .

		CIFAR-10 ( $\eta=25\%$ )		CLCIFAR-10 ( $\eta=3.98\%$ )
Label cost	Score	SCL-NL	CE+SCL-NL	SCL-NL	CE+SCL-NL
noisy-group	calibrated (TW-LAVA)	8.41 $\pm$ 1.86	46.68 $\pm$ 0.58	42.79 $\pm$ 1.79	28.18 $\pm$ 2.10
noisy-group	margin	67.57 $\pm$ 1.31	85.46 $\pm$ 0.08	41.21 $\pm$ 4.00	31.08 $\pm$ 1.89
complementary	calibrated	58.79 $\pm$ 2.12	80.81 $\pm$ 0.32	71.42 $\pm$ 0.16	73.26 $\pm$ 0.49
complementary	margin (CAVA)	74.11 $\pm$ 0.32	87.91 $\pm$ 0.55	79.06 $\pm$ 0.67	80.59 $\pm$ 0.23

Appendix

Table 11: The two components of CAVA in training (CLIP features, fixed cut; mean

\pm

std over three seeds). Table 7 gives the detection AUC of the same four combinations on CIFAR-10. Best per column in bold .

$N_{v}$	50	100	200	500	2,000
CAVA (ours)	82.92 $\pm$ 0.17	84.36 $\pm$ 0.06	85.47 $\pm$ 0.10	86.61 $\pm$ 0.15	87.91 $\pm$ 0.55
CAVA, $w=0$	82.76 $\pm$ 0.21	83.74 $\pm$ 0.11	85.37 $\pm$ 0.41	86.08 $\pm$ 0.34	87.38 $\pm$ 0.44

Appendix

Table 12: Training with small validation sets (CLIP features, CIFAR-10, CE+SCL-NL, fixed cut

p=25\%

, mean

\pm

std over three seeds, final-epoch accuracy on the test images outside the validation set). Best per column in bold .

		MNIST			CIFAR-10			CIFAR-20
Method	Cut	CE Con.	CLL Con.	Acc.	CE Con.	CLL Con.	Acc.	CE Con.	CLL Con.	Acc.
TW-LAVA	$p{=}0.25$	1.24%	0.41%	99.53	9.84%	3.28%	86.34	24.34%	8.11%	64.10
	$p{=}0.35$	28.73%	0.09%	99.15	30.03%	0.78%	85.31	36.81%	4.44%	63.78
	$p{=}0.45$	44.54%	0.08%	99.20	44.99%	0.44%	84.13	47.70%	2.66%	61.87
CAVA (ours)	$p{=}0.25$	0.70%	0.23%	99.57	0.54%	0.18%	92.45	4.44%	1.48%	76.45
	$p{=}0.35$	28.57%	0.00%	98.47	28.57%	0.00%	85.18	28.69%	0.06%	70.44

Appendix

Table 13: Detector quality and branch composition across datasets under the identical synthetic protocol (

\eta=25\%

, AutoAug, combined CE+SCL-NL loss), for the baseline TW-LAVA and for CAVA with the same feature extractor. The detection AUC is

0.9994

0.9833

0.9087

for TW-LAVA and

1.0000

1.0000

0.9971

for CAVA on MNIST, CIFAR-10, CIFAR-20. CE Contam. denotes the fraction of the recycled CE branch that consists of valid complementary samples

(\bar{y}_{i}\neq y_{i})

, which become false-positive ordinary labels when recycled. CLL Contam. denotes the fraction of the retained complementary-label pool that still consists of diagonal-noise samples

(\bar{y}_{i}=y_{i})

. Accuracy denotes the CE+SCL-NL test accuracy: a single run (seed 1126) for TW-LAVA, which uses all 10,000 test images as the validation set, and the mean over seeds 1126, 42, and 2023 for CAVA, which uses a fixed validation set of 2,000 test images the selection statistics are from seed 1126. For

p>\eta

the CE branch necessarily contains valid samples, so its contamination is at least

1-\eta/p

for any detector.

	Branch Composition			Combined	CLL-only
Setting	CLL Size	CLL Contam.	CE Contam.	CE+SCL-NL	SCL-NL	FWD
TW-LAVA (noisy-group label cost)
Static $p{=}0.25$	45,000	0.41%	1.24%	99.53	99.32	99.22
Static $p{=}0.35$	39,000	0.09%	28.73%	99.15	96.39	98.14
Static $p{=}0.45$	33,000	0.08%	44.54%	99.20	55.90	88.99
CAVA (ours; complementary label cost, label margin)

Appendix

Table 14: MNIST ablation under the synthetic diagonal-noise protocol with noise ratio

\eta=25\%

and AutoAug. CLL Contam. denotes the fraction of the retained complementary-label pool that still consists of diagonal-noise samples

(\bar{y}_{i}=y_{i})

. CE Contam. denotes the fraction of the recycled CE branch that consists of valid complementary samples

(\bar{y}_{i}\neq y_{i})

, for which treating

\bar{y}_{i}

as an ordinary label is incorrect. FWD uses the transition matrix computed from the synthetic corruption record, which includes the diagonal. The upper block is the baseline TW-LAVA and the lower block is CAVA with the same feature extractor. Static

p

denotes the fixed cut. For CAVA, the adaptive cut

s_{i}\leq 0

needs no ratio ( ∗ : seed 1126). TW-LAVA entries are single runs (seed 1126) that use all 10,000 test images as the validation set; CAVA entries are means over seeds 1126, 42, and 2023 with a fixed validation set of 2,000 test images (largest standard deviation 7.40, FWD at

p=0.35

; at most 1.20 elsewhere except FWD at

p=0.45

, 4.55), and its selection statistics are from seed 1126; the best accuracy in each column is in bold .

	Branch Composition			Combined	CLL-only
Setting	CLL Size	CLL Contam.	CE Contam.	CE+SCL-NL	SCL-NL	FWD
TW-LAVA (noisy-group label cost)
Static $p{=}0.25$	37,500	8.11%	24.34%	64.10	12.74	15.53
Static $p{=}0.35$	32,500	4.44%	36.81%	63.78	16.31	19.34
Static $p{=}0.45$	27,500	2.66%	47.70%	61.87	17.77	27.16
CAVA (ours; complementary label cost, label margin)

Appendix

Table 15: CIFAR-20 ablation under noise ratio

\eta=25\%

and AutoAug. Column semantics follow Table 14 . CLL Contam. denotes the fraction of the retained complementary-label pool that still consists of diagonal-noise samples

(\bar{y}_{i}=y_{i})

, while CE Contam. denotes the fraction of the recycled CE branch that consists of valid complementary samples

(\bar{y}_{i}\neq y_{i})

. The corruption record is used only for post-hoc evaluation of branch composition and is never used by either method during OT valuation, thresholding, pruning, recycling, or training. The upper block is the baseline TW-LAVA and the lower block is CAVA with the same feature extractor. Static

p

denotes the fixed cut. For CAVA, the adaptive cut

s_{i}\leq 0

Figure 11: OT valuation score distributions for diagonal-noise samples (

\bar{y}_{i}=y_{i}

) and valid complementary samples (

\bar{y}_{i}\neq y_{i}

) on MNIST, CIFAR-10, and CIFAR-20 under noise ratio

\eta=25\%

and seed 1126, with the same feature extractor in both rows (validation set: 10,000 test images for TW-LAVA, a fixed subset of 2,000 for CAVA). Top: TW-LAVA, the baseline with the noisy-group label cost. The two groups become less separable as the dataset becomes harder, with AUC decreasing from

0.9994

on MNIST to

0.9833

on CIFAR-10 and

0.9087

on CIFAR-20, which explains the increasing branch contamination reported in Table 13 . Bottom: CAVA with the complementary label cost and the label margin. Diagonal noise stays on the low side and the separation is close to complete on all three datasets (AUC

1.000

1.000

, and

0.998

Figure 12: Pruning-induced complementary-label bias (MNIST,

\eta=25\%

; pools of the original TW-LAVA protocol). Row-normalized transition matrices

P(\bar{Y}\mid Y)

of the CLL pool at

p{=}0.25

(left, near-uniform) and

p{=}0.45

(right);

\times

marks near-empty transitions (

<2\%

row mass). Aggressive pruning empties the transitions of visually confusable pairs, violating the uniform assumption of SCL-NL while the estimated

Q

of FWD absorbs the bias.

Figure 13: Pruning-induced complementary-label bias on CIFAR-20 (

\eta=25\%

), as in Figure 12 : row-normalized transitions

P(\bar{Y}\mid Y)

of the CLL pool at

p{=}0.25

(left) and

p{=}0.45

(right);

\times

marks near-empty transitions (

<2\%

row mass;

5/380

versus

38/380

cells).

Setting	CE branch			CLL pool		Combined		CLL-only
Setting	Size	Err. Prec.	Err. Rec.	Size	Contam.	CE+SCL-NL	CE+FWD	SCL-NL	FWD
No pruning $(p=0)$	–	–	–	50,000	3.98%	–	–	50.68	51.76
TW-LAVA (noisy-group label cost)
Static $p=0.03$	1,500	32.1%	24.2%	48,500	3.11%	46.78	46.19	53.25	59.38
Static $p=0.05$	2,500	26.7%	33.5%	47,500	2.79%	46.48	52.44	53.81	63.81
Static $p=0.08$	4,000	21.7%	43.7%	46,000	2.44%	43.65	46.78	50.68	67.29

Appendix

Table 16: CLCIFAR-10 ablation with real-world human complementary labels under AutoAug, for the baseline TW-LAVA and for CAVA with the same feature extractor. Static

p

denotes the fixed cut; for CAVA, the adaptive cut

s_{i}\leq 0

needs no ratio ( ∗ : seed 1126). TW-LAVA rows use the original TW-LAVA protocol with

10{,}000

validation images. Err. Prec. is the fraction of the recycled CE branch that consists of true annotation errors

(\bar{y}_{i}=y_{i})

, while Err. Rec. is the fraction of all annotation errors captured by the CE branch. CLL Contam. is the fraction of annotation errors remaining in the retained complementary-label pool. The annotation record is used only for post-hoc evaluation of branch composition and, where indicated, to construct known-

Q

FWD; neither method uses true labels for selection. TW-LAVA entries are single runs (seed 1126) that use all 10,000 test images as the validation set; CAVA entries are means over seeds 1126, 42, and 2023 with a fixed validation set of 2,000 test images (largest standard deviation 2.04), and its selection statistics are from seed 1126; the best accuracy in each column is in bold ; “–”: not applicable.

Setting	CE branch			CLL pool		Combined		CLL-only
Setting	Size	Err. Prec.	Err. Rec.	Size	Contam.	CE+SCL-NL	CE+FWD	SCL-NL	FWD
No pruning $(p=0)$	–	–	–	50,000	2.32%	–	–	8.98	23.73
TW-LAVA (noisy-group label cost)
Static $p=0.03$	1,500	7.8%	10.1%	48,500	2.15%	9.77	16.75	8.98	25.15
Static $p=0.05$	2,500	7.2%	15.5%	47,500	2.07%	9.08	14.10	9.08	24.95
Static $p=0.08$	4,000	7.7%	26.5%	46,000	1.85%	10.30	16.02	9.38	25.44

Appendix

Table 17: CLCIFAR-20 ablation with real-world human complementary labels under AutoAug, for the baseline TW-LAVA and for CAVA with the same feature extractor. Static

p

denotes the fixed cut; for CAVA, the adaptive cut

s_{i}\leq 0

needs no ratio ( ∗ : seed 1126). TW-LAVA rows use the original TW-LAVA protocol with

10{,}000

validation images. Err. Prec. is the fraction of the recycled CE branch that consists of true annotation errors

(\bar{y}_{i}=y_{i})

Q

FWD; neither method uses true labels for selection. TW-LAVA entries are single runs (seed 1126) that use all 10,000 test images as the validation set; CAVA entries are means over seeds 1126, 42, and 2023 with a fixed validation set of 2,000 test images (largest standard deviation 2.38), and its selection statistics are from seed 1126; the best accuracy in each column is in bold ; “–”: not applicable.

		FOOD15			RESISC45-20			Places365-10
Method	Selection	$5\%$	$15\%$	$25\%$	$5\%$	$15\%$	$25\%$	$5\%$	$15\%$	$25\%$
(a) Selection only: SCL-NL on the retained pool
No pruning	–	8.33	3.17	1.90	2.77	0.70	0.17	44.73	3.09	0.84
TW-LAVA	Fixed $p$	7.60	7.20	13.00	3.23	13.57	24.33	48.39	46.04	56.94
CAVA (ours)	Fixed $p$	22.50	21.10	18.90	23.17	23.43	24.70	75.08	74.03	73.90
CAVA (ours)	Adaptive cut	18.67	17.57	11.60	25.17	26.23	22.93	71.60	73.86	71.22

Appendix

Table 18: Test accuracy (%) on three further domains with synthetic diagonal noise (Figure 7 ; datasets in Appendix C.1 ). The validation set holds

50

test images per class (

200

for Places365-10), and the fixed cut is

p=\eta

. Seed 1126; best per column and block in bold .

Figure 14: Other noise ratios. CIFAR-10 test accuracy (%) of TW-LAVA and CAVA against the fixed cut

p\in\{15\%,25\%,35\%,45\%\}

at diagonal-noise ratios

\eta\in\{15\%,35\%,45\%\}

, above the crossover

1/M

, with the selection-only objective (SCL-NL solid, FWD dashed). Same feature extractor and validation set for both methods; AutoAugment; single runs (seed 1126) under the protocol of Table 1 , accuracy after the final epoch on the held-out test images. The dotted line marks

p=\eta

		TW-LAVA (noisy-group label cost)				CAVA (ours, complementary label cost)
$\eta$	Cut	CE+SCL-NL	CE+FWD	SCL-NL	FWD	CE+SCL-NL	CE+FWD	SCL-NL	FWD
2%	none	–	–	68.53 $\pm$ 2.28	69.30	–	–	68.53 $\pm$ 2.28	69.30
	$p=2\%$	48.38	29.57	67.22 $\pm$ 3.19	68.36	84.51	84.41	82.26 $\pm$ 0.25	82.16
	$p=5\%$	24.57	22.64	62.38 $\pm$ 1.80	66.03	77.31	75.89	82.64 $\pm$ 0.11	81.58
	$p=10\%$	9.95	16.25	46.66 $\pm$ 1.27	64.78	56.74	53.64	70.78 $\pm$ 1.37	67.61
	$p=15\%$	7.70	14.18	11.25 $\pm$ 1.30	31.19	42.59	40.69	47.84 $\pm$ 9.72	44.61

Appendix

Table 19: CIFAR-10 test accuracy (%) at small noise rates,

\eta\leq 1/M=10\%

, where the label cost of TW-LAVA is reversed or blind (Theorem 1 ). Both methods use the same fixed cuts; TW-LAVA keeps its original OT settings here (Appendix C.2 ). SCL-NL and No pruning: mean

\pm

std over three seeds; other objectives: seed 1126. Best per noise rate and objective in bold ; “–”: no recycled branch without pruning.

Figure 15: CAVA as a plug-in selection module across CLL objectives. Test accuracy (%) of six objectives without selection, with TW-LAVA, and with CAVA (selection only, no recycling; AutoAugment; seed 1126; final-epoch accuracy on the held-out test images, protocol of Table 1 ). All objectives use SGD as in the main experiments except OP, which uses Adam with learning rate

10^{-4}

as in its official implementation. On synthetic CIFAR-10 (

\eta=25\%

), CAVA uses the adaptive cut and TW-LAVA, which has no adaptive cut, the fixed cut

p=25\%

; on human-annotated CLCIFAR-10 (

\eta=3.98\%

), both methods use the fixed cut

p=5\%

. TW-LAVA and CAVA use the same

2{,}000

validation images.

Figure 16: Data augmentation. CIFAR-10 test accuracy (%) at

\eta=25\%

of TW-LAVA and CAVA against the fixed cut

p\in\{25\%,35\%,45\%\}

, and of CAVA with the adaptive cut

s_{i}\leq 0

(stars right of the gray line, with SCL-NL and CE+SCL-NL), under Cutout, AutoAugment, and RandAugment. Row (a) uses the selection-only objective in Eq. ( 3.13 ) with SCL-NL (solid, filled markers) and FWD (dashed, open markers); row (b) the recycling objective in Eq. ( 3.14 ) with CE+SCL-NL and CE+FWD. Same feature extractor, validation set and OT settings for both methods; single runs (seed 1126), accuracy after the final epoch on the held-out test images, protocol of Table 1 .

Setting	CE Precision	CE Recall	F1	$\mathbf{\|I^{\mathrm{rec}}\|}$	CE Contam.	CLL Contam.	Test Accuracy
Fixed cut $p=25\%$	95.37%	95.37%	95.37%	12,500	4.63%	1.54%	88.46%
Fixed cut $p=35\%$	71.12%	99.57%	82.97%	17,500	28.88%	0.17%	75.67%
Fixed cut $p=45\%$	55.46%	99.82%	71.30%	22,500	44.54%	0.08%	61.58%

Appendix

Table 20: Branch quality of recycling with TW-LAVA on synthetic CIFAR-10 (

\eta=25\%

, CE+SCL-NL, seed 1126). The metrics of Table 4 use the true labels for evaluation only; the last column is the test accuracy.

Representation	Method with $2{,}000$ clean labels	CIFAR-10	CIFAR-20
none	CE from scratch	71.52 $\pm$ 0.66	43.08 $\pm$ 2.24
supervised embedder	CAVA (ours), recycling	91.57 $\pm$ 0.14	75.34 $\pm$ 0.17
CLIP ViT-B/32	CAVA (ours), recycling	87.91 $\pm$ 0.55	67.37 $\pm$ 0.24
validation images only	CAVA (ours), recycling	75.22 $\pm$ 0.67	49.21 $\pm$ 0.85

Appendix

Table 21: What

2{,}000

clean labels are worth (

\eta=25\%

; mean

\pm

std over three seeds). CE from scratch trains on these labels alone. CAVA uses them only as its validation set, together with the

50{,}000

noisy complementary labels (CE+SCL-NL,

p=25\%

), on three fixed representations.

Dataset	Method	$N_{v}$	200	500	1,000	1,500	2,000
CIFAR-10	TW-LAVA	Detector AUC	0.98 $\pm$ 0.00	0.99 $\pm$ 0.00	0.99 $\pm$ 0.00	1.00 $\pm$ 0.00	1.00 $\pm$ 0.00
		CE-branch Prec. (%)	91.52 $\pm$ 0.58	92.99 $\pm$ 0.29	94.21 $\pm$ 0.23	95.27 $\pm$ 0.18	95.46 $\pm$ 0.09
		Accuracy (%)	84.94 $\pm$ 0.06	86.29 $\pm$ 0.31	87.82 $\pm$ 0.25	88.64 $\pm$ 0.07	88.75 $\pm$ 0.40
	CAVA (ours)	Detector AUC	1.00 $\pm$ 0.00	1.00 $\pm$ 0.00	1.00 $\pm$ 0.00	1.00 $\pm$ 0.00	1.00 $\pm$ 0.00
		CE-branch Prec. (%)	99.23 $\pm$ 0.11	99.29 $\pm$ 0.14	99.32 $\pm$ 0.13	99.34 $\pm$ 0.14	99.33 $\pm$ 0.15
		Accuracy (%)	91.47 $\pm$ 0.16	91.69 $\pm$ 0.17	91.51 $\pm$ 0.17	91.69 $\pm$ 0.46	91.57 $\pm$ 0.14

Appendix

Table 22: Effect of the validation-set size

N_{v}

on CIFAR-10 and CIFAR-20 (

\eta=25\%

, fixed cut

p=25\%

, CE+SCL-NL). Prec. is the share of true diagonal noise in the recycled branch. Mean

\pm

std over three seeds; best per row in bold , ties broken by the unrounded value.

		Training time		Acc. (%), final epoch		Acc. (%), best epoch
Method	$p$ (%)	20 ep.	200 ep.	20 ep.	200 ep.	20 ep.	200 ep.
No pruning	0	3.1 h	31.5 h	0.12	–	2.52	–
TW-LAVA	15	2.7 h	27.4 h	27.79	42.90	27.96	43.66
	25	2.4 h	24.2 h	61.01	68.26	61.01	69.64
	35	2.1 h	20.7 h	67.76	71.05	67.80	72.40
	45	1.8 h	17.7 h	55.95	70.28	56.00	71.14

Appendix

Table 23: Scaling to CIFAR-10-1M (

\eta=25\%

, SCL-NL, single run). Training time is the measured time of one epoch on a dedicated NVIDIA RTX A6000, multiplied by 20 or 200; it depends only on the size of the retained pool. Valuation adds about

2.5

hours for TW-LAVA and

4

minutes for CAVA. The CAVA times at

p=15\%

are estimated by a linear fit in the pool size. The best-epoch columns are for reference only; the text uses the final epoch. Best per column in bold ; “–”: not run.

Method	Training Size	Validation Size	Data-Selection Runtime	Remark
LAVA	10K	10K	45 seconds	Full-set OT computation
SAVA	10K	10K	300 seconds	Batch-wise OT computation
TW-LAVA (task-wise)	10K	10K	45 seconds	One task-wise OT selection step
CAVA (ours)	10K	10K	0.2 seconds	OT solve and label margin on precomputed features

Appendix

Table 24: Runtime of one OT-based selection step on CIFAR-10 with 10K training and 10K validation samples. The CAVA time is the mean of three runs on one GPU, with features computed beforehand.

				CAVA (ours)
Training set	LAVA	SAVA	TW-LAVA	$N_{v}=2{,}000$	$N_{v}=10{,}000$
10K	21.65 GB	3.00 GB	21.65 GB	0.10 GB	0.35 GB
20K	43.00 GB	3.00 GB	21.65 GB	0.17 GB	0.65 GB
30K	OOM	3.00 GB	21.65 GB	0.23 GB	0.95 GB
40K	OOM	3.00 GB	21.65 GB	0.30 GB	1.25 GB
50K	OOM	3.00 GB	21.65 GB	0.35 GB	1.55 GB

Appendix

Table 25: Peak GPU memory of OT-based selection as the training set grows. LAVA, SAVA, and TW-LAVA run their original pipelines with

10{,}000

validation images (TW-LAVA with tasks of 10K samples). For CAVA we report its valuation step, without feature extraction, with the

2{,}000

validation images of the paper and with

10{,}000

for a direct comparison. OOM: out of memory; “–”: not measured.

Figure 17: Label-margin visualization for randomly drawn samples from CLCIFAR-10 (human complementary labels, $3.98\%$ annotation errors; first task, $2{,}000$ validation images). Columns: image (red border: annotation error), labels of the validation images with the largest transport weight, with the weights (green: true class), label potentials $f_{i}(c)-\min_{c}f_{i}(c)$ with the given label in red, margins of all samples in the task (blue: valid, red: annotation error; dashed: adaptive-cut threshold $s_{i}=0$ ) with this sample marked, and the decision of the adaptive cut.

Figure 18: Label-margin visualization for randomly drawn samples from Places365-10, ten scene classes of Places365 [ 41 ] with synthetic diagonal noise ( $\eta=25\%$ ; first task, $2{,}000$ validation images). Columns as in Figure 17 . The fourth row is a failure: an annotation error whose image resembles a forest path is kept.

Data Valuation

Data valuation estimates how examples, datasets, or contributors affect model performance to guide selection, auditing, and fair compensation.

See all 43 papers

Embracing Biased Transition Matrices for Complementary-Label Learning with Many Classes
May 15, 2026Tan-Ha Mai, Chao-Kai Chiang, Han-Hwa Shih +3Multiclass Classification Weakly Supervised Learning
1National Taiwan University · 3RIKEN Center for Advanced Intelligence Project · 2The University of Tokyo
Same Target, Different Basins: Hard vs. Soft Labels for Annotator Distributions
May 20, 2026Mirerfan Gheibi, Gashin GhazizadehAnnotator Disagreement Label Distribution Learning
Independent Researcher.
Quantifying Annotation Agreement in Object Detection with Optimal Transport
Oct 14, 2026Kirill Prokhorov, Alexandr A. KalininInter-Rater Reliability Object Detection
Openface.io, Vilnius, Lithuania · Broad Institute of MIT and Harvard, Cambridge, MA, USA

May 15, 2026J/K move · Enter open · S save

Embracing Biased Transition Matrices for Complementary-Label Learning with Many Classes

Tan-Ha Mai, Chao-Kai Chiang, Han-Hwa Shih, Gang Niu+2

1National Taiwan University · 3RIKEN Center for Advanced Intelligence Project · 2The University of Tokyo

Multiclass Classification Weakly Supervised Learning Learning with Noisy Labels

Open paper AskPDF arXiv

Complementary-label learning (CLL) is a weakly supervised paradigm where instances are labeled with classes they do not belong to. Despite a decade of research, CLL methods remain competitive mainly on 10-class classification, with scaling to large label spaces continuing to be an enduring bottleneck. This limitation stems from the common assumption of uniform label generation in traditional methods, which fatally dilutes the learning signal in many-class settings. In this paper, we demonstrate that this long-standing barrier can be overcome by deliberately designing a biased (non-uniform) generation process that restricts complementary labels to a subset of classes. This finding motivates us to propose Bias-Induced Constrained Labeling (BICL), a principled framework spanning data collection to training that leverages this bias. BICL enables effective learning on CIFAR-100 and TinyImageNet-200, achieving more than sevenfold accuracy improvements over traditional methods. Our findings establish a new trajectory for making CLL feasible for many classes in real-world applications.

Abstract

Data Valuation

Explore similar work

Embracing Biased Transition Matrices for Complementary-Label Learning with Many Classes

Same Target, Different Basins: Hard vs. Soft Labels for Annotator Distributions

Quantifying Annotation Agreement in Object Detection with Optimal Transport