Rapid advances in video analytics have fueled the development of innovative applications across various fields. In medical education, surgery videos enhance students' procedural knowledge by illustrating complex temporal and spatial events [38]. In biology, scientists use wildlife footage to study organism behaviors and interactions in their natural habitats [34,92]. In transportation, traffic surveillance systems analyze and manage traffic flow, improving urban mobility [43]. Across these applications, analysts seek to query video databases for events characterized by spatio-temporal and semantic interactions. For instance, an analyst might search for "a motorcycle swerving near a silver Subaru and then colliding with it" or "a doctor holding a scalpel before placing it on a table. " ○ automatically builds new UDFs, 3
○ updates its available UDF list, 4 ○ reparses the query, and 5 ○ executes the query to return matching video segments. VOCAL-UDF supports both program-based UDFs (i.e., Python functions) and distilled-model UDFs (i.e., ML models) for diverse concepts.
Though promising, answering video queries using frontier vision-language models (VLMs) remains underwhelming. Although VLMs have demonstrated notable capabilities on diverse, challenging tasks [68,69,87], they struggle to answer compositional queries [74] that involve recognizing objects (e.g., "car", "truck"), reasoning about relationships (e.g., "behind", "holding"), and identifying attributes (e.g., "silver color", "Subaru make"). This challenge is further amplified when queries require temporal reasoning [112] (e.g., "X then Y", "X for at least 10 seconds"). While new models continue to improve their ability to reason spatially [19] and compositionally [52], their performance remains low [103]. Additionally, deploying large models at scale is prohibitively expensive [84] and inference is slow [99]. For example, current VLMs can only achieve a throughput of around 100 tokens per second [3,10], making their use in large-scale video analytics intractable.
Alternatively, workflow-oriented video data management systems (VDBMSs) answer compositional queries by decomposing them into granular subtasks [8,13,39,42,76,94,97,118]. Submodules identify and track objects, attributes, and relationships across frames, forming spatio-temporal scene graphs [53,63]. These scene graphs can expressively represent many complex visual queries. Various scene graph generation techniques [31,116] have been proposed to extract scene graphs from images and videos. In these systems, subtasks that extract scene graph elements are solved individually and then composed to answer a compositional query [71].
However, VDBMSs make a critical assumption: the existence of modules capable of executing subtasks to answer a complex query. Systems typically provide a variety of built-in modules [42,76,94,97,118] and often allow extensibility via user-defined functions (UDFs) for unsupported scenarios [54,107,118]. Concerning our motorcycle query, a user might need to supply a UDF to filter for "silver" or nearby objects if the system lacks these capabilities. Despite the availability of pretrained computer vision models that can be readily integrated as UDFs, users may require solutions for domain-specific applications or seek to identify fine-grained object classes and subjective concepts for which no off-the-shelf models exist. Identifying or adapting domain-specific models in such cases may be possible, though tedious. Additionally, it may be necessary to-on a per-UDF basis-curate datasets and perform extensive training to achieve satisfactory performance [8].
To address these challenges, we present VOCAL-UDF (Figure 1), a self-enhancing VDBMS that empowers users to flexibly issue and answer compositional queries, even when the necessary modules are unavailable. To use VOCAL-UDF, a user only needs to provide a video dataset and a Table 2. Relational views for query execution with UDFs.
ObjView(vid, video_pixels) RelView(vid, fid, pixels, rid, o1_o2_rnames, o2_o1_rnames, o1_oid, o1_x1, o1_y1, o1_x2, o1_y2, o1_anames, o2_oid, o2_x1, o2_x2, o2_y1, o2_y2, o2_anames) AttrView(vid, fid, pixels, oid, oname, x1, y1, x2, y2, anames) Listing 1. An example of the query language.
% The first graph detects a car far from a truck g1(vid, fid, fid, oid1, oid2) :-Objects(vid, fid, oid1, 'car', _, _, _, _), Objects(vid, fid, oid2, 'truck', _, _, _, _), Relationships(vid, fid, _, oid1, 'far', oid2), oid1 != oid2. % The second graph detects the 'near' relationship g2(vid, fid, oid1, oid2) :-Relationships(vid, fid, _, oid1, 'near', oid2), oid1 != oid2. % Use recursive rules to declare duration constraints g2_star(vid, fid, fid, oid1, oid2) :-g2(vid, fid, oid1, oid2). g2_star(vid, fid_start, fid_end, oid1, oid2) :-g2_star(vid, fid_start, fid, oid1, oid2), g2(vid, fid_end, oid1, oid2), fid_end = fid + 1. % Finally, define the temporal order of the two region graphs q(vid) :-g1(vid, fid11, fid12, oid1, oid2), g2_star(vid, fid21, fid22, oid1, oid2), fid21 > fid12, fid22 -fid21 + 1 > 10 * 24. % Assume 24 frames per second VOCAL-UDF leverages EQUI-VOCAL's [118] scene graph data model and query language, which models compositional video events as spatio-temporal scene graphs. This approach draws from cognitive foundations in human perception [14,64,115] and enables a variety of compositional queries [118]. This section summarizes key background information about these concepts.
Data model. In VOCAL-UDF, each video comprises a series of 𝑁 frames {𝑓 1 , . . . , 𝑓 𝑁 }. The visual content of each frame is represented by a scene graph 𝑔 𝑖 = (o 𝑖 , r 𝑖 ), capturing all objects o 𝑖 and all relationships r 𝑖 between those objects within the frame at some time. Objects may also possess attributes. While a relationship links two objects, an attribute is attached to one object. A region graph 𝑔 𝑖 𝑗 is a subgraph of 𝑔 𝑖 , i.e., 𝑔 𝑖 𝑗 ⊆ 𝑔 𝑖 , that contains information critical for identifying an event. Finally, an event 𝑒 is a sequence of region graphs 𝑒 = {𝑔 1 , . . . , 𝑔 𝑘 }, where region graphs with a smaller index occur earlier in time than those with a larger index, but they do not need to be contiguous or distinct. The relational schema in Table 1 captures the scene graphs data model.
Query language. In VOCAL-UDF, a query identifies video segments that match a user-specified event. VOCAL-UDF supports relational queries over the schema in Table 1, which are of the following form. Using Datalog notation: 𝑞(𝑣𝑖𝑑) :-𝑔 1 , . . . , 𝑔 𝑘 , p, d, 𝑤, where 𝑔 1 , . . . , 𝑔 𝑘 is a temporally ordered sequence of region graphs specifying that a matching event consists of 𝑔 1 , followed by 𝑔 2 , followed by 𝑔 3 , etc. Each 𝑔 𝑖 can persist for multiple frames and there can be other frames between 𝑔 𝑖 and 𝑔 𝑖+1 . p is a set of predicates that are applied to objects, relationships, and attributes in region graphs. d is a set of constraints on the duration for which a region graph must remain valid before transitioning to the next one. Lastly, 𝑤 is the maximum number of frames between 𝑔 1 and 𝑔 𝑘 . As an example, the event "A car is initially far from a truck, then remains close to the truck for more than 10 seconds" can be expressed as in Listing 1.
DSL. VOCAL-UDF adopts EQUI-VOCAL's domain-specific language (DSL) [118], which encapsulates query logic while abstracting away SQL details. The query executor compiles these DSL queries into efficient SQL for execution over relational tables. Using the DSL, the same event can be expressed as (assuming 24 frames per second): (Car(𝑜 1 ), truck(𝑜 2 ), far(𝑜 1 , 𝑜 2 ); Duration(near(𝑜 1 , 𝑜 2 ), 240). In this DSL, the variable 𝑜 represents an arbitrary object in a query, with distinct subscripts indicating objects with different 𝑜𝑖𝑑's. All predicates in a region graph are separated by commas. Region graphs are then sequenced in temporal order using semicolons. Each region graph can Self-Enhancing Video Data Management System for Compositional Events with Large Language Models 215:5 Listing 2. SQL query to identify frames where a silver car is behind a truck. SELECT DISTINCT f.vid, f.fid, o1.oid, o2.oid FROM frames f, objects AS o1, objects AS o2 WHERE f.vid = o1.vid AND f.fid = o1.fid AND o1.vid = o2.vid AND o1.fid = o2.fid AND o1.oid <> o2.oid AND car(o1.oname) = TRUE AND truck(o2.oname) = TRUE AND behind(o1.y1, o1.y2, o2.y1, o2.y2) = TRUE AND silver(f.pixels, o1.x1, o1.y1, o1.x2, o1.y2) = TRUE persist for multiple frames and there can be other frames between two adjacent region graphs. Finally, Duration(𝑔, 𝑑) stipulates that the region graph 𝑔 exists in at least 𝑑 consecutive frames. The query returns a set of video segment identifiers.
In this section, we formalize the types of UDFs supported by VOCAL-UDF. These UDFs allow users to define custom objects, relationships, and attributes. We then describe how UDFs are compiled and executed in VOCAL-UDF.
Table 1 shows VOCAL-UDF's relational schema. The Frames relation includes a virtual pixels column that stores the frame pixel values in a 3D array (𝐻 × 𝑊 × 3, where 𝐻 is height, 𝑊 is width, and 3 represents the color channels). The Objects, Relationships, and Attributes relations store corresponding detected frame elements.
A UDF extends database functionality. A typical UDF takes columns as input, returns a scalar value or a row set, and is used in SQL statements, e.g., in WHERE clauses. When querying video databases, VOCAL-UDF supports generating and executing UDFs to identify custom objects, relationships, and attributes, enabling users to find complex, compositional events. Listing 2 shows an example SQL query with UDFs for the objects car and truck, the relationship behind, and the attribute silver. VOCAL-UDF supports imperative and declarative Python-based UDFs, and are categorized into the following classes: relationship, attribute, object, and value-lookup.
A relationship UDF or attribute UDF is a deterministic, scalar predicate that indicates whether an input exhibits a specified relationship or attribute. It accepts zero (i.e., a dummy UDF; see Section 4.4.2) or more columns as arguments and produces a boolean result. The parameters can include any of the following columns from each table in the SQL query's FROM clause: pixels, oname, x1, y1, x2, y2, rname, and aname. VOCAL-UDF restricts relationship UDFs and attribute UDFs to be frame-level, i.e., they operate on object(s) within the same frame. Therefore, input arguments are all from the same video frame (identified by vid and fid) and are associated with one or two distinct objects. As an example, we might define a relationship UDF to indicate whether object 𝑜 1 is behind another object 𝑜 2 by comparing their centroid 𝑦-coordinates:
We could also define an attribute UDF to indicate if a detected car is silver by running an ML model over the frame pixels:
def silver(pixels, x1, y1, x2, y2): cropped_img = pixels[y1:y2, x1:x2] is_silver = awesome_color_classifier(cropped_img) return is_silver
An object UDF requires localizing, classifying, and tracking objects in videos. Instead of returning a boolean value, it is a table-valued function that takes a video segment, video_pixels, as input. A video segment comprises frames with the same vid concatenated into a 4D array with an additional dimension for the frame index. An object UDF detects and tracks objects of a specific class. Given a video segment, the UDF makes calls to a custom object detection and tracking model and returns a row set, which follows the Objects schema listing the detected and tracked objects. As an example, we can define an object UDF that detects all cars in a video:
def car(video_pixels): obj_tuples = [] car_detector, tracker = load_models() for frame in video_pixels: detected_cars = car_detector(frame) tracked_objs = tracker.update(detected_cars) obj_tuples.extend(tracked_objs) return obj_tuples
In this paper, we assume that object UDFs are given and focus on proposing and generating relationship and attribute UDFs. We leave the extension to object UDFs for future work.
A value-lookup UDF is a class of UDFs that simply encapsulate a predicate over existing column values. As an example, suppose the value "car" is in the domain of the object oname. Then, a value-lookup UDF can be defined as:
While value-lookup UDFs are not strictly necessary, as they can be directly and easily expressed in SQL statements, we wrap all predicates of our DSL queries in UDFs to simplify the compilation from the DSL to SQL.
UDFs can have different lists of parameters in their signatures. To execute a query with UDFs, VOCAL-UDF first constructs the relational views as shown in Table 2 derived from the relations in Table 1. The views-ObjView, RelView and AttrView-contain all attributes that an object UDF, relationship UDF, and attribute UDF can potentially accept as input arguments, respectively. For simplicity, VOCAL-UDF generates UDFs with a uniform list of parameters for each class.
Object, relationship, and attribute UDFs can be expensive to evaluate, as they may operate on image pixels and invoke ML models. To optimize query execution, VOCAL-UDF caches the results of all UDFs and replaces them with value-lookup UDFs. When executing a UDF over a video corpus for the first time, VOCAL-UDF materializes the results to make it available as a value in the corresponding column and substitutes the UDF with a value-lookup UDF of the same name. For example, when running a query with the silver attribute UDF for the first time, VOCAL-UDF evaluates the UDF for each object in the video corpus. If an object OID1 in a frame F1 of a video segment V1 is classified as silver, VOCAL-UDF inserts a new row with values (V1, F1, OID1, 'silver') into the Attributes relation. Then, VOCAL-UDF replaces the silver attribute UDF with a valuelookup UDF that checks whether the aname is 'silver'. Reusing the results of predicate evaluation for query optimization is a long-standing research topic [36,78,89,107] and is not the focus of this paper. Batch inference can further accelerate ML-based UDFs.
VOCAL-UDF needs to address several challenges. First, it must determine whether existing UDFs can adequately answer a user query, or if new UDFs should be created (C1). Second, VOCAL-UDF should support implementing UDFs drawn from diverse range of semantic concepts (C2). Third, since VOCAL-UDF utilizes error-prone LLMs to generate UDFs, it is crucial to ensure high quality in the produced UDFs (C3). We now discuss our solutions to each challenge. Figure 2 shows the architecture of VOCAL-UDF. The user initializes the system with a video dataset and an optional set of UDFs. After preprocessing (Section 5), the user can issue NL queries to identify compositional events within the videos. The Query Parser (Section 4.1) parses the query into the DSL notation described in Section 2. If successful, the DSL query is passed to the Query Executor to find all matching videos in the dataset. If the query contains predicates that existing UDFs cannot resolve, the UDF Proposer (Section 4.1) is invoked to propose the names and descriptions of new UDFs. The UDF Generator (Sections 4.2 and 4.3) creates executable candidates for each proposed UDF. Next, the UDF Selector (Section 4.4) solicits user labels to select the implementation that best aligns with the user's intent. With updated UDFs, the Query Parser re-parses the query for execution. The Storage Manager maintains raw videos, relational data, and available UDFs.
The Query Parser converts NL queries into our DSL and determines the need for new UDFs. VOCAL-UDF must understand the semantics of the user's query and available UDFs, mapping each part of the query to an existing UDF or suggesting the creation of a new one. Moreover, VOCAL-UDF needs to be resilient to the linguistic ambiguities and synonymous terms in NL queries.
VOCAL-UDF utilizes LLMs to convert complex NL to a consistent DSL format. LLMs show strong capabilities in SQL and program generations [42,83,100] via in-context learning without finetuning. We incorporate domain-specific constraints into LLM prompts to ensure adherence to DSL grammar and conduct post-verification to ensure syntax correctness. Inspired by Wang et. al. [100] and Hsieh et. al. [50], VOCAL-UDF provides the DSL definition, UDF format, and descriptions of available UDFs as NL documentation. This enables VOCAL-UDF to generate grammatically correct DSL queries, determine whether new UDFs need to be created, and interact with LLMs in a zero-shot manner (C1). While VOCAL-UDF focuses on zero-shot prompting, introducing few-shot examples [15] could potentially further improve UDF proposal performance. However, referencing unavailable UDFs in examples may lead LLMs to incorrectly assume their availability at query time. Since the available UDFs can change as the database evolves, examples must be carefully curated for different database states. Figuring out the optimal prompting strategy, though beneficial, is not the focus of this paper. An example prompt is shown in our technical report [119].
To enhance LLM response reliability, VOCAL-UDF performs post-verification of the generated DSL query to ensure it is syntactically valid and only uses available UDFs. If parse errors occur, VOCAL-UDF appends the error message to the context and asks the LLM to make another attempt.
When the query contains predicates that cannot be resolved using the available UDFs, we prompt the LLM to identify this and propose new UDFs. The output from this process is the function signature and textual description of the proposed UDF generated by the LLM. In case of a query with multiple missing UDFs, VOCAL-UDF returns a list of proposed UDFs and will generate them one by one. An example proposed UDF of behind is: {"signature": "behind(o0, o1)", "description": "Whether o0 is behind o1"} Since both the Query Parser and UDF Proposer utilize LLMs, their outputs may sometimes be inaccurate. If the LLM proposes fewer UDFs than needed, it may make performance improvements less noticeable but will not degrade performance. Conversely, proposing more UDFs can increase system runtime and monetary costs; however, as detailed in Section 4.4, we have implemented techniques to ensure that generated UDFs (whether superfluous or inaccurate) do not adversely affect performance. Finally, users may also rephrase their NL query if they are not fully satisfied with the query results.
We show the effectiveness of our approach empirically in Section 6 for queries with detailed and explicit descriptions. Semantic parsing (e.g., text-to-SQL) is a highly active research area with significant recent advances [35,40,58,114,120]. While current methods still fall short of humanlevel performance [67], improving text-to-SQL is not the goal of our paper. VOCAL-UDF focuses on the efficient generation of missing UDFs, relies on LLMs currently adequate performance for text-to-SQL in our context, and will benefit from future advances in this area.
The UDF Generator implements executable UDFs based on the LLM-proposed UDF signatures and descriptions. As discussed, VOCAL-UDF should produce high-quality UDFs (C3) for a wide range of semantic concepts (C2). While VOCAL-UDF leverages the programming capabilities of LLMs [16,20,24,90] to generate UDFs as Python programs, more work is required. Some tasks require complex visual understanding, rendering it challenging to solve via programs (e.g., determining a car's make). Additionally, even the most advanced LLMs remain error-prone and their programming performance for nuanced tasks is not yet on par with humans.
To address the first problem, VOCAL-UDF supports two types of UDF implementations: programbased UDFs, which are Python programs generated by LLMs (Section 4.2), and distilled-model UDFs, which are lightweight vision models distilled from strong pretrained models (Section 4.3). To improve generated UDF quality, VOCAL-UDF uses a two-step approach by verifying both syntactic (Section 4.2.2) and semantic (Section 4.4) correctness.
At a high level, given a UDF signature ℎ and description 𝑑, a video database instance 𝐼 over schema 𝑅, VOCAL-UDF performs the following steps to generate a UDF 𝑝:
1. Generate UDF candidates using an LLM. Given ℎ, 𝑑, 𝐼 , and 𝑅, VOCAL-UDF prompts an LLM to generate a set of 𝑘 candidate Python functions {𝑝 1 , ..., 𝑝 𝑘 }. 2. Syntactically verify candidates. VOCAL-UDF executes each candidate 𝑝 𝑖 on a small dataset sampled from 𝐼 to verify syntactic correctness, ensuring that all passing candidates are executable. 3. Semantically verify candidates. VOCAL-UDF finally evaluates the semantic correctness of the remaining candidates and selects the best one (see Section 4.4).
We next describe each step in further detail.
In its most basic form, VOCAL-UDF prompts the LLM to generate a program 𝑝 based on the UDF signature ℎ and description 𝑑. To ensure 𝑝 can be eventually expressed as a SQL predicate, VOCAL-UDF rewrites ℎ in the DSL format to ℎ ′ that accepts columns from the schema 𝑅 as inputs. For example, the behind function is rewritten from behind(o0, o1) to behind(o1_y1, o1_y2, o2_y1, o2_y2), where o1_y1, o1_y2, o2_y1, o2_y2 are columns of 𝑅. The generated Python program's input is a set of attribute values that correspond to one or two objects in the video def behind(o1_y1, o1_y2, o2_y1, o2_y2): o1_center_y = (o1_y1 + o1_y2) / 2 o2_center_y = (o2_y1 + o2_y2) / 2 return o1_center_y < o2_center_y def behind(o0_aname, o1_aname): return o0_aname == 'location_top' and o1_aname == 'location_bottom' def behind(o1_y1, o1_y2, o2_y1, o2_y2, **kwargs): thresh = kwargs.get('threshold', 50) o1_cy = (o1_y1 + o1_y2) / 2 o2_cy = (o2_y1 + o2_y2) / 2 return o2_cy -o1_cy > thresh
Interpretation 𝒔 𝟑 : Uses the respective positions of the two objects to determine if o0 is behind o1.
Interpretation 𝐬 𝟐 : check if the center of o0 is behind the center of o1 along the y-axis, based on a threshold distance.
Interpretation 𝒔 𝟏 : check if the center of o0 is positioned behind the center of o1 along the y-axis.
1
Program 𝒑 𝟏 :
Program 𝒑 𝟐 :
Program 𝒑 𝟑 :
Fig. 3. Program candidates, using behind as an example.
database, depending on the number of variables in ℎ. It generates code that operates on those values, including the pixels column, and returns a boolean indicating if the predicate is satisfied or not. Figure 3 (program 𝑝 1 ) shows an example program UDF for the behind(•) predicate.
To generate quality UDFs, VOCAL-UDF must resolve three challenges. First, NL descriptions are often ambiguous and may not entirely capture the user intent [65] (e.g., user-specific definition of "far"). Second, predicates in video compositional queries often include hyperparameters that require tuning [76,77] for different datasets and user intents, e.g., determining the threshold distance for the "far" relationship. Lastly, as VOCAL-UDF expands its collection of UDFs and database incrementally, it is essential that new UDFs be able to utilize results from previously established ones.
To address linguistic ambiguity, we provide the LLM with ℎ ′ and 𝑑 and ask it to generate a list of 𝑘 candidate programs with a variety of semantic interpretations: 𝐶 = {(𝑝 1 , 𝑠 1 ), • • • , (𝑝 𝑘 , 𝑠 𝑘 )}, where 𝑝 𝑖 and 𝑠 𝑖 respectively denote a Python program and its semantic interpretation. [119] shows an example prompt used by VOCAL-UDF in this step. Later, VOCAL-UDF verifies and selects one program for each proposed UDF. See Figure 3 for candidate program examples.
To resolve the challenge of parametric predicates, VOCAL-UDF additionally prompts the LLM to generate UDFs with optional numeric hyperparameters and their valid ranges. More formally, VOCAL-UDF prompts the LLM to produce a (possibly empty) list
In later steps, VOCAL-UDF instantiates each hyperparameter with its default value as well as values sampled from the range and then selects the best program. See Figure 3 2 ○ for an example of a program that relies on a hyperparameter. To resolve the final challenge of incrementally building the video database, our approach is to additionally include in the LLM prompt, the active domain of all attributes populated by UDFs, which include oname, rname, and aname. This additional information enables the LLM to leverage the results of existing UDFs as building blocks to dynamically compose more complex UDFs. Figure 3 3 ○ shows an example program inlining an existing UDF. Overall, program-based UDFs are well-suited for concepts involving bounding box-like spatial relationships. In addition, other attributes and the pixels column can also be used to reason about existing concepts and perform statistical analysis of the pixels in a frame. A program-based UDF could also invoke a pretrained model over each frame, but this is in general expensive and slow. As discussed in Section 4.3, a distilled-model UDF is a more efficient approach for concepts that require visual understanding of videos.
Prior works have proposed various approaches to improve the performance of LLM-generated programs. One line of work leverages unit tests to verify the functional correctness of generated programs [18,22,27,52]. This approach is not suitable for VOCAL-UDF because users do not know in advance what UDFs will be generates, and thus cannot provide labeled data before issuing a query. Another line of work leverages LLMs to automatically generate test cases [20], evaluate the generated programs [24,95], and select the best one [104]. However, the ambiguity of semantic concepts in video queries means that the correct program is not always unique and often many of the generated programs are reasonable. As a result, the best program cannot be easily identified without user feedback and a working dataset.
Additionally, the quality of an LLM is not guaranteed. To address this issue, VOCAL-UDF uses a two-step approach to verify and select the best program: syntax verification and semantic verification. In the first step, VOCAL-UDF focuses solely on the syntax correctness of the programs. VOCAL-UDF executes each candidate program on a small sample of data from the database 𝐼 and checks whether: (i) the number and types of inputs and outputs are correct, (ii) the program can be executed with the data samples, and (iii) Θ, if any, can be parsed successfully. If the verification fails, VOCAL-UDF appends the error message to the context and prompt the LLM to make another attempt. VOCAL-UDF draws samples by constructing tuples that contain attributes and values that respectively correspond to one or two objects in the database. If the program still fails after a few trials, VOCAL-UDF discards the program. In our prototype, we empirically set the number of trials to five. Recent research has demonstrated the potential for formally verifying the correctness of generated UDFs based on a given semantic interpretation [23], which could be incorporated into VOCAL-UDF to further enhance the reliability of its generated Python programs. After generating multiple candidate programs, VOCAL-UDF next utilizes user labels to select the one that best aligns with user intent, which we discuss in Section 4.4.
While program-based UDFs are powerful and flexible for predicates that reason about existing concepts, bounding box coordinates, or perform a simple statistical analysis of pixel values, they struggle with tasks that require understanding the visual contents of frames. Even though pretrained models like VLMs can be used in a program-based UDF to classify relationships and attributes in a zero-shot manner, running such models over the entire video dataset is expensive. For instance, applying GPT-4o to every frame of the 10,000 five-second videos in the CLEVRER dataset [111] to evaluate a predicate (e.g., "color-red" or some more complex predicate) would cost approximately $1,413. This cost remains high even when applying techniques such as downsampling or predicate push-down: There are about 1.28M video frames and 5.44M objects to consider. Even if 99% of the image patches corresponding to these objects were filtered, the cost of evaluating a predicate on the remaining 1% of objects would still be around $14-far higher than generating one UDF (about $0.15; see Section 6.1). VOCAL-UDF's goal is to generate cheaper UDFs with visual understanding capabilities. However, training a lightweight image classifier from scratch would require the user to spend a lot of time labeling for just one concept.
Model distillation is a common technique in machine learning to transfer knowledge from a large model to a smaller, more efficient model [17,21,48,49,98]. Modeling Collaborator [98] is a newly proposed framework that leverages foundation models to train image classifiers for visual concepts using minimal user effort. To do so, given a target concept and description, the system (i) mines relevant images from the public domain, (ii) uses foundation models to annotate sampled images, (iii) trains a lightweight classifier using features extracted from a pretrained model (e.g., CLIP) and labels annotated by the foundation models, and (iv) performs multiple rounds of active learning to further improve its performance.
VOCAL-UDF adopts a similar approach to automatically construct lightweight image classifiers for new concepts without requiring user labeling but with the modifications needed to resolve three unique challenges presented in our compositional query setting. First, random sampling of the user dataset might not give enough positive samples for training, especially for rare concepts. Second, VOCAL-UDF generates UDFs for relationships and attributes, which differ from the concepts in [98]. An image usually includes multiple objects, and VOCAL-UDF needs a different prompting strategy to guide a VLM in classifying specific objects or pairs of objects*. Finally, for the same reason, merely extracting features from the entire image is insufficient to train a good classifier.
To generate a distilled-model UDF, VOCAL-UDF initially randomly samples frames from the user's video dataset for annotation. However, when the target visual concept is infrequent in the dataset, random sampling does not effectively collect enough positive samples for training. For instance, only 0.83% human-object pairs have an "eating" relationship in the Charades [53] dataset. Our solution is to apply object-aware sampling to bootstrap the sampling process. Since all objects of interest are already detected and tracked in the dataset, VOCAL-UDF can filter out irrelevant objects and sample only those likely to be involved in the target concept. For example, when labeling the "eating" relationship, object classes like "food" and "person" are more relevant than "car" and "window". To do this, VOCAL-UDF first asks an LLM for relevant object classes, and then only samples objects belonging to these classes. [119] shows an example prompt of object-aware sampling. 4.3.2 Data labeling. VOCAL-UDF uses VLMs to automatically label sampled video frames as positive or negative based on a UDF description. A VLM takes as input an image-text pair and outputs a textual response. However, using a video frame and the UDF description as a direct query is ineffective, since the concepts we are interested in target specific objects or pairs of objects, rather than the frame as a whole. Thus, VOCAL-UDF applies the following prompting strategy, with the goal of encouraging the VLM to focus on particular objects or interactions between two objects. For attribute concepts, we use the UDF description proposed in Section 4.1 as the text input, and create the image input by sampling an object from the Objects relation and cropping the video frame to include only the object. For relationship concepts, VOCAL-UDF augments the text input with the class names and bounding box coordinates of the relevant objects in the video frame to provide more context to the VLM. It then generates an image patch cropped from the video frame that includes a pair of objects in the same frame from the Objects relation. VOCAL-UDF further augments the image patch by overlaying a red box around the subject and a blue box around the target, thereby providing the VLM with directional information about the relationship. Figure 4 shows an example prompt for labeling the behind relationship. 4.3.3 Model training. Similar to [33,96,98], VOCAL-UDF leverages a pretrained vision model (e.g., CLIP) as the feature extractor and uses the feature-label pairs to train a multi-layer perceptron (MLP). However, for relationship classification, directly extracting features from the image patch containing two objects would perform poorly, as the feature extractor is not aware of the object locations and cannot capture directional relationships (e.g., 𝑜 1 holding 𝑜 2 vs. 𝑜 2 holding 𝑜 1 ). To address this, VOCAL-UDF concatenates features from three versions of an image patch: the original one containing both objects, one where everything except the subject is masked, and one where everything except the target is masked. For attribute UDFs, VOCAL-UDF simply extracts features from the image patch containing the object. In addition, VOCAL-UDF incorporates text features of object class names, derived from the Objects relation, to enhance the MLP's performance. After training an initial model, VOCAL-UDF uses an active learning approach similar to [96,98] to iteratively improve the model. During each iteration, the trained MLP is run over the unlabeled dataset, VOCAL-UDF selects a batch of samples with the highest uncertainty for labeling by the VLM. VOCAL-UDF then retrains the MLP with the updated labeled dataset.
VOCAL-UDF uses VLMs to automatically label data and the cost is bounded by the training data size, which is at most 500 frames in our evaluation. This is only 0.04% of the 1.28M frames in the entire database for CLEVRER, 0.8% of the 65K frames for CityFlow-NL, and 0.2% of the 289K frames for Charades (see Section 6), which correspond to extremely low sampling rates. This cost is thus far lower than directly applying an LLM to the entire video dataset, even with downsampling. Although VOCAL-UDF's distilled model process may occasionally deliver unsatisfactory performance, its UDF Selector component, described next, mitigates this by selecting the best candidate UDFs and filtering low-performing models.
For a given UDF, VOCAL-UDF can generate both a distilled-model and a set of program-based implementations. When there are multiple implementation candidates, VOCAL-UDF needs to select the best one. VOCAL-UDF does not have any initial data to validate semantic correctness, only the user NL query. If VOCAL-UDF were to collect labeled data for validation before query execution, the user would need to manually go through the video dataset to find positive and negative examples. Instead, VOCAL-UDF utilizes active learning at query time to strategically request binary labels on carefully selected samples that are most likely to resolve disagreements among UDF candidates. This approach minimizes labeling effort while effectively guiding the UDF selection process, which we now describe in detail.
To best align with the user's intent, VOCAL-UDF strives to select the candidate UDF that yields the best F1 score for a given set of user labels. As summarized in Algorithm 1, VOCAL-UDF uses active learning [57,81,118] to reduce the number of labeled examples needed from the user. Key hyperparameters include: a labeling budget 𝑏, thresholds 𝑡 𝑝 and 𝑡 𝑛 giving the number of positive and negative samples needed to initiate active learning, and the number of tuples 𝑛 𝑠 sampled per iteration. Section 6 details the values used in our experiments.
During each iteration, the algorithm randomly samples 𝑛 𝑠 tuples from the database (Line 4). It operates in two phases: bootstrapping and active learning. The bootstrapping phase collects at least 𝑡 𝑝 positive and 𝑡 𝑛 negative samples. While the number of labeled positives (|𝐿 𝑝 |) or negatives (|𝐿 𝑛 |) remains below its respective threshold, VOCAL-UDF selects samples most likely to be positive or negative (Lines 5 to 8). Once enough initial labeled data has been collected, VOCAL-UDF transitions to active learning, adopting the margin and positive strategy from [81]. Specifically, if |𝐿 𝑝 | < |𝐿 𝑛 |, it asks the user to label samples most likely to be positive; otherwise, it picks the sample with the greatest disagreement among UDF candidates to differentiate them [118] (Lines 9 to 12).
In PickPositive(𝑈 𝑠 , 𝐶,𝑊 ) and PickNegative(𝑈 𝑠 , 𝐶,𝑊 ), the algorithm priorities VLM annotations obtained in Section 4.3.2 over the UDF candidates' majority vote, as VLM labels are empirically Algorithm 1: UDF selection using active learning. Input : Set of unlabeled data 𝑈 , set of UDF candidates 𝐶, and hyperparameters 𝑏, 𝑛 𝑠 , 𝑡 𝑝 , 𝑡 𝑛 Output : Selected UDF with highest score 1 𝐿 𝑝 ← {}, 𝐿 𝑛 ← {} 2 𝑊 ← {𝑤 𝑖 | 𝑤 𝑖 = 1/|𝐶 |, 𝑖 = 1, 2, . . . , |𝐶 |} 3 for 𝑖 = 1 to 𝑏 do 4 𝑈 𝑠 ← SampleSubset(𝑈 , 𝑛 𝑠 ) /* Phase 1: Bootstrapping */ 5 if |𝐿 𝑝 | < 𝑡 𝑝 then 6 𝐿 ′ 𝑝 , 𝐿 ′ 𝑛 ← PickPositive(𝑈 𝑠 , 𝐶,𝑊 ) 7 else if |𝐿 𝑛 | < 𝑡 𝑛 then 8 𝐿 ′ 𝑝 , 𝐿 ′ 𝑛 ← PickNegative(𝑈 𝑠 , 𝐶,𝑊 ) /* Phase 2: Active learning */ 9 else if |𝐿 𝑝 | < |𝐿 𝑛 | then 10 𝐿 ′ 𝑝 , 𝐿 ′ 𝑛 ← PickPositive(𝑈 𝑠 , 𝐶,𝑊 ) 11 else 12 𝐿 ′ 𝑝 , 𝐿 ′ 𝑛 ← PickDisagreed(𝑈 𝑠 , 𝐶,𝑊 ) 13 𝐿 𝑝 ← 𝐿 𝑝 ∪ 𝐿 ′ 𝑝 , 𝐿 𝑛 ← 𝐿 𝑛 ∪ 𝐿 ′ 𝑛 , 𝑈 ← 𝑈 -(𝐿 ′ 𝑝 ∪ 𝐿 ′ 𝑛 ) 14 𝑊 ← ComputeScore(𝐿 𝑝 , 𝐿 𝑛 , 𝐶) more reliable. In PickDisagreed(𝑈 𝑠 , 𝐶,𝑊 ), it computes a disagreement score for each sample in 𝑈 𝑠 based on UDF candidates 𝐶, selecting the one with the highest disagreement [57, 118]. Each sample's disagreement score is the weighted disagreement among UDF candidates, with candidate weights initialized to 1/|𝐶 | (Line 2) and updated to its performance (F1 score in our prototype) over 𝐿 𝑝 and 𝐿 𝑛 after each iteration (Line 14). At the end of each iteration, 𝐿 𝑝 , 𝐿 𝑛 and 𝑈 are updated with the new user labels (Line 13). 4.4.2 Dummy UDFs. Several factors can contribute to the unsatisfactory performance of generated UDFs, including the complexity of the target concept, the low quality of VLM labels, and an insufficient number of positive training samples for rare events. When no UDF candidate performs well, VOCAL-UDF should not apply a UDF that can hurt the performance. To prevent this, VOCAL-UDF appends a dummy UDF to its list of UDF candidates. A dummy UDF is a constant-valued function that produces True and is equivalent to omitting the predicate. When all other candidates perform poorly, VOCAL-UDF opts for the dummy UDF during its UDF selection process. 4.4.3 UDF generation strategy. Program-based UDFs and distilled-model UDFs offer different tradeoffs in terms of performance, interpretability, generation cost, and inference throughput. VOCAL-UDF provides four strategies depending on the user's preference and the system's performance requirements: program only generates program-based UDFs, model only generates distilled-model UDFs, llm asks the LLM to decide whether to generate program-based or distilled-model UDFs, and both generates both classes of UDFs. [119] shows an example prompt of using the llm UDF generation strategy. Depending on the user specification, one or more program-based UDFs may be generated for each proposed UDF, and one distilled-model UDF is generated for each proposed UDF. By default, VOCAL-UDF uses the both strategy to maximize query performance. In Section 6.4, we also evaluate the performance of using the llm strategy to automatically choose UDF types.
As an alternative to VOCAL-UDF, a multimodal LLM can directly answer user queries. However, as shown in prior work [74,103] and as we confirm in Section 6.1.2, LLMs still struggle with compositional queries, and directly providing the LLM with the video frames and the user query in a single prompt (the "vanilla LLM" approach in Section 6.1.2) leads to low F1 scores. Furthermore, the cost scales with the dataset size, making it expensive for large video collections today, as we discussed in Section 4.3 and evaluate in Table 3.
A higher performance LLM baseline is to parse the query into our DSL, then use a combination of existing cheap models for common concepts and an LLM for application-specific concepts (i.e., VOCAL-UDF without UDF generation, or "LLM for concepts" in Table 3). While it may yield good F1 scores, this approach is only practical for short videos and a small number of queries. For larger workloads, the cost and latency of this method are even greater than "vanilla LLM" due to repeated LLM calls to identify concepts for each object or object pair. As Table 3 shows, executing just one query with three missing UDFs over the CLEVRER dataset using GPT-4o costs about $1,504 USD. Reducing costs through sampling is also non-trivial because low sampling rates can degrade query performance, especially for compositional events involving temporal dimensions. As we show in Figure 6b, even a small downsampling factor of 8 can greatly reduce the upper bound of achievable F1 scores from 1.0 to 0.51.
VOCAL-UDF overcomes these issues by using the multimodal LLM to learn each new applicationspecific concept once, over a fixed-size sample of the data, and generate cheaper, domain-specific models (either program-based or distilled-model UDFs) that can then be applied to the remaining videos and to all future queries, avoiding repeated reliance on the LLM and reducing overall costs.
VOCAL-UDF is implemented in Python using the AutoGen framework [105]. The Query Executor converts queries in DSL notation into SQL and uses a relational engine (DuckDB [86] in our prototype) to execute them. We apply the same query translation algorithm as in [118] to optimize query execution. To reduce system latency, we parallelize API calls to the LLM.
VOCAL-UDF requires a preprocessing stage per dataset before queries can be issued. The user provides a video dataset and optionally a set of UDFs. If these UDFs include object detection and tracking models, VOCAL-UDF uses them to populate the Objects relation. Otherwise, VOCAL-UDF uses a predefined object detection and tracking model to identify common objects. VOCAL-UDF pre-extracts features into Parquet files for use by distilled models at query time (Section 4.3.3), and we utilize NVIDIA DALI [5] to accelerate this process. VOCAL-UDF also executes the initial UDFs ahead of time to populate the Relationships and Attributes relations and compute the active domains for oname, rname, and aname. These operations happen as soon as VOCAL-UDF receives the videos and UDFs and before the user issues any queries. If no initial UDFs are supplied, the Relationships and Attributes relations will be empty. Similarly, when a new UDF is later created, our prototype runs it over the entire dataset and materializes the results in the database. It then converts the UDF into a value-lookup UDF so that subsequent queries can reuse the materialized results. All UDFs are implemented in Python.
There is preprocessing overhead in the initial setup. The cost of running object detection, object tracking, and feature extraction is relatively modest compared to that of LLMs and VLMs, and they can be run locally. The cost of executing a UDF depends on its implementation. In this paper, we materialize all results in the video dataset before issuing new queries. Several works have focused on optimizing query execution with UDFs [54,107], which could be integrated into our system.
Baselines. We compare VOCAL-UDF against VisProg [42] and EQUI-VOCAL [118], both of which are limited to predefined UDFs when answering queries. VisProg uses a different set of modules for different tasks, so we manually write new modules for the system to be able to answer compositional queries. These include both logical (e.g., Eval, Event, Before) and conceptual (e.g., Red, Holding) modules. VisProg also requires in-context examples, which we create separately from the evaluation queries. While EQUI-VOCAL does not need such examples, it does not accept NL queries as input.
To address this, we adapt VOCAL-UDF's approach of converting NL into the EQUI-VOCAL DSL using an LLM. We further compare VOCAL-UDF with two LLM baselines as described in Section 4.5. Metrics. We evaluate query answering performance using F1 scores, precision, and recall. We propose and generate UDFs using training data and report query performance over the test set. We evaluate each dataset using 30 queries, and each query is run three times. We additionally evaluate the system efficiency in terms of latency and cost. For latency, we report the wall-clock time as perceived by the user from the moment they submit a query to the moment when VOCAL-UDF returns the query results. For cost, we measure both the LLM API invocation cost using the OpenAI pricing model [6] and the resource cost using the AWS pricing model [1,2]. Datasets: We evaluate VOCAL-UDF on three datasets: CLEVRER [111], CityFlow-NL [37] and Charades [53]. CLEVRER is a benchmark that facilitates testing queries with varying complexities. CityFlow-NL and Charades represent real-world applications-traffic monitoring and human activities-typical for video data management systems. UDFs in CityFlow-NL include fine-grained vehicle types, while Charades comes with complex human interactions. The evaluation queries are based on concepts from these datasets, which are labeled by the original annotators and reflect events from those domains. CLEVRER: The CLEVRER [111] dataset consists of 10,000, 5-second synthetic videos of moving objects. To determine ground-truth information, following [111], we use a Mask R-CNN [46] to locate objects and predict their colors, shapes, and materials. We write rule-based functions to extract spatial relationships and attributes. For our experiments, we use the same Mask R-CNN and rule-based functions as UDFs, for a total of six relationships and 17 attributes. Among them, we select two relationships and nine attributes as the base UDFs, which are available to all systems during query evaluation. We use templates to automatically generate 30 target queries with seven predicates, up to three variables (i.e., three distinct objects), up to three region graphs, and duration constraints with three possible values. We ensure there are at least 5% positive examples in the dataset for each target query (we ensure the same for all datasets). We then rewrite the DSL queries as NL queries using GPT-4 and manually verify the correctness. CityFlow-NL: The CityFlow-NL [37] dataset contains traffic videos captured from multiple cameras and NL descriptions for vehicle tracks. Following [66], we extract vehicle colors and types from the NL descriptions. Since only sampled vehicle tracks are annotated, we only consider them in our evaluation. We extract six spatial relationships using rule-based predictors and create 1,473 non-overlapping 50-frame video segments from the original dataset. To create UDFs for attributes, we train binary image classifiers. For relationships, we use the same rule-based functions as UDFs. Then, we select three relationships and four attributes as base UDFs. We automatically generate 30 queries with up to four predicates, up to three variables, up to three region graphs, and duration constraints with three possible values. An example query is "a vehicle o0 with type sedan is to the right of another vehicle o1 for at least 15 frames. Then, o0 is to the left of o1 for at least 15 frames", which could be used to find sedans changing their positions with other vehicles. Charades: The Charades [53] dataset contains 30-second indoor activity videos. We focus exclusively on frames with scene graph annotations provided by Action Genome [53], which only provide human-object relationships but do not cover attributes or object-object relationships. Thus, our evaluation queries focus on human interactions with objects. At query time, only human-object pairs are sampled to collect more positive examples. Incomplete annotations is a common issue in real-world datasets [19] like Charades. To address this, we augment the dataset by automatically generating dense spatial relationship annotations using rule-based predictors to replace the existing ones. For semantic relationships, we train binary image classifiers. In total, we have 20 relationships (five spatial, 15 semantic) and 35 object classes. Among them, we select two spatial and seven semantic relationships as the base UDFs. We automatically generate 30 target queries with up to four predicates (one is always object(o 𝑖 ,'person')), up to three variables, and up to two region graphs, but without duration constraints. An example query is "a person is eating something, and then the same person is holding another object while being in front of it", which could retrieve videos including a person taking a bite from an apple, and then picking up a cookbook in front of them to read a recipe.
For each dataset, we use half of the videos as training data and the rest as test data. To generate ground truth labels, we run each target DSL query on the dataset. Evaluation setup. We conduct all experiments on a compute cluster. For each experiment, we request one node with eight Intel Xeon Gold 6230R CPUs at 2.10GHz, 200GB of RAM, and one NVIDIA A40 GPU. We use the GPT-4o model (gpt-4o-2024-08-06) as the LLM and VLM across all systems. We configure VOCAL-UDF as follows. For the CLEVRER dataset, we use a labeling budget of 20 for each UDF during selection. We generate 10 candidate programs, allowing numeric parameters and frame pixels as inputs. During UDF selection, we bind each numeric parameter to its default value as well as five random values. When generating distilled-model UDFs, we ask the VLM to annotate 100 sampled frames per UDF. Given their increased complexity, for the CityFlow-NL and Charades datasets, we set the labeling budget per UDF to 50 and the number of VLM-annotated frames per UDF to 500. 100 frames are annotated for the initial training, and then active learning is performed to select 100 additional frames in each round. Frame pixels are disallowed in program-based UDF generation due to their limited impact on performance. To focus our evaluation on relationships and attributes, we assume objects are pre-detected and tracked.
6.1 End-to-end performance 6.1.1 F1 score, precision, and recall. We first evaluate the end-to-end performance of VOCAL-UDF and baseline systems by varying the number of missing UDFs from zero (i.e., all required UDFs are available) to three. In each experiment, all base UDFs are available, but 𝑋 supplemental UDFs are randomly removed. We execute thirty distinct queries three times. Figure 5 presents the F1 scores, precision, and recall. VOCAL-UDF maintains high performance even when UDFs are missing. When all required UDFs are available, all systems perform similarly. For CLEVRER, F1 scores with no missing UDFs reach 1.0 since predefined UDFs are also used to generate ground-truth scene graph annotations. However, CityFlow-NL and Charades contain less accurate ML models in their UDFs, leading to lower F1 scores. When UDFs are missing, VisProg and EQUI-VOCAL experience significant F1 score drops, as they cannot generate new UDFs, with VisProg performing worse due to its higher likelihood of including unavailable UDFs. VOCAL-UDF mitigates F1 score degradation by generating new UDFs as needed, though performance drops more on Charades as its missing UDFs involve complex, harder-to-generate semantic relationships. Interestingly, while EQUI-VOCAL achieves higher recall than VOCAL-UDF on CLEVRER and CityFlow-NL when UDFs are missing, it does so at the expense of substantially lower precision, for an overall lower F1 score.
To understand the performance gap between VOCAL-UDF and using an LLM directly, we evaluate both approaches on CLEVRER. We use the same queries from the end-to-end experiments, but under a simplified setting due to the high expense of GPT-4o. We select 500 videos and downsample each by 75%, retaining every fourth frame. We use the first 10 queries as evaluated in Section 6.1.1 but remove any duration constraints due to the downsampling. We compare VOCAL-UDF to a vanilla LLM method in which we provide GPT-4o with a sequence of video frames and ask with the prompt: "Examine the sequence of frames from a video and determine if the following event occurs? <user_query>. Answer with 'yes' or 'no'." We use OpenAI's Batch API that offers 50% lower cost. Figure 6a shows that VOCAL-UDF achieves significantly higher F1 scores than the vanilla LLM approach. The cost of the vanilla LLM method scales with the dataset size, averaging $5.17 USD per query under this simplified setting. If extended to the full 5,000 videos in the test set of CLEVRER, the estimated cost would be $207 USD per query.
As an alternative baseline, one can use an LLM to classify new concepts instead of generating UDFs. However, as discussed later in Section 6.1.4, the cost of doing so without downsampling is prohibitively high. While downsampling reduces LLM costs, it can also degrade query performance. Figure 6b shows the F1 scores of executing ground-truth DSL queries (i.e., assuming perfect LLM predictions) over the simplified CLEVRER with various downsampling factors. Downsampling
0 10 20 Time (mins) 0 1 2 3 # generated UDFs CLEVRER 0 5 10 15 Time (mins) 0 1 2 CityFlow-NL 0 5 10 15 20 Time (mins) 0 1 2 Charades query parsing UDF proposal UDF generation UDF selection query execution (a) Total time. greatly reduces the upper bound on achievable F1 scores, with performance dropping to 0.51 at a downsampling factor of just 8.
To analyze VOCAL-UDF's efficiency, we perform an end-to-end evaluation of execution time. Figure 7a breaks down the wall-clock time for each system component, with each stacked bar showing the mean execution time for queries with different numbers of UDFs that VOCAL-UDF decides to generate. VOCAL-UDF may occasionally decide to generate extra, unnecessary UDFs. For clarity, we omit CLEVRER with four generated UDFs and CityFlow-NL with three generated UDFs from Figure 7, as each has only one data point-arising from the LLM's inaccurate decision-and does not reflect an average execution time for that number of generated UDFs. The average execution time is under 100 seconds when all required UDFs are available and increases proportionally with the number of generated UDFs. In CLEVRER, query execution takes longer when new UDFs need to be created, requiring several minutes to process the full 14-hour video dataset as VOCAL-UDF materializes new UDF outputs. Subsequent queries using the same UDFs, however, are as fast as the case with no missing UDFs. CityFlow-NL and Charades are faster due to smaller datasets and the exclusion of frame pixels in program-based UDF generation, which eliminates the need for video loading and reduces the program execution cost. For CityFlow-NL and Charades, UDF generation dominates the execution time, as the number of VLM-annotated frames per UDF increases to 500, with active learning applied after labeling every 100 samples. UDF selection requires non-negligible time across all datasets, involving tasks such as frame loading, feature extraction, program execution, and model prediction.
Figure 7b provides a detailed breakdown of wall-clock time for the UDF generation process. Since VOCAL-UDF asynchronously parallelizes calls to the LLM, we measure the time breakdown as follows. All categories except for "other" capture the synchronous portions of each sub-step (i.e., excluding LLM calls), while "other" represents the remaining observed time, which includes the time spent explicitly waiting on asynchronous LLM calls. Program-based UDF generation is labeled as "program, " while distilled-model UDF generation is further divided into sub-steps ("init", "data loading", etc.). Distilled-model UDF generation takes significantly longer than programbased UDFs, but no single sub-step consistently dominates across all cases. Specifically, training distilled models takes the longest in CLEVRER and CityFlow-NL, whereas active learning takes the longest in Charades due to a larger dataset. The active learning step could be accelerated by performing it on a sample of the unlabeled dataset. The results also suggest that LLM calls do not dominate UDF generation time, thanks to asynchronous execution. For example, during data labeling, VOCAL-UDF submits batches of 100 asynchronous tasks to maximize parallelization. 6.1.4 Monetary cost. To understand the query execution cost, we consider both the LLM API invocation cost and the compute resource cost. Figure 7c shows the mean monetary cost of OpenAI LLM calls per query. VOCAL-UDF costs less than $1.0 USD per query, with data labeling for distilled-model UDFs being the primary cost factor. Moreover, GPT-4o can be replaced by open-source models. For instance, Amazon Bedrock offers Llama 3.1 70B for a price of $0.72 USD per 1M tokens [1], which is 3.5× cheaper for input and 14× cheaper for output tokens than GPT-4o. Other open-source models and hosting options [4] are available to further reduce costs, with a potential trade-off in query F1 scores. Compute resource costs depend on deployment scenarios. For example, on a g4dn.12xlarge EC2 spot instance, the estimated average resource cost of running a query with the largest number of missing UDFs is $0.7 USD for CLEVRER, $0.4 for CityFlow-NL, and $0.5 for Charades [2]. Thus, the total per-query cost for each dataset remains under $1.5.
Table 3 the estimated LLM costs of VOCAL-UDF, "vanilla LLM", and "LLM for concepts" (as described in Section 4.5) using both GPT-4o and Llama 3.1 70B. Due to the high expense of the baselines, we estimated costs rather than running full experiments. We estimate the cost of "LLM for concepts" as follows: Each CLEVRER video contains an average of 544 objects and 1,933 object pairs. Each LLM call requires 300 input tokens (255 for the image and 45 for the task) and one output token ("yes" or "no"). We first run the query with missing UDFs removed, then invoke the LLM only on the matching videos to minimize costs. As shown in Table 3, VOCAL-UDF is much more cost-effective than direct LLM baselines. While further optimizations-e.g., evaluating immutable attributes on a single frame and propagating them to other frames for the same object-could reduce the cost of "LLM for concepts", the cost remains proportional to the dataset size, in contrast to VOCAL-UDF. Translating NL queries to DSL is not a contribution of this paper, but we report it as it affects the end-to-end performance. For this experiment, all UDFs are available, and the LLM translates the same queries from the end-to-end experiment, running each three times. We measure the F1 score of the generated queries. As shown in Table 4, VOCAL-UDF can effectively parse the complex textual queries into the DSL notation, returning correct video segments at least 79% of the time, which increases to ≥97% if we consider an F1 score ≥ 0.98. Common translation errors include missing and redundant predicates, misuse of UDFs with similar names, and incorrect temporal ordering of predicates.
We evaluate VOCAL-UDF's UDF proposal using the same set-up as the end-to-end evaluation. A proposed UDF is considered correct if its name matches one of the target query's ground truth UDFs, with a manual check for synonyms. As shown in Table 5, VOCAL-UDF proposes fewer UDFs than expected, with more false negatives (FNs) than false positives (FPs). This occurs because some new UDFs are equivalent to available UDFs (e.g., "above(o1, o2)" vs. "beneath(o2, o1)"). However, this is beneficial as it avoids unnecessary UDF generation. Most other FNs are mainly because VOCAL-UDF decides to approximate using other available UDFs (e.g., "touching" for "holding"). Most FPs arise from proposing compositional UDFs, such as "behind_and_near" for "behind" and "near".
We now evaluate the performance of program-based UDFs. We consider all correctly proposed program-based UDFs across the 270 experiments with the largest number of new UDFs (3 datasets × 30 queries × 3 runs). We classify UDFs into two categories, one where at least one of their best implementations is program-based, and another where the best is not program-based. Table 6 shows the median F1 score of the best generated program for each UDF (best UDFs) and all generated programs for each UDF (all UDFs). When the best UDF generation is program-based, VOCAL-UDF consistently produces high-quality programs. However, not all generated UDF candidates are of high quality; for instance, the median F1 score of all program-based UDFs for Charades is only 0.092. Thus, VOCAL-UDF must carefully select the best candidate during the UDF selection phase. When the best UDF is not program-based, F1 scores decrease significantly, indicating that certain relationships or attributes may not be well-suited to program-based UDFs.
Using the same method as above, we evaluate the performance of distilled-model UDFs. UDFs are classified into two categories, one where at least one of their best implementations is distilledmodel, and another where none are distilled-model. Table 6 shows the median F1 score for both distilled-model generation and dummy generation (as the baseline) for each UDF. When the best UDF generated is distilled model, VOCAL-UDF shows a significant improvement in F1 scores over the baseline. When the best UDF is not distilled model, the F1 scores of distilled models are comparable or worse than the baseline, indicating that certain relationships or attributes may not be suitable for distilled-model UDFs. For CityFlow-NL, F1 scores are higher for UDFs whose best implementations are not distilled models, likely due to the complexity of semantic attributes that are more challenging to classify.
To access VOCAL-UDF's ability to handle ambiguous intent in program-based UDFs, we test three concepts from CLEVRER-"behind", "far", and "location_bottom". For each concept, we execute the same query with one predicate but three different interpretations. For instance, "behind" is interpreted as: (1) o1's center above o2's center, (2) o1's center below o2's center, and (3) o1's bottom edge above o2's bottom edge. We compare VOCAL-UDF to a baseline that uses an LLM to generate a single program without numeric hyperparameters or UDF reuse. Figure 8 shows the F1 scores for each concept across varying interpretations, showing that VOCAL-UDF can more robustly adapt to different definitions of the same concept. The baseline struggles with "behind" since it uses an interpretation based on bounding box overlap that mismatches all three ground truths. While it works well for one interpretation of the other concepts, its single-generation method fails to accommodate varying interpretations, leading to significant performance drops. One limitation of VOCAL-UDF is that a concept becomes fixed once a UDF is generated. The UDF would have to be explicitly deleted or disabled if a user wanted a different interpretation for an already-existing concept. Additionally, VOCAL-UDF currently does not handle intent ambiguity for distilled-model UDFs, but this can be extended by asking LLMs to generate diverse descriptions of the target concept and distilling multiple models.
We further examine the VLM's labeling quality during distilled-model UDF generation on the CityFlow-NL and Charades datasets. We evaluate nine attributes in CityFlow-NL and 18 relationships in Charades. For each attribute or relationship, we use GPT-4o to label a randomly selected, balanced set of 500 samples. Table 7 shows the average F1 score of each concept over three runs. GPT-4o generally achieves high labeling quality for a wide range of concepts: seven out of the 27 concepts achieve F1 scores of at least 0.9, and 15 attain F1 scores of at least 0.8. However, GPT-4o struggles to label the five spatial relationships, suggesting that VLMs like GPT-4o are still limited in spatial reasoning.
Table 8 reports the UDF selection results. The "best" column shows the number of UDFs selected by VOCAL-UDF that achieve the highest F1 score among all UDF candidates, while the "80% of best" column shows many attain at least 80% of the best F1 score. VOCAL-UDF effectively selects better-performing UDFs from candidates, even with a labeling budget as low as 20.
Although VOCAL-UDF does not always pick the best UDF due to similar scores for many candidate UDFs, it can still select a good UDF implementation at least 85% of the time (with an F1 score of at least 80% of the best implementation). Table 8 also breaks down the types of UDFs that VOCAL-UDF selects. To handle diverse semantic concepts, VOCAL-UDF generates and selects UDFs of various types, underscoring the necessity for VOCAL-UDF to support two different types of UDFs. Interestingly, VOCAL-UDF selects more dummy UDFs (41 instances, 28%) on the Charades dataset than the other datasets. Notably, 20 instances are "holding", which is difficult to distinguish under the current labeling budget. Another 17 cases are "in", which our rule-based predictor identifies by checking bounding box overlap. This method classifies most object pairs as having this relationship, thereby allowing even the dummy UDFs to perform exceptionally well.
VOCAL-UDF supports four UDF generation strategies, as described in Section 4.4.3. We now compare the "both" and "llm" strategies in selecting the correct UDF type. When multiple candidates of different types share the highest F1 score, any of these types is considered correct. Using the same end-to-end experiment setting with the largest number of missing UDFs, Table 9 shows the number of correctly selected UDF types. The results are divided into two categories: one where the best UDF type is not "dummy" and one where it is "dummy." When the best UDF type is not "dummy," VOCAL-UDF correctly selects the UDF type at least 72% of the time with the "both" strategy, reaching up to 90% on CLEVRER. Interestingly, using "llm" with GPT-4o yields a higher accuracy than "both". However, this strategy is highly sensitive to the model used; switching to an earlier GPT-4 Turbo model reduces the accuracy to 46-64%. Despite this, the "llm" strategy demonstrates potential to further improve performance while reducing latency and cost. When the best UDF type is "dummy, " VOCAL-UDF can also select the correct UDF type 43% to 90% of the time using the "both" strategy.
We study the impact of active learning and dummy UDFs to the UDF selection process, using the same end-to-end experiment setting with the largest number of new UDFs. F1 scores across three system variants: the complete system with both active learning and dummy UDFs (All), the system with random sampling and dummy UDFs (No active learning), and the system with active learning but without dummy UDFs (No dummy UDFs). Both active learning and dummy UDFs help achieve higher F1 scores. For CityFlow-NL, the best UDF implementations are easily distinguishable from candidates, so active learning does not improve F1 scores but also does not degrade system performance. VOCAL-UDF reduces user effort by using active learning to request labels at query time rather than asking the user to provide all examples upfront. Figure 10 compares the number of samples needed under two approaches-active learning during UDF selection and random sampling before query execution-to obtain at least ten positive examples for a given UDF. We consider all generated UDFs from the end-to-end experiment and classify them as "easy" (spatial relationships and attributes with relatively balanced labels) or "hard" (other concepts with greater class imbalance). Active learning allows VOCAL-UDF to collect positive samples with reduced labeling effort, particularly for "hard" concepts. Since most object pairs exhibit "in" relationships in Charades, random sampling requires labeling only 11.5 samples on average to yield 10 positives. As a result, the overall labeling effort for "easy" concepts in Charades is similar between random sampling and active learning.
Video analytics. Numerous video analytics systems have been developed to support a wide range of data management tasks [32,33,60,61,88]. Query execution over videos typically involves running expensive ML models. Thus, many techniques have been proposed to accelerate query processing, including indexing [47,51,56], sampling [11,12,80], pre-filtering frames [44,45,73,106], reusing results [107], and building specialized models [7,55]. VOCAL-UDF can incorporate existing methods to optimize query execution.
Compositional video query processing. VOCAL-UDF is most related to systems designed for compositional video queries [13,25,30,39,70,76,107,108,113,118]. However, these systems often require users to have a certain level of database expertise to manually construct compositional queries [25,39,70,107,113] or to provide examples to learn a query from [76,118]. In contrast, VOCAL-UDF leverages advances in LLMs and allows expressing queries in NL.
LLMs with tools. LLMs are widely used to tackle challenging text tasks across a variety of applications [22,26,41,59,82,93,101,102]. By integrating external tools, LLMs can address even more complex reasoning tasks [72,75,85,91,121], including vision tasks [29,42,79,94,97]. However, these systems generally rely on the availability of existing tools or modules. For instance, VisProg [42] and ProViQ [29] utilize LLMs to transform complex tasks into executable programs that invoke predefined tools. VOCAL-UDF also employs LLMs to handle compositional queries over videos but extends this capability by generating new UDFs. Several systems explore the capacity of LLMs to create new tools. LATM [18] generates reusable code snippets for NL tasks, while GENOME [27] generates and reuses code-based modules to solve visual tasks. VOCAL-UDF distinguishes itself as an end-to-end VDBMS that generates both program-based and distilled-model UDFs which significantly enhances performance.
VOCAL-UDF does not currently support relationship and attribute UDFs involving state changes over time, such as identifying a car "moving close" to a truck, which requires distance comparisons at different timestamps. As an approximation, multiple frame-level UDFs can represent each state separately; for instance, detecting a "far" relationship followed by a "near" one.
Materializing and reusing UDF results can be problematic when the definition of an attribute or relationship is not objective (e.g., "near") and varies from query to query. To address this, VOCAL-UDF could allow users to access and manage generated UDF descriptions, implementations, and results, enabling them to dynamically enable or disable specific UDFs before issuing queries.
VOCAL-UDF's performance is affected by its ability to semantically understand the user queries and available UDFs. We assume that predefined UDFs are relevant to the target domain and that an LLM is capable of disambiguating each UDF effectively. The performance of VOCAL-UDF thus heavily depends on the underlying LLM, which is why we used the latest LLMs (e.g., GPT-4o) to ensure high-quality semantic understanding. Furthermore, VOCAL-UDF currently supports queries with detailed and explicit descriptions. Extending support to vague queries is left for future work.
VOCAL-UDF leverages LLMs in various system components, making the quality of query results dependent on the underlying LLM performance. To enhance the reliability of LLM-generated answers, VOCAL-UDF employs syntax verification, generates multiple candidate UDFs, and leverages user annotations via active learning to select the best implementation. Introducing dummy UDFs further ensures that newly generated UDFs do not negatively impact query results. While users already provide annotations to guide UDF selection, VOCAL-UDF could be extended to incorporate additional human interventions, allowing users to access intermediate results for manual examination [28,109,117]. Our experiments empirically demonstrate the promising potential of our LLM-based approach, and we posit that as LLMs advance, VOCAL-UDF performance will correspondingly improve.
This paper presents VOCAL-UDF, a new system that supports compositional video queries with the capability to generate new UDFs. VOCAL-UDF utilizes LLMs to parse natural language queries and automatically determine the need for new UDFs. It supports both program-based and distilled-model UDF generations and improves UDF quality through syntax verification and semantic verification.
Proc. ACM Manag. Data, Vol. 3, No. 3 (SIGMOD), Article 215. Publication date: June 2025.