REVIEW 3 major objections 5 minor 39 references
Refining Labeling Functions with Limited Labeled Data
T0 review · 3 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash
Pith's one-line read This paper claims that noisy labeling functions in programmatic weak supervision can be repaired with only tens of labeled examples, by minimally changing their outputs on those examples and refining them as conditional rules with new…
desk verdict A useful new formalization of LF repair that is undercut by an error-balanced evaluation sample; worth reviewing but needs a controlled re-run. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The central object is a rule: a binary tree whose internal nodes are predicates and whose leaves are labels, representing any labeling function. The key operation is refinement, which replaces a leaf with a predicate subtree to reroute some datapoints to a different label. The argument rests on two results: the output-change decision is a mixed-integer linear program of size O(n·m) in the number of labeled points and rules, and, provided the predicate space is partitioning (any two distinct datapoints can be separated by some predicate), a path repair that assigns each labeled point its desired label always exists with cost at most the number of points on that path. EntropyPathRepair greedily picks the predicate minimizing Gini impurity at each step to build that repair.
What would settle it
On a synthetic text dataset where every pair of documents shares the same word multiset but ground-truth labels differ, run RuleCleaner with any predicate space composed only of word-containment predicates. Since no predicate can separate such documents, the repair cannot assign both labels correctly, so global accuracy on this two-point dataset cannot reach the required thresholds.
Extended reading notes
Core claim
RuleCleaner treats each labeling function as a rule tree whose leaves are labels and whose internal nodes are Boolean predicates over datapoints. A repair is a sequence of refinements that replace a leaf with a new predicate and two label leaves, so the function's behavior changes only on datapoints that match the new condition. The paper proves that finding an optimal repair is NP-hard in general, then separates the problem: a mixed-integer linear program decides which output changes are needed on the labeled set to satisfy evidence, datapoint-accuracy, and rule-accuracy thresholds while minimizing changes, and an entropy-guided greedy path repair implements those changes by adding the fewest new predicates it can. Experiments with the standard weak-supervision pipeline show the repaired functions improve global accuracy on most datasets, and the approach is orders of magnitude faster than using a large language model as a direct labeler while preserving interpretable rules.
Load-bearing premise
The method's guarantee rests on the assumption that the predicate space can tell any two different datapoints apart; for text, this requires that no two documents share exactly the same vocabulary.
Editorial extensions
If this is right
- Users can fix a rule set with tens of labeled examples instead of laboriously auditing large training sets.
- The repaired rules remain interpretable trees, so the fix is auditable and can be inspected or further edited.
- The method is agnostic to how rules were created, whether hand-written, generated from data, or generated by a large language model, and to the label model that combines them.
- Minimal change preservation means rules that were already correct on most points stay unchanged, limiting overfitting to the small labeled set.
- The NP-hardness results justify the two-step decomposition: decide outputs with an MILP, then implement per-path refinements greedily.
Reading between the lines
- If the accuracy gains hold at scale, weak supervision could become an iterative process where a handful of curated examples repairs heuristics on the fly, and the same rule-refinement machinery could likely be reused for other rule-based systems such as information extraction or entity matching.
- Because the partitioning-predicate assumption suggests that for text domains the method's guarantees degrade when documents share identical word sets, a natural testable extension is to enrich predicate spaces with n-grams, embeddings, or regular expressions to restore separability for near-duplicate documents.
- Because the MILP only sees the labeled points, a testable prediction is that performance degrades gracefully with label noise: the minimal-change objective and accuracy thresholds should absorb a fraction of mislabeled examples, an experiment the paper does not report.
- A hybrid design in which a large language model proposes candidate predicates and RuleCleaner selects among them could combine broader predicate coverage with the paper's interpretable, minimal-change repair mechanism.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies the problem of repairing labeling functions (LFs) in programmatic weak supervision (PWS). It models LFs as decision-tree-style rules, defines the rule repair problem as minimizing output changes on a small labeled set X* subject to per-datapoint evidence, per-datapoint accuracy, and per-rule accuracy thresholds, and proves NP-hardness by reduction from set cover. The proposed system, RuleCleaner, solves a mixed-integer linear program (MILP) to determine desired label changes on X*, then refines individual rules with new predicates, using an entropy-based greedy algorithm (EntropyPathRepair) with an optional brute-force path repair. Experiments on multiple datasets and LF sources (Witan, LLM-generated) report improved global labeling accuracy after repair on 8 of 9 datasets for both setups, plus comparisons against LLM labeling and LLM-based LF repair.
Significance. If the results hold, the paper addresses a practically important problem: improving interpretable weak supervision sources with only tens of labeled examples. The formal framing of LF repair as rule refinement is useful, and the MILP-plus-refinement architecture is a reasonable decomposition. The paper includes NP-hardness reductions, a correctness theorem for the path-repair heuristic under a partitioning predicate assumption, an extensive experimental comparison across multiple datasets and PWSSs, and a public code artifact, which are strengths. However, as detailed below, the main empirical claim is currently vulnerable to the specific way X* is sampled in Section 5.1, and there is a formal inconsistency between Definition 2 and the MILP constraints that needs to be resolved before the theoretical claims can be taken at face value. The approach is promising and the issues appear addressable, but the central claim as stated is not yet established by the reported experiments.
major comments (3)
- [Section 5.1, Section 3.1] The evaluation protocol for X* is not a random sample: the text states that 'the labeled datapoints are randomly sampled from X, with 50% correct predictions by PWSS and 50% wrong predictions within each sample.' This deliberately over-samples the exact failures that RuleCleaner is designed to fix, and it gives the MILP direct supervision on errors, making the accuracy constraints much easier to satisfy than under ordinary random sampling. The justification that one can select such a sample from a larger labeled pool changes the task from 'a small set of labeled examples' to an active error-selection scenario, which is not what the abstract and problem statement claim. The reported global-accuracy gains on 8 of 9 datasets should therefore be re-run with an unstratified random sample of X (or of an arbitrary labeled pool) with the same |X*| sizes, and the results should be compared. The paper should also state explicitly whether the global accuracy is computed over X including X*; if X* is not excluded, the evaluation double-counts the points on which the repair was explicitly enforced. Without these controls, the headline claim of 'significantly improves labeling accuracy using a small number of labeled examples' is not supported.
- [Definition 2 vs. Section 3.1] There is a formal mismatch between the printed rule repair problem and the MILP formulation. In Definition 2, Acc(x_i) is defined as (1/m) times the number of non-abstaining rules that label x_i correctly, so the denominator is the total number of rules m. The MILP constraint, however, enforces sum_j c_ij >= sum_j e_ij * tau_acc, which is equivalent to requiring that the accuracy among non-abstaining rules be at least tau_acc. For rules that abstain on x_i, these two formulations differ: a rule set with many abstentions and high precision on the non-abstentions could satisfy the MILP but violate Definition 2 as written. Consequently, Proposition 1 is only correct under the conditional-accuracy reading that the MILP implements, not under the formula printed in Definition 2. The definition needs to be corrected to divide by the number of non-abstaining rules (or the MILP needs to match the printed definition), otherwise the connection between the optimization problem and the MILP is not established.
- [Section 4.2, Theorem 2, Appendix C.2] The correctness guarantee of EntropyPathRepair (Theorem 2) and the existence of path repairs (Lemma 2) both assume a partitioning predicate space P, i.e., that any two distinct datapoints can be separated by some predicate. The paper argues this holds for text when P contains word-containment predicates, but this is not true in general: two distinct documents with the same word vocabulary (or near-duplicates) are indistinguishable by all word-containment predicates, so they violate the partitioning assumption. The examples and datasets likely contain such cases (e.g., duplicate reviews or short SMS messages). The theorem should be stated with a precise condition that is actually satisfied by the experimental predicate spaces, or the paper should provide evidence on how often the partitioning assumption fails in the datasets and how the algorithm behaves when it fails. As written, the formal guarantee applies only to a restricted setting that is not shown to hold for the reported experiments.
minor comments (5)
- [Appendix B] In the proof of Theorem 1, the thresholds are listed with tau_E appearing twice: first as tau_E = 1/|X*| and then as tau_E = 1. Presumably one of these is meant to be tau_racc or the second is a different constraint; the construction should be labeled consistently.
- [Section 5.1] The paper uses the word 'significant' when reporting global-accuracy improvements, but no statistical significance tests or error bars are reported for the main result; the figures appear to show point estimates. Please qualify the claim as an observed improvement or provide appropriate variance/significance measures.
- [Section 5.3] The experiments report results on 9 datasets for the Witan and LLM-LF setups, but Table 2 lists 11 datasets (and 10 for Witan, excluding CmPt). The text should clarify which datasets are included in each figure and which are deferred to the appendix, especially for the LLM comparison where a 48-hour time limit is mentioned.
- [Section 5.5] The claim that sublinear growth in rule size 'suggests ... without leading to overfitting' is an extrapolation: the table reports only tree depth and node count, not held-out accuracy. If overfitting is meant to be addressed, report accuracy on a held-out test set as a function of refinement size.
- [Section 5.4] The phrase 'prohibitory large' should be 'prohibitively large'. Also, the sentence 'It is obvious that the runtime for BruteForcePathRepair is significantly higher than the other 2 algorithms' can be tightened.
Circularity Check
No significant circularity: improvements are empirical on full-dataset accuracy, and formal results are conditional on explicit assumptions.
full rationale
The paper's formal chain is not circular. The NP-hardness results (Theorems 1 and 3) are reductions from Set Cover, independent of the paper's own claims. The correctness guarantee of EntropyPathRepair (Theorem 2) and the existence of path repairs (Lemma 2) are conditional on an explicit partitioning-predicate-space assumption (Appendix C.2); they show that the refinement algorithm can implement the desired labels on X*, not that accuracy improves on X. The paper explicitly disclaims a formal accuracy guarantee on X ('we can, in general, not guarantee that the PWSS's performance on the unlabeled dataset X will improve'), so the observed improvement is an empirical result, not a derived prediction. The evaluation uses a stratified X* (50% correct / 50% wrong predictions), which may affect external validity, but the global accuracy is computed over the full dataset X and is not the same quantity optimized by the MILP (which optimizes LF-output changes under evidence/accuracy constraints on X* only). No load-bearing self-citation appears: [18] is used only to construct an LLM-based LF generation baseline in Section 5.3. Therefore the central claim does not reduce to its inputs.
Assumptions & free parameters
free parameters (1)
- Thresholds tau_acc, tau_E, tau_racc =
recommended ~0.7
assumptions (3)
- domain assumption Labeling functions can be translated into rule trees in PTIME, with black-box predicates for code the translator cannot decompose.
- domain assumption The predicate space P is partitioning: for any two datapoints x1 != x2 there exists p in P with p(x1) != p(x2).
- domain assumption Repairing rules on a small labeled subset improves the black-box PWSS's accuracy on the full dataset.
Cite this review
Pith. "Pith review of Refining Labeling Functions with Limited Labeled Data." pith.science (2026). https://pith.science/paper/A5P4D4DH
@misc{pith2026250523470,
author = {Pith},
title = {Pith review of: Refining Labeling Functions with Limited Labeled Data},
year = {2026},
howpublished = {\url{https://pith.science/paper/A5P4D4DH}},
note = {Machine review of arXiv:2505.23470}
}
read the original abstract
Programmatic weak supervision (PWS) significantly reduces human effort for labeling data by combining the outputs of user-provided labeling functions (LFs) on unlabeled datapoints. However, the quality of the generated labels depends directly on the accuracy of the LFs. In this work, we study the problem of fixing LFs based on a small set of labeled examples. Towards this goal, we develop novel techniques for repairing a set of LFs by minimally changing their results on the labeled examples such that the fixed LFs ensure that (i) there is sufficient evidence for the correct label of each labeled datapoint and (ii) the accuracy of each repaired LF is sufficiently high. We model LFs as conditional rules which enables us to refine them, i.e., to selectively change their output for some inputs. We demonstrate experimentally that our system improves the quality of LFs based on surprisingly small sets of labeled datapoints.
Figures
Figures from the paper (15 more)
Reference graph
Works this paper leans on
-
[1]
Hadeer Ahmed, Issa Traoré, and Sherif Saad. 2018. Detecting opinion spams and fake news using text classification.Secur. Priv.1, 1 (2018)
work page 2018
-
[2]
Almeida, José María Gómez Hidalgo, and Akebo Yamakami
Tiago A. Almeida, José María Gómez Hidalgo, and Akebo Yamakami. 2011. Con- tributions to the study of SMS spam filtering: new collection and results. InACM Symposium on Document Engineering. ACM, 259–262
work page 2011
-
[3]
Simran Arora, Brandon Yang, Sabri Eyuboglu, Avanika Narayan, Andrew Ho- jel, Immanuel Trummer, and Christopher Ré. 2023. Language Models Enable Simple Systems for Generating Structured Views of Heterogeneous Data Lakes. Proceedings of the VLDB Endowment17, 2 (2023), 92–105
2023
-
[4]
Benedikt Boecking, Willie Neiswanger, Eric Xing, and Artur Dubrawski. 2021. Interactive Weak Supervision: Learning Useful Heuristics for Data Labeling. In International Conference on Learning Representations
work page 2021
-
[5]
Bradley Butcher, Miri Zilka, Darren Cook, Jiri Hron, and Adrian Weller. 2023. Op- timising Human-Machine Collaboration for Efficient High-Precision Information Extraction from Text Documents.arXiv preprint arXiv:2302.09324(2023)
work page Pith review arXiv 2023
-
[6]
Maria De-Arteaga, Alexey Romanov, Hanna M. Wallach, Jennifer T. Chayes, Christian Borgs, Alexandra Chouldechova, Sahin Cem Geyik, Krishnaram Ken- thapadi, and Adam Tauman Kalai. 2019. Bias in Bios: A Case Study of Semantic Representation Bias in a High-Stakes Setting. InFAT, danah boyd and Jamie H. Morgenstern (Eds.). 120–128
work page 2019
-
[7]
Benjamin Denham, Edmund M.-K. Lai, Roopak Sinha, and M. Asif Naeem. 2022. Witan: Unsupervised Labelling Function Generation for Assisted Data Program- ming.PVLDB15, 11 (2022), 2334–2347
work page 2022
-
[8]
Daniel Fu, Mayee Chen, Frederic Sala, Sarah Hooper, Kayvon Fatahalian, and Christopher Ré. 2020. Fast and three-rious: Speeding up weak supervision with triplet methods. InInternational conference on machine learning. PMLR, 3280– 3291
work page 2020
Show all 39 references
-
[9]
Sainyam Galhotra, Behzad Golshan, and Wang-Chiew Tan. 2021. Adaptive Rule Discovery for Labeling Text Data. InSIGMOD. 2217–2225
2021
-
[10]
2008.Linear and Nonlinear Opti- mization 2nd Edition
Igor Griva, Stephen G Nash, and Ariela Sofer. 2008.Linear and Nonlinear Opti- mization 2nd Edition. SIAM
2008
-
[11]
Naiqing Guan, Kaiwen Chen, and Nick Koudas. 2025. DataSculpt: Cost-Efficient Label Function Design via Prompting Large Language Models. InProceedings 28th International Conference on Extending Database Technology, EDBT 2025, Barcelona, Spain, March 25-28, 2025. OpenProceedings...
2025
-
[12]
Naiqing Guan and Nick Koudas. 2024. Weshap: Weak Supervision Source Evalu- ation With Shapley Values.CoRRabs/2406.11010 (2024). arXiv:2406.11010
2024 arXiv
-
[13]
Braden Hancock, Martin Bringmann, Paroma Varma, Percy Liang, Stephanie Wang, and Christopher Ré. 2018. Training classifiers with natural language explanations. InACL, Vol. 2018. 1884
2018
-
[14]
Ruining He and Julian J. McAuley. 2016. Ups and Downs: Modeling the Visual Evolution of Fashion Trends with One-Class Collaborative Filtering. InWWW, Jacqueline Bourdeau, Jim Hendler, Roger Nkambou, Ian Horrocks, and Ben Y. Zhao (Eds.). 507–517
2016
-
[15]
Cheng-Yu Hsieh, Jieyu Zhang, and Alexander J. Ratner. 2022. Nemo: Guiding and Contextualizing Weak Supervision for Interactive Data Programming.PVLDB 15, 13 (2022), 4093–4105. KDD ’25, August 3–7, 2025, Toronto, ON, Canada Chenjie Li, Amir Gilad, Boris Glavic, Zhengjie Miao, a...
2022
-
[16]
Kotsiantis
Sotiris B. Kotsiantis. 2013. Decision Trees: a Recent Overview.Artif. Intell. Rev. 39, 4 (2013), 261–283
2013
-
[17]
Martin Krallinger, Obdulia Rabal, Saber A Akhondi, Martın Pérez Pérez, Jesús Santamaría, Gael Pérez Rodríguez, Georgios Tsatsaronis, Ander Intxaurrondo, José Antonio López, Umesh Nandal, et al . 2017. Overview of the BioCreative VI chemical-protein interaction Track. InProceed...
2017
-
[18]
Chenjie Li, Dan Zhang, and Jin Wang. 2024. LLM-assisted Labeling Function Generation for Semantic Type Detection. InProceedings of Workshops at the 50th International Conference on Very Large Data Bases, VLDB 2024, Guangzhou, China, August 26-30, 2024
2024
-
[19]
B. Liu, L. Chiticariu, V. Chu, HV Jagadish, and F.R. Reiss. 2010. Automatic Rule Refinement for Information Extraction.PVLDB3, 1 (2010)
2010
-
[20]
Maas, Raymond E
Andrew L. Maas, Raymond E. Daly, Peter T. Pham, Dan Huang, Andrew Y. Ng, and Christopher Potts. 2011. Learning Word Vectors for Sentiment Analysis. In Association for Computational Linguistics: Human Language Technologies, Dekang Lin, Yuji Matsumoto, and Rada Mihalcea (Eds.). 142–150
2011
-
[21]
Hussein Mouzannar, Yara Rizk, and Mariette Awad. 2018. Damage Identification in Social Media Posts using Multimodal Deep Learning. InInternational Confer- ence on Information Systems for Crisis Response and Management, Kees Boersma and Brian M. Tomaszewski (Eds.). ISCRAM Association
2018
-
[22]
Northcutt, Lu Jiang, and Isaac L
Curtis G. Northcutt, Lu Jiang, and Isaac L. Chuang. 2021. Confident Learning: Estimating Uncertainty in Dataset Labels.J. Artif. Intell. Res.70 (2021), 1373–1411
2021
-
[23]
Fatemah Panahi, Wentao Wu, AnHai Doan, and Jeffrey F Naughton. 2017. To- wards Interactive Debugging of Rule-based Entity Matching.. InEDBT. 354–365
2017
-
[24]
Bach, Henry R
Alexander Ratner, Stephen H. Bach, Henry R. Ehrenberg, Jason A. Fries, Sen Wu, and Christopher Ré. 2020. Snorkel: rapid training data creation with weak supervision.VLDBJ29, 2-3 (2020), 709–730
2020
-
[25]
Ratner, Christopher De Sa, Sen Wu, Daniel Selsam, and Christopher Ré
Alexander J. Ratner, Christopher De Sa, Sen Wu, Daniel Selsam, and Christopher Ré. 2016. Data Programming: Creating Large Training Sets, Quickly. InNIPS. 3567–3575
2016
-
[26]
Ilyas, and Christopher Ré
Theodoros Rekatsinas, Xu Chu, Ihab F. Ilyas, and Christopher Ré. 2017. HoloClean: Holistic Data Repairs with Probabilistic Inference.PVLDB10, 11 (2017), 1190– 1201
2017
-
[27]
Sudeepa Roy, Laura Chiticariu, Vitaly Feldman, Frederick R Reiss, and Huaiyu Zhu. 2013. Provenance-based dictionary refinement in information extraction. InSIGMOD. 457–468
2013
-
[28]
Anastasiya Sedova and Benjamin Roth. 2022. ULF: Unsupervised Labeling Function Correction using Cross-Validation for Weak Supervision.CoRR abs/2204.06863 (2022)
2022 arXiv
-
[29]
Paroma Varma and Christopher Ré. 2018. Snuba: Automating Weak Supervision to Label Training Data.PVLDB12, 3 (2018), 223–236
2018
-
[30]
Zihan Wang, Jingbo Shang, Liyuan Liu, Lihao Lu, Jiacheng Liu, and Jiawei Han
-
[31]
Peilin Yu and Stephen Bach. 2023. Alfred: A System for Prompted Weak Supervi- sion.arXiv preprint arXiv:2305.18623(2023)
2023 arXiv
-
[32]
Yue Yu, Simiao Zuo, Haoming Jiang, Wendi Ren, Tuo Zhao, and Chao Zhang. 2020. Fine-tuning pre-trained language model with weak supervision: A contrastive- regularized self-training approach.arXiv preprint arXiv:2010.07835(2020)
2020 arXiv
-
[33]
Jieyu Zhang, Cheng-Yu Hsieh, Yue Yu, Chao Zhang, and Alexander Ratner. 2022. A Survey on Programmatic Weak Supervision.CoRRabs/2202.05433 (2022). arXiv:2202.05433
2022 arXiv
-
[34]
Jieyu Zhang, Haonan Wang, Cheng-Yu Hsieh, and Alexander J. Ratner. 2022. Understanding Programmatic Weak Supervision via Source-aware Influence Function. InAdvances in Neural Information Processing Systems 35: Annual Con- ference on Neural Information Processing Systems 2022, ...
2022
-
[35]
Jieyu Zhang, Yue Yu, Yinghao Li, Yujing Wang, Yaming Yang, Mao Yang, and Alexander Ratner. 2021. WRENCH: A comprehensive benchmark for weak supervision.arXiv preprint arXiv:2109.11377(2021)
2021 arXiv
-
[36]
Xiaoyu Zhang, Xiwei Xuan, Alden Dima, Thurston Sexton, and Kwan-Liu Ma
-
[37]
separates
Xiang Zhang, Junbo Jake Zhao, and Yann LeCun. 2015. Character-level Convo- lutional Networks for Text Classification. InNeurIPS, Corinna Cortes, Neil D. Lawrence, Daniel D. Lee, Masashi Sugiyama, and Roman Garnett (Eds.). 649–657. A Translating Labeling Functions Into Rules In...
2015
-
[2019]
InEMNLP-IJCNLP
CrossWeigh: Training Named Entity Tagger from Imperfect Annotations. InEMNLP-IJCNLP. 5153–5162
-
[2023]
In2023 IEEE 16th Pacific Visualization Symposium (PacificVis)
LabelVizier: Interactive Validation and Relabeling for Technical Text An- notations. In2023 IEEE 16th Pacific Visualization Symposium (PacificVis). IEEE, 167–176
Reviewed August 7, 2026 · model on record in the stance chip above.
Discussion (0). Sign in to comment.