💬 NLP

When Correct Isn't Usable: Improving Structured Output Reliability in Small Language Models

This paper identifies a critical reliability gap where small language models fail to produce both mathematically correct and format-compliant outputs under standard prompting, and proposes AloLab, an iterative meta-agent system that optimizes system prompts to achieve high output accuracy with near-native latency without requiring model fine-tuning or constrained decoding.

Original authors: Cosimo Galeone, Minsu Park, Giuseppe Ettorre, Daniele Ligorio

Published 2026-05-05

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Cosimo Galeone, Minsu Park, Giuseppe Ettorre, Daniele Ligorio

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a brilliant but slightly chaotic assistant (a "Small Language Model") who is incredibly good at solving complex math puzzles. If you ask them, "What is 2 plus 2?", they will happily tell you, "Well, I added them up, and the answer is 4."

But in the real world of computers, that's not enough. The system waiting for the answer doesn't want a sentence; it wants a specific, rigid format, like a digital envelope with two labeled windows: one for "Reasoning" and one for "Answer." If the assistant writes the answer in a paragraph, or wraps it in a fancy box, or forgets to put it in the envelope at all, the computer rejects it. To the computer, a perfect answer in the wrong format is the same as a wrong answer.

This paper, titled "When Correct Isn't Usable," investigates why these smart assistants keep failing to follow these simple formatting rules and how the authors fixed it.

The Problem: The "Perfect Answer, Wrong Envelope" Gap

The researchers tested three popular, smaller AI models on math problems. They found a strange phenomenon:

The Math: The models were great at solving the problems (getting 77–85% of the math right).
The Format: They were terrible at following the rules (getting 0% of the answers in the correct JSON format).

It's like a chef who can cook a perfect steak but keeps serving it on a plate made of paper that falls apart. The steak is delicious, but you can't eat it.

They tried two common fixes, and both failed:

Just asking nicely (Naive/Reference): Telling the model, "Please give me the answer in a box," didn't work. The models kept ignoring the instruction or wrapping the box in extra decorations (like markdown fences) that broke the computer's parser.
Force-feeding the rules (Constrained Decoding): This is like putting the model in a straitjacket where it physically cannot type anything that isn't valid JSON. It worked for the format, but it made the model slow (3 to 8 times slower) and sometimes confused, causing the math quality to drop.

The Solution: AloLab (The "Prompt Coach")

The authors built a system called AloLab. Think of AloLab as a specialized coach who watches the model try to solve problems, sees where it fails, and rewrites the instructions (the "system prompt") to fix those specific mistakes.

Here is how the coach works:

Watch: The coach (using a very smart AI called Claude Sonnet 4.5) watches the model try to answer questions.
Spot the Error: If the model keeps wrapping the answer in a "markdown fence" (a weird symbol that breaks the format), the coach notices this pattern.
Rewrite the Rules: The coach updates the instruction manual to say, "Do not use markdown fences," or "Put the answer in the 'answer' field, not the 'reasoning' field."
Repeat: This happens over a few rounds until the model gets it right.

The Result:

Speed: Unlike the "straitjacket" method, AloLab doesn't slow the model down. In fact, because the instructions become clearer, the model sometimes answers faster.
Success: On the math tests, AloLab boosted the "usable" answer rate from 0% to 84–87% for the smaller models.
Even for the Big Guys: They tested this on a massive, expensive model (GPT-4o). Even that model was failing to follow the format (0% success) until AloLab coached it, at which point it jumped to 95% success.

Key Takeaways from the Paper

The "Meta-Agent" Matters: The coach needs to be smart. When they swapped the smart coach (Sonnet 4.5) for a cheaper, dumber one (Haiku), the results became a coin flip. Sometimes it worked, sometimes it failed completely. You need a capable coach to get consistent results.
No "Inside Access" Needed: AloLab works like a black box. It doesn't need to see the model's internal code or weights; it just watches what comes out and adjusts the instructions.
The "Reasoning vs. Answer" Glitch: Even with AloLab, there's a small remaining problem. Sometimes the model does the math correctly in its "reasoning" section but accidentally writes the wrong number in the final "answer" box. It's like the model knows the answer but has a typo when writing it down. This happens in about 1.5% to 1.8% of cases.

Summary

The paper argues that for small AI models, the biggest hurdle isn't intelligence; it's communication. They know the answer, but they can't format it correctly for computers. The authors found that instead of forcing the model to move slowly (constrained decoding), it's better to have a smart coach (AloLab) rewrite the instructions until the model learns to speak the computer's language perfectly. This makes the AI both faster and much more reliable.

Technical Summary: When Correct Isn't Usable

Problem Statement

Deployed language models face a critical reliability gap: an output must be both mathematically correct and format-compliant (e.g., valid JSON with specific fields) to be usable in production. Standard benchmarks typically measure task accuracy in isolation, ignoring the "structured-output reliability gap" where a model solves a problem correctly but fails to adhere to the required schema, rendering the response unusable.

This paper investigates this gap using mathematical benchmarks (GSM8K and MATH) as a controlled testbed. The ground truth is unambiguous, and the output contract is strict (JSON objects with reasoning and answer fields). The primary metric is output accuracy, defined as the joint event of mathematical correctness and valid JSON structure.

