{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/129705"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/129705","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Ghostdecoding: leveraging random-feature kernels for error-aware and training-free KV cache selection","abstract":"Submission published under a 24 month embargo labeled 'Closed Access', the embargo will last until 2027-05-01","abstract_html":"Submission published under a 24 month embargo labeled 'Closed Access', the embargo will last until 2027-05-01","abstract_has_math":false,"creators":["Guo, Hao"],"institution":"University of Illinois Urbana-Champaign","degree_name":"M.S.","degree_level":"Thesis","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":["Mendis, Charith"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2025,"date_issued":"2025-04-22","date_published":"2025-04-22","updated_at":"2026-07-22T22:25:05Z","subjects":["Large Language Models","Efficient ML","KV Cache"],"languages":["en","eng"],"rights":["Copyright 2025 Hao Guo"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"https://hdl.handle.net/2142/129705","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Mendis, Charith"]},{"key":"dc:creator","label":"Author","values":["Guo, Hao"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2025-04-22","2025-05"]},{"key":"dc:type","label":"Dc Type","values":["text","Thesis"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Thesis"]},{"key":"thesis:degree_name","label":"Degree Name","values":["M.S."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Large Language Models","Efficient ML","KV Cache"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en","eng"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2025 Hao Guo"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://hdl.handle.net/2142/129705"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Submission published under a 24 month embargo labeled 'Closed Access', the embargo will last until 2027-05-01","The student, Hao Guo, accepted the attached license on 2025-04-22 at 00:56.","The student, Hao Guo, submitted this Thesis for approval on 2025-04-22 at 01:04.","This Thesis was approved for publication on 2025-04-22 at 15:40.","DSpace SAF Submission Ingestion Package generated from Vireo submission #21877 on 2025-10-19 at 19:53:35","Key-value (KV) cache is essential for efficient inference in large language models (LLMs) by storing intermediate representations to reduce redundant computations. However, as sequence lengths grow, it becomes a major bottleneck due to increasing computational and memory demands. Existing KV cache compression methods mitigate this issue by pruning or selecting critical entries, but often suffer from several limitations, including unpredictable errors, limited dynamism, and strong assumptions about context relevance. In this work, we propose GhostDecoding, a novel training-free KV cache selection mechanism that dynamically reduces the effective sequence length while maintaining error awareness for evicted entries. Using a random feature softmax kernel, our method estimates the attention score of an arbitrary number of evicted positions with O(1) time and space overhead, and selectively recomputes them when necessary. We develop efficient sparse CUDA kernels to support our algorithm. Experimental results demonstrate that GhostDecoding achieves up to 1.6× more computation reduction compared to H2O, leading to up to 1.9× decoding speed-up compared to full attention on long sequences."]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Ghostdecoding: leveraging random-feature kernels for error-aware and training-free KV cache selection"]}]}],"canonical_facts":{"dc:contributor":["Mendis, Charith"],"dc:creator":["Guo, Hao"],"dc:date":["2025-04-22","2025-05"],"dc:description":["Submission published under a 24 month embargo labeled 'Closed Access', the embargo will last until 2027-05-01","The student, Hao Guo, accepted the attached license on 2025-04-22 at 00:56.","The student, Hao Guo, submitted this Thesis for approval on 2025-04-22 at 01:04.","This Thesis was approved for publication on 2025-04-22 at 15:40.","DSpace SAF Submission Ingestion Package generated from Vireo submission #21877 on 2025-10-19 at 19:53:35","Key-value (KV) cache is essential for efficient inference in large language models (LLMs) by storing intermediate representations to reduce redundant computations. However, as sequence lengths grow, it becomes a major bottleneck due to increasing computational and memory demands. Existing KV cache compression methods mitigate this issue by pruning or selecting critical entries, but often suffer from several limitations, including unpredictable errors, limited dynamism, and strong assumptions about context relevance. In this work, we propose GhostDecoding, a novel training-free KV cache selection mechanism that dynamically reduces the effective sequence length while maintaining error awareness for evicted entries. Using a random feature softmax kernel, our method estimates the attention score of an arbitrary number of evicted positions with O(1) time and space overhead, and selectively recomputes them when necessary. We develop efficient sparse CUDA kernels to support our algorithm. Experimental results demonstrate that GhostDecoding achieves up to 1.6× more computation reduction compared to H2O, leading to up to 1.9× decoding speed-up compared to full attention on long sequences."],"dc:format":["application/pdf"],"dc:identifier":["https://hdl.handle.net/2142/129705"],"dc:language":["en","eng"],"dc:rights":["Copyright 2025 Hao Guo"],"dc:subject":["Large Language Models","Efficient ML","KV Cache"],"dc:title":["Ghostdecoding: leveraging random-feature kernels for error-aware and training-free KV cache selection"],"dc:type":["text","Thesis"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["Thesis"],"thesis:degree_name":["M.S."],"thesis:institution_name":["University of Illinois Urbana-Champaign"]},"updated_at":"2026-07-22T22:25:05Z"}