Resource-efficient Inference with Foundation Model Programs
Authors: Lunyiu Nie
Zhimin Ding
Kevin Yu
Marco Cheung
Chris Jermaine
Swarat Chaudhuri
Venue: COLM 2025 (2025)
Keywords: Neurosymblic Programming
Multimodal LMs
Agent Programming
LLM Computational Efficiency
Multi-modal Reasoning
TL;DR: We give a program synthesis method for resource-efficient multimodal reasoning in streaming tasks. Our programs exploit task structure and tailor submodules to each input, so as to achieve an optimal cost-performance tradeoff.

Abstract: The inference-time resource costs of large language and vision models present a growing challenge in production deployments. 
We propose the use of ***foundation model programs***, i.e., programs that can invoke foundation models with varying resource costs and performance, as an approach to this problem. Specifically, we present a method that translates a task into a program, then learns a policy for resource allocation that, on each input, selects foundation model "backends" for each program module. The policy uses smaller, cheaper backends to handle simpler subtasks, while allowing more complex subtasks to leverage larger, more capable models. We evaluate the method on two new "streaming" visual question-answering tasks in which a system answers a question on a sequence of inputs, receiving ground-truth feedback after each answer. Compared to monolithic multi-modal models, our implementation achieves up to 98\% resource savings with minimal accuracy loss, demonstrating its potential for scalable and resource-efficient multi-modal inference. The source code and the benchmarks are available at [GitHub](https://github.com/Flitternie/FMProgramming).

Published as a conference paper at COLM 2025
Resource-efficient Inference with Foundation Model Programs
Lunyiu Nie! Zhimin Ding² Kevin Yu!
Marco Cheung!
Christopher Jermaine? Swarat Chaudhuri!
'The University of Texas Austin 1ynie@utexas, edu,, awaratecs. utexas.eeu
Rice University
Abstract
The inference-time resource costs of large language and vision models present growing challenge in the deployment of agentic systems. We propose the use of foundation model programs, i.e, programs that can invoke foundation models with varying resource costs and performance, as an approach to this problem. Specifically, we present method that translates a task into program, then learns a policy for resource allocation that, on each input, selects foundation model "backends" for each program module. The policy uses smaller, cheaper backends to handle simpler subtasks, while allowing more complex subtasks to leverage larger, more capable models. We evaluate the method on two new "streaming" visual question- answering tasks in which a system answers question on a sequence of inputs, receiving ground-truth feedback after each answer. Compared to monolithic multi-modal models, our implementation achieves up to 98% resource savings with minimal accuracy loss, demonstrating its potential for scalable and resource-efficient multi-modal inference
Introduction
Foundation models (FMs) have reshaped the landscape of machine learning over the past few years, demonstrating unprecedented capabilities in language understanding (Achiam et al., 2023; Dubey et al., 2024), complex reasoning (Lu et al., 2024; Gupta al., 2024), and multimodal tasks (Li et al., 2022a; Liu et al., 2024). While much of the community's attention has focused on their training costs, the inference-time resource use of FMs is increasingly be- coming practical bottleneck. For commercial applications that require real-time responses - for instance, continuous streams of user queries to multimodal large language model (MLLM) - computational overhead and high latency can severely degrade user experience and inflate operational expenses (Xu et al., 2024).
In this paper, we propose the use of foundation model programs (FMP's) code in Python-like languages that can call into a variety of specialized vision and language models as subrou- tines
way to address this problem. Such programs have been previously motivated by the interpretability and composability they bring to multi-step tasks (Surís et al., 2023; Gupta & Kembhavi, 2023; Subramanian et al., 2023) and agentic AT systems (Wu et al., 2023; Khattab et al., 2023). Our insight is that they can also enable fine-grained decisions about resource allocation: simpler subtasks can rely on smaller, cheaper backends while more complex components can leverage larger, more capable models.
Concretely, we propose framework of resource-efficient foundation model programmiing in which task is automatically translated into an FMP that captures subtask dependencies and conditional control flow. The framework is modality-agnostic making it directly applicable to any domain - text, vision, speech, or multimodal - as long as the task can be expressed as an FMP. Fach submodule of the program is then assigned to one of several backend models, differing in resource cost and capability. For example, consider the scenario in
Source code and benchmarks are available at https://gii htt.ggituub.coo com/ /Fl htt:/FFiitttte Lttttrniee/MPrrgraamit

---

Published as a conference paper at COLM 2025
Is there a cat sitting or laying laptop keyboard?
Single LLM
Powerful,
Yes No
But Slow & Expensive!
Inference
FM Backends
Modkerss
User Query
FM Programming
Dynomic
Backend
30
708
exeratte conmandi (mage):
Selection
Ofject Detection Fou nounddatonn Models
cots (rrd) sf cent)
VCC seaccten
232
taptape tenclaptups)
Policy
if arytcats. eec.caeeppp...... with Laptspee return image_astchh aatch egai"is there a cat
Multiiloueel Fourdiaion Mocble
Exec
Input Streams
Yes / No
Figure 1: Illustration of an FM program synthesizing a VQA task by decomposing the task into sub-components. At runtime, the resource-efficient FM programming framework dynamically selects FM backends based on the task and input complexity to optimize accuracy and resource efficiency in real-time processing.
Figure 1, in which visual question answering (VQA) system receives the query "Is there cat sitfing or laying on a laptop keyboard?" Here, our method generates a program that uses small, inexpensive object detection model to check whether both a cat and a laptop are present. Only if that condition is met does invoke a more powerful vision-language model (VLM) for finer-grained reasoning.
We specifically focus on "streaming" tasks in which the system repeatedly solves a task - for example, answering question on sequence of inputs. An answer is generated without prior knowledge of the ground truth, then the system receives ground-truth feedback after each answer. In such settings, the cost of using a monolithic model is proportional to the number of inputs processed. By contrast, our approach uses the feedback from the early answers to learn a policy that dynamically selects which backend model to invoke for each subtask, conditioned on the program input. Specifically, we use a combination of structured REINFORCE estimator and Thompson Sampling to learn this policy.
While existing routing or cascading strategies (Chen et al., 2023; Shnitzer et al., 2023; Lu et al., 2023; Nie et al., 2024) attempt to reduce large language model (LLM) inference overheads by switching between model sizes, they do not exploit the rich structural dependencies that arise in complex, compositional workflows. By contrast, our programs make these dependencies explicit, opening up opportunities for more flexible resource optimization.
Given the lack of standard benchmarks for resource-efficient sequential Recision-making evaluate our approach on two newly introduced benchmarks: (1) a streaming binary VQA benchmark, where the questions require yes/ no answers, spanning 33 compositional reasoning tasks with over 2,000 annotated images per task; and (2) streaming open-form form VQA benchmark, involving diverse questions with a broader answer space, covering 50 tasks with 500 annotated images per task. Experimental results show that our FMP-based system consistently reduces inference costs by 50% to 98% compared to one-size-fits-all baselines, without compromising task accuracy.
In summary, our contributions are as follows:
We propose the use foundation model programs as a flexible approach to cost-efficient inference for complex, multimodal workflows.
We give a specific method for learning such programs in sequential decision-making setting. The highlight of the method is an online resource allocation method that sys- tematically trades off the resource consumption and performance of models in an input- dependent way.
We release two streaming benchmarks for binary and open-form VQA, reflecting real- world tasks where inputs arrive sequentially at scale and resourc--efficency is key.
We show empirical results on these benchmarks, which demonstrate that our program- based approach can achieve up to 98% cost savings with minimal accuracy degradation.
2

---