Methodology

Experimental Setup

The study evaluates three open-weight small language models (7–9B parameters): Llama 3.1-8B Instruct, Gemma 2-9B IT, and Qwen 2.5-7B Instruct. Additionally, GPT-4o is evaluated as a generalization probe on GSM8K. The models are tested under five prompting strategies:

NAIVE: No system prompt; only task input.
REFERENCE: A minimal, hand-written static prompt with basic JSON instructions (no iterative tuning).
CONSTRAINED: Grammar-based constrained decoding (vLLM) to enforce syntactic validity.
REF+CONSTRAINED: Combination of the REFERENCE prompt and constrained decoding.
ALOLAB: An iterative system-prompt optimizer (described below).

The AloLab Framework

AloLab is an iterative, black-box system-prompt optimizer designed to close the output accuracy gap without model fine-tuning or weight access.

Architecture: It operates as a meta-agent pipeline using Claude Sonnet 4.5 as the underlying LLM for both the Analyzer and Optimizer nodes.
Process:
1. Solver: Queries the target model via API (black-box) on a training/validation split.
2. Evaluator: Deterministically computes json_valid and is_correct.
3. Analyzer: Identifies recurring failure patterns (e.g., markdown fence wrapping, field mismatches) and success patterns, optionally utilizing a "model card" (architecture, parameter count) to tailor findings.
4. Optimizer: Rewrites the system prompt to address identified failures while preserving successful behaviors.
Cost: Optimization requires ~5,000–10,000 target-model inference calls and 30 meta-agent calls per model/dataset. Deployment incurs zero additional overhead, using only the final optimized prompt.

Ablation Studies

History-only: Removing explicit model profile information from the Analyzer/Optimizer to test if iterative feedback alone is sufficient.
Meta-agent Quality: Replacing Claude Sonnet 4.5 with the smaller Claude 3 Haiku to test if optimizer capability drives results.

Key Results

1. The Baseline Format Failure

A systematic format failure emerges at the baseline:

NAIVE prompting achieves high task accuracy (e.g., 77–85% on GSM8K) but 0% output accuracy across all models. The models solve the math but fail to produce valid JSON.
REFERENCE prompting (static hand-written prompts) fares poorly, yielding 0% output accuracy for Gemma and Qwen on MATH, and 0% for Gemma on GSM8K due to systematic markdown fence wrapping (```json) that breaks parsers.

2. AloLab Performance

AloLab substantially closes the gap:

GSM8K: Achieves 84–87% output accuracy across all three open models and 95.2% on GPT-4o.
MATH: Achieves 34–40% output accuracy.
Statistical Significance: In 29 out of 30 paired McNemar comparisons (5 runs × 3 models × 2 datasets), AloLab significantly outperforms the best static prompt (REFERENCE) at $p < 0.05$ .
Latency: AloLab operates at near-baseline inference latency (0.71×–1.06× NAIVE on GSM8K), whereas constrained decoding incurs a 3.6×–8.2× latency overhead.

3. Constrained Decoding Trade-offs

While constrained decoding enforces syntactic validity, it introduces significant latency and, in some cases (e.g., Gemma on GSM8K), degrades task performance (52.4% of outputs became exact duplicates). It occupies a "high-latency, lower-output-accuracy" region compared to AloLab.

4. Ablation Findings

Meta-agent Capability: Replacing Sonnet 4.5 with Haiku reduces mean output accuracy from 84.15% to 61.0% and increases run-to-run variance from <1 pp to 21.8 pp. This confirms that meta-agent capability is a primary driver of optimization quality; the iterative loop alone is insufficient without a capable optimizer.
Model Knowledge: Removing explicit model profiles (architecture, etc.) from the optimizer resulted in negligible performance drops (<1.3 pp), suggesting that observed execution patterns are the dominant signal for optimization, not prior model knowledge.

5. Generalization

The format failure is not limited to small open models. GPT-4o also exhibited 0% output accuracy under NAIVE and REFERENCE prompts due to systematic markdown wrapping. AloLab resolved this by learning to suppress the fences, achieving 95.2% output accuracy, confirming the failure is a model-specific generation default rather than a size-related limitation.

6. Residual Failures

A specific failure mode persists even with AloLab: Format-Execution Inconsistency. In 1.5–1.8% of failures, the JSON is valid and the reasoning field contains the correct logic, but the answer field contains the wrong value. An independent LLM judge verified this decoupling, suggesting it is an intrinsic generation property that becomes more visible as simpler format errors are eliminated.

Significance and Claims

The paper claims that the practical limits of small language models under strict output contracts are not limits of reasoning (as evidenced by high NAIVE task accuracy) but limits of structured communication.

AloLab demonstrates that iterative black-box prompt optimization can effectively bridge the gap between task correctness and format compliance without fine-tuning.
It offers a more accurate and cost-effective solution at inference time compared to constrained decoding, which suffers from high latency and potential task degradation.
The work highlights that static prompts are often insufficient for complex format constraints and that model-specific generation defaults (like markdown wrapping) must be dynamically identified and suppressed.

The authors conclude that while AloLab significantly improves reliability, the remaining "format-execution inconsistency" (correct reasoning, wrong answer field) represents a concrete direction for future research.