A method and system are provided for improving inlining using stack trace cache-based dynamic profiling. In one embodiment, a relationship map is provided to map a key representing a caller-callee relationship with a corresponding value indicating a frequency of call site executions. Whether a last stack frame of a stack frame trace is cached is determined. A caller-callee relationship is recorded if the last stack frame is not cached, wherein the caller-callee relationship is recorded in the relationship map, and the relationship map is updated with the recorded caller-callee relationship and then monitored via a recompilation scheduler, the monitoring to determine when a compilation or recompilation of callers and callees is to be performed. A turning on or turning off of dynamic profiling is conducted to perform partial unwinding of the frames in the stack trace.