  Recent work has shown that language models' (LMs) prompt-based learning
capabilities make them well suited for automating data labeling in domains
where manual annotation is expensive. The challenge is that while writing an
initial prompt is cheap, improving a prompt is costly -- practitioners often
require significant labeled data in order to evaluate the impact of prompt
modifications. Our work asks whether it is possible to improve prompt-based
learning without additional labeled data. We approach this problem by
attempting to modify the predictions of a prompt, rather than the prompt
itself. Our intuition is that accurate predictions should also be consistent:
samples which are similar under some feature representation should receive the
same prompt prediction. We propose Embroid, a method which computes multiple
representations of a dataset under different embedding functions, and uses the
consistency between the LM predictions for neighboring samples to identify
mispredictions. Embroid then uses these neighborhoods to create additional
predictions for each sample, and combines these predictions with a simple
latent variable graphical model in order to generate a final corrected
prediction. In addition to providing a theoretical analysis of Embroid, we
conduct a rigorous empirical evaluation across six different LMs and up to 95
different tasks. We find that (1) Embroid substantially improves performance
over original prompts (e.g., by an average of 7.3 points on GPT-JT), (2) also
realizes improvements for more sophisticated prompting strategies (e.g.,
chain-of-thought), and (3) can be specialized to domains like law through the
embedding functions.
