{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,29]],"date-time":"2026-05-29T21:09:27Z","timestamp":1780088967408,"version":"3.54.0"},"reference-count":36,"publisher":"Association for Computing Machinery (ACM)","issue":"2","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Meas. Anal. Comput. Syst."],"published-print":{"date-parts":[[2026,5,29]]},"abstract":"<jats:p>\n                    Retrieval services increasingly operate over continuously updated corpora, yet must keep latency and cost predictable. In practice, many pipelines rely on TTL-based caching with periodic refresh, which inevitably creates stale windows. We formalize the staleness-latency-cost tradeoff and prove a lower bound for periodic TTL refresh: the staleness violation rate is at least p\n                    <jats:sub>dep<\/jats:sub>\n                    (\u03c4)\/2, where p\n                    <jats:sub>dep<\/jats:sub>\n                    (\u03c4) is the probability that a query depends on an update committed within the TTL interval tau. The bound follows from a refresh-phase argument and is stated for the periodic-refresh and dependency model analyzed in this paper.\n                  <\/jats:p>\n                  <jats:p>We introduce EviDex, a provenance-weighted evidence-path index that avoids periodic answer refresh by continuously compacting a log-structured commit stream into intent-partitioned evidence-path buckets. Queries retrieve ranked multi-hop evidence paths with provenance, yielding low-latency lookup with streaming consistency. We prove admissible pruning preserves exact top-B ranking (Lemma 1); in our study it reduces candidate paths by 67.3%.<\/jats:p>\n                  <jats:p>We conduct a large-scale measurement study on two workloads chosen to span a high-stakes bursty stream and a broad public revision stream. The clinical workload has 170K documents, and the Wikipedia workload contains 2.84M revision events. We compare against 12 baselines spanning streaming-aware caching, system-level incremental indexing, and production near-real-time search (OpenSearch). At T = 15 minutes, EviDex achieves 1.3% evidence-set violation on clinical and 1.1% on Wikipedia, compared to 2.4% and 2.1% for the strongest streaming-aware baseline (adaptive TTL). EviDex costs 0.68 per 1k queries on clinical, 42% cheaper than adaptive TTL at better freshness. At scale, on 16 nodes with 10M documents, the evidence-path lookup service (lookup-only; excluding LLM generation) reaches 1,856 q\/s with p99 = 2.14s. We report this lookup-service scaling separately from the end-to-end clinical QA results.<\/jats:p>\n                  <jats:p>Finally, we validate end-to-end impact in a safety-critical clinical QA stress test with 800 questions rated by 5 physicians (ICC = 0.862). EviDex achieves 0.884 clinical correctness [0.860-0.908], with macro-SCER of 0.84%.<\/jats:p>","DOI":"10.1145\/3805636","type":"journal-article","created":{"date-parts":[[2026,5,29]],"date-time":"2026-05-29T20:34:18Z","timestamp":1780086858000},"page":"1-23","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["EviDex: Provenance-Weighted Evidence-Path Indexing for Fresh and Auditable Retrieval under Continuous Updates"],"prefix":"10.1145","volume":"10","author":[{"ORCID":"https:\/\/orcid.org\/0009-0007-6857-2127","authenticated-orcid":false,"given":"Rui","family":"Li","sequence":"first","affiliation":[{"name":"Hill Research, Princeton, NJ, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0000-5254-0883","authenticated-orcid":false,"given":"Shuang","family":"Cao","sequence":"additional","affiliation":[{"name":"Hill Research, Princeton, NJ, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0004-0848-3315","authenticated-orcid":false,"given":"Ruihua","family":"Liu","sequence":"additional","affiliation":[{"name":"Hill Research, Princeton, NJ, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8310-8508","authenticated-orcid":false,"given":"Alexandre","family":"Duprey","sequence":"additional","affiliation":[{"name":"Hill Research, Princeton, NJ, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2026,5,29]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/3292500.3330701"},{"key":"e_1_2_1_2_1","volume-title":"Self-RAG: Learning to Retrieve, Generate, and Critique through Self-Reflection. arXiv preprint arXiv:2310.11511","author":"Asai Akari","year":"2023","unstructured":"Akari Asai, Zeqiu Wu, Yizhong Wang, Avirup Sil, and Hannaneh Hajishirzi. 2023. Self-RAG: Learning to Retrieve, Generate, and Critique through Self-Reflection. arXiv preprint arXiv:2310.11511 (2023). https:\/\/arxiv.org\/abs\/2310.11511"},{"key":"e_1_2_1_3_1","volume-title":"International Conference on Machine Learning. https:\/\/arxiv.org\/abs\/2112","author":"Borgeaud Sebastian","unstructured":"Sebastian Borgeaud, Arthur Mensch, Jordan Hoffmann, Trevor Cai, Eliza Rutherford, Katie Millican, George van den Driessche, Jean-Baptiste Lespiau, Bogdan Damoc, Aidan Clark, Diego de Las Casas, Aurelia Guy, et al. 2021. Improving language models by retrieving from trillions of tokens. In International Conference on Machine Learning. https:\/\/arxiv.org\/abs\/2112.04426"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/3--540--44503-X_20"},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of the Ninth Conference on Machine Learning and Systems (MLSys).","author":"Cao Shuang","year":"2026","unstructured":"Shuang Cao and Rui Li. 2026. Ontology-Guided Long-Term Memory for Conversational RAG. In Proceedings of the Ninth Conference on Machine Learning and Systems (MLSys)."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.21203\/rs.3.rs-8466783\/v1"},{"key":"e_1_2_1_7_1","doi-asserted-by":"crossref","unstructured":"Shuang Cao Rui Li R. Wu R. Liu A. Duprey and J. Zhao. 2026. Real-time clinical analytics at scale: a platform built on large language models-powered knowledge graphs. JAMIA Open 9 1 (2026) ooaf167. https:\/\/academic.oup.com\/jamiaopen\/article\/9\/1\/ooaf167\/8415655","DOI":"10.1093\/jamiaopen\/ooaf167"},{"key":"e_1_2_1_8_1","volume-title":"Multi-Functionality, Multi-Granularity Text Embeddings Through Self-Knowledge Distillation. arXiv preprint arXiv:2402.03216","author":"Chen Jianlv","year":"2024","unstructured":"Jianlv Chen, Shitao Xiao, Peitian Zhang, Kun Luo, Defu Lian, and Zheng Liu. 2024. M3-Embedding: Multi-Linguality, Multi-Functionality, Multi-Granularity Text Embeddings Through Self-Knowledge Distillation. arXiv preprint arXiv:2402.03216 (2024). https:\/\/arxiv.org\/abs\/2402.03216"},{"key":"e_1_2_1_9_1","volume-title":"Domain-Specific Language Model Pretraining for Biomedical Natural Language Processing. arXiv preprint arXiv:2007.15779","author":"Gu Yu","year":"2020","unstructured":"Yu Gu, Robert Tinn, Hao Cheng, Michael Lucas, Naoto Usuyama, Xiaodong Liu, Tristan Naumann, Jianfeng Gao, and Hoifung Poon. 2020. Domain-Specific Language Model Pretraining for Biomedical Natural Language Processing. arXiv preprint arXiv:2007.15779 (2020). https:\/\/arxiv.org\/abs\/2007.15779"},{"key":"e_1_2_1_10_1","first-page":"3","article-title":"Maintenance of Materialized Views: Problems, Techniques, and Applications","volume":"18","author":"Gupta Ashish","year":"1995","unstructured":"Ashish Gupta and Inderpal Singh Mumick. 1995. Maintenance of Materialized Views: Problems, Techniques, and Applications. IEEE Data Engineering Bulletin 18, 2 (1995), 3--18. http:\/\/sites.computer.org\/debull\/95JUN-CD.pdf","journal-title":"IEEE Data Engineering Bulletin"},{"key":"e_1_2_1_11_1","volume-title":"GRAG: Graph Retrieval-Augmented Generation. arXiv preprint arXiv:2405.16506","author":"Hu Yuntong","year":"2024","unstructured":"Yuntong Hu, Zhihan Lei, Zheng Zhang, Bo Pan, Chen Ling, and Liang Zhao. 2024. GRAG: Graph Retrieval-Augmented Generation. arXiv preprint arXiv:2405.16506 (2024). https:\/\/arxiv.org\/abs\/2405.16506"},{"key":"e_1_2_1_12_1","volume-title":"Few-shot Learning with Retrieval Augmented Language Models. Journal of Machine Learning Research","author":"Izacard Gautier","year":"2022","unstructured":"Gautier Izacard, Patrick Lewis, Michael Lomeli, Lucas Hosseini, Fabio Petroni, Timo Schick, Jane A Yu, Armand Joulin, Sebastian Riedel, and Edouard Grave. 2022. Few-shot Learning with Retrieval Augmented Language Models. Journal of Machine Learning Research (2022). https:\/\/arxiv.org\/abs\/2208.03299"},{"key":"e_1_2_1_13_1","volume-title":"Active Retrieval Augmented Generation. arXiv preprint arXiv:2305.06983","author":"Jiang Zhengbao","year":"2023","unstructured":"Zhengbao Jiang, Frank F Xu, Luyu Gao, Zhiqing Sun, Qian Liu, Jane Dwivedi-Yu, Yiming Yang, Jamie Callan, and Graham Neubig. 2023. Active Retrieval Augmented Generation. arXiv preprint arXiv:2305.06983 (2023). https: \/\/arxiv.org\/abs\/2305.06983"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1038\/s41597-022-01899-x"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/TBDATA.2019.2921572"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.18653\/v1\/2020.emnlp-main.550"},{"key":"e_1_2_1_17_1","volume-title":"Baleen: Robust Multi-Hop Reasoning at Scale via Condensed Retrieval. In NeurIPS. https:\/\/arxiv.org\/abs\/2101.00436","author":"Khattab Omar","year":"2021","unstructured":"Omar Khattab, Christopher Potts, and Matei Zaharia. 2021. Baleen: Robust Multi-Hop Reasoning at Scale via Condensed Retrieval. In NeurIPS. https:\/\/arxiv.org\/abs\/2101.00436"},{"key":"e_1_2_1_18_1","first-page":"9459","article-title":"Retrieval-Augmented Generation for Knowledge-Intensive NLP Tasks","volume":"33","author":"Lewis Patrick","year":"2020","unstructured":"Patrick Lewis, Ethan Perez, Aleksandara Piktus, Fabio Petroni, Vladimir Karpukhin, Naman Goyal, Heinrich K\u00fcttler, Mike Lewis, Wen-tau Yih, Tim Rockt\u00e4schel, et al. 2020. Retrieval-Augmented Generation for Knowledge-Intensive NLP Tasks. In Advances in Neural Information Processing Systems, Vol. 33. 9459--9474. https:\/\/arxiv.org\/abs\/2005.11401","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.21203\/rs.3.rs-8769058\/v1"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.21203\/rs.3.rs-8769125\/v1"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.21203\/rs.3.rs-8912526\/v1"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.21203\/rs.3.rs-8912660\/v1"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.21203\/rs.3.rs-8912156\/v1"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.21203\/rs.3.rs-8912469\/v1"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.21203\/rs.3.rs-8912612\/v1"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357223.3362720"},{"key":"e_1_2_1_27_1","unstructured":"National Comprehensive Cancer Network. 2024. NCCN Clinical Practice Guidelines in Oncology. https:\/\/www.nccn.org\/guidelines\/."},{"key":"e_1_2_1_28_1","unstructured":"National Library of Medicine. 2024. PubMed Central Open Access Subset. https:\/\/www.ncbi.nlm.nih.gov\/pmc\/tools\/openftlist\/."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/s002360050048"},{"key":"e_1_2_1_30_1","volume-title":"Faster, Cheaper and Lighter. arXiv preprint arXiv:1910.01108","author":"Sanh Victor","year":"2019","unstructured":"Victor Sanh, Lysandre Debut, Julien Chaumond, and Thomas Wolf. 2019. DistilBERT, a Distilled Version of BERT: Smaller, Faster, Cheaper and Lighter. arXiv preprint arXiv:1910.01108 (2019). https:\/\/arxiv.org\/abs\/1910.01108"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.18653\/v1\/2024.naacl-long.463"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1038\/s41586-023-06291--2"},{"key":"e_1_2_1_33_1","volume-title":"BEIR: A Heterogenous Benchmark for Zero-shot Evaluation of Information Retrieval Models. In NeurIPS Datasets and Benchmarks Track. https:\/\/arxiv.org\/abs\/2104.08663","author":"Thakur Nandan","year":"2021","unstructured":"Nandan Thakur, Nils Reimers, Andreas R\u00fcckl\u00e9, Abhishek Srivastava, and Iryna Gurevych. 2021. BEIR: A Heterogenous Benchmark for Zero-shot Evaluation of Information Retrieval Models. In NeurIPS Datasets and Benchmarks Track. https:\/\/arxiv.org\/abs\/2104.08663"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1101\/2025.06.09.655966"},{"key":"e_1_2_1_35_1","volume-title":"Srini Iyer, Jingfei Du, Patrick Lewis, William Yang Wang, Yashar Mehdad, Wen-tau Yih, Sebastian Riedel, Douwe Kiela, and Barlas Oguz.","author":"Xiong Wenhan","year":"2021","unstructured":"Wenhan Xiong, Xiang Lorraine Li, Srini Iyer, Jingfei Du, Patrick Lewis, William Yang Wang, Yashar Mehdad, Wen-tau Yih, Sebastian Riedel, Douwe Kiela, and Barlas Oguz. 2021. Answering Complex Open-Domain Questions with Multi-Hop Dense Retrieval. In ICLR. https:\/\/openreview.net\/forum?id=EMHoBG0avc1 arXiv:2009.12756."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","unstructured":"Donghan Yu Chenguang Zhu Yiming Yang and Michael Zeng. 2022. KG-FiD: Infusing Knowledge Graph in Fusion-in-Decoder for Open-Domain Question Answering. In ACL. 4961--4974. doi:10.18653\/v1\/2022.acl-long.340","DOI":"10.18653\/v1\/2022.acl-long.340"}],"container-title":["Proceedings of the ACM on Measurement and Analysis of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3805636","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,5,29]],"date-time":"2026-05-29T20:34:49Z","timestamp":1780086889000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3805636"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,5,29]]},"references-count":36,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2026,5,29]]}},"alternative-id":["10.1145\/3805636"],"URL":"https:\/\/doi.org\/10.1145\/3805636","relation":{},"ISSN":["2476-1249"],"issn-type":[{"value":"2476-1249","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,5,29]]},"assertion":[{"value":"2026-05-29","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}