A placeholder for recording papers I read during winter break and my process of getting started with mlsys.

About OS

Learned rCore.

LLM Learning

RAG

Theoretical Origin

Before 2020, academia had already made scattered attempts to combine retrieval and generation, but no systematic methodology had yet formed. In 2020, the field saw two milestone works: Facebook formally introduced the concept of “RAG” in the paper Retrieval-Augmented Generation for Knowledge-Intensive NLP Tasks and applied it to knowledge-intensive tasks, while Google’s REALM significantly improved open-domain question answering by incorporating a latent knowledge retriever during pretraining.

After ChatGPT was released, RAG research entered an accelerated golden period. During this process, RAG gradually evolved from a single retrieve-generate framework into a comprehensive system involving multi-hop reasoning, memory enhancement, multimodality, and other complex capabilities.

Naive RAG

In October 2020, the Meta team first defined the Naive RAG architecture in Retrieval-Augmented Generation for Knowledge-Intensive NLP Tasks, establishing a three-stage “indexing-retrieval-generation” workflow:

  • Indexing: The indexing stage first cleans and extracts raw data from formats such as PDF, HTML, Word, and Markdown, then converts them into a unified plain-text format. To fit the context limits of language models, the text is split into smaller, more digestible chunks. An embedding model then encodes the chunks into vector representations and stores them in a vector database. This step is crucial for efficient similarity search in the later retrieval stage.
  • Retrieval: After receiving a user query, the RAG system uses the same encoding model as in indexing to convert the query into a vector representation, then computes similarity scores between the query vector and chunk vectors in the indexed corpus. The system retrieves the top-k most similar chunks. These chunks are then used as extended context in the prompt.
  • Generation: The query and selected document chunks are synthesized into a coherent prompt, and the large language model generates the response.

Advanced RAG

Advanced RAG emerged from attempts to break through the limitations of Naive RAG, namely indexing, retrieval, and generation. Early researchers found that relying only on vector retrieval led to problems such as a semantic gap, where ambiguous questions or multi-hop reasoning caused retrieval failure, and information redundancy, where retrieved results were repetitive or irrelevant. To address these issues, teams such as Meta and Microsoft began exploring end-to-end optimization frameworks, proposing directions such as pre-retrieval preprocessing, post-retrieval refinement, and embedding-model optimization:

  • Pre-index optimization:
    • Multi-granularity chunking: introduce sliding-window segmentation, semantic chunking, and similar strategies to solve semantic breakage caused by splitting long texts, such as dynamically splitting documents by paragraphs or sections.
    • Metadata injection: embed metadata into chunks to improve retrieval efficiency, including title, abstract, author, time, and entity information.
    • Hybrid indexing: combine BM25 keyword matching with vector semantic retrieval to balance exact recall and semantic understanding.
    • Hypothetical questions: let the LLM generate a question for each chunk, save the mapping between questions and text chunks, and store these questions in the vector database. During retrieval, the system first searches the vector question database, finds similar questions, then routes back to the original text chunks and sends them as context to the LLM. This improves search quality through higher semantic similarity between the query and hypothetical questions.
    • HyDE (Hypothetical Document Embeddings): use an inverse-logic method where the LLM generates a hypothetical response for a given query, then uses its vector together with the query vector to improve search quality.
  • Post-index optimization:
    • ReRank: reordering the most relevant information toward the prompt boundaries is a simple idea.
    • Prompt Compression: focus on compressing irrelevant context, highlighting key paragraphs, and reducing total context length.
  • Embedding optimization:
    • Fine-tuning Embedding: the goal of fine-tuning is to improve relevance between retrieved content and queries. Fine-tuning embedding methods are usually divided into adapting embeddings in a domain-specific context and optimizing the retrieval step. Especially in professional domains with evolving or rare terminology, customized embeddings can improve retrieval relevance.
    • Dynamic Embedding: dynamic embeddings adapt according to the context in which a word appears. Unlike static embeddings that use one vector per word, ideal embeddings should include as much context as possible to ensure “healthy” results.
  • Query transformation:
    • Query transformation uses the LLM as a reasoning engine to modify user input and improve retrieval quality. For more complex user queries, the LLM can decompose them into subqueries, retrieve relevant context for each subquery, then combine the contexts to answer the original complex question. In multi-turn conversations, using conversation history to complete the current query for more accurate retrieval is also a form of query transformation.

