An update-insert (“upsert”) interface manages updates to key-value storage at a memory or storage device. An upsert token is used to store a key and data for a transform to update a previous value stored for a key-value pair. The upsert token processing includes an upsert command to generate the upsert token for an existing key-value pair and store the upsert token in one or more first non-volatile memory (NVM) devices maintained at a memory or storage device. A hash-to-physical (H2P) table or index stored in one or more second NVM devices of the memory or storage device is utilized to locate and read the data for the key and the data for the transform and coalesce the transform(s) into a current value for the key-value pair, thereby avoiding unnecessary read and write amplification when updating key-value storage.