A computer-implemented method for looking up anti-malware metadata may include identifying a plurality of executable objects to be scanned for malware before execution. The computer-implemented method may also include, for each executable object within the plurality of executable objects, assessing an imminence of execution of the executable object. The computer-implemented method may further include prioritizing, based on the assessments, a retrieval order for anti-malware metadata corresponding to the plurality of executable objects. The computer-implemented method may additionally include retrieving anti-malware metadata corresponding to an executable object within the plurality of executable objects based on the retrieval order. Various other methods, systems, and computer-readable media are also disclosed.