What, When, and How: Audio Description as Constrained Global Optimization

1 INTRODUCTION

• AD must select the few visual details that carry the story and omit most incidental frame content, while content, wording, and timing compete for narration time.Dense dialogue may force fewer descriptions, terser wording, or delivery displaced from the referenced moment.Source: §1 · pp. 1–2
• Prior systems largely caption clips whose content and timing come from reference AD, leaving the decisions of what and when to describe unaddressed.The introduction describes clip captioning as a reasonable proxy for phrasing, but not for choosing content or timing.Source: §1 · pp. 1–2
• LLMs propose, ground, score, and compress visual events, while a scene-level MILP jointly selects events, wording variants, and delivery times under hard temporal constraints.Descriptions must fit dialogue gaps, remain close to the events they describe, and avoid overlapping other narration.Source: §1 · pp. 2–3
• On REFRAMED, constrained optimization beats an LLM scheduler with identical inputs, conveys more story than prompted and captioning systems, and achieves the strongest automatic QA performance.The comparison with prompted and captioning systems concerns systems given when to describe; a substantial gap to human describers remains.Source: §1 · pp. 2–3

2 RELATED WORK

• Most AD generation systems caption clips with placement inherited from reference AD, thereby constraining both when and what to describe (Han et al., 2023a;b; 2024; Lin et al., 2024; Deganutti et al., 2025; Wang et al., 2025; Ye et al., 2025; Chu et al., 2024; Zhang et al., 2024; Xie et al., 2024).These systems include fine-tuned multimodal models and zero-shot LLM prompting.Source: §2 · p. 3
• Other methods relax fixed placement or content assumptions, but none jointly allocates all three decisions across a scene (Pavel et al., 2020; Gupta et al., 2026; Khandelwal et al., 2025).Some assume human-written content, generate independently at insertion points, or fix temporal placement.Source: §2 · p. 3
• REFRAMED establishes a what-and-when setting, while this paper adds wording choice and jointly optimizes content, formulation, and placement across a scene.The cited account of what/when/how comes from AD translation studies, but does not specify a computational mechanism for coordinating the decisions.Source: §2 · p. 3
• The formulation follows global summarization methods that select salient content under a budget, but replaces a single length budget with soundtrack-defined temporal windows and delivery locations (McDonald, 2007; Gillick et al., 2008; Gillick & Favre, 2009; Madnani et al., 2007; Clarke & Lapata, 2008; Martins & Smith, 2009; Berg-Kirkpatrick et al., 2011; Woodsend & Lapata, 2010; 2012).The paper also adopts the separation between models that score candidates and a solver that chooses among them.Source: §2 · p. 3

• The formulation calls dynamic events, ongoing processes, and static states eventualities; delivery spans can differ from occurrence spans when dialogue blocks narration at the event time.Source: §3 · p. 4
• AD generation selects eventualities, chooses a description variant for each, and assigns delivery times using candidate descriptions, salience scores, occurrence spans, and permissible narration gaps.Source: §3 · p. 4
• The objective maximizes salience weighted by narration time, favoring the longest variant that fits and allowing denser short descriptions to displace less-salient longer ones.Source: §3 · p. 4
• Selected descriptions must use exactly one variant, fit within a permissible narration interval, remain near their eventuality, and avoid overlap while preserving scene order.Source: §3 · p. 5
• In the illustrated 9.5-second gap, the solver drops the least-salient event, schedules the others in order without overlap, and compresses a description that otherwise would not fit.Source: §3 · p. 5, Figure 2 · p. 5

• REFRAMED contains 2,023 excerpts from 206 movies; the challenge set covers ten full-length movies and 1,221 scenes, with ablations on eight validation movies.Source: §4 · pp. 5–6
• Evaluation measures dialogue-gap text overlap, monotonic alignment and timing, and narrative usefulness through QEval and QEval-T, with significance assessed by permutation tests.Source: §4 · p. 6
• The pipeline uses Qwen 3.5 or Gemini 3.1 to generate scene descriptions, segment elements, estimate spans and salience, create compressions, and compute narration durations.Source: §4 · p. 6
• Salience comparisons include random, embedding-based, and BM25 scores, alongside oracles, while leaving the rest of the pipeline unchanged.Source: §4 · pp. 6–7
• The MILP uses a 10-second event-proximity window and stops at optimality criteria or ten minutes; prompted LLM outputs are also evaluated after filtering timing and speech-rate violations.Source: §4 · pp. 6–7
• Comparisons include prompted Qwen and Gemini generations, Random, Expert AD, ShotbyShot, and DistinctAD; controlled LLM schedulers receive the MILP inputs plus text and compressions.Source: §4 · p. 7

