Imagine watching a film without seeing the picture. A voice tells you: "Mark walks into the room, wearing a suit, looking serious." "It's raining outside the window." "He puts down a cup of coffee on the table."
This is Audio Description (AD) — a service that describes key visual information for visually impaired audiences. Doing it well is far more complex than it sounds.
Descriptions must fit into gaps between dialogue lines without interrupting them. You must decide what is worth describing — facial expressions, actions, scene changes, on-screen text — each with different priority. And you must convey information concisely: a description that is too long will overlap the next line of dialogue.
What to describe, when to describe, and how to describe — these three decisions are coupled and cannot be made independently. In *Audio Description as Constrained Global Optimization*, Sterner and Lapata (University of Glasgow) formally model the problem as a constrained optimization task.
Three Coupled Decisions
Traditional automatic AD pipelines decouple the decisions: one model decides what to describe, another decides where to place it, a third generates the text. This staged approach ignores the coupling between constraints.
For example: you decide to describe "Mark is wearing a suit" — but the next dialogue gap is only 2 seconds, and the description needs 3 seconds. You must either shorten the phrasing ("in a suit"), defer it to a longer gap, or drop it entirely. This trade-off spans content, timing, and wording simultaneously.
The authors solve the problem with mixed-integer linear programming (MILP):
- Candidate generation: an LLM produces multiple candidate descriptions per scene (varying length and detail)
- Scoring: each candidate is scored on content relevance, temporal fit, and phrasing quality
- Constraint solving: MILP selects the optimal combination globally under constraints:
- Descriptions must not overlap dialogue
- Each description must fit entirely within one gap
- Minimum spacing between adjacent descriptions
- Overall description density must stay below an overload threshold
- Output: the selected descriptions and their timing
- CIDEr/METEOR: n-gram overlap with reference descriptions
- SODA-M/SODA-T: content coverage and timing quality
- QEval/QEval-T: question-based evaluation — can questions about the film be answered from the descriptions, and is the timing correct?
- The MILP optimizer wins across the board. Gemini MILP achieves QEval=45.9 and QEval-T=25.5, significantly outperforming all other automatic systems (p<0.01).
- The biggest gains come from timing. Gemini MILP reaches SODA-T of 55.7 versus 36.0 for pure Gemini prompting. Timing improved far more than content quality — the bottleneck is not *what* to say but *when* to say it.
- CIDEr actually decreased. MILP scores 13.6 versus 19.0 for pure LLM prompting. The authors argue this is a feature, not a flaw: CIDEr rewards wording overlap with references, while MILP produces more concise, fragmented descriptions that convey the same content differently. Low lexical overlap does not mean low quality.
- LLM schedulers underperform MILP. LLMs lack a global view of timing — they greedily fill each gap without considering overall rhythm.
- Human experts still substantially outperform all automatic systems. Expert QEval-T is 61.2 versus 25.5 for the best MILP. Automatic AD remains far from human level.
The REFRAMED Benchmark
The authors built REFRAMED, a benchmark containing audio description data from multiple films. Evaluation covers both text quality and timing:
Key Findings: Optimization Beats Prompting
The experiments compared pure LLM prompting (Qwen 3.5, Gemini 3.1), an LLM scheduler (the LLM decides timing itself), and the MILP optimizer (LLM generates candidates, MILP optimizes globally).
Why Global Optimization Beats End-to-End
The result seems counterintuitive: if LLMs can do everything, why does splitting the task into "generate candidates + optimize selection" work better?
The answer is constraint satisfaction. LLMs are strong at natural language generation but weak at satisfying hard constraints. Ask an LLM to "fit a description into a 2.3-second gap" and it often violates the limit — running over time or leaving too much silence. MILP is inherently built for constraint satisfaction.
This echoes the "judgment-gate decoupling" idea: the LLM handles generation (judgment), MILP handles selection and scheduling (gate). The LLM's creativity is unconstrained; MILP's constraint satisfaction doesn't depend on the LLM's "self-discipline." Each component does what it does best.
Commentary
What I appreciate most about this paper is that it refuses the "end-to-end LLM solves everything" route. Amid the current narrative of LLM omnipotence, decomposing a problem into "what LLMs are good at" and "what classical algorithms are good at" requires clear-eyed problem analysis.
The finding that CIDEr drops while QEval rises is worth remembering. It reveals that metric choice changes conclusions: judged only by CIDEr, MILP looks worse than pure prompting; judged by QEval, the conclusion reverses. Metrics measure what they define — not necessarily what you care about.
The finding that timing improved far more than content quality is also meaningful. In multimodal generation, the bottleneck often lies not in content generation but in coordination. LLMs already produce decent description text; they just don't know when to say it.
Human experts' QEval-T (61.2) is more than double the best MILP (25.5) — a sobering gap. On tasks requiring deep understanding and creative judgment, automatic systems remain far from human level. But MILP lifting the baseline from 19.0 to 25.5 is genuine, concrete progress.
---
Paper: Sterner, A., & Lapata, M. (2026). Audio Description as Constrained Global Optimization. arXiv:2609.30121 Link: https://arxiv.org/abs/2609.30121