Usar consultas pre-compiladas.

La creación de consultas consume sobre un 10% de la ejecución de ésta. Algunas partes se cachean y las siguientes son más rápidas, pero otras partes no, así que se reconstruye cada vez que la consulta se ejecuta (a no ser que se use EntitySql).

Por eso cuando una aplicación ejecuta muchas veces consultas que tienen una estructura similar en EF se mejora el  rendimiento si se compila la consulta una vez y se ejecuta varias veces con parámetros diferentes que son especificados en tiempo de ejecución. 
Para ello se usa el método CompiledQuery.Compile, el cual usa un delegado Func genérico. Almacenando y usando de este modo también se reduce el coste de hacer una llamada virtual, cada vez que accedes a la colección, que de hecho se reduce a una llamada. Además, ésta será compilada sólo la primera vez que la consulta se ejecute. Pero, si usas CompiledQuery , asegúrate de que se llama a la consulta más de una vez, ya que  la primera vez que se lanza, tarda el doble de tiempo que una consulta simple sin cachear.

Éste es el ejemplo  de Microsoft  para la creación de una consulta compilada:

static readonly Func> s_compiledQuery2 = 
    CompiledQuery.Compile>(
            (ctx, total) => from order in ctx.SalesOrderHeader
                            where order.TotalDue >= total
                            select order);

Para más información, o ver el código completo se puede consultar el artículo completo de Microsoft.

Via: http://msdn.microsoft.com/en-us/library/bb399335.aspx