5 RESULTS AND DISCUSSION

• Gemini MILP leads automatic systems on QEval (45.9) and QEval-T (25.5); its gains center on temporal and narrative measures rather than CIDEr overlap.It also achieves the best SODA-T score except for ShotbyShot, with no significant difference; expert human performance exceeds all systems across metrics.Source: Table 1 · p. 7, §5 · pp. 7–8
• Against an LLM scheduler, Gemini MILP improves SODA-T (55.7 vs. 45.8) and QEval-T (25.5 vs. 19.9), while Qwen’s clearest gain is SODA-T (53.6 vs. 47.6).The MILP is significantly better on every metric except CIDEr; Qwen’s QEval-T difference is numerically small (22.1 vs. 21.8).Source: §5 · p. 8
• The MILP selects 45.2% of Qwen and 41.2% of Gemini candidate eventualities on average, selecting fewer when narration time is scarcer.For Gemini, selection rises from 21.0% with under 5 seconds free to 91.8% with over 80 seconds; among selected events, 49.4% retain full variants. The Table 2 comparison shows the MILP’s advantage widens as solve time increases.Source: §5 · p. 8, Table 2 · p. 8
• The realistic filter removes LLM descriptions that exceed narration limits or conflict with timing; 28.9% of Qwen and 16.7% of Gemini generations exceed 300 WPM.Realistic variants score significantly worse than raw LLMs across all metrics, while the MILP satisfies the filter by construction.Source: §5 · p. 8
• Removing grounding lowered SODA-T (54.9 →47.8) and QEval-T (28.2 →16.0); removing compressed variants lowered CIDEr (12.9 →9.2) and QEval (48.4 →43.4).The authors attribute placement to grounding and greater retention of useful content to compression.Source: §5 · p. 9
• LLM salience scoring yields QEval=48.4 and QEval-T=28.2, versus 43.6 and 20.0 for random salience; oracle scores improve CIDEr (16.3–16.5 vs. 12.9), not temporal metrics.The reported differences suggest salience scoring primarily changes which content is selected rather than when it is delivered.Source: §5 · p. 9
• Screenplay descriptions yield the best QA performance (QEval=53.1; QEval-T=31.1), while temporal alignment falls (SODA-T 54.9 →47.7).The authors suggest screenplays better capture narrative intent, but their pre-production events can be harder to ground in final video.Source: §5 · p. 9

6 CONCLUSION

• The hybrid system uses LLMs to propose, ground, score, and compress visual events, then a mixed-integer linear program jointly decides across a scene.On REFRAMED, it achieves the strongest QA-based performance among automatic systems and improves over an LLM scheduler with the same structured inputs.Source: §6 · p. 9
• Ablations associate temporal grounding and compression with placement, and salience with story content retained; screenplay descriptions yield the largest QA-based gains.Oracle salience shows further content-selection headroom but does not consistently improve temporal placement or QA-based measures.Source: §6 · p. 9
• A substantial gap to professional describers remains in content selection and temporal realization; better narrative-salience and visual-grounding models are needed.The conclusion states these improvements can be incorporated as better inputs to the same global optimization framework.Source: §6 · pp. 9–10

AI USE STATEMENT

• The authors report using generative AI for coding implementation assistance and writing feedback, with manual review of AI-assisted work.They state it was not used for conceptual development, methodology, experiments, results interpretation, or several other listed research tasks.Source: AI USE STATEMENT · p. 10

A DETAILED WORKED EXAMPLE