Modular RAG

Modular RAG splits the linear workflow of traditional RAG systems into independent pluggable modules, such as retriever, preprocessor, and generator. Each module focuses on a specific function, such as query optimization, hybrid retrieval, or generation control, and can be freely combined like building blocks.

LLM Serving

CPU Scheduling Algorithms, Migration to GPU Scheduling, and Concurrent LLM Serving

Today I sat in on an OS class from the neighboring John class and listened to a lecture on CPU scheduling algorithms. It was quite inspiring.

Basic Concepts

CPU-I/O Burst Cycle: process execution consists of alternating CPU execution, or CPU burst, and I/O waiting, or I/O burst.

CPU Scheduler: selects one process from those ready to run in memory and allocates the CPU to it.

Preemptive and Non-preemptive Scheduling

Non-preemptive: a process keeps the CPU until it terminates or switches to the waiting state.

Preemptive: the system can forcibly take the CPU away from the current process. This may cause race conditions and requires synchronization mechanisms.

Dispatcher: transfers CPU control to the selected process, including context switching and jumping to the appropriate position in the user program. Dispatch latency is the time it takes for the dispatcher to stop one process and start another.

Scheduling Criteria

To evaluate scheduling algorithms, the following metrics are commonly used:

  • CPU utilization: keep the CPU as busy as possible.

  • Throughput: the number of completed processes per unit time.

  • Turnaround time: the time required to execute a specific process, from submission to completion.

  • Waiting time: the total time a process spends waiting in the ready queue.

  • Response time: the time from request submission to the first response, not the final output.

Scheduling Algorithms

First-Come, First-Served (FCFS)

Principle: schedule processes in arrival order.

Drawback: average waiting time is usually long. It suffers from the convoy effect, where short processes wait behind long ones.

Shortest Job First (SJF)

Principle: assign the CPU to the process with the shortest next CPU burst.

Property: for a given set of processes, it minimizes average waiting time.

Challenge: it is hard to know the exact length of the next CPU burst, so exponential averaging is usually used for prediction.

Round Robin (RR)

Principle: designed for time-sharing systems. Each process is assigned a small unit of time called the time quantum.

Rule: after the time quantum expires, the process is preempted and placed at the end of the ready queue.

Performance: depends on the quantum size. If the quantum is too large, it degenerates to FCFS. If it is too small, context-switch overhead becomes significant.

Priority Scheduling

Principle: each process has an associated priority, usually an integer, and the CPU is allocated to the highest-priority process.

Problem: starvation. Low-priority processes may never run.

Solution: aging. Increase the priority of waiting processes over time.

Multilevel Feedback Queue

Principle: split the ready queue into multiple independent queues, each with its own scheduling algorithm.

Property: processes can move between queues. Processes that occupy the CPU too long are moved to lower-priority queues as a penalty, while processes that wait too long are moved to higher-priority queues as a reward or aging mechanism.

Some Ideas

I read a paper, 2026_arxiv_justitia.pdf. Reading one paper to understand the background feels the most beginner-friendly. The background is the rise of task-parallel LLM agents: when solving multi-step logic tasks such as long-text summarization merging or complex math problems, systems often execute multiple LLM inference tasks concurrently. Such workloads are called “task-parallel LLM agents.” Justitia does not make all concurrent agents evenly split resources. Instead, it computes their expected “completion order” under perfectly fair allocation, then follows that order and lets higher-priority agents use resources exclusively or saturate them. This greatly reduces the system’s average completion time while ensuring that no agent finishes later than it would under equal resource sharing. Justitia’s core is a scheduling algorithm that dynamically adjusts resource allocation based on agents’ expected completion times. In this way, Justitia significantly improves the performance of task-parallel LLM agents while keeping the system efficient.

Computing completion order: to efficiently determine the “expected completion order” above, Justitia borrows the virtual time ($V(t)$) algorithm from traditional network-packet scheduling. This algorithm allows the system to compute an agent’s virtual completion time once when the agent arrives and use it as scheduling priority. Later it does not need to refresh state repeatedly, greatly reducing scheduling overhead.

A related thought: it is a kind of SJF, but not exactly, because it guarantees that the process currently running on the GPU uses all resources until it finishes, with no mid-task preemption.