Published as a conference paper at COLM 2025
2 Problem Formulation
Foundation Model Programs. We consider programs written in a language such as Python, potentially synthesized by an LLM. The programs are neurosymbolic because they interleave symbolic control flow with calls to fixed set of generic neural functions = (fi ....f...xxx where each fx denotes high-level functionality (e-g., object detection, visual question answering, natural language understanding). For example, the program in Figure makes calls to two generic neural functions ImagePatch. find() and ImagePatch, vqa(). In practice, we are interested in the case where the neural functions are implemented via foundation models. Hence, use the term foundation model program (FMP) to refer to such programs.
Each generic function ft in an FMP has an associated set of ny backend models that can be used to implement it, namely Mx = [ME,, 12.2,, ...., mgn, }, where each backend mig has different trade-offs between accuracy and computational cost. These backends may span spectrum of models, from lightweight task-specific models to large, general-purpont language or multimodal models. Without loss of generality, we assume that the cost of invoking a backend is fixed and independent of the specific input it processes.
Now, assume that we analyze the program and produce an arbitrary ordering for the total of N calls to generic neural functions, such that k; is the identity of the generic neural function associated with the i-th call in the program. Note that a program can call the same neural function multiple times with different inputs or arguments. The list of neural functions called by the program is then (fk, fkz, ...., fky)- In our example program, the list is (ImagePatch. find(), ImagePatch. find(), ImagePatch. vqa())
Further, assume the host programming language has runtime in which we are able to dynamically assign each of the N calls to generic neural functions to particular backend. Let ji denote which of the backends selected for the i-th generic neural function call, where ji {1, }. That is, we select the j-th available neural backend mk,,j; for the i-th generic neural function call.
Thus, we can customize the behavior of an FMP to optimize for accuracy and runtime cost specific program input, by choosing a specific list of backends 5 (Ma ..., m We call 5 a program configuration vector. On input x, we use p(x|T) denote the output of the program, given that program configuration vector T was chosen.
Generality. This framework generalizes the formulation of existing LLM resource manage- ment methods, including routing and cascading, Routing, as it is typically defined, is the problem of choosing specific backend for a simple program that consists of single generic neural function call: lambda x fxx.. Cascading can be implemented as foundation model program with nested if-else statements.
Task objective. The idea of using FMPs for resource use optimization can be instantiated in a wide range of problems. In this paper, we focus on settings in which the goal is to solve a task - for example, answer a question - on sequence of input-output pairs {x,, yr ) We assune that the structure of the programs we use only depends on the overall task and not the specific inputs. Therefore, on the input x for time step f, we only need to decide on a suitable program configuration vector o; We want o, to be such that the program execution output p(x; ō.) approximates the ground truth yt, while minimizing execution cost. To capture this trade-off, we define the following reward function:
R R Nt. y:) -((p(x)))), y.) AC
where L quantifies the output discrepancy between p(x: T.)) and the ground truth yı, C represents the actual computational cost incurred when running the program with configu- ration 8, on input xt, and À > 0 is trade-off weighting factor. Importantly, due to control flow in the program, not all neural backends specified in o may be invoked on a given input; C accounts only for the cost of the operations actually executed.
3

---