• The input video is prepared as permissible dialogue-free narration times, a scene description segmented into eventualities, occurrence spans, compressed variants, durations, and salience scores.The example has 15 description elements and five compressed variants per element, in addition to the uncompressed version.Source: A DETAILED WORKED EXAMPLE · p. 14
• The optimizer chooses whether each eventuality is selected, its delivery start time, and which compressed wording variant to use.The resulting selected descriptions and start times form the generated AD script.Source: A DETAILED WORKED EXAMPLE · pp. 14–15
• With 36 seconds needed for the full description but only 14 seconds between dialogue, the example’s optimum selects five of 15 eventualities.Three fit in the first gap and two in the second; one selected description is shortened so the first gap ends at 10 seconds, while background details and e12 are omitted.Source: A DETAILED WORKED EXAMPLE · p. 14
• Table 4 shows each description’s on-screen occurrence and illustrative salience score, plus optimal delivery starts for selected eventualities; unselected ones are marked with a dash.The caption identifies occurrence and salience as distinct information from delivery time.Source: Table 4 · p. 15

B EVALUATION METRICS

• Dialogue-gap CIDEr and METEOR compare descriptions assigned to gaps; SODA-M scores aligned pairs, SODA-T measures references aligned within 10 seconds, and QEval measures narrative-answer accuracy.Scores are macro-averaged over sequences within each movie and then over movies; challenge-set sequences average 6.8 scenes, with 17.8 sequences per movie.Source: B EVALUATION METRICS · p. 15

C SCENE DESCRIPTIONS

• The scene-description appendix covers video-generated descriptions, supplied character information, and screenplay descriptions used as an alternative in ablations.These descriptions provide inputs from which the MILP’s candidate eventualities are drawn.Source: C SCENE DESCRIPTIONS · p. 16

C.1 LLM-GENERATED DESCRIPTION PROMPT

• The video-description prompt requests continuous, present-tense narrative prose with visually depicted details in visual order, and excludes audio, camera details, and repetitive information.It also directs the model to name characters only when established by supplied information and to vary description density with visual change.Source: §C.1 · p. 16

C.2 CHARACTER NAMING

• The system supports character naming with two complementary sources: speaker names added to subtitles and names and faces supplied to video-only LLMs from reference AD.The authors describe these as orthogonal, text-based and video-based approaches that models may both benefit from.Source: §C.2 · p. 16
• Face recognition against IMDb actor-headshot and character-name pairs achieves F1 = 73.7 on REFRAMED’s human-labeled test set.The pipeline filters recognized characters using AD-derived named entities, whose exact-match NER has P = 97.2, R = 96.6, and F1 = 96.9; reference AD is excluded from full-movie challenge-set inputs.Source: §C.2 · p. 16
• Speechmatics diarization separates character speakers with 12.8% confusion, 90.1% coverage, and 91.6% purity; combined with SDH-based naming, speaker identification reaches F1 = 77.9.SDH explicitly names speakers when they are not visually apparent, and the reported diarization comparison uses 10 post-production screenplays as gold standard.Source: §C.2 · p. 17

C.2.1 DIALOGUE SPEAKER IDENTIFICATION

• The identification pipeline combines speaker diarization with SDH-based character naming, then propagates names across dialogue segments in the same speaker cluster.Subtitle-level names are resolved to cast entries using full names, token subsequences, and common nicknames, accepting only unambiguous matches.Source: §C.2.1 · pp. 17–18
• Confusion falls to 12.8 and purity rises to 91.6 after Speechmatics clusters tagged as the AD narrator are removed, with missed rate increasing to 1.2.Before removal, Speechmatics Enhanced has confusion 15.8, purity 89.7, coverage 87.1, and missed rate 0.1.Source: §C.2.1 · p. 17, Table 5 · p. 18
• F1 = 77.9, +4.2 over the extractive variant: LLM-based name extraction with speaker-based propagation achieves the best overall character speaker identification results.Propagation raises recall from 3.3 to 69.3 for the extractive variant and from 4.1 to 74.5 for the LLM variant.Source: §C.2.1 · p. 19, Table 6 · p. 19

C.2.2 CHARACTER NAMES VIA SUBTITLE IDENTITIES AND AD NER

• Names extracted from SDH and US AD are resolved to IMDb character entries, and the most frequent combined name variation becomes the canonical form.US AD name extraction achieves exact-match P = 97.2, R = 96.6, and F1 = 96.9 against REFRAMED human annotation.Source: §C.2.2 · p. 20

C.2.3 CHARACTER FACE DETECTION

• F1 = 73.7 after NER-based filtering improves precision from 46.7 to 83.9 while recall declines from 71.7 to 65.7 on 230 labeled character faces.NER-based filtering is skipped for the full-movie challenge set, which is treated as a blind set.Source: §C.2.3 · p. 21

