Mapping the Course for Prompt-based Structured Prediction

1. Problem Statement

Large Language Models (LLMs) have demonstrated remarkable zero-shot and few-shot capabilities across various NLP tasks. However, when applied to structured prediction tasks (e.g., parsing, coreference resolution, moral framing), LLMs face significant limitations:

• Inconsistency: Autoregressive generation often produces outputs that violate structural constraints (e.g., logical contradictions, transitivity violations in coreference, or conflicting role assignments).
• Hallucinations: LLMs struggle with complex reasoning required to maintain global consistency across multiple related components.
• Confidence Calibration: Traditional structured inference algorithms (like Integer Linear Programming) require reliable confidence scores (probabilities) for candidate substructures. LLMs do not natively output calibrated probabilities for specific labels in the same way discriminative classifiers do; they output token probabilities over a vocabulary. It is unclear how to best extract these scores from prompt-based interactions to feed into symbolic inference engines.

2. Methodology

The authors propose a framework that combines the predictive power of LLMs with combinatorial inference to enforce structural consistency. The approach involves three main components:

A. General Framework (Factor Graph + ILP)

The problem is modeled as an LLM-based factor graph $\Psi$.

1. Local Scoring: An LLM is prompted to score individual candidate substructures (local decisions).
2. Global Optimization: These scores are fed into an Integer Linear Programming (ILP) solver to find the optimal global structure $y$ that maximizes the sum of scores while satisfying structural constraints $C$.
   $$\text{arg max}_{y \in Y} \sum_{\psi_i \in \Psi} \rho(x_i, y_i; \theta) \quad \text{s.t. } c(x_c, y_c)$$
   Where $\rho$ is the LLM score and $c$ represents constraints (e.g., transitivity, mutual exclusivity).

B. Confidence Estimation Strategies

The paper exhaustively evaluates methods to derive confidence scores from LLMs, categorized into White-Box (access to token probabilities) and Black-Box (text-only) methods:

• White-Box:
  • True/False: Formulating the task as a binary question (e.g., "Is the label X true?") and using the probability of the "True" token.
  • Multiple Choice: Using the probability of the token corresponding to the correct option.
  • Generative Classification: Reversing the prompt (Label $\to$ Text) and calculating the likelihood of generating the input text given the label.
• Black-Box:
  • Generation Sampling: Sampling $n$ generations and using the frequency of a specific label as the confidence score.
  • Verbalized Confidence: Prompting the model to output a numerical confidence score (0-100) directly.

C. Learning and Calibration Strategies

Beyond zero-shot prompting, the authors explore methods to align LLMs with structured objectives:

1. Score Calibration (Post-hoc): Training a logistic regression layer on top of frozen LLM scores.
   • Local Calibration: Trains separate regressors for each sub-task.
   • Global Calibration: Jointly trains regressors using a structured hinge loss that considers the global inference result.
2. Fine-Tuning:
   • Local Fine-Tuning: Standard next-token prediction fine-tuning on local components.
   • Global Fine-Tuning: Backpropagating the structured hinge loss (from the ILP step) directly into the LLM parameters (using LoRA), effectively teaching the model to optimize for global consistency.

3. Key Contributions

1. Exhaustive Confidence Estimation Study: The paper provides a systematic comparison of five distinct prompting strategies for extracting confidence scores, identifying that True/False prompting yields the most effective scores for downstream inference.
2. Integration of Symbolic Inference: Demonstrates that combining LLMs with ILP-based inference consistently outperforms pure prompting, regardless of the confidence estimation strategy used.
3. Structured Learning Objectives: Introduces and validates Global Calibration and Global Fine-Tuning, showing that optimizing for the global structured objective (rather than just local token prediction) significantly boosts performance.
4. Empirical Validation: Extensive experiments on two challenging discourse-level tasks: Morality Framing (identifying moral foundations and roles in political tweets) and Coreference Resolution (biomedical and general news).

4. Experimental Results

The authors evaluated their methods on the Morality Frames dataset and GENIA/OntoNotes coreference datasets using models like Llama-3.1-8B, Mistral-7B, and larger variants (Llama-70B, GPT-5).

• Inference vs. Prompting: Adding combinatorial inference (+ constr) improved performance across all strategies. For example, in Morality Framing, the True/False method improved Micro F1 from 0.498 to 0.517; in Coreference, it improved F1 from 0.815 to 0.820.
• Best Confidence Strategy: The True/False prompting strategy consistently provided the best confidence scores for inference, outperforming Multiple Choice, Generation Sampling, and Verbalized Confidence.
• Learning Impact:
  • Global Calibration outperformed Local Calibration, particularly for pre-trained models.
  • Global Fine-Tuning achieved the state-of-the-art results. On the Morality Frames task, the Global Fine-Tuned model achieved a Micro F1 of 0.764, surpassing the previous state-of-the-art (0.723) and significantly outperforming "All-in-One" prompting strategies.
  • On the GENIA coreference task, Global Fine-Tuning reached an F1 of 0.890, outperforming the previous best (0.916 was a specific constrained deep model, but the LLM-based approach with global tuning was highly competitive and superior to standard baselines).
• Model Size: Interestingly, for some tasks, the 8B model performed slightly better than the 70B model when using specific prompting strategies, suggesting that larger models may be over-parameterized for simple local classification tasks unless guided by global constraints.
• Computational Cost: While inference adds negligible time (~0.1s to 3s), methods like Verbalized Confidence and Generative Classification are computationally expensive due to multiple prompts per instance. Multiple Choice and True/False are the most efficient.

5. Significance and Conclusion

This paper establishes that structured learning remains vital in the era of LLMs. While LLMs possess vast world knowledge, they lack the inherent ability to enforce strict logical consistency.

• Hybrid Approach: The most effective path forward is a hybrid approach: using LLMs as powerful local scorers and symbolic inference (ILP) as the global constraint enforcer.
• Prompt Engineering Matters: The way a prompt is formulated (e.g., True/False vs. Open Generation) drastically affects the quality of the confidence scores used for inference.
• Training Objective: Simply fine-tuning LLMs on local tokens is insufficient for structured tasks. Optimizing the model (via Global Fine-Tuning) directly against the global structured objective yields superior results, bridging the gap between generative models and discriminative structured prediction.

The work provides a roadmap for building robust, consistent, and high-performing NLP systems that leverage the flexibility of LLMs while mitigating their tendency for hallucination and inconsistency through formal inference.