Requallo: Maximizing Crowdsourcing Utility Under Tight Budgets

TL;DR

In crowdsourcing, a common nightmare is spending your entire budget and ending up with a dataset full of "maybe" labels. Requallo changes the game by letting requesters set a hard "quality bar" (e.g., "I need a 4:1 vote ratio"). It then uses a smart sequential policy to ensure the maximum number of instances hit that bar, effectively prioritizing "easy" wins to guarantee a high-quality subset of data when you can't afford to label everything perfectly.

Background: The Quantity-Quality Dilemma

In the world of Amazon Mechanical Turk (mTurk), we usually face a trade-off: do we label many things poorly or a few things well? When the budget is tight (i.e., you have 1,000 images but only 1,500 labels worth of cash), standard algorithms like Opt-KG (Optimistic Knowledge Gradient) tend to spread the budget thin. They try to give one label to everyone first. The result? You have 1,000 images with 1.5 labels each—statistically useless for high-stakes downstream tasks.

Requallo's core insight is Requirement-based allocation: If we know we need high confidence, we should focus our limited "coins" on instances that are close to becoming certain, essentially treating the labeling process as a path toward a "Completed" state.

Methodology: Crowdsourcing as a Markov Decision Process (MDP)

The researchers framed budget allocation as an MDP. Here is the breakdown:

• State: The current tally of +1 and -1 votes for all instances.
• Action: Deciding which specific instance to show to the next worker.
• Reward: The increase in Expected Completeness.

The Concept of Completeness

Unlike accuracy, which requires knowing the ground truth (which we don't have), Completeness is internal to the requester's needs. If your requirement is a 4:1 ratio, and an image has 3 positive votes and 1 negative, it is "80% complete" for the positive class.

The workflow: Requesters define confidence, the MDP engine selects the next instance, and workers provide labels in a loop.

Handling Worker Reliability

Real-world workers aren't perfect. Requallo extends its basic model by incorporating Maximum Likelihood Estimation (MLE) to estimate worker reliability ($heta$). It effectively weights votes: a label from a "Master" worker pushes the instance much further toward "Completeness" than a label from a potential spammer.

Experiments: Performance in the "Tight Budget" Zone

The most striking evidence of Requallo's efficacy is found in its comparison with SOTA methods on the RTE (Recognizing Textual Entailment) dataset.

(a) Quantity of labeled instances across different budgets.

Key Insights from Results:

1. The Dead Zone of Baselines: Methods like Opt-KG and LU show zero labeled instances (at a minimum 3-label threshold) until the budget exceeds the total number of instances ($N$).
2. Early Bloom: Requallo begins delivering high-quality, high-confidence labeled instances almost immediately because it doesn't try to label every instance equally. It picks favorites (the easier ones) to ensure they are completed.
3. Accuracy Stability: While "Random" and "Looping" results fluctuate wildly in accuracy when budgets are low, Requallo maintains high precision because it only "approves" an instance once its internal confidence requirement is met.

Critical Analysis & Conclusion

Takeaway

Requallo is a vital tool for researchers working in low-resource environments. It moves away from the "one-size-fits-all" allocation and acknowledges that some data points are harder than others. By focusing on "Completeness," it ensures that the money spent results in data you can actually trust.

Limitations

• Greedy Bias: The one-step look-ahead is computationally efficient but might miss long-term optimal strategies for extremely complex, inter-dependent tasks.
• Cold Start: The model relies on pseudo-labels (prior knowledge) to start the estimation. If the initial prior is wildly wrong, the early allocation might be sub-optimal.

Future Outlook

As we move toward "Small Data" and active learning for proprietary LLM fine-tuning, frameworks like Requallo will be essential for "Budget-Aware AI," where the cost of human verification is the primary bottleneck.