Description quality-assessment with QA evaluation

• QEval is 52.9% for screenplay scene descriptions, 47.7% for Gemini descriptions, 48.6% after adding character faces, and 50.6% after also adding speaker timing.Across 30 sampled movies, QEval and WIP have a moderate correlation (ρ = 0.52, p = 0.003), rising by about 9 points across the WIP range.Source: §C.3 · p. 22, Figure 5 · p. 22, Figure 6 · p. 22

Quantifying Screenplay–Movie Match

• WIP compares matched screenplay and movie dialogue words, multiplying match rates in both directions to measure alignment symmetrically on a [0,1] scale.The components represent screenplay dialogue retained in the movie and movie dialogue also present in the screenplay.Source: §C.3 · p. 22
• SIP adapts WIP’s deletion- and insertion-based structure to scenes, using the proportion of scenes with at least one aligned counterpart.SIP is bounded in [0,1] and is compared with WIP in Figure 4.Source: §C.3 · p. 23
• ρ = 0.87 (p = 0.002) for WIP versus SIP with human scene alignments, and ρ = 0.83 (p = 0.005) with automatic alignments.The comparison covers ten challenge-set movies; Figure 4 separates deletion and insertion components as well as overall scores.Source: §C.3 · p. 23
• WIP varies widely across the training and validation splits, reflecting the range of screenplay versions in MovieSum.The test split has no screenplays in REFRAMED.Source: §C.3 · p. 23, Figure 7 · p. 23

D LLM PROCESSING

• The candidate-generation prompt asks an LLM to ground each scene-description extract in a video span, produce AD wording and five compressed variants, and assign narrative salience.The output includes occurrence start and end times; content not visible or visually established receives null times and salience.Source: D LLM PROCESSING · pp. 23–24
• Two of the ten highest-WIP screenplay movies were excluded after inspection because MovieSum parsing errors affected screenplay structure or scene segmentation.The affected films were The Breakfast Club and Tár.Source: D LLM PROCESSING · p. 23

E LLM SCHEDULING

• The scheduler receives candidate descriptions, temporal spans, salience scores, durations, and dialogue gaps, then selects elements and assigns delivery start times.Each element may be selected at most once, and the scheduler may return no elements.Source: E LLM SCHEDULING · pp. 25–26

F.1 PUTTING OUT FIRES

• At [+87s], the example systems describe the scene differently: MILP says the woman holds a lighter, while MILP (screenplay) says she lights the box.At [+90s], their descriptions also diverge on whether flames erupt from the wastebasket or he tosses the phone onto the bed.Source: §F.1 · pp. 27–28

F.2 I’M NOT A BAD GUY

• The visual-description examples differ at [+5s]: American AD describes Mark facing an open laptop and typing, while MILP describes Marylin entering with a jacket.The screenplay variant says Mark types at a table and Marylin holds a coat.Source: §F.2 · p. 29
• After the attorney leaves, the examples vary: American AD says Mark lingers staring distantly, British AD says he looks thoughtful, and MILP describes him resuming work at his laptop.The screenplay variant says Mark smiles at the screen.Source: §F.2 · p. 30
• The sampled QA asks what Mark does after turning to face the young attorney, with waves, smiles, shrugs, frowns, and nods as options.The excerpt’s dialogue includes the attorney telling Mark, “You’re not an asshole, Mark.”Source: §F.2 · p. 30

F.3 WE HAVE GROUPIES

• The sequence identifies Christy and Alice as the women while Mark sits seriously at a wooden table.Source: §F.3 · p. 31
• From 16–36 seconds, MILP describes bathroom framing, passing legs, and kissing, while the screenplay details pinning, a nearby noise, and belt action.Source: §F.3 · p. 31
• From 40–60 seconds, American and British AD describe sexual actions and guard duty; MILP describes a belt adjustment and a later candlelit room, while the screenplay includes stall events and quiet glances.Source: §F.3 · p. 31
• In the restaurant, Mark spots Erica and approaches; she confronts him about his online insults and declines his request to speak privately.Source: §F.3 · p. 32
• Mark turns away and leaves the club, while Eduardo praises his choice and two women watch from the hall.Source: §F.3 · pp. 32–33
• A sampled QA item asks who is sitting with Erica, with “friends” among the answer choices.Source: §F.3 · p. 33