Exascale computing systems will execute computationally intensive tasks on unprecedented amounts of data. Tuning the design of such systems for a specific application or for an application domain is a challenging task as it is not yet possible to analyze the actual run-time behavior of exascale applications. Run-time properties, such as the memory access pattern, the available instruction-level parallelism and the instruction mix, are valuable information for architects to tune the processing elements, the memory system and the communication infrastructure. We propose a methodology for extrapolating application properties at exascale from an analysis of workload sizes feasible on current systems. The methodology is suitable for applications scaling over different parameters (e.g., the number of vertices and edges represent two parameters in a graph algorithm). The proposed methodology combines a) a statistically sound approach for model selection and b) knowledge coming from computational theory, such as the order of complexity of the application under analysis. Compared with state-of-the-art techniques, the proposed methodology reduces the prediction error by an order of magnitude on the instruction count and improves the accuracy of memory access pattern prediction by up to 1.3×.