StoryTeller: Training-Free Narrative Grounding for Long-Form Audio Description¶
Conference: ECCV 2026
Paper: ECCV Official
Code: https://github.com/SEE-AI-Lab/ECCV2026_StoryTeller_StoryAD_QA
Area: Audio & Speech
Keywords: audio description, long-form video understanding, narrative grounding, retrieval-augmented generation, accessibility
TL;DR¶
StoryTeller is a training-free framework for long-form audio description that maintains an evolving identity graph and a salience-weighted narrative memory, generating grounded, cross-scene coherent descriptions from raw video and movie titles without task-specific tuning or curated character banks.
Background & Motivation¶
Audio description (AD) provides spoken narration between dialogue gaps to convey critical visual information for blind and low-vision (BLV) audiences. High-quality AD requires far more than transcribing isolated actions in a single frame: it must identify recurring characters, clarify causal context, and connect current scenes to the overarching story. Professional human narrators accomplish this because they digest the entire narrative arc before writing. However, manual AD authoring remains prohibitively expensive and time-consuming, while copyright restrictions on feature-length films severely hinder the collection and public distribution of large-scale AD datasets.
Automated AD systems have largely evolved along two constrained tracks. Supervised models such as AutoAD-I/II/III and MiCap achieve strong clip-level matching scores on curated datasets like LSMDC and MAD, but rely heavily on supervised fine-tuning, aligned subtitles, script transcripts, and precomputed face recognition banks. These prerequisites limit their scalability, reproducibility, and generalizability to new, unannotated media. Conversely, recent training-free methods like AutoAD-Zero and MM-Narrator remove task-specific parameter optimization, yet they still depend on manually prepared character banks or aligned external subtitles, while propagating context through shallow concatenation of adjacent captions without modeling how story significance evolves over long horizons.
Human viewers never retain every transient visual detail across hundreds of film scenes; rather, they maintain an evolving narrative representation where central protagonists, enduring conflicts, and pivotal relationships remain prominent while incidental visual clutter gradually fades. The core idea of StoryTeller is to maintain an explicit dual-track narrative state consisting of a dynamic identity graph and a reinforcement–decay salience memory, admitting candidate facts through two-stage semantic filtering and VLM verification to achieve coherent, training-free long-form narrative grounding.
Method¶
Overall Architecture¶
StoryTeller takes as input a sequence of chronological video clips \(\{v_1, \dots, v_T\}\) and the movie title. Throughout processing, the system maintains a persistent narrative state \(\mathcal{S}_{t-1} = (\mathcal{G}_{t-1}, \mathcal{M}_{t-1})\), where \(\mathcal{G}_{t-1}\) is the identity graph tracking visual character representations and \(\mathcal{M}_{t-1}\) is the narrative memory storing verified story facts alongside their continuous salience weights.
For each incoming clip \(v_t\), StoryTeller updates the narrative state via \(\mathcal{S}_t = \Phi(v_t, \mathcal{S}_{t-1})\) through three sequential steps: first, it associates detected face tracklets with existing nodes or creates anonymous clusters in the identity graph; second, it induces structured fact candidates conditioned on scene summaries, public title-keyed metadata, and prior memory, screening them with a fast semantic filter and a strict VLM visual verifier; third, it applies reinforcement–decay dynamics to adjust memory salience weights. The updated state then conditions the final audio description synthesis.
%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
A["Input: Video clip sequence v_t and movie title"] --> B["Dynamic Identity Graph and Unsupervised Reseeding<br/>ArcFace tracklet clustering + progressive anonymous naming"]
B --> C["Structured Fact Induction and Dual-Stage Verification<br/>Candidate quadruple extraction + semantic filter + VLM verifier"]
C --> D["Salience-Based Narrative Memory with Reinforcement-Decay<br/>Cosine relevance drives dynamic weight updating and decay"]
D --> E["Output: Narrative-grounded audio description text"]
Key Designs¶
1. Dynamic Identity Graph and Unsupervised Reseeding: Eliminating offline character banks
Conventional identity-aware AD methods depend on static character banks with precomputed face embeddings and ground-truth name tags. In contrast, StoryTeller maintains an online-updated identity graph \(\mathcal{G}_t = \{(c_j, \boldsymbol{\mu}_j)\}_{j=1}^{N_t}\). In clip \(v_t\), detected faces across consecutive frames are grouped into tracklets \(T_k\). A pretrained ArcFace encoder \(\phi\) extracts face embeddings \(\mathbf{v}_{t,i} = \phi(\mathbf{x}_{t,i})\), which are averaged across the tracklet to form \(\mathbf{e}_k = \frac{1}{|T_k|} \sum \mathbf{v}_{t,i}\). For each tracklet, cosine similarity is computed against existing character mean embeddings \(\boldsymbol{\mu}_j\):
If \(\cos(\mathbf{e}_k, \boldsymbol{\mu}_{j^*}) > \tau\) (calibrated to \(\tau = 0.58\)), the tracklet is assigned to identity \(c_{j^*}\) and updates \(\boldsymbol{\mu}_{j^*}\); otherwise, a new anonymous identity node is instantiated. To handle narrative delays where characters appear before their names are spoken, the identity reseeding mechanism allows initial anonymous clusters to be bound to character names once subsequent scenes provide verified visual and textual evidence, retroactively propagating identity references without requiring offline supervised face labels.
2. Structured Fact Induction and Dual-Stage Verification: Preventing multimodal hallucination leakage
While external metadata (e.g., public IMDb plot summaries) helps resolve proper names and background context, feeding raw retrieved text directly into description models often causes severe hallucinations. StoryTeller establishes a two-stage hypothesis-and-verification funnel. The model first produces a concise scene summary \(s_t\), embeds it as \(\mathbf{s}_t = \varepsilon(s_t)\), and retrieves relevant IMDb paragraphs. Conditioned on \(\mathcal{G}_t\), \(\mathcal{M}_{t-1}\), and retrieved metadata, a lightweight VLM proposes candidate structured quadruples \(f = (\text{subject}, \text{action}, \text{object}, \text{context})\).
To bypass the prohibitive computational cost of verifying every candidate with a heavy VLM, StoryTeller employs a rapid vector-based semantic filter:
where \(\mathbf{z}_f = \varepsilon(f)\), retaining only candidates satisfying \(g_f > \sigma\) (calibrated to \(\sigma = 0.20\)). Running roughly 3,000\(\times\) faster than full model inference, this step discards irrelevant hypotheses instantaneously. Surviving candidates are submitted to a dedicated VLM verifier (Qwen3-VL-8B-Thinking), which outputs a binary ACCEPT or REJECT judgment grounded strictly in video evidence. Facts pass into memory only if visually confirmed by the clip, preventing unobserved metadata plots from polluting the narrative state.
3. Salience-Based Narrative Memory with Reinforcement–Decay: Modeling human-like story dynamics
Accumulating unpruned history over a feature-length movie creates context fragmentation and dilutes crucial plot threads. StoryTeller structures narrative memory as \(\mathcal{M}_t = \{(f_m, w_m^{(t)})\}_{m=1}^{M_t}\), initializing each newly verified entry with \(w_m^{(0)} = 0.25\). At time step \(t\), the semantic relevance between the current scene summary \(\mathbf{s}_t\) and stored fact embedding \(\mathbf{z}_m\) is evaluated:
All memory weights evolve dynamically across time according to:
where \(\lambda \in (0, 1)\) acts as a decay factor and \(\alpha\) governs reinforcement strength. When a narrative element (such as an injury or a recurring key object) remains relevant to current events, \(r_m^{(t)} > 0\) and its salience is reinforced. Conversely, transient episodic details with \(r_m^{(t)} \approx 0\) decay exponentially with each scene step. This allows the model to prioritize core story trajectories while naturally discarding obsolete visual details.
A Worked Example¶
Consider a scene from a fantasy movie: an unfamiliar character with distinct facial scars and a prosthetic eye appears at a podium holding a jar containing a spider. The identity module assigns this appearance to anonymous node Person_A and registers the verified candidate (Person_A, holds, a spider, classroom). In a later dialogue scene, chalkboard text and narrative cues reveal his identity as Professor Mad-Eye Moody. The identity reseeding mechanism binds Person_A to Mad-Eye Moody, updating graph embeddings and historical fact representations.
In the subsequent scene, students cower as the spider moves across a desk. While a baseline VLM lacking narrative memory erroneously identifies the figure as Dumbledore casting a spell, StoryTeller retrieves the high-salience fact (Mad-Eye Moody, holds, spider, classroom) and generates: "Mad Eye Moody presents a spider to the class. A boy covers his head as a spider crawls on it," preserving narrative accuracy across discontinuous scenes.
Key Experimental Results¶
Main Results¶
StoryTeller was evaluated on the MAD-Eval benchmark (10 full-length feature films from LSMDC) and the proposed StoryAD-QA benchmark. StoryAD-QA evaluates long-range narrative retention across two tracks: Track A (segment-only QA across 30s to 240s windows) and Track B (context-conditioned QA where the answerer receives only the 30s main-clip AD text with no video access, answering questions conditioned on 30s, 60s, or 90s of preceding video context).
The table below presents comparative performance on MAD-Eval against supervised and training-free baselines:
| Model | Train | Curated Res. | Public Meta. | VLM Backbone | CIDEr | SPICE | ROUGE-L |
|---|---|---|---|---|---|---|---|
| AutoAD-I | ✓ | ✓ | ✗ | - | 14.3 | 4.4 | 11.9 |
| AutoAD-II | ✓ | ✓ | ✗ | - | 19.2 | - | 13.4 |
| AutoAD-III | ✓ | ✓ | ✗ | - | 24.0 | - | - |
| MM-Vid | ✗ | ✓ | ✓ | GPT-4V | 6.1 | 6.1 | 9.8 |
| MM-Narrator | ✗ | ✓ | ✓ | GPT-4 | 13.9 | 5.2 | 13.4 |
| AutoAD-Zero | ✗ | ✓ | ✓ | VideoLLaMA2 | 22.4 | 7.3 | 14.4 |
| StoryTeller (Ours) | ✗ | ✗ | ✓ | VideoLLaMA2 | 19.1 | 9.0 | 16.0 |
| StoryTeller (Ours) | ✗ | ✗ | ✓ | Qwen3-VL | 21.4 | 6.7 | 15.3 |
The table below reports question-answering accuracy on StoryAD-QA:
| Model / Setting | Track A: 30s | Track A: 60s | Track A: 120s | Track A: 240s | Track B: 30+30s | Track B: 60+30s | Track B: 90+30s |
|---|---|---|---|---|---|---|---|
| Reference AD (Human) | 0.953 | 0.963 | 0.995 | 0.981 | 0.828 | 0.825 | 0.806 |
| AutoAD-Zero | 0.840 | 0.830 | 0.896 | 0.917 | 0.662 | 0.654 | 0.673 |
| StoryTeller (Ours) | 0.892 | 0.928 | 0.953 | 0.972 | 0.754 | 0.716 | 0.788 |
| Absolute Gain over AutoAD-Zero | +5.2% | +9.8% | +5.7% | +5.5% | +9.2% | +6.2% | +11.5% |
Ablation Study¶
Ablation experiments conducted on MAD-Eval systematically isolate each component (using the unified Qwen3-VL backbone):
| Variant | Public Meta. | Identity | Schema | Memory | CIDEr | SPICE | ROUGE-L |
|---|---|---|---|---|---|---|---|
| StoryTeller (Full) | ✓ | ✓ | ✓ | ✓ | 21.4 | 6.7 | 15.3 |
| A1: VLM only | ✗ | ✗ | ✗ | ✗ | 11.4 | 4.3 | 9.6 |
| A2: No schema | ✓ | ✓ | ✗ | ✓ | 15.4 | 4.4 | 12.5 |
| A3: No memory | ✓ | ✓ | ✓ | ✗ | 18.0 | 6.0 | 13.2 |
| A4: No identity | ✓ | ✗ | ✓ | ✓ | 17.9 | 5.6 | 12.3 |
| A5: No IMDb metadata | ✗ | ✓ | ✓ | ✓ | 17.2 | 4.8 | 12.2 |
Ablation results on StoryAD-QA narrative comprehension show pronounced drops over longer horizons: - On Track A at 240s, removing narrative memory (A3) drops accuracy from 0.972 to 0.891 (-8.1 points), while disabling IMDb retrieval (A5) drops it to 0.901; - On Track B in the challenging 90+30s setting, removing structured schema extraction (A2) reduces accuracy to 0.751, and eliminating identity tracking (A4) drops accuracy to 0.774, compared to 0.788 for the full model.
Key Findings¶
- Narrative comprehension versus surface caption overlap: Traditional n-gram matching metrics (CIDEr, SPICE) penalize descriptions that prioritize long-range character grounding over exact local phrasing. Under StoryAD-QA's context-conditioned Track B (90+30s), StoryTeller outperforms AutoAD-Zero by 11.5 percentage points (0.788 vs 0.673), demonstrating that its descriptions effectively carry forward plot-critical information needed by non-sighted listeners.
- Interdependence between identity tracking and external metadata: External metadata alone cannot sustain character coherence. Variant A4 (retaining IMDb metadata but removing identity tracking) exhibits relative drops of 16.4% in CIDEr and 19.6% in ROUGE-L, confirming that textual character names must be anchored to continuous visual tracklets.
- Dual-stage verification throughput and factual safety: Pre-filtering with cosine similarity runs ~3,000\(\times\) faster than VLM forward passes, pruning over 80% of spurious candidates. This enables full-length feature film processing in 3–4 hours on a single A100 GPU while VLM verification guarantees zero hallucinated metadata insertion.
Highlights & Insights¶
- Completely training-free, zero-annotation AD pipeline: StoryTeller eliminates dependencies on task-specific fine-tuning, aligned audio transcripts, subtitle files, and manually precomputed face banks, providing a practical blueprint for zero-shot movie accessibility.
- Biologically inspired reinforcement–decay memory dynamics: The system mirrors human cognitive salience management by reinforcing recurrent narrative facts and decaying obsolete background details, preventing memory explosion without sacrificing context.
- Narrative comprehension benchmark via blind QA: StoryAD-QA introduces an evaluation paradigm where answering LLMs access only generated descriptions without video input, directly measuring how well AD conveys narrative causality to visually impaired audiences.
Limitations & Future Work¶
- Admitted limitations: Under severe occlusions, extreme lighting, or rapid motion blur, ArcFace tracklet clustering may fragment, leading to duplicate identity nodes; additionally, minor background characters absent from public metadata cannot be readily resolved by name.
- Observed limitations: Narrative memory focuses heavily on entity actions and interactions, offering coarse representation of environmental transitions (e.g., temporal jumps, geographical shifts) or non-human narrative cues (e.g., written letters, ticking clock displays). Furthermore, generation operates on fixed clip intervals rather than dynamically aligning with acoustic speech gaps in movie audio tracks.
- Future directions: Integrating body pose and clothing Re-ID into the identity graph would bolster tracking across occlusions; pairing the pipeline with voice activity detection (VAD) would enable speech-gap-aware adaptive narration timing and speech rate modulation.
Related Work & Insights¶
- vs AutoAD Series (AutoAD-I/II/III, CVPR/ICCV): The AutoAD family requires supervised training on aligned movie datasets and depends on pre-annotated character face banks. StoryTeller is fully training-free and constructs identity graphs dynamically from raw video.
- vs AutoAD-Zero (ACCV 2024): AutoAD-Zero operates training-free but still requires curated character banks and propagates context via shallow caption concatenation. StoryTeller eliminates character banks and achieves +11.5% accuracy in cross-scene narrative QA.
- vs MM-Narrator (CVPR 2024): MM-Narrator relies on proprietary GPT-4 multimodal in-context learning and is vulnerable to ungrounded hallucinations. StoryTeller utilizes open-source models with strict two-stage visual fact verification to guarantee fidelity.
Rating¶
- Novelty: ⭐⭐⭐⭐☆ [Dynamic identity reseeding combined with reinforcement–decay narrative memory presents an elegant, human-like approach to long-form video grounding]
- Experimental Thoroughness: ⭐⭐⭐⭐⭐ [Extensive evaluations across MAD-Eval, detailed ablations, and the introduction of the 2,574-question StoryAD-QA benchmark]
- Writing Quality: ⭐⭐⭐⭐⭐ [Clear structural organization, rigorous technical formulation, and comprehensive narrative context]
- Value: ⭐⭐⭐⭐⭐ [Substantially advances accessible media technologies by enabling practical, training-free AD generation on unseen feature films]