Published as a conference paper at COLM 2025
Over T time steps, the objective is to learn policy that maps each input to program configuration vector j. Let be the space of such policies. We seek to solve the problem
max mtll
Σ R(ō, Nt, xt,y1) y1) subject to हे r(x)).
(1)
Importantly, we require this optimization problem to be solved online. That is, we assume that our inputs arrive sequentially and require decisions be made without prior knowl- edge of the ground truth. Only after the selected configuration is executed and the output p(x; 84) is produced is the ground truth y/ revealed and the reward R (0 Xt, computed.
3 Methodology
Our approach to addressing this problem consists two key phases: offline code generation and online resource allocation.
3.1 Offline Code Generation
We begin by synthesizing foundation model program p from the user specification us- ing an LLM. This process yields a task-specific program sketch, including sequence of generic neural function calls (fky figr...,ffy. which defines the high-level structure of the computation, while the backend selection for these neural functions is determined online.
The correctness of the FMP is critical, it defines the entire computational workflow for the task. To ensure transparency and verifiability, FMPs are constructed with an explicit neurosymbolic representation, making them straightforward to inspect, validate, and debug. Although we employ an LLM to generate these programs, our framework is designed to be agnostic the source of the FMP and fully supports human-authored workflows.
3.2 Online Resource Allocation
After offline synthesis, the main challenge is to select program configuration vector ह for each input x,, dynamically assigning a neural backend miyy E M₁, to each function call fi.- The space of possible configurations grows combinatorially with N, making exhaustive search intractable. To address this, we propose a structured policy that decomposes this decision process into N manageable sub-policies,
per function call.
Specifically, for each function call fke we define a sub-reward function:
Tkis = (m N ((:(xx(0)),)1 where mkyji E o7.
This sub-reward decomposes the global reward R R yt) into structured contributions. It integrates the local computational cost C (mar)) associated with backend Mkjjj and portion
of the predictive loss ((p(z, (..), y:), that determined when the program p is executed with the entire configuration 7/.
To model these rewards, we define a subpolicy πt; with learnable parameters fg.. Given the input x,, subpolicy Ti, outputs reward prediction
K = nzz (mari (x,) for each mayh E M
This structured design simplifies the decision space: rather than jointly optimizing over all fl; x... X Mky backend combinations, we train separate subpolicies. Each subpolicy is specialized to one of the N function calls, thereby simplifying the optimization process, enabling parallel learning, and reducing unwanted interference across calls. This per-call decomposition is critical for precise credit assignment. In monolithic joint policy, it difficult to attribute rewards correctly, especially in the presence of control flow where some function calls may be conditionally skipped. Our structured approach resolves this
4

---

Published as a conference paper at COLM 2025
Algorithm 1 Structured REINFORCE Framework
Initialize: Policy parameters e, uncertainty estimates U learning rate y/, exploration factor
for each input x do for each function call fú, in program p do
Predict reward Kks.i = TT; (MKk, Ne; 0x,) for each FM backend migs.ji
Compute uncertainty ok,,i VE U
Sample adjusted reward for exploration:
PkIM N (rkhii (v. okii)
Select FM backend "k,, with highest sampled reward Pkani Update parameter uncertainties Ukz end for
Execute program p with selected configuration (Mkk) Mkxdss
Observe final reward ( X;, for each function call fi, do
Compute policy gradient V ey I (Tgg) based on observed reward
Update policy parameters:
0% 0g Vee, J (TTK,)
end for end for
by updating subpolicy only when its corresponding function is executed, ensuring that reward signals are correctly aligned with the decisions that caused them.
Gradient-based Thompson Sampling. To balance exploration and exploitation in the online setting, decisions are made using Thompson Sampling (Zhang et al., 2020) instead of greedily selecting the FM backend with the highest predicted reward. For each backend Mkkjj E M2. the subpolicy samples a reward from a normal distribution:
Pkub N (tkast (v (koo)
where Okyl
quantifies uncertainty in the reward prediction. Here, / indexes each individual parameter of the subpolicy, 8h,j is the gradient of the reward prediction with respect parameter Uj; tracks the accumulated gradient-based parameter uncer- tainties, and scales the exploration. We select the backend with the highest sampled reward:
arg max Pknjji" Ae.
After selection, the uncertainty parameter Ug is updated to refine future exploration:
UK U 8ka
where 2 is the gradient of the selected backend mk. with respect parameter 1.
We repeat the above process for each = 1,..., N, allowing each subpolicy to choose one backend per function call, thereby yielding the program configuration vector at time step !:
c (mk 11k
MiN.ff
Structured REINFORCE Algorithm. We now describe the online learning of the sub- policies using only the global reward R( X,, Vt) observed after execution. The learning objective for the overall policy = ( Tky is to maximize cumulative reward over episodes:
I(T)= = Σ R(T,xxyyt)
where Uz (mK ...
5

---

Published as a conference paper at COLM 2025
Since the reward (i X,, yr) is equivalent to the aggregation of all sub-rewards:
R x1)):)
(p((x))))) vi AC(T.)
N 1 - (p AC (mkks))
N
Σ =1
convert the learning objective into optimizing each subpolicy niy independently:
I Σ B ~ (11x)) [rrnt]
((Th))
Because the program execution non-differentiable due control flow structures like condi- tional branches and loops (Kreikemeyer & Andelfinger, 2023), we employ the REINFORCE algorithm (Williams, 1992) estimate policy gradients:
I EE Te, (1xx) Vogg log 74, (Mi Xti 02,))
Vor 0gg (Tt))
Note that each ' depends the full program execution but reflects partial credit assignment for subpolicy Tk
In practice we approximate the expectation using S sampled trajectories:
V&,y (
(6) log TT, (m
xx 0x,)
(+)
The sub-policies are periodically trained to stabilize learning:
02 + 02, VV I (TKk)),
where 7) is the learning rate.
The overall framework is detailed in Algorithm with walk-through example in Appendix Figure 5. This methodology provides a tractable solution to the online resource allocation challenge, with a theoretical no-regret guarantee provided in Appendix A. By separating offline synthesis from online optimization and employing a decomposed policy structure, we achieve both flexibility and efficiency in program execution.
Benchmark
Motivated by the need for structured, sequential evaluation beyond the single-imagg--per query setups typical of existing visual question answering (VQA) datasets (Goyal et al., 2017), we introduce two novel streaming VQA benchmarks. These benchmarks are designed to reflect real-world latency-critical deployments by simulating input streams, long-tail difficulty, class imbalance, and adversarial distractors. While partially synthetic, they are constructed using real data (e.g., COCO, GQA) and validated through LLM and human annotations to ensure complexity and robustness.
Our first Streaming Binary VQA benchmark focuses on yes/no question answering, task commonly studied in previous works (Antol et al., 2015; Zhang et al., 2016; Hudson Manning, 2019). In this benchmark, systems are challenged to determine whether sequence of images satisfies complex, compositional queries. These queries incorporate diverse reasoning types-spatin (e.g., "Is there a person riding a bicycle next to a bus on the street?"), logical (e.g., "Are there people riding bikes, scooters, or motorcycles while holding or using umbrellas?"), and numerical (e.g., "Are there at least four horses on beach?") better reflect real-world reasoning demands. The final benchmark includes 33 queries with more than 2000 annotated images for each query, featuring realistic class imbalance setup. Further details the benchmark construction and evaluation are provided in Appendix C.1.

---

Published as a conference paper at COLM 2025
Example 1:
Example 2:
User Query: which bottle is taller, the left one or the right one?
User Query: How eany legs would this aninal have if the number of its tegs suddenly doubled?
Answerable Images:
Answerable Images:
right
Unanswarable Images:
Unanswerable Images:
Unanswerable Images that closely resemble answerable cases:
Unarswerable Images that closely resemble answerable cases:
Randomly selected distractors:
Randomly selected distractoes:
Figure 2: Examples of the synthetic images in the Streaming Open-form VQA benchmark.
Our second benchmark, Streaming Open-form VQA, evaluates a system's ability to answer open-form questions for a sequence of input images. This benchmark spans five reasoning categories: spatial (egg,, "What is in the jar to the left of the juice?"), logical (e.g., "What is the black object on the desk that is not electronic?"", numerical (e.g,, "How many extra bottles of beer do need to make it half dozen?"), comparative (e.g, "Which bottle is taller, the left one or the right one?"), and external knowledge reasoning (e.g., "How many states are there in the country whose flag is shown?"). Images are generated using a diffusion model with dedicated pipeline to ensure diversity and quality control. To evaluate model robustness, we also introduce unanswerable images that are visually similar the query but semantically invalid for answering. The final benchmark includes 50 queries with 500 annotated images per query. Complete details of the image generation pipeline, neurosymbolic program synthesis, and evaluation metrics (exact match accuracy) are described in Appendix C.2.
Experiments
5.1 Implementation Details and Experimental Setups
We implement the structured policy using ResNet-18 with ~11M parameters (He et al., 2016), ensuring the policy training and inference overheads do not exceed the resource savings. During evaluation, our experiments use varying sizes of GLIP (Li et al., 2022b) and GroundingDINO (Liu et al., 2023) for object detection, OFA (Wang et al., 2022), BLIP-2 (Li et al., 2023), and Qwen2.5-VL series (Bai et al., 2025) for visual-language understanding, and Llama 3 series (Dubey et al., 2024) as the LLMss We implement an instrumentation system that analyzes the programs to determine function calls, modifies the abstract syntax tree (AST) to inject program configurations, and executes the modified program while collecting performance metrics including the execution traces and the computational costs.
5.2 Baselines
We compare system against several baselines to establish its effectiveness:
Single MLLMs. We evaluate our system against the state-of-the multimodal LLMs (MLLMs) that integrate both vision and language reasoning capabilities (Bai et al., 2025).
MLLM Routing. As an alternative adaptive strategy, a multi-armed bandit dynamically routes user queries to multimodal LLMs of varying sizes with different cost-accuracy trade- offs based on estimated rewards, balancing exploration and exploitation (Nguyen et al., 2024; Li, 2025). However, it does not account for the task structures in user queries.
7

---

Published as a conference paper at COLM 2025
0.995
0.70
MLLM, Cost
Overall Accuracy
Overall F1-score
Single MLLM, Lowest Cost
0.993
0.65
FM Programs, Highest Cost.
RM Programs, Lowest Cost
Pareto Random, MILMs
Programs
0.991
Pareto front, MLUM Routing
Programming (Unstructured)
0.55
Pareto Front, FM Programming (Ours]
0.989
0.50
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
Normalized Cost
Normalized Cost
Figure 3: Experimental results the Streaming Binary VQA benchmark. Costs are normal- ized based on the inference costs of the most expensive MLLM, i.e,, Qwen2.5-VL 72B.
Static FM Program Configurations. common approach to resource management is to use fixed, pre-determined configuration of foundation models for the FM programs without dynamic backend selection. Given the combinatorial space of configurations, we implement two variants: one using the cheapest FM configurations and another using the most expensive configurations.
Pareto-Random Routing. Following the standard practice in prior works (Hu al., 2024; Jitkrittum et al., 2025), we employ a straightforward yet effective Pareto-random routing strategy through linear interpolation. We implement this approach separately for two scenarios: multimodal LLMs and static FM program configurations.
In the experiments reported in the main paper, we consistently use Qwen2.5-VL (3B and 72B) for both the Single MLLM and LLM Routing baselines. The FM program backends consist of Grounding-DINO Tiny (172M) and Base (224M) for object detection, along with Qwen2.5-VL. and 72B for vision-language understanding.
5.3 Results
Streaming Binary VQA. As shown in Figure 3, the FM Programming approach achieves accuracy comparable to the largest MLLM, while reducing computational costs by over 98%. This striking efficiency gain stems from its ability to exploit task structure: FM Programs use lightweight object detection modules to filter out most negative samples, drastically reducing expensive MLLM inference.
Beyond cost savings, FM Programming consistently delivers superior cost-accuracy and cost- F1 trade-offs, particularly in the low-cost regime. The Pareto frontier of FM Programming (green line) significantly outperforms both the Pareto Random baseline for FM Programs (red dashed line) and the LLM routing baseline (blue line), illustrating the effectiveness of structured decision-making via the Structured REINFORCE algorithm.
Compared to the LLM routing baseline, FM Programming achieves 6% improvement in Fl score at similar computational cost (10% of the largest MLLM). While its maximum Fl score is lower than that of the Single MLLM and LLM routing baselines, this is due to conservative thresholds in the object detection modules that prioritize precision over recall to minimize costly false positives. As shown in Appendix Figure 8, the learned policy increasingly favors precision over recall the cost budget grows. In practice, this trade-off can be adjusted by tuning the reward function used in Structured REINFORCE.
To evaluate robustness, backends. As shown in Appendix Figure 9, despite reduced backend capabilities leading to lower raw accuracy and Fl scores, FM Programming still maintains clear Pareto dominance over the baseline. This demonstrates its strong generalizability and adaptability across different FM backend configurations.
conduct additional experiments using alternative set of FM
8

---

Published as a conference paper at COLM 2025
0.86
0.84
Single MLLM, Highest Cost Single MILM,, Lowest Cost
Overall Accuracy
X FM Programs, Highest Cost Programs, Lowest Cast
0.80
Pareto Random, MULMs
0.78
Parato Random, FM Programs
Frent, Routing
0.76
Pareto Frant, FM Programming (Unstructured)
Pareto Front, FM Programming (Ours)
0.0
0.2
0.4
0.6
0.8
1.0
Normalized Cost
Figure 4: Experimental results on the Streaming Open-form VQA benchmark. Costs are normalized based on the inference costs of the most expensive MLLM, Le., 72
Streaming Open-form VQA. We further evaluate our method on the more challenging Streaming Open-form VQA benchmark. As shown in Figure 4, FM Programs (red dashed line) consistently outperform MLLMs (black dashed line) by over 2% in accuracy at equiv- alent cost, showcasing the advantage of modular programs over end-to-end models in leveraging task structures.
Building on this, the FM Programming approach (purple line) effectively expands the Pareto frontier. Through dynamic backend allocation with Structured REINFÖRCE, it achieves up to 50% cost savings without sacrificing performance compared to the largest MLLM, and in some cases even outperforms the MLLM while reducing cost by 30%.
Notably, FM Programming offers high marginal returns in low-cost regimes small in- creases in cost yield substantial accuracy gains. It clearly surpasses the Pareto Random baseline and consistently outperforms the LLM Routing method, providing better cost- performance trade-offs. This demonstrates that the proposed FM Programming framework is effective in fully leveraging the task and input structure for optimal cost-efficiency.
Ablation Study. To assess our structured policy design, we compare it against an unstruc- tured policy variant that jointly optimizes all backend selections. As shown in Figures 3 and 4, the unstructured policy (yellow line) significantly underperforms on both benchmarks, due to its inability to manage conditional branches and accurately assign rewards to local decisions, particularly when the resource budgets increase. This highlights the critical role of our Structured REINFORCE algorithm in enabling precise credit assignment and effective resource allocation.
These results emphasize that FM Programming is not only cost-efficient but also highly adaptive and scalable. Its ability to generalize across both binary and open-form VQA tasks suggests strong potential for real-world deployment in latency- and resource-constrained scenarios.
Related Works
6.1 Multi-modal Reasoning
Multi-modal reasoning tasks, such as visual question answering, require integrating vision and language to address complex queries. End-to-end models, powered by large pre-trained transformers (Deitke al., 2024; Bai et al., 2025), achieve high accuracy but often come with significant computational costs and limited interpretability. In contrast, modular approaches like ViperGPT (Surís et al., 2023) and VisProg (Gupta & Kembhavi, 2023) decompose complex tasks into smaller, executable programs, enhancing flexibility and interpretability by dynamically composing models based on task needs. Compared to the existing methods that rely fixed programs, our work extends this modular paradigm with particular

---

Published as a conference paper at COLM 2025
focus cost-efficiency, introducing dynamic FM backend selection to handle varying input complexities for achieving the Pareto frontier between resource and performance.
v
6.2 Foundation Model Inference Cost Optimization
Optimizing foundation models, such as LLMs and MLLMs, is essential for deployment in resource-constraine environments. Common techniques include distillation (Hinton et al., 2015; Gu et al., 2023) and quantization (Gholami et al., 2022; Lin et al., 2024) that operate at the model level, and speculative decoding (Leviathan et al., 2023; Miao et al., 2023) and mixture-of-expene
routing (Fedus et al., 2022; Huang et al., 2024) that operate at the token level. In contrast, our approach works at the task level, allowing dynamic resource allocation across multiple subtask backends, making it complementary to these strategies.
More recently, Compound Al systems have emerged, leveraging multiple model backends to optimize inference costs. Among these, LLM routing selects the best model for query to balance cost and quality (Lu et al., 2023; Hu et al., 2024); Cascading uses series of models, starting with simpler ones for easy tasks and escalating to complex ones as needed (Chen et al., 2023; Nie al., 2024). Although effective, these methods generally lack integration with task-specific reasoning structures. In contrast, our approach combines task decomposition with dynamic backend selection in FM programs, enabling resource allocation that adapts to both input complexity and task structures for cost saving.
7 Conclusion
We introduced the first framework to use foundation model programs in optimizing the trade-off between task performance and resource consumption. By decomposing complex, multi-modal reasoning tasks into programs with control flow and dynamically selecting FM backends in online setups, our method can navigate the Pareto frontier of trade-offs between resource use and performance in real-time, in a way that exploits both task and input structure. As demonstrated in our experiments, this strategy can deliver substantial computational savings with minimal performance degradation.
Many directions of future work remain open. The idea of using FMPs for resource-efficient inference goes beyond the tasks we considered; in particular, we believe they can be de- ployed in broader agentic and multi-agent applications. Another direction is to explore more advanced program synthesis techniques, such as ones that jointly learn program structure and configurations.
Limitations
Our framework's performance relies on several assumptions: (a) The initial program struc- ture must be correct - an illogical workflow will lead to sub-optimal performance, regardless of backend allocation; (b) The policy constrained by the capabilities of the available FM backends. If the backend pool is too weak for given subtask, even optimal routing may not achieve the desired accuracy, as shown in Appendix Figure 9; (c) The online learning algo- rithm requires immediate ground-trute feedback, which may not be available in real-wwr roal-world settings; (d) We also do not explicitly model error propagation, where an early mistake from lightweight module can impact downstream steps.
Acknowledgement
We thank the anonymous reviewers for their valuable comments and suggestions in enhanc- ing the paper. This research was supported by the NSF under grant numbers CCF-1918651, 2008240, 2131294, and 2212557, NSE PPoSS award #2316161, ARO award #W911NF-21-1- 0009, DARPA award #HR00112320018,, NIH CTSA award #UM1TR004906, and US DOT Tier-1 UTC CYBER-CARD grant #69A3352388332.
10

---

Published as a conference paper at COLM 2025
References
Josh Achiam, Steven Adler, Sandhini Agarwal, Lama Ahmad, lige Akkaya, Florencia Leoni Aleman, Diogo Almeida, Janko Altenschmidt, Sam Altman, Shyamal Anadkat, et al. Gpt-4 technical report. arXiv preprint ar xxXio:2333.08774, 2023.
Alekh Agarwal, Sham Kakade, Jason D Lee, and Gaurav Mahajan. On the theory of policy gradient methods: Optimality, approximation, and distribution shift. Journal of Machine Learning Research, 22(98): 2021.
Contributors AgentLego. Agentlego:
Open-source tool api library to extend and enhance Ilm agents, december 2023. URL https://github. htsp/ltternLMMManttlee 2023.
Stanislaw Antol, Aishwarya Agrawal, Jiasen Lu, Margaret Mitchell, Dhruv Batra, Lawrence Zitnick, and Devi Parikh. Vqa: Visual question answering. In Proceedings of the IEEE international conference on computer vision, pp. 2425-2433, 2015.
Shuai Bai, Keqin Chen, Xuejing Liu, Jialin Wang, Wenbin Ge, Sibo Song, Kai Dang, Peng Wang, Shijie Wang, Jun Iang, al. Qwen2. 5-vl technical report. Xrv preprint arXiv:2502.13923, 2025.
Yikun Ban, Jingrui He, and Curtiss B Cook. Multi-facet contextual bandits: A neural network perspective. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, pp. 35-45, 2021.
Black Forest Labs. Flux. https: //gi htt.ggitt.....bbcco.oeeeoo wwwp.//baac---orsst-aaaaaa////// 2023.
Kai Chen, Jiaqi Wang, Jiangmiao Pang, Yuhang Cao, Yu Xiong, Xiaoxiao Li, Shuyang Sun, Wansen Feng, Ziwei Liu, Jiarui Xu, et al. Mmdetection: Open mmlab detection toolbox and benchmark. aiv preprint arXiv:1906.07155 2019.
Lingjao Chen, Matei Zaharia, and James Zou. Frugalgpt: How to use large language models while reducing cost and improving performance. ar arviv preprint ar arXio22305.05170 2023.
Matt Deitke, Christopher Clark, Sangho Lee, Rohun Tripathi, Yue Yang, Jae Sung Park, Mohammadreza Salehi, Niklas Muennighoff, Kyle Lo, Luca Soldaini, et al. Molmo and pixmo: Open weights and open data for state-of-the-art multimodal models. ar preprint arXiv=2409.17146, 2024.
Abhimanyu Dubey, Abhinav Jauhri, Abhinav Pandey, Abhishek Kadian, Ahmad Al-Dahle, Aiesha Letman, Akhil Mathur, Alan Schelten, Amy Yang, Angela Fan, et al. The llama herd of models. arXiv preprint ar Xii::2407221783 2024.
William Fedus, Barret Zoph, and Noam Shazeer. parameter models with simple and efficient sparsity. Journal of Machine Learning Research, 23(12)):1-39, 2022.
Switch transformers: Scaling to trillion
2022.
Amir Gholami, Schoon Kim, Zhen Dong, Zhewei Yao, Michael W Mahoney, and Kurt Keutzer. A survey of quantization methods for efficient neural network inference. In Low-power computer vision, pp. 291-326. Chapman and HaIl/CRC, 2022.
Yash Goyal, Tejas Khot, Douglas Summers-Stay Dhruv Batra, and Devi Parikh. Making the v vqa matter: Elevating the role of image understanding in visual question answering. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 6904-6913, 2017.
Yuxian Gu, Li Dong, Furu Wei, and Minlie Huang. Knowledge distillation of large language models. Xiv preprint arXio:2306.08543 2023.
Neha Gupta, Harikrishna Narasimhan, Wittawat Jitkrittum, Ankit Singh Rawat, Aditya Kr- ishna Menon, and Sanjiv Kumar. Language model cascades: Token-level uncertainty and beyond. arxiv preprint ar 2r14:2200..101.6, 2024.
11

---

Published as a conference paper at COLM 2025
Tanmay Gupta and Aniruddha Kembhavi. Visual programming: Compositional visual reasoning without training. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 14953-14962, 2023.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference computer vision and pattern recognition, pp. 770-778, 2016.
Geoffrey Hinton, Oriol Vinyals, and Jeff Dean. Distilling the knowledge in a neural network. arXiv preprint ar arXit:1503.02531 2015.
Qitian Jason Hu, Jacob Bieker, Xiuyu Li, Nan Jiang, Benjamin Keigwin, Gaurav Ranganath, Kurt Keutzer, and Shriyash Kaustubh Upadhyay. Routerbench: A benchmark for multi- IIm routing system. arXiv preprint ar Xrx::22403. 12031, 2024.
Quzhe Huang, Zhenwei An, Nan Zhuang, Mingxu Tao, Chen Zhang, Yang Jin, Kun Xu, Liwei Chen, Songfang Huang, and Yansong Feng. Harder tasks need more experts: Dynamic routing in moe models. arviv preprint arXtv:2403.07657 2024.
Drew A Hudson and Christopher D Manning. Gqa: A new dataset for real-world visual reasoning and compositional question answering. In Proceedings of the IEEE/CVE conference on computer vision and pattern recognition, pp. 6700-6709, 2019.
Aaron Hurst, Adam Lerer, Adam P Goucher, Adam Perelman, Aditya Ramesh, Aidan Clark, AJ Ostrow, Akila Welihinda, Alan Hayes, Alec Radford, et al. Gpt-Ao system card. aiv preprint arXio:2410.21276, 2024.
Aman Jain, Mayank Kothyari, Vishwajeet Kumar, Preethi Jyothi, Ganesh Ramakrishnan, and Soumen Chakrabarti. Select, substitute, search: A new benchmark for knowledge augmented visual question answering. In Proceedings of the 44th International ACM SIGIR Conference on Research and Development in Information Retrieval, pp. 2491-24922222 -448,, 2021.
Wittawat Jitkrittum, Harikrishna Narasimhan, Ankit Singh Rawat, Jeevesh Juneja, Zifeng Wang, Chen-Yu Lee, Pradeep Shenoy, Rina Panigrahy, Aditya Krishna Menon, and Sanjiv Kumar. Universal model routing for efficient llm inference. ar Xiv preprint ar Xii::2502.08773, 2025.
Justin Johnson, Bharath Hariharan, Laurens Van Der Maaten, Li Fei-Fei, C Lawrence Zitnick, and Ross Girshick. Clevr: A diagnostic dataset for compositional language and elementary visual reasoning. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 2901-2910, 2017.
Omar Khattab, Arnav Singhvi, Paridhi Maheshwari, Zhiyuan Zhang, Keshav Santhanam, Sri Vardhamanan, Saiful Haq, Ashutosh Sharma, Thomas T Joshi, Hanna Moazam, al. Dspy: Compiling declarative language model calls into self-improving pipelines. Xiv preprint ar xrXio:2310.03114, 2023.
Justin N Kreikemeyer and Philipp Andelfinger. Smoothing methods for automatic differen- tiation across conditional branches. IEEE Access, 2023.
Woosuk Kwon, Zhuohan Li, Siyuan Zhuang, Ying Sheng, Lianmin Zheng, Cody Hao Yu, Joseph E. Gonzalez, Hao Zhang, and Ion Stoica. Efficient memory management for large language model serving with pagedattention. In Proceedings of the ACM SIGOPS 29th Symposium Operating Systems Principles, 2023.
Yaniv Leviathan, Matan Kalman, and Yossi Matias. Fast inference from transformers via speculative decoding. In International Conference on Machine Learning, pp. 19274-19286. PMLR, 2023.
Junnan Li, Dongxu Li, Caiming Xiong, and Steven Hoi. Blip: Bootstrapping language-image pre-training for unified vision-language understanding and generation. In International conference machine learning, pp. 1 12900. PMI.R, 2022a.
12

---

Published as a conference paper at COLM 2025
Junnan Li, Dongxu Li, Silvio Savarese, and Steven Hoi. Blip-2: Bootstrapping language- image pre-training with frozen image encoders and large language models. International conference machine learning, Pp. 19730-19742. PMLR, 2023.
Liunian Harold Li, Pengchuan Zhang, Haotian Zhang, Jianwei Yang, Chunyuan Li, Yiwu Zhong, Lijuan Wang, Lu Yuan, Lei Zhang, Jenq-Neng Hwang, et al. Grounded language- image pre-training. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 10965-10975, 2022b.
Yang Li. Lim bandit: Cost-efficient Ilm generation via preference-conditionedd dynamic routing. arviv preprint ar Xr1::2502.002733, 2025.
Ji Lin, Jiaming Tang, Haotian Tang, Shang Yang, Wei-Ming Chen, Wei-Chen Wang, Guangx- uan Xiao, Xingyu Dang, Chuang Can, and Song Han. Awq: Activation-aware weight quantization for on-device Ilm compression and acceleration. Proceedings of Machine Learning and Systems, 6:87-100, 2024.
Tsung-Yr Yi Lin, Michael Maire, Serge Belongie, James Hays, Pietro Perona, Deva Ramanan, Piotr Dollár, and C Lawrence Zitnick. Microsoft coco: Common objects in context. In Computer Vision-ECCV 2014: 13th European Conference, Zurich, Switzerland, September 6-12, 2014, Proceedings, Part V 13, pp. 740-755. Springer, 2014.
Haotian Liu, Chunyuan Li, Yuheng Li, and Yong Jae Lee. Improved baselines with visual instruction tuning. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, pp. 26296-26306, 2024.
Shilong Liu, Zhaoyang Zeng, Tianhe Ren, Feng Li, Hao Zhang, Jie Yang, Chunyuan Li, Jianwei Yang, Hang Su, Jun Zhu, et al. Grounding dino: Marrying dino with grounded pre-training for open-set object detection. arXiv preprint arXiv:2303.05499 2023.
Keming Lu, Hongyi Yuan, Runji Lin, Junyang Lin, Zheng Yuan, Chang Zhou, and Jingren Zhou. Routing to the expert: Efficient -wwrrd-guiddd ensemble of large language models. Xiv preprint ar arXio:2311.082 2023.
Pan Lu, Baolin Peng, Hao Cheng, Michel Galley, Kai-Wei Chang, Ying Nian Wu, Song-Chun Zhu, and Jianfeng Gao. Chameleon: Plug-and-play compositional reasoning with large language models. Advances in Neural Information Processing Systems, 36, 2024.
Xupeng Miao, Gabriele Oliaro, Zhihao Zhang, Xinhao Cheng, Zeyu Wang, Zhengxin Zhang, Rae Ying Yee Wong, Alan Zhu, Lijie Yang, Xiaoxiang Shi, et al. Specinfer: Accelerat- ing generative large language model serving with tree-based speculative inference and verification. XrXiv preprint ar arXio:2305.09781, 2023.
Quang H Nguyen, Duy C Hoang, Juliette Decugis, Saurav Manchanda, Nitesh V Chawla, and Khoa D Doan. Metallm: A high-performant and cost-efficient dynamic framework for wrapping 1lms. ar Xiv preprint ar XXio:2407.10834 2024.
Lunyiu Nie, Zhimin Ding, Erdong Hu, Christopher Jermaine, and Swarat Chaudhuri. Online cascade learning for efficient inference over streams. In Forfy-first International Conference on Machine Learning, 2024.
OpenAl. Gpt-4o mini: Advancing cost-efficient intelligence. https://openai. com/index/// 2024.
pt-4o-mini
Dustin Schwenk, Apoorv Khandelwal, Christopher Clark, Kenneth Marino, and Roozbeh Mottaghi. A-okvqa: A benchmark for visual question answering using world knowledge. In European conference on computer vision, pp. 146-162. Springer, 2022."
Tal Shnitzer, Anthony Ou, Mírian Silva, Kate Soule, Yuekai Sun, Justin Solomon, Neil Thompson, and Mikhail Yurochkin. Large language model routing with benchmark datasets. Xix preprint arXtt:2309.15788 2023.
13

---

Published as a conference paper at COLM 2025
Sanjay Subramanian, Medhini Narasimhan, Kushal Khangaonkar, Kevin Yang, Arsha Nagrani, Cordelia Schmid, Andy Zeng, Trevor Darrell, and Dan Klein. Modular visual question answering via code generation. arXiv preprint ar arXio:2306.05392, 2023.
Didac Surís, Sachit Menon, and Carl Vondrick. Vipergpt: Visual inference via python execution for reasoning. In Proceedings of the IEFF/CVF International Conference Computer Vision, pp. 11888-11898, 2023.
Peng Wang, An Yang, Rui Men, Junyang Lin, Shuai Bai, Zhikang Li, Jianxin Ma, Chang Zhou, Jingren Zhou, and Hongxia Yang. Ofa: Unifying architectures, tasks, and modalities through simple machine learning, pp.
learning framework. In International conference on PMLR, 2022.
Ronald J Williams. Simple statistical gradient- fooliwin--- algorithms for connectionist rein- forcement learning. Machine learning, 8:229-255 1992.
Qingyun Wu, Gagan Bansal, Jieyu Zhang, Yiran Wu, Shaokun Zhang, Erkang Zhu, Beibin Li, Li Jiang, Xiaoyun Zhang, and Chi Wang. Autogen: Enabling next-gen Ilm applications via multi-agent conversation framework. arviv preprint ar Xix::2308.08155, 2023.
Mengwei Xu, Wangsong Yin, Dongqi Cai, Rongjie Yi, Daliang Xu, Qipeng Wang, Bingyang Wu, Yihao Zhao, Chen Yang, Shihe Wang, et al. A survey of resource-efficient Ilm and multimodal foundation models. arXiv preprint ar 00o:2401.08092, 2024.
Peng Zhang, Yash Goyal, Douglas Summers-Star Dhruv Batra, and Devi Parikh. Yin and yang: Balancing and answering binary visual questions. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 5014-5022, 2016.
Weitong Zhang, Dongruo Zhou, Lihong Li, and Quanquan Gu. Neural thompson sampling. Xrv preprint ar arXto:2010.0082,, 2020.
Martin Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In Proceedings of the 20th international conference on machine learning (icml-03), pp. 928-936, 2003.
A No-Regret Guarantee for Structured REINFORCE
We establish that our proposed structured REINFORCE algorithm achieves a no-regret guarantee in an online learning setting. Before presenting the main theorem, we outline the key assumptions that underpin our analysis:
Assumption 1 (Bounded Rewards). For all time steps I, configurations ह, E and inpuls x, E D, the reward satisfies R X1,
( yr) E [Rmin/ Rmax), where Rmax Rmin < co.
Assumption 2 (Policy Expressiveness). For each input Xt, there exists an optimal configuration UH E V that maxinizes R(ū,xt, yt). Moreover, the policy class is sufficiently expressive such 1 that there exist parameters ki 1 for which Tt, (m xx; 22; 1, where m the optimal backend for fi, in o2,
Assumption (Sufficient Exploration). The algorithm employs Thompson Sampling with an exploration parameter v > O, ensuring that every backend my. E MM, has a non-zero probability of being sampled at each time step t.
Assumption 4 (Convergence of Policy Gradient). The learning rate nn is 1/ 1/, and the policy parameterization (e.g., softmax over M&) guarantees that gradient updates converge to near-optimal policy (Agarwal et al., 2021).
Assumption 5 (Stationary Input Distribution). Inputs x, are drawn independently and identically distributed (i.id.) from a fixed distribution D, ensuring a consistent optimal policy over time.
With these assumptions in place, we can formally state the main result:
14

---

Published as a conference paper at COLM 2025
Theorem 1. Under Assumptions 1-5, the structured REINFORCE algorithm is no-regret, meaning that the average regret satisfies:
YT - as T
T
both in expectation and with high probability, where the regret "T is defined as:
T
E R(T,xty1) - Σ R(
max BCV
We now prove this theorem, showing that the algorithm's regret diminishes over time. The proof proceeds by defining the regret, analyzing the algorithm's behavior under the assumptions, and bounding the regret both in expectation and with high probability.
Proof of Theorem 1
We start with giving the formal definition of regret "T, which measures the cumulative difference between the maximum achievable reward and the algorithm's actual reward over steps:
YT
max BEV
x1)))
R(B. x..)).
Our goal is to show that the average regret, F, approaches zero as -> co. To simplify the analysis, we stronger benchmark: the optimal context-dependent configuration 8 that maximizes (t,1)) for each Xt. Since maxtev R(T, xt, yt) S Xt, (t),,, we have:
TT E R(F,, x.y1)
Σ R(T..)).11.
This upper bound focuses the proof on the gap between the optimal and achieved rewards per step.
The structured REINFORCE algorithm updates sub-policy parameters 0s, using policy gradients. The expected cumulative reward is:
Σ R(T,,xt.11)
[(T)= = En
with the gradient for each sub-policy:
Va, (TtK.)
Σ E - (1xx) [Ve,, log nı, (ma.. [x;;k;,) Tk
The algorithm approximates this gradient with single sample, updating parameters as:
0 = 17: Veg log π4. (Ma,.) xy; x
where 7/: = 1/Vi (Assumption 4), and the sub-reward is defined as:
The = -C (m
[(p(x) [T),
Assumptions 2 (expressive policy class) and (sufficient exploration via Thompson Sam- pling) ensure that each sub-policy 74; converges the optimal sub-policy Tt. where पे, (mi xi) = for the optimal backend mi, in J. Thus, the overall policy n; con- verges to the optimal policy Λ" leading to E,, [R( ( yt)] + R(T,, X,, yt) as f - cz.
Define the per-step regret as:
pt R(O x,y:) R(ō x(,xx),y))
15

---

E, Published as a conference paper at COLM 2025
with expected value:
E[pp} Ex,=D [R Xt) By [R(T, Nt, y+)]]
Since 74 + n², we have E[pi] - 0. The total expected regret is:
EB B
Elpr].
Given 1/| = f and standard policy gradient convergence (Assumption 4), we bound:
Elrrl s CVT,
for some constant C based on the reward bounds and policy parameters (Zinkevich, 2003; Ban et al., 2021). Thus, the average expected regret satisfies:
E(rr. T
C
0
as T
VT
establishing no-regret in expectation.
Now, we extend this to show that the actual regret yr converges similarly with high probability. By Assumption 1, rewards Rmin), and let Rmax Rmin- Since x are i.id. (Assumption 5) and ū are sampled independently given x; and Tı, the Pt are independent. Applying Hoeffding's inequality to
bounded, pt (-(Rmax R Rmax
YT 1P:p
2E
P P1 2 e) s 2eep
TB²
Set c 8T, so:
282T
P P( 1orr-Iipp [[[r]] 2 8T) S 2xxp
B2
This probability approaches exponentially as T co. Thus, with probability least 2 g²
1 ee2e
which approaches T grows, we have:
YI [B(r]] + 5T < CCV++ ST.
Dividing by T, we find:
YI T
<
+6.
VT
2C 2
For any é > 0, choose ô = & and T >
50 vT
C
< 2, yielding:
'T
T
with probability approaching 1. Hence, . - 0 with high probability, completing the no-regret proof.
B Detailed Experimental Setups
All experiments are conducted on a single machine equipped with NVIDIA A40 GPUs (48GB memory each), running CUDA 12.4. Detailed package versions listed in the envi- ronment file available at Gi tib. Hyperparameter settings are specified the experimental configuration files for binary VQA and open-form VQA.
For the offline code generation, we use prompt format similar to ViperGPT, including the DSL, the user query, and one-shot example. In practice, the generated programs >90% correct, and errors are easily caught during dry runs or audits. A full prompt example is also available at Gi tHu..
16

---

Published as a conference paper at COLM 2025
Online Resource Allocation
Input X
find("cat")
(1.56, 0.67)
(1.61, 0.52)
"Iptoo""
(0.74, 1.03)
(0.91, 0.89)
0
Program Execution
"eal"Is there -"1
(0.67, 0.98)
(0.69, 0.96)
Functions
Policy Tk;
Predicted
Thompson Sampling
Adjusted Reward
Configuration Vector T
fg
Reward
Update parameter uncertainties
Update policy parameters
UN <- Up siaz
Reward R(G,,
Execution
Trace
6, +- 4 VV, J(m.)
Figure 5: A walk-through example showing how FMP is compiled and routed with online resource allocation in Algorithm 1. Here we look at a specific input x for illustration but the user inputs actually arrive continuously in stream.
The current FM backend is set up with VLLM (Kwon et al., 2023), Huggingface Hub, MMDetection (Chen et al., 2019), and AgentLego (AgentLego, 2023). Our framework supports flexible backend construction with any open-source closed-source API-based models. However, due to the unavailability of computational costs of closed-source models, such GPT and Gemini series models, we do not include them in our FM backend during experiments.
For open-form VQA experiments, we consistently use the same system prompt for MLLMs:
System Prompt
Keep your answer short. Try to answer within 3 words. For numerical answers, number digits (e.g., 5 instead of five), and returns the number only. If there are multiple answers, separate them with a comma (e.g., , cat, dog). If you find the question unanswerable based the image content, output "N/A". For example, if the image content is irrelevant to the question, or the content in the image does not fully and clearly match all the entities, humans, attributes, spatial, logical, and numerical constraints in the question, output "N/A".
C Detailed Benchmark Construction and Evaluation
C.1 Streaming Binary VQA
Benchmark Construction. Our dataset is constructed from COCO (Lin et al., 2014), selecting captions that require multi-object compositional reasoning with spatial, logical, or numerical constraints. For each query, we prepare a set more than 2,000 images, sampled based on the similarity of their captions to the query. The system must output a binary decision (yes/no) for each image indicating whether satisfies the compositional query. To enforce structured reasoning, we leverage an LLM2 to generate FM programs in a predefined DSL. These programs decompose the query into discrete reasoning steps, guiding the selection of foundation models for subtask execution. A detailed pipeline for benchmark construction is illustrated in Figure 6.
We GPT-4o (Hurst et al., 2024) the L.M throughout this section unless otherwise specified.
17

---

Published as a conference paper at COLM 2025
dliigg molorgyle degi
Modilied Query
al man and dig nolay
COCO
Selected Images with Captions
Positive Images
High Similarity Images
Manual Validation
Images Captions
Vector Database
Negative Images
Lower Similarity Images
Figure 6: Benchmark construction pipeline for the Streaming Binary VQA dataset.
Annotation and Verification. Eleven human annotators validate the correctness of the neurosymbolic programs and the image labels, ensuring that each program aligns with the intended reasoning process and each image is correctly labeled against the compositional constraints. The final dataset consists of 33 queries covering three primary reasoning types (note that query may fall into multiple types):
Spatial Reasoning (20 queries): These queries require understanding and interpreting the spatial relationships between objects or people in an image. They often describe where things are located relative to each other, e.g., "Is there a person riding bicycle next to bus on the street".
Logical Reasoning (15 queries): These queries involve conditions, attributes, combina- tions that require deductive thinking. The model needs to process logical relationships, such as inclusion, exclusion, conjunction, e.g., "Are there people riding bikes, scooters, or motorcycles while holding or using umbrellas?".
Numerical Reasoning (9 queries): These queries test the ability to understand and count quantities or numbers in scene. They often specify exact counts or comparisons, e-g,, "Are there at least four horses on beach".
Evaluation. Since the benchmark is highly imbalanced, with a positive-to-negatiee ratio of around 1:100, task performance is measured using accuracy, recall, precision, and F1-score.
C.2 Streaming Open-form VQA
To enable evaluation on more complex open-form questions, construct a dataset comprising 50 queries and 25,000 images, spanning five distinct reasoning categories. To ensure the validity and diversity of these queries, we randomly sample them from established benchmark datasets. Specifically, spatial queries are drawn from the GQA dataset (Hudson & Manning, 2019), focusing on queries labeled rels and Rels. Logical queries are also sampled from GQA, targeting the detailed types twoCommon, twoSameMaterial,, twoDifferentc, and twoDi fferent. Numerical queries are selected from the A-OKVQA dataset (Schwenk et al., 2022), while comparative and external knowledge queries are sourced from OKVQAS3 (Jain et al., 2021). To enhance clarity and naturalness, some of the queries are manually rewritten.
Benchmark Construction.
Each query is associated with 500 generated images. The image generation pipeline begins with an LLM generating a set 10 possible answers for each query, proposing potential scene setups along with 3 additional objects, and constructing detailed image descriptions. These descriptions are then used to prompt diffusion model for image generation.
To assess model robustness and reasoning precision, we incorporate unanswerable images that are visually coherent but semantically invalid with respect the query. These include
We FLUX. 1-dev (Black Forest Labs, 2023) as the diffusion model for image generation.
18

---

Published as a conference paper at COLM 2025
Streaming VQA
VQA v2.0
GQA
CLEVR
A-OKVQA
Binary
Open-form
Multiple Objects
Spatial Reasoning
/
Logical Reasoning
/
Query
Numerical Reasoning
Comparative Reasoning
Extemal Knowledge
X
Source
COCO X
COCO & Flickr Synthetic
COCO
COCO
Generation v
Image Unanswerable Images
X
x
X
Queries
1.1M 200K
22M 113K
999,968 100,000
24,903
50
Scale
Images
23,692
66,279
25,000
Image(s) per query
2
1
2-2000
500
Table 1: Comparing to the existing VQA benchmarks (Goyal et al., 2017; Hudson & Manning,
2019; Johnson et al., 2017; Schwenk et al., 2022), Streaming VQA is the first that provides sequence of images for each query.
both unrelated (random) images and images that intentionally crafted to closely resemble answerable cases, making them more difficult to distinguish, as illustrated in Figure 2. This setup challenges models not only to infer the correct answer when possible but also to recognize when question cannot be answered from the image.
Additionally, for each query, we also synthesize the corresponding FM program in the predefined DSL, providing a structured decomposition of the reasoning process.
Quescion-Arswer Pair
Description Generation
Generation
netion winse flgg displeyd have?
Selected Querles
Verfication
Statest 30,
classroom, stadlum, guverTanN everrment buildingg
mexico bus stop, founladdy,
Aetics siatlaned, petroucdirg cteee asch strevt stds,
Existting Benchmarks
Nexicot 32,
Manual Verlication
Mustraliat 6,
Goneration
Image Soone Generation
Object Generation
flag.
Figure 7: Benchmark construction pipeline for the Streaming Open-form VQA dataset.
Annotation and Validation. A two-step validation process is employed. First, a multi- modal LLM, GPT-4o-mini (OpenAI, 2024), verifies each image by generating an answer and comparing it the expected answer. Only images where the MLLM's s response matches the assigned answer are retained. Then, human evaluators verify random image subset, achieving approximately 93% accuracy. The final benchmark encompasses five reasoning types:
Spatial Reasoning (13 queries): These questions require understanding the spatial rela- tionships between objects within a scene, e.g., "What is in the jar to the left of the juice?".
Logical Reasoning (9 queries): This category involves applying conditions, rules, or filters to identify specific objects or answer complex queries, e.g., "What is the black object the desk that is not electronic?", "How many people are wearing both glasses and hat?".
Numerical Reasoning (11 queries): This category requires counting, comparing numbers, or calculating quantities based on visual information, egg., "How many extra bottles of beer do need to make it a half dozen?".
Comparative Reasoning (11 queries): These questions involve evaluating two more objects in terms of their attributes, such as size, height, quantity, or quality, egg., "Which bottle is taller, the left one or the right one?".
External Knowledge Reasoning (6 queries): These questions rely on information that extends beyond what is immediately visible in the image, often drawing common sense or factual knowledge, e.g., "The fruit in the picture is good source of what vitamin?", "How many states are there in the country whose flag is being displayed?".
19

---

Published as a conference paper at COLM 2025
0.68
0.78
Overall Precision
Overall Recall
0.66
FM Programs, Highest Cost
FM Programs. Lowest Cost
0.64
Pareto Random, Programs
0.74
Programming
0.72
0.60
Normalized Cost
Normalized Cost
Figure 8: Pareto front of precision and recall scores the Streaming Binary VQA benchmark. The policy prioritizes precision over recall as the cost budget increases.
0.96
Overall Accuracy
0.94
Overall F1-Score
0.92
FM Programs, Highest Cost
FM Programs, Lowest Cost
0.90
Pareto Random,
0.16
Parato Front, FM Programming
0.88
0.015 0.020 0.025 0.030 0.035 0.040 0.045 Normalized Cost
0.015 0.020 0.025 0.030 0.035 0.040 0.045 Normalized Cost
Figure 9: Additional results on the Streaming Binary VQA benchmark with different FM backends. Costs are normalized based on the inference costs of Qwen2.5-VL 72B. The backends include GLIP tiny (231M) and base (430M) models (Li al., 2022b) for object detection, OFA base (182M) (Wang et al., 2022) and BLIP-2 OPT-2.7B (3.745B) (Li et al., 2023) for language-vision understanding. FM programming outperforms the baseline with better cost-performance trade-offs, demonstrating its adaptability across backend setups.
Evaluation. Performance for the streaming VQA task is evaluated using exact match accuracy, measuring the proportion of questions answered correctly without partial credit.
20


Reviews:
[{"review_id": "mGSzKfvJkr", "reviewer": "Reviewer_Y93Q", "summary": "This paper introduces a novel framework for resource-efficient inference in multi-modal tasks by leveraging Foundation Model Programs (FMPs). These programs, composed of modular neural function calls, dynamically select appropriate model backends based on input complexity. The approach combines program synthesis with online backend selection via a structured REINFORCE algorithm and Thompson Sampling, enabling dynamic trade-offs between computational cost and accuracy. Experiments on newly introduced streaming VQA benchmarks show up to 98% cost savings with minimal loss in performance, highlighting the practical utility and flexibility of the proposed method.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "* It introduces a novel and modular framework that generalizes routing and cascading.\n* It has shown strong cost-performance trade-offs. \n* The use of REINFORCE is interesting here.", "reasons_to_reject": "* It covers limited number of tasks here. The paper has proposed its own benchmarks. It will be interesting to see how the method applies to broader domains.\n\n* The method is complex. The paper did not show limitations or error analysis for when the system would fail.", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "dV3hlgX01p", "reviewer": "Reviewer_3qCW", "summary": "This paper introduces a resource-efficient inference framework using Foundation Model Programs (FMPs), which decomposes tasks into modular workflows and dynamically selects model backends of varying scales. The method achieves 98% resource savings with minimal accuracy loss on novel streaming VQA benchmarks (spanning spatial, logical, and numerical reasoning), outperforming monolithic models and routing baselines. Key innovations include a structured REINFORCE algorithm that decomposes policy optimization into sub-policies and gradient-based Thompson Sampling for sample-efficient exploration, supported by no-regret theoretical guarantees. While broader task validation (e.g., text-only workflows) and deployment overhead analysis (e.g., cold-start latency) remain open challenges, the work significantly advances practical FM deployment by explicitly leveraging task structure for resource-performance Pareto optimization.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "1. Addresses the critical challenge of inference-time resource costs in foundation model programs, a pressing issue for real-world deployments.\n\n2. Combines program synthesis, online learning (structured REINFORCE + Thompson Sampling), and theoretical analysis (no-regret guarantees in Appendix A).\n\n3. Introduces two novel benchmarks for streaming VQA with compositional reasoning (33 binary and 50 open-form tasks).\nDemonstrates 98% resource savings over monolithic models with minimal accuracy loss.\nExtends analysis to precision-recall tradeoffs and alternative backends.", "reasons_to_reject": "1. Experiments focus on VQA; broader validation (e.g., agentic planning, text-only tasks) is needed.\n\n2. Overheads from program synthesis and cold-start model loading are not quantified.\n\n3. The streaming setup assumes immediate ground-truth feedback, which is unrealistic in many real-world scenarios (e.g., delayed or missing feedback).\n\n4. The policy’s dependency on predefined subtasks limits flexibility. Joint optimization of program structure and backend selection is unexplored.", "questions_to_authors": "1. Your streaming VQA benchmarks use synthetic/modified datasets. How do you ensure these reflect real-world challenges, such as distribution shifts or adversarial inputs? Have you tested on established benchmarks (e.g., COCO, A-OKVQA) to validate generalizability?\n\n2. If a lightweight backend (e.g., object detector) makes an error early in the program, how does this affect downstream modules? Is there a recovery mechanism, or does the system rely entirely on the initial module’s correctness?\n\n3. Could you elaborate on the LLM-based program synthesis process? What prompts/templates were used? How do you handle incorrect program structures generated by the LLM, and what is the error rate in practice?\n\n4. The motivation of this paper is similar to the previous work [1], please discuss the differences in related work.\n\n[1] De-fine: Decomposing and Refining Visual Programs with Auto-Feedback", "extra_scores": {}}, {"review_id": "phLu4icDTg", "reviewer": "Reviewer_PfjH", "summary": "This paper proposes a framework for resource-efficient inference using Foundation Model Programs (FMPs), where tasks are decomposed into neurosymbolic programs that invoke different foundation model backends with varying computational costs. A structured online policy learns to select backends adaptively for each function call depending on the input. This allows simple sub-tasks to be handled by small models, while complex ones use more powerful foundation models. Experimental results show significant inference cost savings with minimal accuracy degradation.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "The problem tackled—real-time resource bottlenecks in LLM inference—is both important and timely.\n\nThe modular decomposition of reasoning tasks into executable programs might not be new, but using this to dynamically allocate computation via backend selection is practical.\n\nThe use of structured policies with decomposed sub-policies is technically sound and works well in practice.", "reasons_to_reject": "The method has only been tested in a specific task setting (streaming VQA), using image-language tasks. It’s unclear whether the same method would generalize to other multi-modal problems (e.g., audio, video, or multi-turn dialog), where the notion of task decomposition and backend assignment might be more ambiguous. This should be discussed explicitly in Section 7.\n\nIn Section 3.2, the policy gradient training assumes that each function call can be independently optimized. While this makes the optimization tractable, it potentially ignores important dependencies between calls in real-world programs (e.g., errors compounding across steps). A brief analysis or ablation (e.g., full policy vs. per-call policy) would help support this design choice.\n\nThe method is compared against reasonable baselines (static FM config, LLM routing), but other recent cost-aware LLM inference techniques (e.g., speculative decoding, efficient MoE routing, dynamic prompt compression) are not discussed or compared, which weakens the positioning of this work in the broader ecosystem.\n\nThe REINFORCE-style algorithm is presented clearly, but it’s still challenging to grasp the full execution flow from the paper alone. Algorithm 1 is helpful but dense; an additional diagram or walk-through (e.g., on a toy example program) would improve accessibility.\n\nAlthough new benchmarks are provided, both are synthetic or constructed, with limited discussion on their transferability to production tasks. The authors should clarify how realistic the workloads are (e.g., is Streaming VQA representative of real-world latency-critical deployments?).", "questions_to_authors": "* Would this approach generalize to multi-turn dialog or multi-hop retrieval tasks where structure is more latent?\n* Have you tested stability of the sub-policy training (e.g., convergence behavior over seeds)?\n* Could the method benefit from joint learning of program generation and backend selection instead of separating them?", "extra_scores": {}}, {"review_id": "y53zDWysqh", "reviewer": "Reviewer_MUgH", "summary": "This paper proposes Foundation Model Programs (FMPs) to address inference-time resource efficiency in multi-modal tasks like visual question answering (VQA). By decomposing tasks into modular subroutines and dynamically selecting foundation model (FM) backends (e.g., small vs. large models) based on input complexity, the approach aims to balance accuracy and computational cost. The method uses structured REINFORCE with Thompson Sampling to learn backend selection policies, validated on two new streaming VQA benchmarks (binary and open-form). Results show up to 98% resource savings over monolithic models with minimal accuracy loss.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "1. The paper introduces Foundation Model Programs (FMPs), a new method that combines symbolic reasoning with neural networks and dynamically selects the best backend to improve resource efficiency during inference. This framework allows for detailed, input-specific allocation of resources, offering a fresh perspective on how to integrate multiple models into one system.\n\n2. The proposed method achieves up to 98% savings in resource usage on two new streaming visual question-answering (VQA) benchmarks while still maintaining strong accuracy (for example, a 6% improvement in F1 score compared to LLM routing at only 10% of the cost). These benchmarks fill important gaps in evaluating systems that handle sequential tasks under tight resource constraints, and the experiments show that the approach is fairly robust when using different backend setups.", "reasons_to_reject": "1. The benchmarks based on synthetic data or COCO lack the complexity of real-world scenarios (e.g., adversarial examples, domain shifts, and more complex instruction requirements), which raises concerns about how well the method can generalize. Additionally, the reliance on pre-generated programs assumes that the LLM-produced code is of high quality, which might not reflect the challenges faced in practical deployment.\n\n2. The overall system involves multiple backend models, and the paper does not systematically analyze how cumulative errors and contextual dependencies interact in complex ways. There is a particular concern about how well the system will perform in real-world environments.", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper introduces foundation model programs (FMPs), offering a solution to the growing challenge of inference-time resource costs for large foundation models. By translating tasks into programs and learning policies for resource allocation, the proposed method allows simpler tasks to be handled by smaller, cheaper models, while more complex tasks utilize larger, more capable models. The authors also introduce two benchmarks for binary and open-form visual question answering. The proposed approach demonstrates significant resource savings with minimal accuracy loss.

Pros:
- The proposed approach is suitable for real-world deployment where computational resources are constrained.
- The proposed streaming tasks are new for agentic evaluation.
- The authors conduct comprehensive analyses of the proposed FMPs and new benchmarks.

Cons:
- The implementation of the system, which includes code generation, program synthesis, and dynamic backend selection, is complex and may be challenging to integrate into existing systems. The authors promise to add the discussion of the incorrect workflow structure or incapable neural backends in the final version.
- Limited Evaluation: The manuscript only reports their performance on streaming tasks. The authors claim the proposed approach is modality-agnostic and promise to add more discussion in the final version.
Decision: Accept