The estimation of permeability in carbonate formations remains one of the main challenges in reservoir engineering. Existing literature predominantly utilizes total porosity as the sole input for characterizing permeability. However, the recognition of other influential parameters and their corresponding correlations is deemed important for enhancing accuracy, particularly in heterogeneous tight and deep carbonate formations. Despite progress, a universal, accurate, and straightforward approach for achieving this goal is still lacking. In this study, the advanced heuristic algorithm known as gene expression programming (GEP) is employed to estimate absolute permeability. An all-inclusive database that includes permeability, formation resistivity factor, total porosity, moldic porosity, interparticle porosity, and non-fabric-selective dissolution (connected) porosity is compiled from existing literature. Initially, a sensitivity analysis is conducted to identify the key variables affecting permeability. Notably, the formation resistivity factor emerges as the most relevant variable on permeability prediction. Subsequently, the reliability of the database is assessed using Williams’ plot to detect outliers. After excluding the outlier data and considering the detected influential variable on permeability, multiple realizations of GEP modeling strategies are constructed. As a result, four GEP-derived symbolic equations are proposed. Statistical measures and graphical analyses demonstrate that GEP Model-IV provides the most accurate estimations, with a root mean square error (RMSE) of 1.09, a determination coefficient (R2) of 0.72, and a mean absolute error (MAE) of 1.33. Furthermore, the accuracy of the proposed GEP Model-IV is verified by Williams’ plot, covering approximately 97.32% of the databank. Finally, it is recognized that considering pore description parameters enhances the accuracy of permeability estimation, particularly in studies characterizing carbonate reservoirs, especially when dealing with tight and deep formations.