In modern operating system, virtual and physical address translation is done through paging. We argue that different address space implementations could be more competitive than paging. Within an experimental aero-kernel, Nautilus, we decouple the abstraction of address spaces from its implementation and implement paging as well as a new novel implementation, KARAT, which is an allocation level address space implementation based on Compiler-and Runtime-Based Address Translation (CARAT). Using KARAT, we show that the same functionality of paging is possible while providing new benefits such as finer grain control of memory. KARAT is implemented using a combination of the kernel, compiler, and runtime which operates without needing to make changes to the original code.